Exact results and the structure of extremal families for the Duke--Erdős forbidden sunflower problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915630774484992 |
|---|---|
| author | Kupavskii, Andrey Noskov, Fedor |
| author_facet | Kupavskii, Andrey Noskov, Fedor |
| contents | In 1977, Duke and Erdős asked the following general question: What is the largest size of a family $\mathtt{F} \subset \binom{[n]}{k}$ that does not contain a sunflower with $s$ petals and core of size exactly $t - 1$? This problem is closely related to the famous Erdős--Rado sunflower problem of determining the size $ϕ(s,t)$ of the largest $t$-uniform family with no $s$-sunflower. In this paper, we answer this question exactly for $t=2$, odd $s$ and $k\ge 5$, provided $n$ is large enough. Previously, the only know exact extremal result on this problem was due to Chung and Frankl from 1987.
One of the important ingredients for the proof that we obtained is a stability result for the Duke--Erdős problem, which was previously not known, mostly due to our lack of understanding of the behaviour of $ϕ(s,t)$.
For large $k$ and $n$ we in fact manage to reduce the Duke--Erdős problem to an Erdős--Rado-like problem which depends on $t$ and $s$ only. In particular, we get a good understanding of the structure of extremal families for the Duke--Erdős problem in terms of the Erdős--Rado problem. Previously, a much looser variant of this connection (only in terms of the sizes, rather than the structure, of respective extremal families) was established in a seminal work of Frankl and Füredi from 1987. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_17142 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact results and the structure of extremal families for the Duke--Erdős forbidden sunflower problem Kupavskii, Andrey Noskov, Fedor Combinatorics In 1977, Duke and Erdős asked the following general question: What is the largest size of a family $\mathtt{F} \subset \binom{[n]}{k}$ that does not contain a sunflower with $s$ petals and core of size exactly $t - 1$? This problem is closely related to the famous Erdős--Rado sunflower problem of determining the size $ϕ(s,t)$ of the largest $t$-uniform family with no $s$-sunflower. In this paper, we answer this question exactly for $t=2$, odd $s$ and $k\ge 5$, provided $n$ is large enough. Previously, the only know exact extremal result on this problem was due to Chung and Frankl from 1987. One of the important ingredients for the proof that we obtained is a stability result for the Duke--Erdős problem, which was previously not known, mostly due to our lack of understanding of the behaviour of $ϕ(s,t)$. For large $k$ and $n$ we in fact manage to reduce the Duke--Erdős problem to an Erdős--Rado-like problem which depends on $t$ and $s$ only. In particular, we get a good understanding of the structure of extremal families for the Duke--Erdős problem in terms of the Erdős--Rado problem. Previously, a much looser variant of this connection (only in terms of the sizes, rather than the structure, of respective extremal families) was established in a seminal work of Frankl and Füredi from 1987. |
| title | Exact results and the structure of extremal families for the Duke--Erdős forbidden sunflower problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.17142 |