Expanders Are Universal for the Class of All Spanning Trees

Details Expanders Are Universal for the Class of All Spanning Trees Expanders Are Universal for the Class of All Spanning Trees

2011-08-23

arxiv.org/abs/1108.4647v1

Mathematics

Combinatorics

25 pages

Scientific paper

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 c\Delta 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.

Affiliated with

Also associated with

No associations

Rating

Expanders Are Universal for the Class of All Spanning Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Expanders Are Universal for the Class of All Spanning Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expanders Are Universal for the Class of All Spanning Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67585