Random perturbation of sparse graphs

DOI10.37236/9510MaRDI QIDQ2030748zbMATH OpenOpenAlexFDO

Authors Max Hahn-Klimroth, Giulia S. Maesaka, Yannick Mogge, S. Mohr, O. Parczyk

Publication date 7 June 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

binomial random graphrandomly perturbed graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In the model of randomly perturbed graphs we consider the union of a deterministic graph $mathcal{G}_{a}lpha$ with minimum degree $alphan$ and the binomial random graph $mathbbG(n,p)$. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by Pos'{a} and Korv{s}unov on the threshold in $mathbbG(n,p)$. In this note we extend this result in $mathcal{G}_{a}lphacupmathbbG(n,p)$ to sparser graphs with $alpha=o(1)$. More precisely, for any $varepsilon>0$ and $alphacolonmathbbNmapsto(0,1)$ we show that a.a.s. $$ is Hamiltonian, where $$. If $alpha>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $alpha=O(1/n)$ the random part $mathbbG(n,p)$ is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into $mathbbG(n,p)$.

Review text

Summary: In the model of randomly perturbed graphs we consider the union of a deterministic graph \(\mathcal{G}_\alpha\) with minimum degree \(\alpha n\) and the binomial random graph \(\mathbb{G}(n,p)\). This model was introduced by \textit{T. Bohman} et al. [Random Struct. Algorithms 22, No. 1, 33--42 (2003; Zbl 1013.05044)] and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by \textit{L. Posa} [Discrete Math. 14, 359--364 (1976; Zbl 0322.05127)] and \textit{A. D. Korsunov} [Sov. Math., Dokl. 17, 760--764 (1976; Zbl 0353.05039); translation from Dokl. Akad. Nauk SSSR 228, 529--532 (1976)] on the threshold in \(\mathbb{G}(n,p)\). In this note we extend this result in \(\mathcal{G}_\alpha\cup\mathbb{G}(n,p)\) to sparser graphs with \(\alpha=o(1)\). More precisely, for any \(\varepsilon>0\) and \(\alpha \colon \mathbb{N} \mapsto (0,1)\) we show that a.a.s. \( \mathcal{G}_\alpha\cup \mathbb{G}(n,\beta /n)\) is Hamiltonian, where \(\beta = -(6 + \varepsilon) \log(\alpha)\). If \(\alpha>0\) is a fixed constant this gives the aforementioned result by Bohman et al. and if \(\alpha=O(1/n)\) the random part \(\mathbb{G}(n,p)\) is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into \(\mathbb{G}(n,p)\).

Recommendations

• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Hamiltonicity in randomly perturbed hypergraphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Universality for bounded degree spanning trees in randomly perturbed graphs

Cites work

• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Embedding large graphs into a random graph
• Embedding nearly-spanning bounded degree trees
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Embedding spanning trees in random graphs
• Factors in random graphs
• Hamiltonian circuits in random graphs
• How many random edges make a dense graph hamiltonian?
• scientific article; zbMATH DE number 1286511 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Introduction to Random Graphs
• Large bounded degree trees in expanding graphs
• Large-scale structures in random graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Long paths and Hamiltonicity in random graphs
• On large matchings and cycles in sparse random graphs
• On Pósa's conjecture for random graphs
• On the existence of a factor of degree one of a connected random graph
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Powers of Hamiltonian cycles in randomly augmented graphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Proof of a Packing Conjecture of Bollobás
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Proof of the Seymour conjecture for large graphs
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Smoothed analysis of algorithms
• Some Theorems on Abstract Graphs
• Spanning Subgraphs of Random Graphs
• Spanning subgraphs of random graphs
• Spanning trees in dense graphs
• Spanning trees in random graphs
• Spanning trees in randomly perturbed graphs
• Spanning universality in random graphs
• Threshold functions
• Tilings in randomly perturbed dense graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Vertex Ramsey properties of randomly perturbed graphs

Cited in

(19)

• Graph perturbations
• Sparse quasi-random graphs
• Push is Fast on Sparse Random Graphs
• Sprinkling a few random edges doubles the power
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Cycle lengths in randomly perturbed graphs
• Rainbow trees in uniformly edge‐colored graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• Hamiltonicity of graphs perturbed by a random geometric graph
• Long paths in heterogeneous random subgraphs of graphs with large minimum degree
• The square of a Hamilton cycle in randomly perturbed graphs
• Schur properties of randomly perturbed sets
• On oriented cycles in randomly perturbed digraphs
• Cycles and trees in randomly perturbed sparse digraphs
• How many random edges make an almost-Dirac graph Hamiltonian?
• Fragile minor-monotone parameters under a random edge perturbation
• Hamiltonicity of random subgraphs of the hypercube

This page was built for publication: Random perturbation of sparse graphs

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