pith. sign in

arxiv: 2606.22697 · v1 · pith:2ZRL3VHKnew · submitted 2026-06-21 · 🧮 math.CO

Intersecting Families of Spanning Trees of K_(n,n)

Gordian C. Bruns , Dheer Noal Desai , Alexander L. Gavrilyuk , Josias Gomez , Nathan Lindzey This is my paper

Pith reviewed 2026-06-26 09:47 UTC · model grok-4.3

classification 🧮 math.CO
keywords intersecting familiesspanning treesK_{n,n}t-intersectingextremal set theorybipartite graphsmatchingsErdős–Ko–Rado
0
0 comments X

The pith

For large n and t up to n over log n, the largest t-intersecting families of spanning trees in K_{n,n} consist of all trees containing a fixed t-matching, plus possibly a small exceptional set.

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

This paper examines families of spanning trees in the balanced complete bipartite graph K_{n,n} where any two trees share at least t edges. It characterizes the largest such t-intersecting families when n is big and t is bounded by roughly n over log n. The main construction is the set of all spanning trees that include a particular fixed t-matching. For the case t equals 1 the bounds are exact and the families are fully described without exceptions. Such results extend ideas from intersecting set systems to the domain of graph spanning trees, showing how edge sharing constraints shape the largest collections.

Core claim

For sufficiently large n and t ≤ n/(C log_2 n) for some absolute constant C>0, any extremal t-intersecting family of spanning trees in K_{n,n} is of the form F union S' where F is the family of all trees containing a fixed t-matching, and S' is a small set of exceptional trees with |S'| = o(|F|). For t=1 the characterization is exact and complete.

What carries the argument

A t-matching, which is a set of t vertex-disjoint edges that all trees in the family must contain to guarantee the t-intersection property.

If this is right

  • The size of the largest t-intersecting family is determined by the number of spanning trees through a fixed t-matching.
  • For t=1, there are no exceptional trees and the extremal families are precisely those fixing a single edge.
  • The characterization holds with the exceptional set vanishing in relative size as n grows.
  • Results apply only when t is sufficiently small compared to n, specifically up to linear over logarithmic.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the log n barrier can be crossed, different constructions might dominate for larger t.
  • The bipartite structure is key, so non-bipartite complete graphs might require separate analysis.
  • Computational verification for moderate n could check the transition point where the bound fails.

Load-bearing premise

The assumption that n is sufficiently large and that t does not exceed n divided by C times log n is required for the stated form of the extremal families to hold.

What would settle it

An explicit construction, for some n larger than the threshold and t in the allowed range, of a t-intersecting family of spanning trees whose size exceeds that of any family fixing a t-matching would disprove the characterization.

read the original abstract

A family of spanning trees of a graph is $t$-intersecting if any pair of spanning trees in the family has $t$ or more edges in common. For sufficiently large $n$ and $t \leq n/C\log_2 n$ for some absolute constant $C>0$, we give a nearly complete characterization of the extremal $t$-intersecting families of spanning trees in balanced complete bipartite graphs with parts of order $n$. In particular, for $t=1$, we give exact bounds and a full characterization of the extremal families. For $t \geq 2$, our bounds are tight up to lower-order terms, and we show that any extremal $t$-intersecting family is of the form $\mathcal{F} \cup \mathcal{S}'$ where $\mathcal{F}$ is a family of all trees containing a fixed $t$-matching, and $\mathcal{S}'$ is a distinguished set of exceptional trees of size $|\mathcal{S}'| = o(|\mathcal{F}|)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper claims that for sufficiently large n and t ≤ n/(C log₂ n) with absolute C>0, the maximum size of a t-intersecting family of spanning trees in K_{n,n} admits a nearly complete structural characterization. For t=1 the bounds are exact and the extremal families are fully described; for t≥2 the extremal families are of the form F ∪ S' where F consists of all spanning trees containing a fixed t-matching and |S'| = o(|F|), with the size bounds tight up to lower-order terms.

Significance. If the proofs are complete, the result supplies the first structural EKR-type theorem for spanning trees in bipartite graphs under an explicit range on t, extending classical intersecting-family techniques to a natural matroid-like setting and giving both exact and asymptotic information.

minor comments (2)
  1. The abstract states the range t ≤ n/(C log₂ n) but does not indicate whether the constant C is effective or merely existential; adding a brief remark on computability of C would clarify the result's scope.
  2. Notation for the exceptional set S' and the o(|F|) term should be defined explicitly in the introduction rather than only in the abstract, to avoid any ambiguity for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, the assessment of its significance, and the recommendation of minor revision. The report contains no specific major comments requiring point-by-point response.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper states a conditional structural result: for sufficiently large n and t ≤ n/(C log₂ n), the extremal t-intersecting families of spanning trees in K_{n,n} are characterized (exactly for t=1; up to o(|F|) exceptions for t≥2) as all trees containing a fixed t-matching plus a small exceptional set. No equations, definitions, or derivations in the provided abstract reduce the claimed extremal size or form to a fitted parameter, a self-citation chain, or an input by construction. The result is presented as a direct theorem with explicit regime conditions rather than a renaming or self-referential prediction. This is the expected non-circular outcome for a standard extremal combinatorics characterization.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper is a pure existence-and-structure proof in extremal graph theory; it invokes standard background results on graphs and intersecting families but introduces no fitted numerical parameters or new postulated objects.

axioms (1)
  • standard math Standard theorems from extremal set theory and graph theory on intersecting families and spanning trees of complete bipartite graphs
    The characterization builds directly on known EKR-type results and basic facts about K_{n,n}.

pith-pipeline@v0.9.1-grok · 5729 in / 1221 out tokens · 21087 ms · 2026-06-26T09:47:41.223196+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 1 linked inside Pith

  1. [1]

    B´ ona and S

    M. B´ ona and S. Wagner. On the intersection of pairs of trees.arXiv preprint arXiv:2501.18570, 2025

    arXiv 2025

  2. [2]

    Dong and J

    F. Dong and J. Ge. Counting spanning trees in a complete bipartite graph which contain a given spanning forest.Journal of Graph Theory, 101(1):79–94, 2022

    2022

  3. [3]

    Frankl, G

    P. Frankl, G. Hurlbert, N. Lindzey, A. Kupavskii, K. Meagher, F. Ihringer, and V. R. T. Pantangi. Intersecting families of spanning trees.arXiv preprint arXiv:2502.08128, 2025

    arXiv 2025

  4. [4]

    Godsil and K

    C. Godsil and K. Meagher. A new proof of the Erd˝ os–Ko–Rado theorem for intersecting families of permutations.Eur. J. Comb., 30(2):404–414, Feb. 2009

    2009

  5. [5]

    J.-M. Guo. Thek-th Laplacian eigenvalue of a tree.Journal of Graph Theory, 54(1):51–57, 2007

    2007

  6. [6]

    Iarovikova and A

    E. Iarovikova and A. Kupavskii. A completet-intersection theorem for families of spanning trees.arXiv preprint arXiv:2507.17913, 2025

    arXiv 2025

  7. [7]

    Kirchhoff

    G. Kirchhoff. On the solution of the equations obtained from the investigation of the linear distribution of galvanic currents.IRE transactions on circuit theory, 5(1):4–7, 1958

    1958

  8. [8]

    Kupavskii

    A. Kupavskii. Erd˝ os–Ko–Rado type results for partitions via spread approximations.Euro- pean Journal of Combinatorics, 132:104288, 2026

    2026

  9. [9]

    Kupavskii and D

    A. Kupavskii and D. Zakharov. Spread approximations for forbidden intersections problems. Advances in Mathematics, 445:109653, 2024. 20 G. BRUNS, D. DESAI, A. GA VRILYUK, J. GOMEZ, AND N. LINDZEY

    2024

  10. [10]

    N. Lindzey. Erd˝ os–Ko–Rado for perfect matchings.European Journal of Combinatorics, 65:130–142, 2017

    2017

  11. [11]

    Malniˇ c, D

    A. Malniˇ c, D. Maruˇ siˇ c, P. Potoˇ cnik, and C. Wang. An infinite family of cubic edge- but not vertex-transitive graphs.Discrete Mathematics, 280(1):133–148, 2004

    2004

  12. [12]

    R. Merris. Laplacian matrices of graphs: a survey.Linear algebra and its applications, 197:143–176, 1994

    1994

  13. [13]

    B. Mohar. Eigenvalues, diameter, and mean distance in graphs.Graphs and combinatorics, 7(1):53–64, 1991

    1991

  14. [14]

    J. Moon. Enumerating labelled trees. In F. Harary, editor,Graph Theory and Theoretical Physics, pages 261–272. Academic Press, London, 1967

    1967

  15. [15]

    J. W. Moon.Counting Labelled Trees. Number 1 in Canadian Mathematical Monographs. Canadian Mathematical Congress, Montreal, 1970

    1970

  16. [16]

    Saengrungkongka

    P. Saengrungkongka. Ont-intersecting families of spanning trees.arXiv preprint arXiv:2507.18629, 2025

    arXiv 2025

  17. [17]

    Wang and J

    W. Wang and J. Ge. On enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest.rXiv preprint arXiv:2602.03602, 2026

    arXiv 2026

  18. [18]

    H. Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differential- gleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung).Mathematische Annalen, 71(4):441–479, 1912

    1912

  19. [19]

    X.-D. Zhang. The Laplacian eigenvalues of graphs: a survey.arXiv preprint arXiv:1111.2897, 2011. Department of Mathematical Sciences, University of Memphis, Memphis, TN 38111 Email address:gcbruns@memphis.edu Department of Mathematical Sciences, University of Memphis, Memphis, TN 38111 Email address:dndesai@memphis.edu Department of Mathematical Sciences,...

    Pith/arXiv arXiv 2011