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 (6)

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

This page was built for publication: Expanders Are Universal for the Class of All Spanning Trees