Intersecting Families of Spanning Trees

Andrey Kupavskii; Ferdinand Ihringer; Glenn Hurlbert; Karen Meagher; Nathan Lindzey; Peter Frankl; Venkata Raghu Tej Pantangi

REVIEW 3 major objections 4 minor 1 cited by

Intersecting Families of Spanning Trees

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves a tree analogue of the Erdős–Ko–Rado theorem: for large n, the largest t-intersecting families of spanning trees are the trivial ones fixing t disjoint edges, plus a star exception at t=1.

desk verdict The main theorem is subsumed by the paper's own citations, and the proof's LLLL computation has a repairable numeric bug; worth a referee only if the constants get fixed. read the letter →

arxiv 2502.08128 v2 pith:IKG57ONP submitted 2025-02-12 math.CO

Peter Frankl , Glenn Hurlbert , Ferdinand Ihringer , Andrey Kupavskii , Nathan Lindzey , Karen Meagher , Venkata Raghu Tej Pantangi This is my paper · ORCID

classification math.CO MSC 05C0505C3505D40

keywords Erdős–Ko–Radotheoremspanningtreest-intersectingfamiliesspreadapproximationLopsidedLovászLocalLemmacompletegraphextremalcombinatorics

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to determine the largest families of labelled spanning trees of the complete graph in which every two trees share at least t edges. It proves that, once n is at least about a constant times t log n (explicitly n ≥ $2^{19}$ and t ≤ n/(4032 log_2 n)), the maximum is attained by the natural trivial family: all trees containing a fixed set of t pairwise disjoint edges, of size 2^t $n^{{n-t-2}}$. A separate statement handles t=1, where adding the n stars produces a slightly larger extremal family of size 2 $n^{{n-3}}$ + n − 2. The proof, which combines spread approximation with the Lopsided Lovász Local Lemma, also shows equality forces the trivial structure.

What carries the argument

The load-bearing objects are the trivial t-intersecting families T_n[F], defined as all spanning trees that contain a fixed t-edge forest F; by the standard product formula for labelled trees containing a given forest (Lemma 2.1), their size is maximised when F is t disjoint edges, giving 2^t $n^{{n-t-2}}$. The proof's control comes from two mechanisms. First, the spread approximation theorems reduce an arbitrary t-intersecting family F to a small t-intersecting family S of edge sets of size at most q = 42t log_2 n, leaving a tiny remainder F'; this uses the fact that T_n is (n/2, n−1)-spread. Second, the quantity D_t — the minimum, over t-edge forests F and non-star trees T0 not containing F, of the number of trees that contain F but avoid T0 outside F — is bounded below by $n^{{n-2t-17}}$ through the Lopsided Lovász Local Lemma applied to the line graph of T0. The final inequality |F| ≤ |T_n[F]| − D_t + |F'| is what forces the extremal family to be trivial.

What would settle it

Take the double star T0 with two adjacent centers and about n/2 leaves at each center, let t=2, and let F be two disjoint edges away from the centers. Compute |T_n[T0;F]|, the number of spanning trees containing F and sharing no edge with T0 outside F; if this count is below $n^{{n-2t-17}}$, Proposition 3.1 is false and the proof's lower bound fails, so the theorem would need a different counting argument.

Watch

Extended reading notes

Core claim

The core discovery is an Erdős–Ko–Rado theorem for spanning trees of K_n: the largest t-intersecting families are the 'trivial' ones in the same sense as the classical theorem for sets, but with a boundary correction at t=1. Specifically, Theorem 1.4 states that for n ≥ $2^{19}$ and 1 < t ≤ n/(4032 log_2 n), every t-intersecting family F of trees satisfies |F| ≤ 2^t $n^{{n-t-2}}$, with equality if and only if F is the family of all trees containing a fixed set of t pairwise disjoint edges. Theorem 1.5 states that for t=1 the bound is 2 $n^{{n-3}}$ + (n-2), achieved exactly by the n stars together with all trees containing one fixed edge. The result is proved via a reduction to a small 'spread approximation' family of edge sets, followed by a counting argument, based on the Lopsided Lovász Local Lemma, that bounds how many trees a non-trivial family can miss.

Load-bearing premise

The counting lemma's lower bound rests on an iterative vertex-deletion step: after deleting the largest-degree vertex from a non-star tree, the remaining forest is asserted to be non-star, which is used to keep the Local-Lemma count applicable at each stage.

Editorial extensions

If this is right

For n ≥ 2^19 and 1 < t ≤ n/(4032 log_2 n), every t-intersecting family of spanning trees of K_n has size at most 2^t n^{n-t-2}.
If a family achieves this bound, it must be exactly the set of all trees containing a fixed set of t pairwise disjoint edges; no other construction can tie it.
For t=1 the maximum is 2 n^{n-3} + (n-2), achieved exactly by the n stars together with all trees containing one fixed edge.
Any non-trivial t-intersecting family is quantitatively smaller than the trivial one: the proof shows it must omit at least n^{n-2t-17} trees that the fixed-forest construction contains.
The result is a spanning-tree analogue of the classical Erdős–Ko–Rado theorem, with the same 'fix a core of t elements, take all supersets' structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural extension is to carry the same spread-approximation plus local-lemma strategy to other dense graph classes, such as complete multipartite or quasi-random graphs, where analogous tree-counting formulas exist; the paper lists this as an expectation, not a proved result.
The star exception at t=1 suggests a general principle: when a small class of objects intersects every member of the ambient family, the extremal family gains a boundary term, and the correction disappears for t≥2 because no tree intersects every other tree on two edges.
The explicit constants (n ≥ 2^19 and the factor 4032) are stated as unoptimised; a concrete follow-up is to shrink them or extend the range toward t ≤ n/2, where the paper conjectures the same trivial families remain extremal.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know. First, the main theorem is already covered by stronger results the paper itself flags in Section 7: Conjecture 7.1 (all t ≤ n/2) was proven by Saengrungkongka, and Conjecture 7.2 by Iarovikova–Kupavskii. So the headline result isn't new. Second, the proof as written has a real, but repairable, bug in Lemma 3.5, the counting lemma that drives Proposition 3.1.

The paper does good things. It formulates a natural EKR problem for spanning trees, sets up the spread approximation machinery on a non-uniform family, and the reduction of Theorem 1.4 to a lower bound on D_t is clean. The reliance on the spread-approximation results from [10] is legitimate self-citation; those theorems are general and the hypothesis checks are explicit. The authors are also upfront about the subsequent work, which is a point in their favor.

The concrete problem is in Lemma 3.5. The proof claims 2 ≤ 4(1−4/n)^{n/6} holds for n=5, but it doesn't; the inequality first holds around n=55. And the final product (1−4/n)^m ≥ (1−4/n)^{n−1} is asserted to be ≥ e^{−4}, but it is actually strictly below e^{−4} for every finite n, because (n−1)ln(1−4/n) = −4 − 4/n + O(n^{−2}). So the lemma's stated bound e^{−4} n^{n−2} is not established. This matters because Proposition 3.1 uses the lemma on K_{n−t−12}, and the final step of Theorem 1.4 depends on that lower bound.

The gap is very likely fixable: the true LLLL constant is (1−4/N)^{N−1}, a fixed positive number for N≥99, and the theorem's range n ≥ 2^19 leaves plenty of slack. I don't put much stock in the double-star objection raised in the initial read; after deleting one center, the remaining forest has isolated vertices, so it's not a star in the spanning-tree sense used here. The numerical issue is the real one.

Who is this for? Someone interested in spread approximations on irregular structures, or in the EKR canon for trees, might find the method useful, but the theorem itself is a corollary of published results. I'd send it to a referee if the authors commit to fixing the constants, but the referee should be told the novelty question is essentially settled by the citations. It's not a desk-reject, but it's close.

Referee Report

3 major / 4 minor

Summary. The paper proves an Erdős–Ko–Rado type theorem for t-intersecting families of spanning trees of K_n. Theorem 1.4 states that for n ≥ 2^19 and 1 < t ≤ n/(4032 log₂ n), every t-intersecting family F of spanning trees has size at most 2^t n^{n−t−2}, with equality only for the family of all trees containing a fixed set of t pairwise disjoint edges. Theorem 1.5 states the corresponding 1-intersecting result, where the extremal family is the set of all stars together with all trees containing one fixed edge. The proof combines the spread approximation method with a counting lemma (Lemma 3.5) proved via the Lopsided Lovász Local Lemma, which is used to lower-bound the quantity D_t in Proposition 3.1. The paper also discusses conjectures for larger t and notes that these conjectures have since been proved by other authors.

Significance. If the proof is repaired, the main theorem is a substantial EKR-type result for a non-uniform, highly irregular ambient family, and it gives a nice demonstration of how spread approximations and the LLLL can handle spanning-tree families. The authors are explicit about the non-optimized constants and about the dependency on external spread-approximation theorems, which is a strength of the exposition. However, the paper itself notes in Section 7.1 that Conjecture 7.1 has been proved independently by Saengrungkongka and Conjecture 7.2 by Iarovikova–Kupavskii; since Conjecture 7.1 covers all t ≤ n/2, it subsumes Theorem 1.4. Thus the novelty of the main result is substantially reduced, even though the method and the explicit quantitative form may still be of interest.

major comments (3)

[Section 3, Lemma 3.5] The numerical check in the proof of Lemma 3.5 is false. The proof asserts that the inequality 2 ≤ 4(1−4/n)^{n/6} holds at n = 5 and then, by monotonicity, for all n ≥ 5; substituting n = 5 gives a right-hand side of approximately 1.05, not at least 2. In addition, the final estimate (1−4/n)^m ≥ e^{−4} is justified by m ≤ n−1, but (1−4/n)^{n−1} < e^{−4} for every finite n, since (n−1)ln(1−4/n) = −4 − 4/n + O(n^{−2}). Consequently the claimed bound |T_n[T_0;∅]| ≥ e^{−4} n^{n−2} is not established as written. This is load-bearing because Proposition 3.1 applies Lemma 3.5 to K_{n−t−12}, and the resulting lower bound on D_t drives the final step of Theorem 1.4. The gap appears repairable—for n ≥ 55 the quantity (1−4/n)^{n−1} is bounded below by a positive constant—but the written proof needs correction.
[Section 3, Proposition 3.1, Stage 2] The proof of Proposition 3.1 asserts: 'Since T_t is a tree and v_t the vertex with the largest degree, T_{t+1} will not be star.' This is false in general: if T_t is a double-star, deleting one centre leaves the other centre with all of its leaves, which is a star. The subsequent 12-iteration bound is also hard to follow: the display with the factor (n−t−1−1)/12 times a sum over i = 1 to 11 is not dimensionally meaningful as written, and the equality to (n−t+54)/12 appears to contain a typo. Since the application of Lemma 3.5 to T_{t+12} requires a clear guarantee that T_{t+12} is not 6-star-like, this part of the proof needs a precise repair rather than the current informal iteration count.
[Section 6, Theorem 1.5] Theorem 1.5 is stated in the introduction but is not actually proved. In the proof of Theorem 1.4 the only comment addressing t = 1 is 'If t = 1, there is nothing to do,' yet the upper bound 2n^{n−3} + (n−2) and the equality characterization (all stars plus all trees containing one fixed edge) do not follow from the t ≥ 2 argument. In particular, the claim 'No two stars are t-intersecting' is false for t = 1, and the extremal example for t = 1 is not a trivial family. A separate proof of Theorem 1.5, covering both the bound and the equality case, is needed.

minor comments (4)

[Section 3, Lemma 3.5 proof] The sentence 'From Corollary, 3.4' contains a misplaced comma and should read 'From Corollary 3.4'.
[Section 3, Proposition 3.1, Stage 2] The phrase 'we pick a vertex v_{t+1} in T_t of largest degree' should refer to T_{t+1}, not T_t.
[Section 3, Lemma 3.5, final line] In the final display of the proof, the notation 'e^{−4} T_n' should be 'e^{−4} |T_n|' for clarity.
[Section 3, Proposition 3.1, final paragraph] The inequality (n−t−12)^{n−t−14} > n^{n−2t−16} is asserted with only a hint to take logarithms; since this inequality is used to absorb the constant from Lemma 3.5, a short derivation would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the main result follows from general spread-approximation theorems plus a self-contained counting argument, neither of which encodes the target extremal statement.

full rationale

Theorem 1.4 rests on two ingredients. Theorems 5.1 and 5.2 are imported from Kupavskii's prior spread-approximation work [10, 12]; although this is a self-citation, those theorems are general results about r0-spread t-intersecting families and do not mention spanning trees or assert the EKR bound for trees. The paper's contribution is to verify that Tn is (n/2, n-1)-spread (Lemma 4.3) and to check the parameter inequalities, so the cited theorems are applied rather than assumed. The second ingredient, the counting bound D_t > n^{n-2t-17} (Proposition 3.1), is proved inside the paper from the Lopsided Lovasz Local Lemma and the Lu-Mohr-Szekely negative dependency graph theorem; the extremal family of trees containing a fixed t-edge forest is only a comparison object and is not fed into the D_t bound. No fitted parameter is relabeled as a prediction, and no uniqueness theorem from the authors' own prior work is invoked to exclude alternatives. The apparent numerical defects in Section 3, such as the claimed n=5 check for 2 <= 4(1-4/n)^{n/6} and the bound (1-4/n)^{n-1} >= e^{-4}, are correctness concerns, but a false inequality is not a circular step: the statement being proved is not assumed by being wrongly estimated. Since every load-bearing external result is independent of the target conclusion and the combinatorial proof is self-contained, no circular step can be exhibited.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The proof is a chain of established external theorems. Cayley's formula counts labelled trees; Lemma 2.1 (Lu, Mohr, Székely) counts trees containing a forest; the Lopsided Lovász Local Lemma and the negative dependency graph theorem of Lu, Mohr, Székely supply probabilistic machinery; the spread approximation theorems of Kupavskii and Kupavskii-Zakharov are invoked with explicit parameter checks. No free parameters are fitted, and the paper introduces no new entities. The constants 2^19 and 4032 are explicit universal choices, not tuned to data.

assumptions (7)

standard math Cayley's theorem: K_n has n^{n-2} labelled spanning trees.
Used in the introduction and in Lemma 2.1 to normalize counts of trees.
standard math Lemma 2.1 (Lu, Mohr, Székely): the number of trees containing a forest F with components of sizes q_i is (∏ q_i) n^{n-2-Σ(q_i-1)}.
Core counting formula used throughout Sections 2-6.
standard math Nash-Williams theorem characterizing edge-disjoint spanning trees.
Used to compute the clique number of the tree disjointness graph in the introduction; not central to the main proof.
standard math Lopsided Lovász Local Lemma (Erdős-Spencer).
Used in Lemma 3.5 to lower-bound the number of trees avoiding a given forest.
standard math Lu-Mohr-Székely negative dependency graph theorem (Theorem 3.3).
Justifies using the line graph as a negative dependency graph for edge-occurrence events.
standard math Spread approximation theorems (Kupavskii [10, Theorems 12 and 14]).
The main structural steps of Theorem 1.4 rely on these black-box theorems; the paper verifies their hypotheses.
standard math AM-GM inequality.
Used in Lemma 2.2 to show that the maximum number of trees containing a fixed forest occurs for a forest of disjoint edges.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Intersecting Families of Spanning Trees." pith.science (2026). https://pith.science/paper/IKG57ONP

@misc{pith2026250208128,
  author       = {Pith},
  title        = {Pith review of: Intersecting Families of Spanning Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IKG57ONP}},
  note         = {Machine review of arXiv:2502.08128}
}

abstract

A family $\mathcal{F}$ of spanning trees of the complete graph on $n$ vertices $K_n$ is \emph{$t$-intersecting} if any two members have a forest on $t$ edges in common. We prove an Erd\H{o}s--Ko--Rado result for $t$-intersecting families of spanning trees of $K_n$. In particular, we show there exists a constant $C > 0$ such that for all $n \geq C (\log n) t$ the largest $t$-intersecting families are the families consisting of all trees that contain a fixed set of $t$ disjoint edges (as well as the stars on $n$ vertices for $t = 1$). The proof uses the spread approximation technique in conjunction with the Lopsided Lov\'asz Local Lemma.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A complete $t$-intersection theorem for families of spanning trees
math.CO 2025-07 conditional novelty 7.0 of 10

For n large and 2≤t≤n−2, every t-intersecting family of spanning trees of K_n has size at most c_{n,t} n^{n−2−t}, with equality exactly for the trivial family containing a balanced fixed forest.

Reference graph

Works this paper leans on

17 extracted references · 15 canonical work pages · cited by 1 Pith paper

[10]

Erd˝ os–Ko–Rado type results for partitions via spread ap- proximations

Andrey Kupavskii. Erd˝ os–Ko–Rado type results for partitions via spread ap- proximations. arXiv preprint arXiv:2309.00097 , 2023

arXiv 2023
[2]

Intersection problems in extremal combinatorics: theorems, tech- niques and questions old and new

David Ellis. Intersection problems in extremal combinatorics: theorems, tech- niques and questions old and new. In Surveys in combinatorics 2022 , volume 481 of London Math. Soc. Lecture Note Ser. , pages 115–173. Cambridge Univ. Press, Cambridge, 2022

work page 2022
[3]

Triangle-intersecting families of graphs

David Ellis, Yuval Filmus, and Ehud Friedgut. Triangle-intersecting families of graphs. Journal of the European Mathematical Society , 14(3):841–885, 2012

work page 2012
[4]

Intersection theorems for systems of finite sets

Paul Erd˝ os, Chao Ko, and Richard Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) , 12:313–320, 1961

work page 1961
[5]

Lopsided Lov´ asz local lemma and latin transver- sals

Paul Erd˝ os and Joel Spencer. Lopsided Lov´ asz local lemma and latin transver- sals. Discrete Applied Mathematics , 30(2):151–154, 1991

work page 1991
[6]

On the maximum number of permutations with given maximal or minimal distance

P´ eter Frankl and Mikhail Deza. On the maximum number of permutations with given maximal or minimal distance. J. Combinatorial Theory Ser. A , 22(3):352–360, 1977. INTERSECTING F AMILIES OF TREES 17

work page 1977
[7]

The Erd˝ os–Ko–Rado theorem for vector spaces

P´ eter Frankl and Richard M Wilson. The Erd˝ os–Ko–Rado theorem for vector spaces. J. Combin. Theory Ser. A , 43(2):228–236, 1986

work page 1986
[8]

Erd˝ os–Ko–Rado Theorems: Algebraic Ap- proaches, volume 149 of Cambridge Studies in Advanced Mathematics

Chris Godsil and Karen Meagher. Erd˝ os–Ko–Rado Theorems: Algebraic Ap- proaches, volume 149 of Cambridge Studies in Advanced Mathematics . Cam- bridge University Press, Cambridge, 2016

work page 2016

Show all 17 references

[9]

A complete t-intersection theorem for families of spanning trees, 2025

Elizaveta Iarovikova and Andrey Kupavskii. A complete t-intersection theorem for families of spanning trees, 2025

2025
[11]

Intersection theorems for uniform subfamilies of hereditary families

Andrey Kupavskii. Intersection theorems for uniform subfamilies of hereditary families. arXiv preprint, arxiv:2311.02246 , 2023

2023 arXiv
[12]

Spread approximations for forbidden intersections problems

Andrey Kupavskii and Dmitrii Zakharov. Spread approximations for forbidden intersections problems. Advances in Mathematics , 445:109653, 2024

2024
[13]

Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest

Danyi Li, Wuxian Chen, and Weigen Yan. Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest. Journal of Graph Theory, 104(1):160–170, 2023

2023
[14]

Quest for negative dependency graphs

Linyuan Lu, Austin Mohr, and L´ aszl´ o Sz´ ekely. Quest for negative dependency graphs. In Recent advances in harmonic analysis and applications , volume 25 of Springer Proc. Math. Stat. , pages 243–258. Springer, New York, 2013

2013
[15]

Edgar M. Palmer. On the spanning tree packing number of a graph: a survey. Discrete Mathematics, 230(1):13–21, 2001. Catlin

2001
[16]

On t-intersecting families of spanning trees, 2025

Pitchayut Saengrungkongka. On t-intersecting families of spanning trees, 2025

2025
[17]

Mikl´ os Simonovits and Vera T. S´ os. Intersection theorems for graphs. InProb- lemes combinatoires et th´ eorie des graphes, volume 260, pages 389–391. Colloq. Internat. CNRS, Paris, 1978

1978
[18]

Mikl´ os Simonovits and Vera T. S´ os. Intersection theorems for graphs. II. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II , pages 1017–1030. Colloq. Math. Soc. J´ anos Bolyai, 18 North-Holland Publishing Co., Amsterdam-New York, 1978. 18 P. FRANKL...

1976

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [10]

Erd˝ os–Ko–Rado type results for partitions via spread ap- proximations

Andrey Kupavskii. Erd˝ os–Ko–Rado type results for partitions via spread ap- proximations. arXiv preprint arXiv:2309.00097 , 2023

arXiv 2023

[2] [2]

Intersection problems in extremal combinatorics: theorems, tech- niques and questions old and new

David Ellis. Intersection problems in extremal combinatorics: theorems, tech- niques and questions old and new. In Surveys in combinatorics 2022 , volume 481 of London Math. Soc. Lecture Note Ser. , pages 115–173. Cambridge Univ. Press, Cambridge, 2022

work page 2022

[3] [3]

Triangle-intersecting families of graphs

David Ellis, Yuval Filmus, and Ehud Friedgut. Triangle-intersecting families of graphs. Journal of the European Mathematical Society , 14(3):841–885, 2012

work page 2012

[4] [4]

Intersection theorems for systems of finite sets

Paul Erd˝ os, Chao Ko, and Richard Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) , 12:313–320, 1961

work page 1961

[5] [5]

Lopsided Lov´ asz local lemma and latin transver- sals

Paul Erd˝ os and Joel Spencer. Lopsided Lov´ asz local lemma and latin transver- sals. Discrete Applied Mathematics , 30(2):151–154, 1991

work page 1991

[6] [6]

On the maximum number of permutations with given maximal or minimal distance

P´ eter Frankl and Mikhail Deza. On the maximum number of permutations with given maximal or minimal distance. J. Combinatorial Theory Ser. A , 22(3):352–360, 1977. INTERSECTING F AMILIES OF TREES 17

work page 1977

[7] [7]

The Erd˝ os–Ko–Rado theorem for vector spaces

P´ eter Frankl and Richard M Wilson. The Erd˝ os–Ko–Rado theorem for vector spaces. J. Combin. Theory Ser. A , 43(2):228–236, 1986

work page 1986

[8] [8]

Erd˝ os–Ko–Rado Theorems: Algebraic Ap- proaches, volume 149 of Cambridge Studies in Advanced Mathematics

Chris Godsil and Karen Meagher. Erd˝ os–Ko–Rado Theorems: Algebraic Ap- proaches, volume 149 of Cambridge Studies in Advanced Mathematics . Cam- bridge University Press, Cambridge, 2016

work page 2016