2-universality in randomly perturbed graphs

DOI10.1016/J.EJC.2020.103118zbMATH Open1439.05160arXiv1902.01823OpenAlexW3014011675MaRDI QIDQ2178671FDOQ2178671

O. Parczyk

Publication date: 11 May 2020

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

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.

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

zbMATH Keywords

embeddingpackinguniversalityuniversal graphs[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=conjecture+of+Bollab%EF%BF%BD%EF%BF%BDs+and+Eldridge&go=Go conjecture 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)

Cites Work

• Title not available (Why is that?)
• Spanning trees in random graphs
• Spanning trees in randomly perturbed graphs
• Proof of the Alon-Yuster conjecture
• The size Ramsey number of a directed path
• Some Theorems on Abstract Graphs
• Factors in random graphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Hamiltonian circuits in random graphs
• Threshold functions
• Adding random edges to dense graphs
• Spanning universality in random graphs
• How many random edges make a dense graph hamiltonian?
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Introduction to Random Graphs
• Embedding Arbitrary Graphs of Maximum Degree Two
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Tilings in Randomly Perturbed Dense Graphs
• An improved upper bound on the density of universal random graphs
• Hamilton \(\ell\)-cycles in randomly perturbed hypergraphs
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs
• Powers of tight Hamilton cycles in randomly perturbed hypergraphs
• Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs
• Optimal threshold for a random graph to be 2-universal
• Embedding large graphs into a random graph
• Sprinkling a Few Random Edges Doubles the Power

Cited In (6)

• The Effect of Adding Randomly Weighted Edges
• 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
• 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)