Erd\H{o}s-Ko-Rado Theorems for Paths in Graphs

Mathematics > Combinatorics [Submitted on 7 Apr 2025 (v1), last revised 17 Jun 2026 (this version, v2)] Title:Erdős-Ko-Rado Theorems for Paths in Graphs View PDF HTML (experimental)Abstract:A family of sets is $s$-intersecting if every pair of its sets has at least $s$ elements in common. It is an $s$-star if all its members have some $s$ elements in common. A family of sets is called $s$-EKR if all its $s$-intersecting subfamilies have size at most that of some $s$-star. For example, the classic 1961 Erdős-Ko-Rado theorem states essentially that the family of $r$-sized subsets of $\{1,2,\ldots,n\}$ is $s$-EKR when $n$ is a large enough function of $r$ and $s$, and the 1967 Hilton-Milner theorem provides the near-star structure of the largest non-star intersecting family of such sets. Two important conjectures along these lines followed: by Chvátal in 1974, that every subset-closed family of sets is 1-EKR, and by Holroyd and Talbot in 2005, that, for every graph, the family of all its $r$-sized independent sets is 1-EKR when every maximal independent set has size at least $2r$. In this paper we present similar 1-EKR results for families of length-$r$ paths in graphs, specifically for sun graphs, which are cycles with pendant edges attached in a uniform way, and theta graphs, which are collections of pairwise internally disjoint paths sharing the same two endpoints. We also prove $s$-EKR results for such paths in suns, and give a Hilton-Milner type result for them as well. A set is a transversal of a family of sets if it intersects each member of the family, and the transversal number of the family is the size of its smallest transversal. For example, stars have transversal number 1, and the Hilton-Milner family has transversal number 2. We conclude the paper with some transversal results involving what we call triangular families, including a few results for projective planes. Submission history From: Neal Bushaw [view email][v1] Mon, 7 Apr 2025 18:22:56 UTC (22 KB) [v2] Wed, 17 Jun 2026 18:51:11 UTC (24 KB) References & Citations Loading... Bibliographic and Citation Tools Bibliographic Explorer (What is the Explorer?) Connected Papers (What is Connected Papers?) Litmaps (What is Litmaps?) scite Smart Citations (What are Smart Citations?) Code, Data and Media Associated with this Article alphaXiv (What is alphaXiv?) CatalyzeX Code Finder for Papers (What is CatalyzeX?) DagsHub (What is DagsHub?) Gotit.pub (What is GotitPub?) Hugging Face (What is Huggingface?) ScienceCast (What is ScienceCast?) Demos Recommenders and Search Tools Influence Flower (What are Influence Flowers?) CORE Recommender (What is CORE?) arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.