The EKR conjecture for induced subgraphs of perfect matchings

About 2 years old · traced to

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 1≤2p+s≤n1\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.

References

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.