Expanders Are Universal for the Class of All Spanning Trees

DOI10.1017/S0963548312000533zbMath1260.05081arXiv1108.4647OpenAlexW2294714952MaRDI QIDQ4911172

Wojciech Samotij, Michael Krivelevich, Daniel Johannsen

Publication date: 14 March 2013

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

random regular graph\(\mathcal{F}\)-universal graph

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Structural characterization of families of graphs (05C75) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Building Spanning Trees Quickly in Maker-Breaker Games, Spanning structures and universality in sparse hypergraphs, Fast embedding of spanning trees in biased maker-breaker games, Universality of random graphs and rainbow embedding, Optimal threshold for a random graph to be 2-universal, The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition

Cites Work

• A randomized embedding algorithm for trees
• Hamilton cycles in highly connected and expanding graphs
• Embedding nearly-spanning bounded degree trees
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Expanding graphs contain all small trees
• Trees in sparse random graphs
• The longest path in a random graph
• On graphs which contain all small trees
• Sparse universal graphs
• Hamilton cycles in random subgraphs of pseudo-random graphs
• On the maximum degree in a random tree
• Tree embeddings
• Random regular graphs of high degree
• Universality of Random Graphs
• Embedding Spanning Trees in Random Graphs
• Explicit sparse almost-universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$
• Local resilience of almost spanning trees in random graphs
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Ars combinatoria
• Maximal Flow Through a Network
• Uniform generation of random regular graphs of moderate degree
• Remarks on positional games. I
• Universal Graphs for Bounded-Degree Trees and Planar Graphs
• On Universal Graphs for Spanning Trees
• Bounding Ramsey numbers through large deviation inequalities
• Sparse universal graphs for bounded‐degree graphs
• Almost universal graphs
• On a combinatorial game