Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.14291 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908547774676992 |
|---|---|
| author | Joseph, Zaphenath |
| author_facet | Joseph, Zaphenath |
| contents | The Erdős-Ko-Rado theorem states that for $r \leq \frac{n}{2}$, the largest intersecting family of $r$-subsets of $[n]$ is given by fixing a common element in all subsets, which trivially ensures pairwise intersection. We investigate this property for families of independent sets in the Cartesian product of complete graphs, $K_n \times K_m$. Using a novel extension of Katona's cycle method, we prove $K_n \times K_m$ is $r$-EKR when $1 \leq r \leq \frac{\min(m,n)}{2}$, demonstrating the Holroyd--Talbot conjecture holds for this class of well-covered graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14291 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An EKR Theorem for the Cartesian Product of Complete Graphs Joseph, Zaphenath Combinatorics The Erdős-Ko-Rado theorem states that for $r \leq \frac{n}{2}$, the largest intersecting family of $r$-subsets of $[n]$ is given by fixing a common element in all subsets, which trivially ensures pairwise intersection. We investigate this property for families of independent sets in the Cartesian product of complete graphs, $K_n \times K_m$. Using a novel extension of Katona's cycle method, we prove $K_n \times K_m$ is $r$-EKR when $1 \leq r \leq \frac{\min(m,n)}{2}$, demonstrating the Holroyd--Talbot conjecture holds for this class of well-covered graphs. |
| title | An EKR Theorem for the Cartesian Product of Complete Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.14291 |