A generalized Turán extension of the Deza--Erdős--Frankl Theorem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911826446385152 |
|---|---|
| author | Helliar, Charlotte Liu, Xizhi |
| author_facet | Helliar, Charlotte Liu, Xizhi |
| contents | For an integer $r \ge 3$ and a subset $L \subset [0,r-1]$, a graph $G$ is $(K_{r}, L)$-intersecting if the number of vertices in the intersection of every pair of $K_r$ in $G$ belongs to $L$. We study the maximum number of $K_r$ in an $n$-vertex $(K_{r}, L)$-intersecting graphs. The celebrated Ruzsa--Szemerédi Theorem corresponds to the case $r=3$ and $L = \{0,1\}$.
For general $L$ with $2 \le |L| \le r-1$, we establish the upper bound $\left(1-\frac{1}{3r}\right) \prod_{\ell \in L}\frac{n-\ell}{r- \ell}$ for large $n$, which improves the bound provided by the celebrated Deza--Erdős--Frankl Theorem by a factor of $1-\frac{1}{3r}$. In the special case where $L = \{t, t+1, \ldots, r-1\}$, we derive the tight upper bound for large $n$ and establish a corresponding stability result. This is an extension of the seminal Erdős--Ko--Rado Theorem on $t$-intersecting systems to the generalized Turán setting.
Our proof for the Deza--Erdős--Frankl part involves an interesting combination of the $Δ$-system method and Turán's theorem. Meanwhile, for the Erdős--Ko--Rado part, we employ the stability method, which relies on a theorem of Frankl regarding $t$-intersecting systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02762 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A generalized Turán extension of the Deza--Erdős--Frankl Theorem Helliar, Charlotte Liu, Xizhi Combinatorics For an integer $r \ge 3$ and a subset $L \subset [0,r-1]$, a graph $G$ is $(K_{r}, L)$-intersecting if the number of vertices in the intersection of every pair of $K_r$ in $G$ belongs to $L$. We study the maximum number of $K_r$ in an $n$-vertex $(K_{r}, L)$-intersecting graphs. The celebrated Ruzsa--Szemerédi Theorem corresponds to the case $r=3$ and $L = \{0,1\}$. For general $L$ with $2 \le |L| \le r-1$, we establish the upper bound $\left(1-\frac{1}{3r}\right) \prod_{\ell \in L}\frac{n-\ell}{r- \ell}$ for large $n$, which improves the bound provided by the celebrated Deza--Erdős--Frankl Theorem by a factor of $1-\frac{1}{3r}$. In the special case where $L = \{t, t+1, \ldots, r-1\}$, we derive the tight upper bound for large $n$ and establish a corresponding stability result. This is an extension of the seminal Erdős--Ko--Rado Theorem on $t$-intersecting systems to the generalized Turán setting. Our proof for the Deza--Erdős--Frankl part involves an interesting combination of the $Δ$-system method and Turán's theorem. Meanwhile, for the Erdős--Ko--Rado part, we employ the stability method, which relies on a theorem of Frankl regarding $t$-intersecting systems. |
| title | A generalized Turán extension of the Deza--Erdős--Frankl Theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2404.02762 |