New bounds on families without large sunflowers

Peter Frankl ; Jian Wang¹

^[e-mail]

The electronic journal of combinatorics, Tome 32 (2025) no. 2

Résumé

Distinct sets $F_1,F_2,\ldots,F_s$ are said to form a {\it sunflower} of size $s$ and center of size $i$ if there is an $i$-element set $C$ satisfying $F_a\cap F_b=C$ for all $1\leq a<b\leq s$. The present paper introduces the function $m_k(r_0,r_1,\ldots,r_{k-1})$, the maximum size of a collection of distinct $k$-sets in which for all $0\leq i<k$ the maximum size of a sunflower with center of size $i$ is at most $r_i$. One of the favorite open problems of Paul Erdős is whether $m_k(r,\ldots,r)<c(r)^k$ holds with some constant $c(r)$ independent of $k$. We present various inequalities and some exact results concerning $m_k(r_0,r_1,\ldots,r_{k-1})$. In particular we show that for $k$ fixed and $r_0,\ldots,r_{k-1}$ simultaneously tending to infinity $m_k(r_0,\ldots,r_{k-1})=(1+o(1))r_0\ldots r_{k-1}$.

Détail

DOI : 10.37236/13277

Classification : 05D05
Mots-clés : Erdős-Ko-Rado theorem, pseudo sunflower