Multicolour Sunflowers. (22nd April 2018)

• Record Type: Journal Article
• Authors: MUBAYI, DHRUV; WANG, LUJIA
• Is Part Of: Combinatorics, probability and computing. Volume 27:Number 6(2018)
• Page Start: 974
• Page End: 987
• Publication Date: 2018-04-22
• Subjects: Primary 05D05, -- Secondary 05D40; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000160
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : A sunflower is a collection of distinct sets such that the intersection of any two of them is the same as the common intersection C of all of them, and | C | is smaller than each of the sets. A longstanding conjecture due to Erdős and Szemerédi (solved recently in [7, 9]; see also [22]) was that the maximum size of a family of subsets of [ n ] that contains no sunflower of fixed size k > 2 is exponentially smaller than 2 n as n → ∞. We consider the problems of determining the maximum sum and product of k families of subsets of [ n ] that contain no sunflower of size k with one set from each family. For the sum, we prove that the maximum is $$(k-1)2^n+1+\sum_{s=0}^{k-2}\binom{n}{s}$$ for all n ⩾ k ⩾ 3, and for the k = 3 case of the product, we prove that the maximum is $$\biggl(\ffrac{1}{8}+o(1)\biggr)2^{3n}.$$ We conjecture that for all fixed k ⩾ 3, the maximum product is (1/8+ o (1))2 kn .