Universality for bounded degree spanning trees in randomly perturbed graphs

DOI10.1002/RSA.20850MaRDI QIDQ5216180zbMATH OpenOpenAlexWikidataFDO

Authors Julia Böttcher, Jie Han, Yoshiharu Kohayakawa, Richard Montgomery, Yury Person, O. Parczyk

Publication date 14 February 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

perturbed graphsrandom graphsspanning treesuniversality

Mathematics Subject Classification ID

Trees (05C05) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We solve a problem of Krivelevich, Kwan and Sudakov [SIAM Journal on Discrete Mathematics 31 (2017), 155-171] concerning the threshold for the containment of all bounded degree spanning trees in the model of randomly perturbed dense graphs. More precisely, we show that, if we start with a dense graph $G_{a}lpha$ on $n$ vertices with $delta(G_{a}lpha)gealphan$ for $alpha>0$ and we add to it the binomial random graph $G(n,C/n)$, then with high probability the graph $G_{a}lphacupG(n,C/n)$ contains copies of all spanning trees with maximum degree at most $Delta$ simultaneously, where $C$ depends only on $alpha$ and $Delta$.

Recommendations

• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Spanning trees in randomly perturbed graphs
• Random perturbation of sparse graphs
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS

Cites work

• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Embedding nearly-spanning bounded degree trees
• Hamilton -cycles in randomly perturbed hypergraphs
• Hamiltonian circuits in random graphs
• How many random edges make a dense graph hamiltonian?
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Large bounded degree trees in expanding graphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Pseudo-random graphs
• Some Theorems on Abstract Graphs
• Spanning trees in dense graphs
• Threshold functions
• Tree embeddings

Cited in

(46)

• The local limit of the uniform spanning tree on dense graphs
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Random perturbation of sparse graphs
• Small rainbow cliques in randomly perturbed dense graphs
• 2-universality in randomly perturbed graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Almost-spanning universality in random graphs (extended abstract)
• Vertex Ramsey properties of randomly perturbed graphs
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Spanning trees in randomly perturbed graphs
• Tree decompositions of graphs without large bipartite holes
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Tilings in randomly perturbed dense graphs
• Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Factors in randomly perturbed hypergraphs
• Rainbow trees in uniformly edge‐colored graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• On powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
• Hamiltonicity of graphs perturbed by a random geometric graph
• Speeding up random walk mixing by starting from a uniform vertex
• A Ramsey–Turán theory for tilings in graphs
• Dirac-type conditions for spanning bounded-degree hypertrees
• Embedding loose spanning trees in 3-uniform hypergraphs
• A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
• Rainbow cliques in randomly perturbed dense graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• On oriented cycles in randomly perturbed digraphs
• Spanning trees in graphs without large bipartite holes
• 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
• Rainbow subgraphs of uniformly coloured randomly perturbed graphs
• Ramsey properties of randomly perturbed hypergraphs
• Minors, connectivity, and diameter in randomly perturbed sparse graphs
• Smoothed analysis of the Komlós conjecture: Rademacher noise
• Rainbow connectivity of randomly perturbed graphs
• Cycles of every length and orientation in randomly perturbed digraphs (extended abstract)
• Hamiltonicity of random subgraphs of the hypercube
• Randomly perturbed digraphs also have bounded-degree spanning trees
• Hamiltonicity in randomly perturbed hypergraphs

This page was built for publication: Universality for bounded degree spanning trees in randomly perturbed graphs

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