Optimal threshold for a random graph to be 2-universal

DOI10.1090/TRAN/7727MaRDI QIDQ5234488zbMATH OpenOpenAlexWikidataFDO

Authors Asaf Ferber, Gal Kronenberg, Kyle Luh

Publication date 26 September 2019

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

graph embeddingrandom graphsuniversal graphsuniversality

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80)

Abstract: For a family of graphs $mathcalF$, a graph $G$ is $mathcalF$-universal if $G$ contains every graph in $mathcalF$ as a (not necessarily induced) subgraph. For the family of all graphs on $n$ vertices and of maximum degree at most two, $mathcalH(n,2)$, we prove that there exists a constant $C$ such that for $pgeqCleft(fraclogn{n}^{2}ight{)}^{frac13}$, the binomial random graph $G(n,p)$ is typically $mathcalH(n,2)$-universal. This bound is optimal up to the constant factor as illustrated in the seminal work of Johansson, Kahn, and Vu for triangle factors. Our result improves significantly on the previous best bound of $pgeqCleft(fraclognnight{)}^{frac12}$ due to Kim and Lee. In fact, we prove the stronger result that for the family of all graphs on $n$ vertices, of maximum degree at most two and of girth at least $ell$, $mathcal{H}^{ell}(n,2)$, $G(n,p)$ is typically $mathcal{H}^{ell}(n,2)$-universal when $pgeqCleft(fraclogn{n}^{ell-1}ight{)}^{frac1ell}$. This result is also optimal up to the constant factor. Our results verify (in a weak form) a classical conjecture of Kahn and Kalai.

Recommendations

• Universality of Random Graphs for Graphs of Maximum Degree Two
• 2-universality in randomly perturbed graphs
• On Universal Threshold Graphs
• scientific article; zbMATH DE number 1047734
• Threshold graph limits and random threshold graphs
• An improved upper bound on the density of universal random graphs
• An improved upper bound on the density of universal random graphs
• An exact threshold theorem for random graphs and the node-packing problem
• The thresholds for diameter 2 in random Cayley graphs
• On universality of graphs with uniformly distributed edges

Cites work

• Almost-spanning universality in random graphs
• An improved upper bound on the density of universal random graphs
• Biased positional games for which random strategies are nearly optimal
• Embedding large graphs into a random graph
• Embedding nearly-spanning bounded degree trees
• Embedding spanning trees in random graphs
• Expanders Are Universal for the Class of All Spanning Trees
• Expanding graphs contain all small trees
• Factors in random graphs
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4212111 (Why is no real title available?)
• scientific article; zbMATH DE number 5764887 (Why is no real title available?)
• scientific article; zbMATH DE number 3733961 (Why is no real title available?)
• scientific article; zbMATH DE number 3750997 (Why is no real title available?)
• scientific article; zbMATH DE number 3613090 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1833411 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Large bounded degree trees in expanding graphs
• Local resilience of almost spanning trees in random graphs
• On graphs which contain all small trees
• On Graphs Which Contain All Sparse Graphs
• On the existence of a factor of degree one of a connected random graph
• On Universal Graphs for Spanning Trees
• Small universal graphs
• Spanning subgraphs of random graphs
• Spanning Subgraphs of Random Graphs
• Sparse universal graphs
• Sparse universal graphs for bounded‐degree graphs
• The probabilistic method
• Thresholds and Expectation Thresholds
• Tree embeddings
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• Universality of random graphs and rainbow embedding
• Universality of Random Graphs for Graphs of Maximum Degree Two

Cited in

(15)

• Thresholds versus fractional expectation-thresholds
• 2-universality in randomly perturbed graphs
• Universality of Random Graphs for Graphs of Maximum Degree Two
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• An improved upper bound on the density of universal random graphs
• Triangles in randomly perturbed graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Finding any given 2‐factor in sparse pseudorandom graphs efficiently
• Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
• The square of a Hamilton cycle in randomly perturbed graphs
• On oriented cycles in randomly perturbed digraphs
• A robust Corrádi-Hajnal theorem
• Cycles of every length and orientation in randomly perturbed digraphs (extended abstract)
• Clique factors in pseudorandom graphs
• Universality for graphs of bounded degeneracy

This page was built for publication: Optimal threshold for a random graph to be 2-universal

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