2018/09/27 by Junichiro Fukuyama, Fukuyama, Junichiro
Mathematics · #05D05: Extremal Set Theory #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1809.10318
25 pages. The 2nd version contained a flaw in the induction step of the main proof. The current one fixes it also proving a slightly stronger claim than the existence of the 3-sunflower: if the Γ-condition is met, the family F includes 3 mutually disjoint sets
arxiv created 2021/12/23 · arxiv updated 2021/12/28
A sunflower with k petals, or k-sunflower, is a family of k sets every two of which have a common intersection. Known since 1960, the sunflower conjecture states that a family \mathcal F of sets each of cardinality m includes a k-sunflower if |\mathcal F| ≥ ckm for some ck ∈ \mathbb R>0 depending only on k. The case k=3 of the conjecture was especially emphasized by Erdös, for which Kostochka's bound c m! ( (log log log m)/(log log m) )m on |\mathcal F| without a 3-sunflower had been the best-known since 1997 until the recent development to update it to c log m. This paper proves with an entirely different combinatorial approach that \mathcal F includes three mutually disjoint sets if it satisfies the Γ( c m(1)/(2)+ δ )-condition for any given δ∈ (0, 1/2). Here c is a constant depending only on δ, and the Γ-condition refers to | \ U~:~ U ∈ \mathcal F \textrm~and~ S ⊂ U \| < ( c m(1)/(2)+ δ )-|S| |\mathcal F|, for every nonempty set S. This poses an alternative proof of the 3-sunflower bound ( c m(1)/(2)+ δ )m.