Expanders Are Universal for the Class of All Spanning Trees
From MaRDI portal
Abstract: Given a class of graphs F, we say that a graph G is universal for F, or F-universal, if every H in F is contained in G as a subgraph. The construction of sparse universal graphs for various families F has received a considerable amount of attention. One is particularly interested in tight F-universal graphs, i.e., graphs whose number of vertices is equal to the largest number of vertices in a graph from F. Arguably, the most studied case is that when F is some class of trees. Given integers n and Delta, we denote by T(n,Delta) the class of all n-vertex trees with maximum degree at most Delta. In this work, we show that every n-vertex graph satisfying certain natural expansion properties is T(n,Delta)-universal or, in other words, contains every spanning tree of maximum degree at most Delta. Our methods also apply to the case when Delta is some function of n. The result has a few very interesting implications. Most importantly, we obtain that the random graph G(n,p) is asymptotically almost surely (a.a.s.) universal for the class of all bounded degree spanning (i.e., n-vertex) trees provided that p geq c n^{-1/3} log^2n where c > 0 is a constant. Moreover, a corresponding result holds for the random regular graph of degree pn. In fact, we show that if Delta satisfies log n leq Delta leq n^{1/3}, then the random graph G(n,p) with p geq c Delta n^{-1/3} log n and the random r-regular n-vertex graph with r geq cDelta n^{2/3} log n are a.a.s. T(n,Delta)-universal. Another interesting consequence is the existence of locally sparse n-vertex T(n,Delta)-universal graphs. For constant Delta, we show that one can (randomly) construct n-vertex T(n,Delta)-universal graphs with clique number at most five. Finally, we show robustness of random graphs with respect to being universal for T(n,Delta) in the context of the Maker-Breaker tree-universality game.
Recommendations
- Expanders are universal for the class of all spanning trees
- Expanders via random spanning trees
- Expanders via Random Spanning Trees
- Universal traversal sequences for expander graphs
- Expanding graphs contain all small trees
- On Constructing Expanders for Any Number of Vertices
- Spanning trees of extended graphs
- Expander spanning subgraphs with large girth
- A unified existence theorem for normal spanning trees
- Generalized spanning trees
Cites work
- A randomized embedding algorithm for trees
- Almost universal graphs
- Ars combinatoria
- Bounding Ramsey numbers through large deviation inequalities
- Embedding nearly-spanning bounded degree trees
- Embedding spanning trees in random graphs
- Expanding graphs contain all small trees
- Explicit sparse almost-universal graphs for G (n, kn)
- Hamilton cycles in highly connected and expanding graphs
- Hamilton cycles in random subgraphs of pseudo-random graphs
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Local resilience of almost spanning trees in random graphs
- Maximal Flow Through a Network
- On a combinatorial game
- On graphs which contain all small trees
- On the maximum degree in a random tree
- On Universal Graphs for Spanning Trees
- Random regular graphs of high degree
- Remarks on positional games. I
- Sharp threshold for the appearance of certain spanning trees in random graphs
- Sparse universal graphs
- Sparse universal graphs for bounded‐degree graphs
- The longest path in a random graph
- Tree embeddings
- Trees in sparse random graphs
- Uniform generation of random regular graphs of moderate degree
- Universal Graphs for Bounded-Degree Trees and Planar Graphs
- Universality of random graphs
Cited in
(12)- Universality of random graphs and rainbow embedding
- 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
- scientific article; zbMATH DE number 1953079 (Why is no real title available?)
- Expanders via random spanning trees
- Optimal threshold for a random graph to be 2-universal
- The approximate Loebl-Komlós-Sós conjecture. I: The sparse decomposition
- Expanders are universal for the class of all spanning trees
- Spanning trees in graphs without large bipartite holes
- Tree universality in positional games
- Spanning trees in pseudorandom graphs via sorting networks
This page was built for publication: Expanders Are Universal for the Class of All Spanning Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4911172)
