Random graph's Hamiltonicity is strongly tied to its minimum degree

DOI10.37236/8339zbMATH Open1431.05136arXiv1810.04987OpenAlexW3002473473MaRDI QIDQ2290359FDOQ2290359

Authors: Yahav Alon, Michael Krivelevich 

Publication date: 27 January 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We show that the probability that a random graph $GsimG(n,p)$ contains no Hamilton cycle is $(1+o(1))Pr(delta(G)<2)$ for all values of $p=p(n)$. We also prove an analogous result for perfect matchings.

Full work available at URL: https://arxiv.org/abs/1810.04987

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 3922707
• scientific article; zbMATH DE number 3950585
• scientific article; zbMATH DE number 4193709
• Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
• Dirac's theorem for random graphs

zbMATH Keywords

Hamilton cycleperfect matching

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• A note on Hamiltonian circuits
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the existence of a factor of degree one of a connected random graph
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Hamilton cycles in highly connected and expanding graphs
• Hamilton cycles, minimum degree, and bipartite holes
• Long paths and Hamiltonicity in random graphs

Cited In (16)

• Entropy bounds for perfect matchings and Hamiltonian cycles
• Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
• Title not available (Why is that?)
• Hamiltonicity of random graphs in the stochastic block model
• Random induced graphs
• Hamilton cycles in random graphs with a fixed degree sequence
• Hamiltonian Berge cycles in random hypergraphs
• On Hamilton cycles in Erdős-Rényi subgraphs of large graphs
• Dirac-type theorems for inhomogenous random graphs
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• Title not available (Why is that?)
• The global resilience of Hamiltonicity in \(G(n, p)\)
• Title not available (Why is that?)
• Compatible Hamilton cycles in random graphs
• Color‐biased Hamilton cycles in random graphs
• Dirac's theorem for random graphs

This page was built for publication: Random graph's Hamiltonicity is strongly tied to its minimum degree

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