Intersecting Families of Spanning Trees

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ő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\ge 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ász Local Lemma.

18 pages; the application of the LLLL is now correct