An EKR Theorem for the Cartesian Product of Complete Graphs

Abstract

The Erdős-Ko-Rado theorem states that for $r\le \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\le r\le \frac{\min (m,n)}{2}$, demonstrating the Holroyd--Talbot conjecture holds for this class of well-covered graphs.