Hamiltonicity in random graphs is born resilient

DOI10.1016/J.JCTB.2019.04.002zbMATH Open1428.05178arXiv1710.00505OpenAlexW2963878442WikidataQ128019940 ScholiaQ128019940MaRDI QIDQ2338643FDOQ2338643

Authors: Richard Montgomery 

Publication date: 21 November 2019

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Let ${G_M}_{Mgeq0}$ be the random graph process, where $G_0$ is the empty graph on $n$ vertices and subsequent graphs in the sequence are obtained by adding a new edge uniformly at random. For each $varepsilon>0$, we show that, almost surely, any graph $G_M$ with minimum degree at least 2 is not only Hamiltonian (as shown by Bollob'as), but remains Hamiltonian despite the removal of any set of edges, as long as at most $(1/2-varepsilon)$ of the edges incident to each vertex are removed. We say that such a graph is $(1/2-varepsilon)$-resiliently Hamiltonian. Furthermore, for each $epsilon>0$, we show that, almost surely, each graph $G_M$ is not $(1/2+varepsilon)$-resiliently Hamiltonian. These results strengthen those by Lee and Sudakov on the likely resilience of Hamiltonicity in the binomial random graph. For each $k$, we denote by $G^{(k)}$ the (possibly empty) maximal subgraph with minimum degree at least $k$ of a graph $G$. That is, the $k$-core of $G$. Krivelevich, Lubetzky and Sudakov have shown that, for each $kgeq15$, in almost every random graph process ${G_M}_{Mgeq0}$, every non-empty $k$-core is Hamiltonian. We show that, for each $varepsilon>0$ and $kgeq{k}_0(varepsilon)$, in almost every random graph process ${G_M}_{Mgeq0}$, every non-empty $k$-core is $(1/2-varepsilon)$-resiliently Hamiltonian, but not $(1/2+varepsilon)$-resiliently Hamiltonian.

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

Recommendations

• Hamiltonicity in random directed graphs is born resilient
• Robust Hamiltonicity of random directed graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• Robust Hamiltonicity of random directed graphs: extended abstract
• Random directed graphs are robustly Hamiltonian
• Cores of random graphs are born Hamiltonian
• Hamiltonicity of random graphs in the stochastic block model
• Hamiltonicity in randomly perturbed hypergraphs
• scientific article; zbMATH DE number 4110727

zbMATH Keywords

thresholdsrandom graphsHamiltonicityresilience

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Sudden emergence of a giant \(k\)-core in a random graph
• Paths in graphs
• Dirac's theorem for random graphs
• Hamiltonian circuits in random graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the resilience of long cycles in random graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Local resilience of graphs
• On two Hamilton cycle problems in random graphs
• Size and connectivity of the \(k\)-core of a random graph
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs
• Cores of random graphs are born Hamiltonian
• Almost all regular graphs are Hamiltonian
• Title not available (Why is that?)
• Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk
• On the threshold for \(k\)-regular subgraphs of random graphs
• Resilience of perfect matchings and Hamiltonicity in random graph processes

Cited In (16)

• Dirac-type theorems in random hypergraphs
• Covering cycles in sparse graphs
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• A Dirac-type theorem for Berge cycles in random hypergraphs
• Transference for loose Hamilton cycles in random 3-uniform hypergraphs
• Resilience for tight Hamiltonicity
• The global resilience of Hamiltonicity in \(G(n, p)\)
• Cores of random graphs are born Hamiltonian
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Triangle resilience of the square of a Hamilton cycle in random graphs
• Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs
• Color‐biased Hamilton cycles in random graphs
• Dirac’s theorem for random regular graphs
• Hamiltonicity in random directed graphs is born resilient
• On resilience of connectivity in the evolution of random graphs
• On the resilience of hamiltonicity and optimal packing of Hamilton cycles in random graphs

This page was built for publication: Hamiltonicity in random graphs is born resilient

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