Intersecting Families of Spanning Trees of $K_{n,n}$

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\le 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\ge 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}}^{\prime }$ where $\mathcal{F}$ is a family of all trees containing a fixed $t$-matching, and ${\mathcal{S}}^{\prime }$ is a distinguished set of exceptional trees of size $|{\mathcal{S}}^{\prime }|=o(|\mathcal{F}|)$.

The authors explicitly reserves all rights in this work. No permission is granted for the reproduction, storage, or use of this document for the purpose of training artificial intelligence systems or for text and data mining (TDM), including but not limited to the generation of embeddings, summaries, or synthetic derivatives