On a $d$-degree Erdős-Ko-Rado Theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913437144055808 |
|---|---|
| author | Huang, Hao Zhang, Yi |
| author_facet | Huang, Hao Zhang, Yi |
| contents | A family of subsets $\mathcal{F}$ is intersecting if $A \cap B \neq \emptyset$ for any $A, B \in \mathcal{F}$. In this paper, we show that for given integers $k > d \ge 2$ and $n \ge 2k+2d-3$, and any intersecting family $\mathcal{F}$ of $k$-subsets of $\{1, \cdots, n\}$, there exists a $d$-subset of $[n]$ contained in at most $\binom{n-d-1}{k-d-1}$ subsets of $\mathcal{F}$. This result, proved using spectral graph theory, gives a $d$-degree generalization of the celebrated Erdős-Ko-Rado Theorem, improving a theorem of Kupavskii. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14091 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On a $d$-degree Erdős-Ko-Rado Theorem Huang, Hao Zhang, Yi Combinatorics A family of subsets $\mathcal{F}$ is intersecting if $A \cap B \neq \emptyset$ for any $A, B \in \mathcal{F}$. In this paper, we show that for given integers $k > d \ge 2$ and $n \ge 2k+2d-3$, and any intersecting family $\mathcal{F}$ of $k$-subsets of $\{1, \cdots, n\}$, there exists a $d$-subset of $[n]$ contained in at most $\binom{n-d-1}{k-d-1}$ subsets of $\mathcal{F}$. This result, proved using spectral graph theory, gives a $d$-degree generalization of the celebrated Erdős-Ko-Rado Theorem, improving a theorem of Kupavskii. |
| title | On a $d$-degree Erdős-Ko-Rado Theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.14091 |