Hamilton cycles in pseudorandom graphs
EUROCOMB’23
491–496
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.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Stefan Glock, David Munha Correia, Benny Sudakov