Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem

Source abstract

Abstract We call a family of s $s$ s sets { F 1 , … , F s } $\{F_1, \ldots , F_s\}$ StartSet upper F 1 comma ellipsis comma upper F Subscript s Baseline EndSet a sunflower with s $s$ s petals if, for any distinct i , j ∈ [ s ] $i, j \in [s]$ i comma j element of left bracket s right bracket , one has F i ∩ F j = ∩ u = 1 s F u $F_i \cap F_j = \cap _{u = 1}^s F_u$ upper F Subscript i Baseline intersection upper F Subscript j Baseline equals intersection Underscript u equals 1 Overscript s Endscripts upper F Subscript u . The set C = ∩ u = 1 s F u $C = \cap _{u = 1}^s F_u$ upper C equals intersection Underscript u equals 1 Overscript s Endscripts upper F Subscript u is called the core of the sunflower. It is a classical result of Erdős and Rado that there is a function ϕ ( s , k ) $\phi (s,k)$ phi left parenthesis s comma k right parenthesis such that any family of k $k$ k -element sets contains a sunflower with s $s$ s petals. In 1977, Duke and Erdős asked for the size of the largest family F ⊂ ( [ n ] k ) $\mathcal {F}\subset {[n]\choose k}$ script upper F subset of StartBinomialOrMatrix left bracket n right bracket Choose k EndBinomialOrMatrix that contains no sunflower with s $s$ s petals and core of size t − 1 $t-1$ t minus 1 . In 1987, Frankl and Füredi asymptotically solved this problem for k ⩾ 2 t + 1 $k\geqslant 2t+1$ k greater than or slanted equals 2 t plus 1 and n > n 0 ( s , k ) $n>n_0(s,k)$ n greater than n 0 left parenthesis s comma k right parenthesis . Their paper is one of the pinnacles of the so-called Delta-system method. In this paper, we extend the result of Frankl and Füredi to a much broader range of parameters: n > p o l y ( s , t ) k $n>poly(s,t) k$ n greater than p o l y left parenthesis s comma t right parenthesis k , when additionally k > p o l y ( s , t ) log ⁡ n $k>poly(s,t)\log n$ k greater than p o l y left parenthesis s comma t right parenthesis log n or n > n 0 ( s , t ) $n>n_0(s,t)$ n greater than n 0 left parenthesis s comma t right parenthesis . We also extend this result to other domains, such as [ n ] k $[n]^k$ left bracket n right bracket Superscript k and ( n k / w ) w ${n\choose k/w}^w$ StartBinomialOrMatrix n Choose k divided by w EndBinomialOrMatrix Superscript w and obtain even stronger and more general results for forbidden sunflowers with core at most t − 1 $t-1$ t minus 1 (including results for families of permutations and subfamilies of the k $k$ k -th layer in a simplicial complex). The methods of the paper, among other things, combine the spread approximation approach, introduced by Zakharov and the first author, with the Delta-system approach of Frankl and Füredi and the hypercontractivity for global functions approach, developed by Keller, Lifshitz, and coauthors. Previous works in extremal set theory relied on at most one of these approaches. Creating such a unified view was one of the goals for the paper.