Exact results and the structure of extremal families for the Duke–Erdős forbidden sunflower problem

Andrey Kupavskii, Fedor Noskov · 2025

Read Exact results and the structure of extremal families for the Duke–Erdős forbidden sunflower problem by Andrey Kupavskii, Fedor Noskov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-17142.txt.

Introduction

Andrey Kupavskii and Fedor Noskov settle a question in extremal combinatorics posed by Duke and Erdős in 1977. The question concerns families of sets that avoid a sunflower, a pattern where several sets share exactly the same common core. It asks how large such a family can be when the forbidden sunflower has a specified number of petals and a core one element short of the set size.

The authors answer exactly for core size one short of two, odd petal counts, and sets of size at least five, provided the ground set is large. Their proof rests on a new stability result describing the shape of near-extremal families, and it reduces the problem to the classic Erdős–Rado sunflower setting. The only earlier exact result dated to 1987, so the paper closes a long-standing gap.

Catalog record

CREATORAndrey Kupavskii, Fedor Noskov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-17142

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact results and the structure of extremal families for the Duke–Erdős forbidden sunflower problem Andrey Kupavskii, Fedor Noskov Abstract In 1977, Duke and Erdős asked the following general question: What is the largest size of a family ℱ ⊂ ( [ n ] k ) \mathcal{F}\subset\binom{[n]}{k} that does not contain a sunflower with s s petals and core of size exactly t − 1 t-1 ? This problem is closely related to the famous Erdős–Rado sunflower problem of determining the size ϕ ⁡ ( s , t ) \phi(s,t) of the largest t t -uniform family with no s s -sunflower. In this paper, we answer this question exactly for t = 2 t=2 , odd s s and k ⩾ 5 k\geqslant 5 , provided n 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 ) \phi(s,t) . For large k k and n n we in fact manage to reduce the Duke–Erdős problem to an Erdős–Rado-like problem which depends on t t and s 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. 1 Introduction Let [n] stand for the standard set \{1,\ldots,n\} and, given a set X and an integer k , we denote by 2^{X} ( \binom{X}{k} ) the family of all subsets of X (all subsets of X of size k ). A family of s sets \{F_{1},\ldots,F_{s}\} is a \Delta(s) -system or a sunflower with s petals if, for any distinct i,j\in[s] , one has F_{i}\cap F_{j}=\cap_{u=1}^{s}F_{u} . The set C=\cap_{u=1}^{s}F_{u} is called the core or kernel of the sunflower. One of the most famous problems in Extremal Set Theory is the Erdős–Rado [ 19 ] sunflower problem. Probem 1 (Erdős and Rado, 1960) . What is the maximum size \phi(s,t) of a family \mathcal{T} that consists of sets of size t and does not contain a sunflower with s petals? Show that \phi(s,t)\leqslant(Cs)^{t} for some absolute constant C. It is one of Erdős’ 1000 $ problems. Erdős and Rado proved the bounds bounds (s-1)^{t}\leqslant\phi(s,t)\leqslant(t-1)!(s-1)^{t} . Over a long period of time, the best known upper bound on \phi(s,t) was of the form t^{t(1+o(1))} , where the o(1) term depends on s , until the breakthrough result of Alweiss, Lovett, Wu and Zhang [ 5 ] . After a series of further improvements in a series of papers and blogposts [ 46 , 51 , 6 , 32 , 50 , 47 ] , the bound is \phi(s,t)\leqslant(Cs\ln t)^{t} for some absolute constant C . The exact value of \phi(s,t) is unknown for most non-trivial cases, with a notable exception of the case \phi(s,2) , where an exact result was obtained by Abbott, Hanson and Sauer [ 1 ] . Their result is stated in Theorem 3.2 below. In 1977, Duke and Erdős [ 16 ] asked a closely related question. Probem 2 (Duke and Erdős, 1977) . Suppose that a family \mathcal{F}\subset\binom{[n]}{k} does not contain a sunflower with s petals and core of size exactly t-1 . What is the maximum size of \mathcal{F} ? The cases t\in\{2,3\} , k=3 and arbitrary s were studied by Duke and Erdős [ 16 ] , Frankl [ 28 ] , Chung [ 14 ] and Chung and Frankl [ 13 ] . In the last paper, Chung and Frankl managed to determine the exact maximum size of a family of 3 -element sets ( 3 -sets) that avoids a sunflower with s petals and core of size 1 and large n . To the best of our knowledge, so far this was the only known exact result for this problem for s,t\geqslant 3 . The first main result of this paper is an exact result for families of larger uniformity that avoid sunflowers with core of size 1 , which extends the result of Chung and Frankl [ 13 ] . Theorem 1.1 . Let s be odd and k\geqslant 5 and n\geqslant n_{0}(s,k) . Let \mathcal{F}\subset\binom{[n]}{k} be an extremal family that does not contain a sunflower with s petals and the core of size 1 . Then, there exists a graph G=K_{1}\sqcup K_{2} consisting of two disjoint cliques K_{1},K_{2} of size s , such that \displaystyle\mathcal{F}=\bigg\{F\in\binom{[n]}{k}\,:\, \displaystyle|F\cap V(G)|\geqslant 2 \displaystyle\text{ and }\forall i\in\{1,2\}\text{ we have }|F\cap V(K_{i})|\neq 1\bigg\}. Here the graph G is coming from the main result of [ 1 ] . It is an extremal 2 -uniform family without a sunflower with s petals (i.e., a graph without a matching of size s or a vertex of degree s ). It is unique up to isomorphism. If s is even and larger than 2 , then an extremal example in the Erdős sunflower problem for t=2 is not unique, see Theorem 3.2 below. This makes it technically much more demanding to state and prove its analogue for even s. One of the important tools in this area and for this paper is the Delta-system method (see the recent survey of the first author [ 43 ] ). It was greatly developed by Frankl and Füredi in late 70s and 80s [ 22 , 22 ] . Using the delta-system method, Frankl and Füredi in their seminal paper [ 23 ] derived the following asymptotically tight bound on a sunflower-free family |\mathcal{F}| when s,k,t are fixed and n tends to infinity. Theorem 1.2 (Frankl and Füredi, 1987) . Let s,k,t be integers, k\geqslant 2t+1 . Suppose that s,k,t are fixed and n\to\infty . Then \displaystyle|\mathcal{F}|\leqslant(\phi(s,t)+o(1))\binom{n}{k-t}, where \phi(s,t) is the maximal size of a t -uniform family \mathcal{T} that does not contain a sunflower with s petals (and arbitrary core). One of the major complications for the study of this problem is that we know little about the behavior of the function \phi(s,t) . However, Frankl and Füredi managed to prove their Theorem 1.2 even without much understanding of the behaviour of this function. Recently, the case k=4 was studied by Bucić et al. in [ 10 ] in the regime when we allow s to grow with n . Later, Bradač, Bucić and Sudakov [ 8 ] generalized the previous result and proved that an extremal family in Problem 2 has size O_{k}(n^{k-t}s^{t}) when n tends to infinity, s grows arbitrarily with n , and k is fixed. The complementary scenario (when k can grow linearly with n , and s,t are small) was studied by the authors in [ 40 ] , where the authors of this paper managed to determine the solution to the problem up to a mutliplicative factor of (1+o(1)) . Problem 2 generalizes two famous problems proposed by Erdős and coauthors, namely Erdős–Sós forbidden

Read the complete text