Proof of Frankl's conjecture on cross-intersecting families
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_ | 1866908358612615168 |
|---|---|
| author | Wu, Yongjiang Feng, Lihua Li, Yongtao |
| author_facet | Wu, Yongjiang Feng, Lihua Li, Yongtao |
| contents | Two families $\mathcal{F}$ and $\mathcal{G}$ are called cross-intersecting if for every $F\in \mathcal{F}$ and $G\in \mathcal{G}$, the intersection $F\cap G$ is non-empty. For any positive integers $n$ and $k$, let $\binom{[n]}{k}$ denote the family of all $k$-element subsets of $\{1,2,\ldots,n\}$. Let $t, s, k, n$ be non-negative integers with $k \geq s+1$ and $n \geq 2 k+t$. In 2016, Frankl proved that if $\mathcal{F} \subseteq\binom{[n]}{k+t}$ and $\mathcal{G} \subseteq\binom{[n]}{k}$ are cross-intersecting families, and $\mathcal{F}$ is $(t+1)$-intersecting and $|\mathcal{F}| \geq 1$, then $|\mathcal{F}|+|\mathcal{G}| \leq\binom{n}{k}-\binom{n-k-t}{k}+1$. Furthermore, Frankl conjectured that under an additional condition $\binom{[k+t+s]} {k+t}\subseteq\mathcal{F}$, the following inequality holds: $$ |\mathcal{F}|+|\mathcal{G}| \leq\binom{k+t+s}{k+t}+\binom{n}{k}-\sum_{i=0}^s\binom{k+t+s}{i}\binom{n-k-t-s}{k-i}. $$ In this paper, we prove this conjecture. The key ingredient is to establish a theorem for cross-intersecting families with a restricted universe. Moreover, we derive an analogous result for this conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09490 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Proof of Frankl's conjecture on cross-intersecting families Wu, Yongjiang Feng, Lihua Li, Yongtao Combinatorics Two families $\mathcal{F}$ and $\mathcal{G}$ are called cross-intersecting if for every $F\in \mathcal{F}$ and $G\in \mathcal{G}$, the intersection $F\cap G$ is non-empty. For any positive integers $n$ and $k$, let $\binom{[n]}{k}$ denote the family of all $k$-element subsets of $\{1,2,\ldots,n\}$. Let $t, s, k, n$ be non-negative integers with $k \geq s+1$ and $n \geq 2 k+t$. In 2016, Frankl proved that if $\mathcal{F} \subseteq\binom{[n]}{k+t}$ and $\mathcal{G} \subseteq\binom{[n]}{k}$ are cross-intersecting families, and $\mathcal{F}$ is $(t+1)$-intersecting and $|\mathcal{F}| \geq 1$, then $|\mathcal{F}|+|\mathcal{G}| \leq\binom{n}{k}-\binom{n-k-t}{k}+1$. Furthermore, Frankl conjectured that under an additional condition $\binom{[k+t+s]} {k+t}\subseteq\mathcal{F}$, the following inequality holds: $$ |\mathcal{F}|+|\mathcal{G}| \leq\binom{k+t+s}{k+t}+\binom{n}{k}-\sum_{i=0}^s\binom{k+t+s}{i}\binom{n-k-t-s}{k-i}. $$ In this paper, we prove this conjecture. The key ingredient is to establish a theorem for cross-intersecting families with a restricted universe. Moreover, we derive an analogous result for this conjecture. |
| title | Proof of Frankl's conjecture on cross-intersecting families |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.09490 |