Resilience of Perfect Matchings and Hamiltonicity in Random Graph\n Processes

2017/10/02 by Rajko Nenadov, Angelika Steger, Nenadov, Rajko +3 · 2 citations
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Complex Network Analysis Techniques #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.1710.00799

Abstract

Let G_i be the random graph process: starting with an empty graph G₀\nwith n vertices, in every step i \≥ 1 the graph G_i is formed by taking\nan edge chosen uniformly at random among the non-existing ones and adding it to\nthe graph G_{i - 1}. The classical `hitting-time' result of Ajtai,\nKoml 'os, and Szemer 'edi, and independently Bollob 'as, states that\nasymptotically almost surely the graph becomes Hamiltonian as soon as the\nminimum degree reaches 2, that is if \δ(G_i) \≥ 2 then G_i is\nHamiltonian. We establish a resilience version of this result. In particular,\nwe show that the random graph process almost surely creates a sequence of\ngraphs such that for m \≥ ( tfrac16 + o(1))n\log n edges, the 2-core\nof the graph G_m remains Hamiltonian even after an adversary removes\n( tfrac12 - o(1))-fraction of the edges incident to every vertex. A\nsimilar result is obtained for perfect matchings.\n

Cited by

• Colour-biased Hamilton cycles in dense graphs and random graphs
• Cyclic subsets of tournaments

Related

• Hamiltonicity in random graphs is born resilient
• Constructing Hamilton cycles and perfect matchings efficiently
• Robust hamiltonicity of random directed graphs
• Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than 2n Rounds
• Berge Hamilton cycles in a random sparsification of dense hypergraphs