Hilton-Milner Theorem for the $r$-independent sets in a union of cliques
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912726462234624 |
|---|---|
| author | Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej |
| author_facet | Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej |
| contents | We give a Hilton-Milner Theorem for the $r$-independent sets in the graph that is the union of copies of $K_k$. That is, we determine the maximum intersecting families of $r$-independent sets in this graph, subject to the condition that the sets in a family do not all share a common element. As a by-product, we also find a tight upper bound for the sum of sizes of a pair of cross intersecting families made up of the same objects.
We apply our theorem to find the largest intersecting family of $r$-independent sets in a family of graphs called ``depth-two claws". This confirms the Holroyd--Talbot conjecture for depth-two claws, extending previous results on these graphs (which covered cases where $r$ was relatively small compared to the number of vertices) to all possible values of $r$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18785 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hilton-Milner Theorem for the $r$-independent sets in a union of cliques Gunderson, Karen Meagher, Karen Morris, Joy Pantangi, Venkata Raghu Tej Combinatorics 05C35, 05C69, 05D05 We give a Hilton-Milner Theorem for the $r$-independent sets in the graph that is the union of copies of $K_k$. That is, we determine the maximum intersecting families of $r$-independent sets in this graph, subject to the condition that the sets in a family do not all share a common element. As a by-product, we also find a tight upper bound for the sum of sizes of a pair of cross intersecting families made up of the same objects. We apply our theorem to find the largest intersecting family of $r$-independent sets in a family of graphs called ``depth-two claws". This confirms the Holroyd--Talbot conjecture for depth-two claws, extending previous results on these graphs (which covered cases where $r$ was relatively small compared to the number of vertices) to all possible values of $r$. |
| title | Hilton-Milner Theorem for the $r$-independent sets in a union of cliques |
| topic | Combinatorics 05C35, 05C69, 05D05 |
| url | https://arxiv.org/abs/2511.18785 |