Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.08128 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909704866758656 |
|---|---|
| author | Frankl, Peter Hurlbert, Glenn Ihringer, Ferdinand Kupavskii, Andrey Lindzey, Nathan Meagher, Karen Pantangi, Venkata Raghu Tej |
| author_facet | Frankl, Peter Hurlbert, Glenn Ihringer, Ferdinand Kupavskii, Andrey Lindzey, Nathan Meagher, Karen Pantangi, Venkata Raghu Tej |
| contents | 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 \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ász Local Lemma. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_08128 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Intersecting Families of Spanning Trees Frankl, Peter Hurlbert, Glenn Ihringer, Ferdinand Kupavskii, Andrey Lindzey, Nathan Meagher, Karen Pantangi, Venkata Raghu Tej Combinatorics 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 \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ász Local Lemma. |
| title | Intersecting Families of Spanning Trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.08128 |