REVIEW 3 major objections 4 minor 21 references
A complete $t$-intersection theorem for families of spanning trees
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read For all $t$ from 2 to $n-2$, the largest $t$-intersecting family of spanning trees is the trivial one: all trees containing a fixed forest of $t$ edges.
desk verdict A substantial and likely true complete t-intersection theorem for spanning trees, but the proof of the second spread approximation has a real gap that needs a fix before the result is verified. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument is carried by the spread approximation technique combined with a peeling procedure. The spread lemma, a sunflower-type covering statement, lets the authors replace a large $t$-intersecting family $\mathcal{F}$ by a $t'$-intersecting family $\mathcal{S}$ of small forests so that most trees of $\mathcal{F}$ contain some forest in $\mathcal{S}$. A peeling process then removes the larger sets in $\mathcal{S}$ layer by layer, and the remaining core layer $\mathcal{W}_k$ is controlled by the estimate $f(j)=\binom{t}{t-j}\binom{k}{j}^2 (k+1)^{k-j}$; the location of its maximum determines how many trees come from each uniformity layer. The decisive comparison is between the candidate families $\mathcal{U}_{n,t,r,F} = \{A \in \mathcal{T}_n : |A \cap F| \ge t+r\}$, and the main technical content is to show that the trivial $r=0$ family is always the largest, which reduces to inequalities comparing $c_{n,t+r}$ with $c_{n,t}$ and to four-regime asymptotics for the maximizer of $f(j)$.
What would settle it
Compute the size of the natural nontrivial candidate — the family of all spanning trees that share at least $t+1$ edges with a fixed forest of $t+2$ edges — for $t = n/2 - 1$ and large $n$. The theorem predicts this family is strictly smaller than $c_{n,t} n^{n-2-t}$, so a count exceeding the trivial bound would refute the extremality claim; if the inequality holds, it confirms the theorem in the regime where the two candidates are closest.
Extended reading notes
Core claim
For $n \ge n_0$ and $2 \le t \le n-2$, any family $\mathcal{F}$ of labelled spanning trees of $K_n$ that is $t$-intersecting — every two trees share at least $t$ edges — satisfies $|\mathcal{F}| \le c_{n,t} n^{n-2-t}$, and equality holds if and only if $\mathcal{F}$ is the family of all spanning trees containing a fixed forest with $t$ edges whose connected components have sizes $\lfloor n/(n-t)\rfloor$ and $\lceil n/(n-t)\rceil$. The constant $c_{n,t}$ is the maximum product of $n-t$ positive integers with sum $n$, which arises from the tree-counting formula for the number of labelled trees containing a given forest. The theorem is complete in the sense that it covers every $t$ in the meaningful range $2 \le t \le n-2$ (the case $t=n-1$ is trivial and $t=1$ was already known), and it identifies the unique extremal families, not just the extremal size.
Load-bearing premise
The proof depends on a detailed asymptotic estimate of where the largest term in $f(j)=\binom{t}{t-j}\binom{k}{j}^2(k+1)^{k-j}$ lies (Observation 18); if that estimate gave the wrong location in any of the four regimes, the proof would lose control of the non-trivial layers and could not force the extremal family to be trivial.
Editorial extensions
If this is right
- Every $t$-intersecting family of spanning trees of $K_n$ has size at most $c_{n,t}n^{n-2-t}$, so the maximum size question is closed for every $t$ from $2$ to $n-2$.
- Extremal families are rigid: the only families of the maximal size are the trivial ones based on a forest whose components differ by at most one vertex, so any family of that size must have exactly this form.
- The ratio $c_{n,t+1}/c_{n,t}$ is at most $2$ in general, and at most $e/3$ or $9/8$ in the two large-$t$ regimes, which is why the trivial example beats the natural alternatives in the entire range.
- Together with the previously known $t=1$ and small-$t$ results, the theorem makes spanning trees one of the few structures for which a complete $t$-intersection theorem is known.
Reading between the lines
- A natural next step is to ask whether an analogous statement holds for spanning trees in other host graphs, such as complete bipartite graphs; the spread-approximation method may transfer, but the product of component sizes would be replaced by a different enumeration.
- The four-regime layer estimate suggests that a stability version should hold: any family whose size is within a constant factor of the maximum must lie mostly inside a trivial family (or, for $(1-\varepsilon)n/2 \le t < n/2$, inside the $i=1$ candidate), extending the paper's approximate-structure remark into a full stability theorem.
- A computational check of the borderline case $t = n/2-1$, where the nontrivial candidate is closest to the trivial one, would provide numerical confirmation of the extremality claim for moderate $n$ and a practical test of how small $n_0$ can be taken.
- The proof's reliance on the four-regime maximizer estimate marks the spot where a different layer structure — as occurs in permutations — would break the 'trivial always wins' phenomenon; host structures whose layer counts obey a different binomial product are the natural place to look for phase transitions.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves a complete t-intersection theorem for families of labelled spanning trees of K_n. For n>n0 and 2≤t≤n−2, any t-intersecting family F⊂T_n is shown to have size at most c_{n,t} n^{n−2−t}, where c_{n,t} is the maximum product of n−t positive integers summing to n, and equality is characterized by the trivial family of all trees containing a fixed forest with t edges whose component sizes are as equal as possible. The proof builds on the small-t result of [7] and uses spread approximation, a peeling procedure, a second finer spread approximation, and a stability/equality analysis. The paper is clearly organized and the overall strategy is coherent, but as written a load-bearing step in the proof of Theorem 23 does not establish that the second approximation family is t-intersecting.
Significance. If the main theorem is correct, this is a rare complete t-intersection theorem, covering the entire meaningful range of t for spanning trees and giving a sharp bound with a clean extremal construction. The proof adapts spread-approximation and peeling techniques to trees, confirms conjectures from the earlier paper [7], and includes precise equality cases. The paper is explicit about the structure of extremal families and provides parameter-free bounds, which is a strength. However, the current version has a significant gap in the derivation of the second spread approximation, and a few supporting estimates are asserted rather than proved; these issues must be addressed before the result can be considered established.
major comments (3)
- [Theorem 23] The verification that the family S produced in Theorem 23 is t-intersecting is invalid as written. After pruning from F_{A_i}(A_i) all sets with |F∩(A_j\A_i)| ≥ x, a set U_i∈G_i may still contain up to x−1 edges of A_j\A_i. Even if U_1 and U_2 are disjoint, the intersection (U_1∪A_1)∩(U_2∪A_2) has size at most |A_1∩A_2| + |U_1∩A_2| + |U_2∩A_1| ≤ (t−x)+2(x−1) = t+x−2, which for x≥2 is at least t and therefore does not contradict t-intersection. The analogous argument in Lemma 15 works only because the threshold n^{1−ε/3}/2 is half the gap; here the threshold must be lowered to x/2 (or the sets meeting the other base forest must be pruned separately), using the fact that 10εt is much larger than |A_j\A_i|. As written, Theorem 23 does not establish that S is t-intersecting, so the peeling procedure in Section 9 has no valid input.
- [Observation 18] Observation 18 asserts, without derivation, the location of the maximizer j0 of f(j)=binom(t,t−j) binom(k,j)^2 (k+1)^{k−j} in four separate regimes. The text says only that this is 'from [16]' and based on simple calculations. This estimate is load-bearing for Lemma 19 and for the layer bounds (12)–(14) in Section 9; if it failed in any regime, the peeling argument would lose control of the non-trivial layers. Please provide a self-contained proof or give a precise citation to the exact statement in [16] and verify that all hypotheses (in particular t ≥ k and 'sufficiently large t') hold in the ranges used here.
- [Proof of Theorem 23] The stopping condition in the iterative construction in Theorem 23 is written as |F_N| ≤ c_{n,t'} n^{n−2−t'} · 2^{−1/2 n^{1−ε/4}}, but t' is not defined in Theorem 23 and this threshold is incompatible with the claimed bound (iii), which is |F'| ≤ 2^{−1/2 n^{1−ε/4}} c_{n,t} n^{n−2−t}. By Lemma 9(iv), c_{n,t'} n^{n−2−t'} can exceed c_{n,t} n^{n−2−t} by a factor exponential in n^{1−ε/3}, so the stated stopping rule would leave a remainder far larger than o(|F|). The threshold should presumably use c_{n,t} n^{n−2−t}; please correct this and adjust the proof accordingly.
minor comments (4)
- [Lemma 13] In Case I of Lemma 13, the number of trees obtained by adding an edge from v to a tree on [n]\{v} is (n−1)(n−1)^{n−3−t} = (n−1)^{n−2−t}, not n(n−1)^{n−3−t}; the displayed inequality '> (n−1)^{n−3−t}' should read '> (n−1)^{n−2−t}' to match the lemma's statement.
- [Introduction] The sentence 'who showed the same result for n ≥ 2^19 and 1 < t ≤ n/(4032 log_2 n) this result was proved in [7]' is garbled and should be rewritten.
- [Lemma 15] The threshold n^{1−ε/3}/2 is not an integer for general n; this is harmless but should be stated with floors or ceilings to avoid a minor formal issue.
- [Proof of Theorem 14] In the displayed bound on |F_N|, the symbol 'c_{n,|S_n|}' should be 'c_{n,|S_N|}' for consistency with the preceding notation.
Circularity Check
No reduction-by-construction circularity: c_{n,t} comes from Cayley-type counting, and the large-t proof is self-contained; the small-t range is imported from [7] (overlapping-authors preprint with an independent proof), and the Theorem 23 sketch leaves the t-intersecting peeling input unproven.
-
other
[Section 8, Theorem 23 (second spread approximation), proof that S is t-intersecting; this S is the input to the Section 9 peeling procedure.]
"The only property that we are left to verify is that S is t-intersecting. This is done in a way that is very similar to the proof of Lemma 15, and we sketch it below. ... we can apply the coloring argument, finding two disjoint sets U1, U2, where U_i ∈ G_i. Then U_i ∪ A_i violate the t-intersection property of F."
Flagged as missing support: the sketch's pruning threshold does not yield the claimed contradiction. For x = t − |A1∩A2|, G_i only excludes F with |F∩(A_j∖A_i)| ≥ x, so each found F_i may still contain up to x−1 edges of the other base forest. With disjoint U_i (hence F1∩F2=∅), |(F1∪A1)∩(F2∪A2)| = |A1∩A2| + |F1∩A2| + |F2∩A1| ≤ (t−x) + 2(x−1) = t+x−2 ≥ t for every x ≥ 2, so F's t-intersection is not contradicted; a threshold of x/2 would close the gap as in Lemma 15, where the threshold is half the gap. This is a proof gap rather than a reduction by construction, but it breaks the chain: Section 9 applies peeling to S on the strength of this verification.
-
self citation load bearing
[Section 9 (proof of Theorem 1, small-t case); Introduction and Theorem 2; cf. Lemma 12 from [7] and Observation 18 from [16].]
"If t < 2 n^{1−ε/7} we are done by the result of [7], so we may assume the opposite inequality holds. ... Our result extends the result of Frankl, Hurlbert, Ihringer, Kupavskii, Lindzey, Meagher and Tej Pantangi, who showed the same result for n ≥ 2^19 and 1 < t ≤ n/(4032 log2 n) this result was proved in [7]."
This is the paper's load-bearing self-citation, and it is not circular in the reduction sense: [7] is a prior, separate proof of the same bound and extremal family for n ≥ 2^19 and 1 < t ≤ n/(4032 log2 n), with assumptions that do not include Theorem 1, and the present theorem is not used in [7]. It is nonetheless load-bearing for the claim of completeness: for every t < 2n^{1−ε/7}, both the upper bound and the equality case of Theorem 1 are imported verbatim from a preprint whose author list overlaps with the present paper, and the t=1 case (Theorem 2) is likewise quoted from [7]. Since the cited result is independent and verifiable, this does not force the present conclusion; it only means the complete theorem is the union of two separately-proven ranges.
full rationale
No step of the derivation reduces to its own input by construction. The extremal constant c_{n,t} is not fitted to the target result: it is the maximum of q_1···q_m over partitions of n into n−t parts, equal to |𝒯_n[F]|/n^{n−2−t} by the Cayley-type formula of Lemma 7 (cited to the external paper [19]), so the bound in Theorem 1 is the size of the trivial family, and the proof's content is the upper bound. The spread-approximation and peeling arguments (Sections 5–7) use the externally proved spread lemma [2, 11, 20] and their own counting; no parameter is fitted to a subset of data and then renamed a prediction. The main self-citations are (i) [7] for the regime t < 2n^{1−ε/7}, Theorem 2 for t=1, and Lemma 12 — a prior overlapping-authors paper with an independent proof of the same statement on a smaller range, hence genuine evidence that does not raise the circularity score; and (ii) Observation 18 from [16], a parameter-free calculation about the location of the maximizer of f(j), whose stated assumptions (t ≥ k, t large) do not include the target theorem. The flagged defect is the sketched verification in Theorem 23 that the second spread approximation S is t-intersecting: with pruning at threshold x rather than x/2, the intersection of the two constructed trees is only bounded by t+x−2 ≥ t, so the contradiction does not follow and the peeling input in Section 9 is unsupported. This is a correctness risk in an otherwise self-contained argument, not a definitional or self-citation circularity, and it does not by itself make the theorem's output equal to its input. Accordingly the overall circularity score is 2.
Assumptions & free parameters
assumptions (5)
- standard math Cayley's tree formula |T_n| = n^{n−2} and the generalized count for trees containing a fixed forest (Lemma 7, from [19]).
- standard math Sharpened spread lemma of Alweiss-Lovett-Wu-Zhang, with improvements by Hu and Stoeckl (Theorem 5).
- domain assumption The prior result [7] proves the theorem for 1<t≤n/(4032 log n) and for t=1; the present proof assumes [7] as the base for small t.
- ad hoc to paper The analytic estimate in Observation 18 about the location of the maximizer j0 of f(j), asserted without proof.
- domain assumption Lemmas 12 and 13 on trees containing a forest and avoiding another tree; Lemma 12 is imported from [7].
Cite this review
Pith. "Pith review of A complete $t$-intersection theorem for families of spanning trees." pith.science (2026). https://pith.science/paper/FD75RGFX
@misc{pith2026250717913,
author = {Pith},
title = {Pith review of: A complete $t$-intersection theorem for families of spanning trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/FD75RGFX}},
note = {Machine review of arXiv:2507.17913}
}
abstract
Let $\mathcal T_n$ denote the set of all labelled spanning trees of $K_n$. A family $\mathcal F \subset \mathcal T_n$ is $t$-intersecting if for all $A, B \in \mathcal F$ the trees $A$ and $B$ share at least $t$ edges. In this paper, we determine for $n>n_0$ the size of the largest $t$-intersecting family $\mathcal F\subset \mathcal T_n$ for all meaningful values of $t$ ($t\le n-1$). This result is a rare instance when a complete $t$-intersection theorem for a given type of structures is known.
Reference graph
Works this paper leans on
-
[16]
A. Kupavskii,An almost complete t-intersection theorem for permutations, arXiv preprint arXiv:2405.07843, (2024)
arXiv 2024
- [7]
-
[1]
Ahlswede and L.H
R. Ahlswede and L.H. Khachatrian,The Complete Intersection Theorem for Systems of Finite Sets, European Journal of Combinatorics. 18 (1997), 125–136
1997
-
[2]
R. Alweiss, S. Lovett, K. Wu, and J. Zhang,Improved bounds for the sunflower lemma, arXiv:1908.08483, (2019)
arXiv 2019
- [3]
-
[4]
P. Erd˝ os, C. Ko, and R. Rado,Intersection theorems for systems of finite sets, The Quart. J. Math. 12 (1961), N1, 313–320
work page 1961
-
[5]
Y. Filmus,The weighted complete intersection theorem, Journal of Combinatorial Theory, Series A 151 (2017), 84–101
work page 2017
-
[6]
Frankl,The Erd˝ os-Ko-Rado theorem is true for n=ckt, Combinatorics (Proc
P. Frankl,The Erd˝ os-Ko-Rado theorem is true for n=ckt, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, 365–375, Colloq. Math. Soc. J´ anos Bolyai, 18, North-Holland
work page 1976
Show all 21 references
-
[8]
Frankl and Z
P. Frankl and Z. F¨ uredi,Beyond the Erdos-Ko-Rado theorem, J. Combin. Theory Ser. A 56 (1991) N2, 182–194
1991
- [9]
-
[10]
Frankl, R.M
P. Frankl, R.M. Wilson,The Erd˝ os-Ko-Rado theorem for vector spaces, Journal of Combinatorial Theory, Series A 43 (1986), 228–236. A COMPLETE𝑡-INTERSECTION THEOREM FOR F AMILIES OF SPANNING TREES 19
1986
-
[11]
L. Hu,Entropy Estimation via Two Chains: Streamlining the Proof of the Sun- flower Lemmahttps:// theorydish.blog/2021/05/19/entropy-estimation-via-two-chains-streamlining-the-proof-of-the-sunflower-lemma/, (2021)
2021
-
[12]
Keevash, N
P. Keevash, N. Lifshitz, E. Long, D. Minzer,Global hypercontractivity and its applications, arXiv preprint arXiv:2103.04604, (2021)
2021 arXiv
-
[13]
Katona,Intersection theorems for systems of finite sets, Acta Math
G. Katona,Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964) 329–337
1964
-
[14]
Keller, N
N. Keller, N. Lifshitz, D. Minzer, and O. Sheinfeld,On𝑡-intersecting families of permutations, http://arxiv.org/abs/2303.15755v2
-
[15]
Kupavskii,Intersection theorems for uniform subfamilies of hereditary families(2023), arXiv.2311.02246
A. Kupavskii,Intersection theorems for uniform subfamilies of hereditary families(2023), arXiv.2311.02246
2023 arXiv
-
[17]
Kupavskii, F
A. Kupavskii, F. Noskov,Linear dependencies, polynomial factors in the Duke–Erd˝ os forbidden sunflower prob- lem, arXiv preprint arXiv:2410.06156, (2024)
2024 arXiv
-
[18]
Kupavskii and D
A. Kupavskii and D. Zakharov,Spread approximations for forbidden intersections problems, Advances in Math- ematics, 445:109653, (2024)
2024
-
[19]
Linyuan Lu, Austin Mohr, and L´ aszl´ o Sz´ ekely,Quest for negative dependency graphs, Recent advances in harmonic analysis and applications, volume 25 of Springer Proc. Math. Stat., pages 243–258. Springer, New York, (2013)
2013
-
[20]
Stoeckl,Lecture notes on recent improvements for the sunflower lemma,https://mstoeckl.com/notes/ research/sunflower_notes.html
M. Stoeckl,Lecture notes on recent improvements for the sunflower lemma,https://mstoeckl.com/notes/ research/sunflower_notes.html
-
[21]
R. M. Wilson,The exact bound in the Erd˝ s–Ko–Rado theorem, Combinatorica 4 (1984), N2-3, 247–257. Moscow Institute of Physics and Technology, Russia; Email:liza.fm@yandex.ru Moscow Institute of Physics and Technology, St. Petersburg State University, Innopolis Uni- versity, R...
1984
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.