The seminal Erd\H{ o}s--Ko--Rado (EKR) theorem states that if $\mathcal{ F}$ is a family of $k$-subsets of an $n$-element set $X$ for $k\leq n/2$ such that every pair of subsets in $\mathcal{ F}$ has a nonempty intersection, then $\mathcal{ F}$ can be no bigger than the trivially intersecting family obtained by including all $k$-subsets of $X$ that contain a fixed element $x\in X$. This family is called the star centered at $x$. In this paper, we formulate and prove an EKR theorem for intersecting families of subgraphs of the perfect matching graph, the graph consisting of $n$ disjoint edges. This can be considered a generalization not only of the aforementioned EKR theorem but also of a signed variant of it, first stated by Meyer (1974), and proved separately by Deza--Frankl (1983) and Bollob\'as--Leader (1997). The proof of our main theorem relies on a novel extension of Katona's beautiful cycle method.
Categories: math.CO