The EKR conjecture for induced subgraphs of perfect matchings

Let MnM_n be the graph consisting of nn pairwise disjoint copies of K2K_2, and let 4H(p,s)(n)44\mathcal{H}^{(p,s)}(n)4 be the family of induced subgraphs of MnM_n consisting of pp disjoint edges and ss isolated vertices, where s,ps,p are non-negative integers and 12p+sn1\leq 2p+s\leq n. A family of members of 4H(p,s)(n)44\mathcal{H}^{(p,s)}(n)4 is intersecting if any two of its members have a common vertex.

EKR conjecture. 4H(p,s)(n)44\mathcal{H}^{(p,s)}(n)4 is EKR: every intersecting subfamily has size at most the size of a star, with equality attained by a family consisting of all members containing a fixed vertex of MnM_n.

This conjecture extends two distinct Erdős–Ko–Rado-type theorems to families of induced subgraphs of perfect matchings. The supplied text does not state whether it has been resolved.

Sources & referencesView supporting material

Primary source

Melissa M. Fuentes and Vikram Kamat, “On intersecting families of subgraphs of perfect matchings”, arXiv:2407.12289 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.