Hamilton cycles in pseudorandom graphs

EUROCOMB’23

Abstract
Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well known conjecture in the area states that any $d$-regular $n$-vertex graph $G$ whose second largest eigenvalue in absolute value $\lambda(G)$ is at most $d/C$, for some universal constant $C>0$, has a Hamilton cycle. We obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree $d$ is at least a small power of $n$. Secondly, in the general case we show that $\lambda(G) \leq d/ C(\log n)^{1/3}$ implies the existence of a Hamilton cycle, improving the 20-year old bound of $d/ \log^{1-o(1)} n$ of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust Pósa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications, giving best bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lovász. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups.

Pages:
491–496
References

M. Ajtai, J. Komlós, and E. Szemerédi. First occurrence of Hamilton cycles in random graphs. North-Holland Math. Stud., 115(C):173-178, 1985.
https://doi.org/10.1016/S0304-0208(08)73007-X

S. Akbari, O. Etesami, H. Mahini, and M. Mahmoody. On rainbow cycles in edge colored complete graphs. Australas. J. Combin., 37:33, 2007.

N. Alon and J. Bourgain. Additive patterns in multiplicative subgroups. Geom. Funct. Anal., 24:721-739, 2014.
https://doi.org/10.1007/s00039-014-0270-y

N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271-284, 1994.
https://doi.org/10.1002/rsa.3240050203

L. Babai. Long cycles in vertex-transitive graphs. J. Graph Theory, 3(3):301-304, 1979
https://doi.org/10.1002/jgt.3190030314

I. Balla, A. Pokrovskiy, and B. Sudakov. A remark on Hamilton cycles with few colors. Moscow Journal of Combinatorics and Number Theory, 7(3):73-77, 2017.

B. Bollobás. Modern graph theory. Springer Science & Business Media, 184, 1998.
https://doi.org/10.1007/978-1-4612-0619-4

B. Bollobás. The evolution of sparse graphs. Graph theory and combinatorics (Cambridge, 1983), 35-57, 1984.

B. Bollobás, T. I. Fenner, and A. M. Frieze. An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica, 7:327-341, 1987.
https://doi.org/10.1007/BF02579321

D. Christofides and K. Markström. Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales. Random Structures Algorithms, 32(1):88-100, 2008.
https://doi.org/10.1002/rsa.20177

D. Christofides and K. Markstrom. Random Latin square graphs. Random Structures Algorithms, 41(1):47-65, 2012.
https://doi.org/10.1002/rsa.20390

D. Christofides, J. Hladký, and A. Máthé. Hamilton cycles in dense vertex-transitive graphs. J. Combin. Theory Ser. B, 109:34-72, 2014.
https://doi.org/10.1016/j.jctb.2014.05.001

V. Chvátal and P. Erdős. A note on Hamiltonian circuits. Discrete Math., 2(2):111-113, 1972.
https://doi.org/10.1016/0012-365X(72)90079-9

C. Cooper, A. Frieze, and B. Reed. Random regular graphs of non-constant degree: connectivity and Hamiltonicity. Combin. Probab. Comput., 11(3):249-261, 2002.
https://doi.org/10.1017/S0963548301005090

B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures. Mem. Amer. Math. Soc., 244, monograph 1154, 164 pages, 2016.
https://doi.org/10.1090/memo/1154

B. Cuckler and J. Kahn. Hamiltonian cycles in Dirac graphs. Combinatorica, 29:299-326, 2009.
https://doi.org/10.1007/s00493-009-2360-2

S. J. Curran and J. A. Gallian. Hamiltonian cycles and paths in Cayley graphs and digraphs-a survey. Discrete Math., 156(1-3):1-18, 1996.
https://doi.org/10.1016/0012-365X(95)00072-5

M. DeVos. Longer cycles in vertex transitive graphs. arXiv:2302.04255, 2023.

G. A. Dirac. Some theorems on abstract graphs. Proc. Lond. Math. Soc., 3(1):69-81, 1952.
https://doi.org/10.1112/plms/s3-2.1.69

A. Ferber, E. Long, and B. Sudakov. Counting Hamilton decompositions of oriented graphs. Int. Math. Res. Not. IMRN, (22):6908-6933, 2018.
https://doi.org/10.1093/imrn/rnx085

A. Frieze and M. Krivelevich. Hamilton cycles in random subgraphs of pseudo-random graphs. Discrete Math., 256(1-2):137-150, 2002.
https://doi.org/10.1016/S0012-365X(01)00464-2

R. J. Gould. Recent advances on the Hamiltonian problem: Survey III. Graphs Combin., 30:1-46, 2014.
https://doi.org/10.1007/s00373-013-1377-x

D. Hefetz, M. Krivelevich and T. Szabó. Hamilton cycles in highly connected and expanding graphs. Combinatorica, 29(5):547-568, 2009.
https://doi.org/10.1007/s00493-009-2362-0

F. Knox, D. Kühn, and D. Osthus. Approximate Hamilton decompositions of random graphs. Random Structures Algorithms, 40(2):133-149, 2012.
https://doi.org/10.1002/rsa.20365

J. Komlós and E. Szemerédi. Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math., 43(1):55-63, 1983.
https://doi.org/10.1016/0012-365X(83)90021-3

A. Korshunov. Solution of a problem of Erdős and Rényi on Hamilton cycles in non-oriented graphs. Soviet Math Dokl, 17:760-764, 1976.

M. Krivelevich and B. Sudakov. Sparse pseudo-random graphs are Hamiltonian. J. Graph Theory, 42(1):17-33, 2003.
https://doi.org/10.1002/jgt.10065

M. Krivelevich. The critical bias for the Hamiltonicity game is (1 + o(1)). J. Amer. Math. Soc., 24(1):125-131, 2011.
https://doi.org/10.1090/S0894-0347-2010-00678-9

M. Krivelevich and B. Sudakov. Pseudo-random graphs. In More sets, graphs and numbers, pages 199-262. Springer, 2006.
https://doi.org/10.1007/978-3-540-32439-3_10

M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald. Random regular graphs of high degree. Random Structures Algorithms, 18(4):346-363, 2001.
https://doi.org/10.1002/rsa.1013

M. Krivelevich, C. Lee, and B. Sudakov. Robust Hamiltonicity of Dirac graphs. Trans. Amer. Math. Soc., 366(6):3095-3130, 2014.
https://doi.org/10.1090/S0002-9947-2014-05963-1

D. Kühn and D. Osthus. Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments. Adv. Math., 237:62-146, 2013.
https://doi.org/10.1016/j.aim.2013.01.005

D. Kühn and D. Osthus. Hamilton cycles in graphs and hypergraphs: an extremal perspective. In Proceedings of the International Congress of Mathematicians2014, Seoul, Korea., 4:381-406, 2014.

D. Kühn, J. Lapinskas, D. Osthus, and V. Patel. Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. Proc. Lond. Math. Soc., 109(3):733-762, 2014.
https://doi.org/10.1112/plms/pdu019

L. Lovász. Combinatorial structures and their applications. In Proc. Calgary Internat. Conf., Calgary, Alberta, 243-246, 1970.

J. Meng and Q. Huang. Almost all Cayley graphs are Hamiltonian. Acta Math. Sinica, 12(2):151-155, 1996.
https://doi.org/10.1007/BF02108156

I. Pak and R. Radoičić. Hamiltonian paths in Cayley graphs. Discrete Math., 309(17):5501-5508, 2009.
https://doi.org/10.1016/j.disc.2009.02.018

L. Pósa. Hamiltonian circuits in random graphs. Discrete Math., 14(4):359-364, 1976.
https://doi.org/10.1016/0012-365X(76)90068-6

E. Rapaport Strasser. Cayley color groups and Hamilton lines. Scripta Math., 24:51-58,1959.

Metrics

0

Views

0

PDF views