Optimal threshold for a random graph to be 2-universal

DOI10.1090/tran/7727zbMath1420.05161arXiv1612.06026OpenAlexW2963969197WikidataQ128974425 ScholiaQ128974425MaRDI QIDQ5234488

Gal Kronenberg, Asaf Ferber, 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

random graphsuniversalityuniversal graphsgraph embedding

Mathematics Subject Classification ID

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

Related Items (7)

Triangles in randomly perturbed graphs ⋮ 2-universality 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 ⋮ Thresholds versus fractional expectation-thresholds ⋮ Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process

Cites Work

• Embedding nearly-spanning bounded degree trees
• Expanding graphs contain all small trees
• Spanning subgraphs of random graphs
• Hamiltonian circuits in random graphs
• On graphs which contain all small trees
• Sparse universal graphs
• Large bounded degree trees in expanding graphs
• Tree embeddings
• Universality of random graphs and rainbow embedding
• Small universal graphs
• Universality of Random Graphs for Graphs of Maximum Degree Two
• Embedding Spanning Trees in Random Graphs
• Local resilience of almost spanning trees in random graphs
• Thresholds and Expectation Thresholds
• Factors in random graphs
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• On Graphs Which Contain All Sparse Graphs
• Spanning Subgraphs of Random Graphs
• On Universal Graphs for Spanning Trees
• Expanders Are Universal for the Class of All Spanning Trees
• An improved upper bound on the density of universal random graphs
• Embedding large graphs into a random graph
• Sparse universal graphs for bounded‐degree graphs
• On the existence of a factor of degree one of a connected random graph
• Almost‐spanning universality in random graphs
• Biased positional games for which random strategies are nearly optimal
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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