Spanning trees with large maximum degrees
Jun Yan · 2025
Read Spanning trees with large maximum degrees by Jun Yan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17736.txt.
Introduction
Jun Yan studies when a dense graph must contain every possible spanning tree. A spanning tree connects all vertices of a graph without cycles. A classic result covers trees whose largest vertex degree stays fairly small. Yan asks what happens when that degree grows much larger.
He finds a near-best minimum degree condition for the large-degree case. Minimum degree means the smallest number of edges at any vertex. Past that threshold, the host graph contains every allowed tree. He proves matching statements for random graphs as well. The work sharpens a celebrated theorem by three earlier authors.
Catalog record
| CREATOR | Jun Yan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-17736
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Spanning trees with large maximum degrees Jun Yan Abstract The celebrated result of Komlós, Sárközy, and Szemerédi states that for any ε > 0 \varepsilon>0 , there exists 0 < c < 1 0<c<1 , such that for all sufficiently large n n , every n n -vertex graph G G with δ ( G ) ≥ ( 1 / 2 + ε ) n \delta(G)\geq(1/2+\varepsilon)n contains every n n -vertex tree with maximum degree at most c n / log n cn/\log n . This is best possible up to the value of c c . In this paper, we extend this result to trees with higher maximum degrees, and prove that for Δ ≫ n / log n \Delta\gg n/\log n , roughly speaking, δ ( G ) ≥ n − n 1 − ( 1 + o ( 1 ) ) Δ / n \delta(G)\geq n-n^{1-(1+o(1))\Delta/n} is the asymptotically optimal minimum degree condition which guarantees that G G contains every n n -vertex spanning tree with maximum degree at most Δ \Delta . We also prove the corresponding statements in the random graph setting. 1 Introduction An important family of problems in extremal graph theory, known as Dirac-type problems, asks for the optimal minimum degree conditions one needs to impose on an n -vertex host graph G in order to guarantee that G contains some desired substructures. This is named after the famous Dirac’s Theorem [ 3 , Theorem 3] from 1952, which says that for n\geq 3 , \delta(G)\geq n/2 ensures the existence of a Hamilton cycle. Since then, Dirac-type problems have been studied extensively for many different structures. For more information on these and other related problems, we refer interested readers to the survey of Kühn and Osthus [ 10 ] . Here, we focus on the case of finding spanning trees with n vertices. For any n and \Delta , let \mathcal{T}(n,\Delta) be the set of n -vertex trees with maximum degrees at most \Delta . What is the optimal minimum degree condition on an n -vertex host graph G that ensures G contains a copy of every T\in\mathcal{T}(n,\Delta) ? The first result of this type was proved in 1995 by Komlós, Sárközy, and Szemerédi [ 7 , Theorem 1.1] . They showed that for any constants \varepsilon,\Delta>0 , and for all sufficiently large n , every n -vertex graph G with \delta(G)\geq(1/2+\varepsilon)n contains every tree in \mathcal{T}(n,\Delta) . The minimum degree condition was improved in 2010 by Csaba, Levitt, Nagy-György, and Szemerédi [ 2 , Theorem 1] , who showed that \delta(G)\geq n/2+C\log n is sufficient for some constant C depending on \Delta , and that this is tight up to the value of C . In 2001, Komlós, Sárközy, and Szemerédi [ 8 , Theorem 1.2] improved their earlier result in another direction by showing that for any \varepsilon>0 , there exists 0<c<1 , such that for all sufficiently large n , every n -vertex graph G with \delta(G)\geq(1/2+\varepsilon)n contains every tree in \mathcal{T}(n,cn/\log n) . Moreover, they showed that this is optimal up to the value of c with a random graph construction. In this paper, we consider the natural question of what happens when \Delta\gg n/\log n . By Komlós, Sárközy, and Szemerédi’s counterexample [ 8 ] , we need to increase the minimum degree condition in order to find all trees in \mathcal{T}(n,\Delta) . Our main result below shows that in this range, if an n -vertex graph G has minimum degree roughly n-n^{1-(1+o(1))\Delta/n} , then G contains every tree in \mathcal{T}(n,\Delta) . Theorem 1.1 . For any \varepsilon>0 , there exists C>1 , such that the following is true for all sufficiently large n . Let \Delta\geq Cn/\log n , and suppose k=\left\lceil(n-1)/\Delta\right\rceil-1\geq 2 . If G is an n -vertex graph with \delta(G)\geq n-n^{1-(1+\varepsilon)/k} , then G contains every tree in \mathcal{T}(n,\Delta) . Note that when \Delta=Cn/\log n , k is roughly \log n/C , and the minimum degree condition is around \delta(G)\geq n-n/e^{C} , which is linear. Thus, for \Delta in the lower range, our result asymptotically matches the form of Komlós, Sárközy, and Szemerédi’s result in [ 8 ] . By a standard application of the Chernoff Bound, we immediately obtain a corresponding random graph version of this result. This deals with a different regime compared to Montgomery’s seminal result [ 11 , Theorem 1.1] in 2019, which shows that for every constant \Delta , there exists a constant C , such that with high probability G(n,C\log n/n) contains every tree in \mathcal{T}(n,\Delta) . Corollary 1.2 . For any \varepsilon>0 , there exists C>1 , such that the following is true. Let \Delta\geq Cn/\log n , and suppose k=\left\lceil(n-1)/\Delta\right\rceil-1\geq 2 . Then, with high probability G(n,1-n^{-(1+2\varepsilon)/k}) contains every tree in \mathcal{T}(n,\Delta) . Proof. For every v\in G(n,1-n^{-(1+2\varepsilon)/k}) , let X_{v} be the number of vertices not adjacent to v . Then, \mathbb{E}[X_{v}]=1+(n-1)n^{-(1+2\varepsilon)/k} , so by Lemma 2.2 , for sufficiently large C , \mathbb{P}(X_{v}\geq n^{1-(1+\varepsilon)/k})\leq\mathbb{P}(X_{v}\geq 2\mathbb{E}[X_{v}])\leq 2\exp(-\mathbb{E}[X_{v}]/3)\leq 2\exp(-n^{1-(1+2\varepsilon)/k}/6)\leq o(n^{-1}). Therefore, by a union bound, with high probability G(n,1-n^{-(1+2\varepsilon)/k}) has minimum degree at least n-n^{1-(1+\varepsilon)/k} , and thus contains every T\in\mathcal{T}(n,\Delta) by Theorem 1.1 . ∎ When n/\Delta=O_{\varepsilon}(1) and n-\Delta\left\lceil(n-1)/\Delta\right\rceil is not “too small”, the choice of k in the two results above can be improved by 1 to \left\lceil(n-1)/\Delta\right\rceil . By being more careful in our proof, it is possible to make this condition more precise, but we did not pursue this direction in order to present more unified versions of our results that work for all n and \Delta . Aside from this, both of these results are asymptotically best possible, as shown by the following random graph construction analogous to the counterexample of Komlós, Sárközy, and Szemerédi in [ 8 ] . Recall that a set K\subset V(G) is dominating if N(K)=V(G)\setminus K . Essentially, for every \Delta\gg n/\log n , the main obstruction to containing all trees in \mathcal{T}(n,\Delta) is the lack of a dominating set of size around n/\Delta , and p=1-n^{-\Delta/n} is around when we can expect G(n,p) to contain such a dominating set. Theorem 1.3 . For every \varepsilon>0 , let n/\log n\leq\Delta\leq n-1 , and let k=\left\lceil(n-1)/\Delta\right\rceil . Then, there exists T\in\mathcal{T}(n,\Delta) , such that with high probability G(n,1-n^{-(1-\varepsilon)/k}) does not contain T . Proof. Let T\in\mathcal{T}(n,\Delta) be a tree that contains a vertex that is adjacent to a set X of k other vertices, such that every other vertex in T is a leaf that is adjacent to a vertex in X , and every x\in X has degree at most \Delta . This is possible as k=\left\lceil(n-1)/\Delta\right\rceil . Moreover, note that X is a dominating set of size k in T . We claim that if G\sim G(n,1-n^{-(1-\varepsilon)/k}) , then with high probability G does not contain a dominating set K of size k , and so with high probability G(n,1-n^{-(1-\varepsilon)/k}) does not contain T . Indeed, for any fixed K\subset V(G) , the probability that K is a dominating set in G is at most \left(1-\left(n^{-\frac{1-\varepsilon}{k}}\right)^{k}\right)^{n-k}\leq\left(1-n^{-1+\varepsilon}\right)^{n/2}\leq\exp\left(-n^{\varepsilon}/2\right). Therefore, by a union bound, the probability that such a K exists is at most \binom{n}{k}\exp(-n^{\varepsilon}/2)\leq\exp\left(k\log n-n^{\varepsilon}/2\right)\leq\exp\left(2(\log n)^{2}-n^{\varepsilon}/2\right)=o(1), where we used