An Erdős–Ko–Rado type theorem for subgraphs of perfect matchings
Let M k be a 2 n -vertex graph with n pairwise disjoint edges and let H ( p , s ) ( n ) be the family of subsets of V ( M n ) that span exactly p edges and s isolated vertices. We prove that for n ≥ 2 p + s this family has the Erdős–Ko–Rado property: the size of the largest intersecting family is equal to the number of sets containing a fixed vertex. The bound n ≥ 2 p + s is the best possible, improving a recent theorem with n ≥ 2 p + 2 s by Fuentes and Kamat.
Authors
- Dániel T. Nagy (ORCID: https://orcid.org/0000-0001-6154-7905)
Institutions
- Eötvös Loránd University (HU)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2025-05-08
- DOI
- https://doi.org/10.1016/j.disc.2025.114560
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00