Note on the codegree version of the Erdős--Ko--Rado theorem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913140256538624 |
|---|---|
| author | Gan, Luyining Han, Jie Im, Seonghyuk |
| author_facet | Gan, Luyining Han, Jie Im, Seonghyuk |
| contents | Kupavskii proved a codegree version of the Erdős--Ko--Rado theorem by showing that for an intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ with $n \geq 2k +3d/(1-d/k)$, the minimum $d$-degree of $\mathcal{F}$ is at most $\binom{n-d-1}{k-d-1}$. Huang and Zhang improved the bound on $n$ to $n \geq 2k+2d-3$. In this short note, we prove that if $d = k-1$, then the bound on $n$ can be improved to $2k + \sqrt{2k} + O(1)$. In addition, we extend our method to show that the bound on $n$ can be improved to $2k + 7k^{2/3}+O(k^{1/3})$ when $d=k-2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17945 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Note on the codegree version of the Erdős--Ko--Rado theorem Gan, Luyining Han, Jie Im, Seonghyuk Combinatorics Kupavskii proved a codegree version of the Erdős--Ko--Rado theorem by showing that for an intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ with $n \geq 2k +3d/(1-d/k)$, the minimum $d$-degree of $\mathcal{F}$ is at most $\binom{n-d-1}{k-d-1}$. Huang and Zhang improved the bound on $n$ to $n \geq 2k+2d-3$. In this short note, we prove that if $d = k-1$, then the bound on $n$ can be improved to $2k + \sqrt{2k} + O(1)$. In addition, we extend our method to show that the bound on $n$ can be improved to $2k + 7k^{2/3}+O(k^{1/3})$ when $d=k-2$. |
| title | Note on the codegree version of the Erdős--Ko--Rado theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.17945 |