Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.17455 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913444006985728 |
|---|---|
| author | Nagy, Dániel T. |
| author_facet | Nagy, Dániel T. |
| contents | Let $M_k$ be a $2n$-vertex graph with $n$ pairwise disjoint edges and let $\mathcal{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\ge 2p+s$ this family has the Erdős--Ko--Rado property: the size of the largest intersecting family equals to the number of sets containing a fixed vertex. The bound $n\ge 2p+s$ is the best possible, improving a recent theorem with $n\ge 2p+2s$ by Fuentes and Kamat. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17455 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Erdős-Ko-Rado type theorem for subgraphs of perfect matchings Nagy, Dániel T. Combinatorics 05D05 Let $M_k$ be a $2n$-vertex graph with $n$ pairwise disjoint edges and let $\mathcal{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\ge 2p+s$ this family has the Erdős--Ko--Rado property: the size of the largest intersecting family equals to the number of sets containing a fixed vertex. The bound $n\ge 2p+s$ is the best possible, improving a recent theorem with $n\ge 2p+2s$ by Fuentes and Kamat. |
| title | An Erdős-Ko-Rado type theorem for subgraphs of perfect matchings |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2407.17455 |