Graph isomorphism and quantisation of longest cycles by means of determinants and spectra
(V Ejov with N Litvak, S Friedland and P Zograf)
We analyse a novel phenomenon of a fractal-based partition of regular graphs in mean-variance coordinates of a certain class of functionals on the graph’s spectrum. We characterise the classical NP-complete Hamiltonian cycle problem by means of maximising determinant and trace of matrices arising from the fundamental matrix of corresponding Markov chains. We aim to prove the existence and uniqueness of an interior critical point of the determinant function over the set of all stochastic matrices, which could play an important role in the graph isomorphism problem. We also approach the graph isomorphism problem using tensor networks techniques and the relaxation method for bilinear functionals on doubly stochastic matrices.
Funding
ARC Discovery (2009 – 2011), “Graph isomorphism and quantisation of
longest cycles by means of determinants and spectra”.
Leading CI: Ass Prof V Ejov
Collaborators: Overseas Investigators: Prof S Friedland (University of
Illinois at Chicago, USA), Asst Prof N Litvak (University of Twente,
Holland), Mr P Zograf (Steklov Mathematical Institute, St. Petersburg,
Russia)
Publications
V. Ejov and G. T. Nguyen, Asymptotic behaviour of certain perturbed
determinants induced by graphs, to appear in Linear Algebra Appl.
(2009).
V. Ejov, Jerzy A. Filar, M. Haythorpe and G. T. Nguyen, Refined MDP-based
branch-and-fixed algorithm for the Hamiltonian cycle problem", to appear
in Math. Oper. Res. (2009).
G. T. Nguyen, Hamiltonian cycle problem, Markov decision processes and
graph spectra, PhD. Thesis, University of South Australia, (2009).