Hamilton cycles in pseudorandom graphs

DOI10.1016/J.AIM.2024.109984MaRDI QIDQ6639724zbMATH OpenFDO

Authors Stefan Glock, David Munhá Correia, Benny Sudakov

Publication date 18 November 2024

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.AIM.2024.109984

zbMATH Keywords

expander graphHamilton cycleHamiltonicitypseudorandom graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Expander graphs (05C48) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Recommendations

• On the number of Hamilton cycles in pseudo-random graphs
• Sparse pseudo‐random graphs are Hamiltonian
• Powers of Hamilton cycles in pseudorandom graphs
• Hamilton cycles in random subgraphs of pseudo-random graphs

Cites work

• A note on Hamiltonian circuits
• A remark on Hamilton cycles with few colors
• Additive patterns in multiplicative subgroups
• Almost all Cayley graphs are hamiltonian
• Almost all regular graphs are hamiltonian
• An algorithm for finding Hamilton paths and cycles in random graphs
• Approximate Hamilton decompositions of random graphs
• Counting Hamilton decompositions of oriented graphs
• Expanding graphs contain all small trees
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• Explicit construction of linear sized tolerant networks
• Hamilton cycles in dense vertex-transitive graphs
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Hamilton cycles in highly connected and expanding graphs
• Hamilton cycles in random subgraphs of pseudo-random graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamiltonian circuits in random graphs
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Hamiltonian cycles in Dirac graphs
• Hamiltonian paths in Cayley graphs
• scientific article; zbMATH DE number 3138254 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• scientific article; zbMATH DE number 3405992 (Why is no real title available?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Long cycles in vertex-transitive graphs
• On rainbow cycles in edge colored complete graphs
• On representatives of subsets.
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Pseudo-random graphs
• Random Cayley graphs and expanders
• Random Latin square graphs
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Random regular graphs of high degree
• Recent advances on the Hamiltonian problem: survey III
• Robust Hamiltonicity of Dirac graphs
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Some Theorems on Abstract Graphs
• Sparse pseudo‐random graphs are Hamiltonian
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• The linear arboricity of graphs
• The probabilistic method
• The size Ramsey number of a directed path

Cited in

(4)

• Nearly Hamilton cycles in sublinear expanders and applications
• Hamiltonicity of sparse pseudorandom graphs
• Spanning trees in pseudorandom graphs via sorting networks
• Title not available (Why is no real title available?)

This page was built for publication: Hamilton cycles in pseudorandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6639724)