2-universality in randomly perturbed graphs

DOI10.1016/J.EJC.2020.103118MaRDI QIDQ2178671zbMATH OpenOpenAlexFDO

Authors O. Parczyk

Publication date 11 May 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

embeddingpackinguniversalityuniversal graphsconjecture of Bollabás and Eldridge

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A graph $G$ is called universal for a family of graphs $mathcalF$ if it contains every element $FinmathcalF$ as a subgraph. Let $mathcalF(n,2)$ be the family of all graphs with maximum degree $2$. Ferber, Kronenberg, and Luh [Optimal Threshold for a Random Graph to be 2-Universal, to appear in Transactions of the American Mathematical Society] proved that there exists a $C$ such that for $pgeC(n^{-2/3}lo{g}^{1/3}n)$ the random graph $G(n,p)$ a.a.s is $mathcalF(n,2)$-universal, which is asymptotically optimal. For any $n$-vertex graph $G_{a}lpha$ with minimum degree $delta(G_{a}lpha)gealphan$ Aigner and Brandt [Embedding arbitrary graphs of maximum degree two, Journal of the London Mathematical Society 48 (1993), 39-51] proved that $G_{a}lpha$ is $mathcalF(n,2)$-universal for an optimal $alphage2/3$. In this note, we consider the model of randomly perturbed graphs, which is the union $G_{a}lphacupG(n,p)$. We prove that $G_{a}lphacupG(n,p)$ is a.a.s. $mathcalF(n,2)$-universal provided that $alpha>0$ and $p=omega(n^{-2/3})$. This is asymptotically optimal and improves on both results from above in the respective parameter. Furthermore, this extends a result of B"ottcher, Montgomery, Parczyk, and Person [Embedding spanning bounded degree subgraphs in randomly perturbed graphs, arXiv:1802.04603 (2018)], who embed a given $FinmathcalF(n,2)$ at these values. We also prove variants with universality for the family $mathcal{F}^{e}ll(n,2)$, all graphs from $mathcalF(n,2)$ with girth at least $ell$. For example, there exists an $el{l}_0$ depending only on $alpha$ such that for all $ellgeel{l}_0$ already $p=omega(1/n)$ is sufficient for $mathcal{F}^{e}ll(n,2)$-universality.

Recommendations

• Universality of Random Graphs for Graphs of Maximum Degree Two
• Optimal threshold for a random graph to be 2-universal
• Almost-spanning universality in random graphs
• Almost-spanning universality in random graphs (extended abstract)
• Universality of random graphs

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Adding random edges to dense graphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• An improved upper bound on the density of universal random graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Embedding Arbitrary Graphs of Maximum Degree Two
• Embedding large graphs into a random graph
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Factors in random graphs
• Hamilton -cycles in randomly perturbed hypergraphs
• Hamiltonian circuits in random graphs
• How many random edges make a dense graph hamiltonian?
• Introduction to Random Graphs
• Optimal threshold for a random graph to be 2-universal
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Proof of the Alon-Yuster conjecture
• Some Theorems on Abstract Graphs
• Spanning trees in random graphs
• Spanning trees in randomly perturbed graphs
• Spanning universality in random graphs
• Sprinkling a few random edges doubles the power
• The size Ramsey number of a directed path
• Threshold functions
• Tilings in randomly perturbed dense graphs
• Universality for bounded degree spanning trees in randomly perturbed graphs

Cited in

(6)

• The square of a Hamilton cycle in randomly perturbed graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• On a 2-parameter class of scale free random graphs
• Optimal threshold for a random graph to be 2-universal
• The effect of adding randomly weighted edges
• Universality of Random Graphs for Graphs of Maximum Degree Two

This page was built for publication: 2-universality in randomly perturbed graphs

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