Sunflowers and L-intersecting families 6 1 0 2 Ga´bor Hegedu˝s n O´buda University a J 9 October 11, 2016 1 ] O Abstract C h. Letf(k,r,s) standfortheleast numbersothatif isan arbitrary F t k-uniform, L-intersecting set system, where L = s, and has more a | | F m than f(k,r,s) elements, then contains a sunflower with r petals. F [ We give an upper bound for f(k,3,s). Letg(k,r,ℓ)betheleastnumbersothatanyk-uniform,ℓ-intersecting 1 v set system of more than g(k,r,ℓ) sets contains a sunflower with r 7 petals. 9 We give also an upper bound for g(k,r,ℓ). 8 4 0 . Keywords. ∆-system, L-intersecting families, extremal set theory 1 0 6 1 1 Introduction : v i X Let [n] stand for the set 1,2,...,n . We denote the family of all subsets of r [n] by 2[n]. { } a Let X be a fixed subset of [n]. For an integer 0 k n we denote by ≤ ≤ X the family of all k element subsets of X. k (cid:0) (cid:1)We call a family of subsets of [n] k-uniform, if F = k for each F . F | | ∈ F A family = F ,...,F of subsets of [n] is a sunflower (or ∆-system) 1 m F { } with m petals if m F F = F i j t ∩ t\=1 for each 1 i,j m. ≤ ≤ 1 The intersection of the members of a sunflower form its kernel. Clearly a a family of disjoint sets is a sunflower with empty kernel. Erd˝os and Rado gave an upper bound for the size of a k-uniform family without a sunflower with r petals in [6]. Theorem 1.1 (Sunflowertheorem) If is a k-uniform setsystem with more F than k 1 − t k!(r 1)k(1 ) − − (t+1)!(r 1)t Xt=1 − members, then contains a sunflower with r petals. F Kostochka improved this upper bound in [9]. Theorem 1.2 Let r > 2 and α > 1 be fixed integers. Let k be an arbitrary integer. Then there exists a constant D(r,α) such that if is a k-uniform F set system with more than (logloglogk)2 k D(r,α)k! αloglogk (cid:16) (cid:17) members, then contains a sunflower with r petals. F Erd˝os and Rado gave in [6] a construction of a k-uniform set system with (r 1)k members such that does not contain any sunflower with r petals. − F LaterAbbott, HansonandSauerimprovedthisconstructionin[1]andproved the following result. Theorem 1.3 There exists a c > 0 positive constant and a k-uniform set system such that F > 2 10k/2 clogk − |F| · and does not contain any sunflower with 3 petals. F Erd˝os and Rado conjectured also the following statement in [6]. Conjecture 1 For each r, there exists a constant C such that if is a r F k-uniform set system with more than Ck r members, then contains a sunflower with r petals. F 2 Erd˝os has offered 1000 dollars for the proof or disproof of this conjecture for r = 3 (see [4]). We prove here Conjecture 1 in the case of some special L-intersecting and ℓ-intersecting families. Afamily isℓ-intersecting, if F F ℓ whenever F,F . Specially, ′ ′ F | ∩ | ≥ ∈ F is an intersecting family, if F F = whenever F,F . ′ ′ F ∩ 6 ∅ ∈ F Erd˝os, Ko and Rado proved the following well-known result in [5]: Theorem 1.4 Let n,k,t be integers with 0 < t < k < n . Suppose is a F t-intersecting, k-uniform family of subsets of [n]. Then for n > n (k,t), 0 n t − . |F| ≤ (cid:18)k t(cid:19) − Further, = n t if and only if for some T [n] we have − |F| k t ∈ t (cid:0) − (cid:1) (cid:0) (cid:1) [n] = F : T F . F { ∈ (cid:18) k (cid:19) ⊆ } Let L be a set of nonnegative integers. A family is L-intersecting, if F E F L for every pair E,F of distinct members of . In this terminology | ∩ | ∈ F a k-uniform set system is a t-intersecting family iff it is an L-intersecting F family, where L = t,t+1,...,k 1 . { − } The following result gives a remarkable upper bound for the size of a k-uniform L-intersecting family (see [11]). Theorem 1.5 (Ray-Chaudhuri–Wilson) Let 0 < s k n be positive ≤ ≤ integers. Let L be a set of s nonnegative integers and an L-intersecting, F k-uniform family of subsets of [n]. Then n . |F| ≤ (cid:18)s(cid:19) Deza proved the following result in [3]. Theorem 1.6 (Deza) Let λ > 0 be a positive integer. Let L := λ . If is { } F an L-intersecting, k-uniform family of subsets of [n], then either k2 k +1 |F| ≤ − or is a sunflower, i.e. all the pairwise intersections are the same set with F λ elements. 3 We generalize Theorem 1.6 for L-intersecting families in the following. Theorem 1.7 Let be a family of subsets of [n] such that does not F F contain any sunflowers with three petals. Let L = ℓ < ... < ℓ be a set 1 s { } of s non-negative integers. Suppose that is a k-uniform, L-intersecting F family. Then (k2 k +2)8(s−1)2(1+√55)k(s−1). |F| ≤ − Next we improve Theorem 1.1 in the case of ℓ-intersecting families. Theorem 1.8 Let r > 2 and α > 1 be fixed integers. Let be an ℓ- F intersecting, k-uniform family of subsets of [n] such that does not contain F any sunflowers with r petals. Then there exists a constant D(r,α) such that k (logloglog(k ℓ))2 k ℓ D(r,α) (k ℓ)! − − . |F| ≤ (cid:18)ℓ(cid:19) − αloglog(k ℓ) (cid:16) (cid:17) − Corollary 1.9 Let r > 2, k > 1 be fixed integers. Let ℓ := k k . Let ⌈ − logk⌉ be an ℓ-intersecting, k-uniform family of subsets of [n] such that does F F not contain any sunflowers with r petals. Then there exists a constant D(r) such that D(r)4k. |F| ≤ We present our proofs in Section 2. We give some concluding remarks in Section 3. 2 Proofs We start our proof with an elementary fact. Lemma 2.1 Let 0 r n be integers. Then ≤ ≤ n n 1 − (cid:18)r(cid:19) ≤ (cid:18)r +1(cid:19) if and only if r2 +(1 3n)r+n2 2n 0. − − ≥ 4 Corollary 2.2 Let 0 r n be integers. If 0 r 3n−1−√5(n+1), then ≤ ≤ ≤ ≤ 2 n n 1 − (cid:18)r(cid:19) ≤ (cid:18)r +1(cid:19) We use the following easy Lemma in the proof of our main results. Lemma 2.3 Let 0 ℓ k 1 be integers. Then ≤ ≤ − 2k −ℓ 8 2(1+√55)k. (cid:18) ℓ+1 (cid:19) ≤ · Proof. First suppose that √5 2√5 ℓ (1 )k (1+ ) . ≤ ⌈ − 5 − 5 ⌉ Then 2k ℓ 2k (1 √5)k (1+ 2√5) − −⌈ − 5 − 5 ⌉ (cid:18) ℓ+1 (cid:19) ≤ (cid:18) (2 √5)k (1+ 2√5) (cid:19) ≤ ⌈ − 5 − 5 ⌉ 22k−⌈(1−√55)k−(1+2√55)⌉ 8 2(1+√55)k. ≤ ≤ · The first inequality follows easily from Corollary 2.2. Namely if √5 2√5 ℓ (1 )k (1+ ) , ≤ ⌈ − 5 − 5 ⌉ then 3 √5 1+√5 ℓ+1 − (2k ℓ) ≤ ⌈ 2 − − 2 ⌉ and we can apply Corollary 2.2 with the choices r := ℓ+1 and n := 2k ℓ. − 5 Secondly, suppose that √5 2√5 ℓ > (1 )k (1+ ) . ⌈ − 5 − 5 ⌉ Then √5 2√5 √5 2k ℓ 2k (1 )k (1+ ) 2+(1+ )k , − ≤ −⌈ − 5 − 5 ⌉ ≤ ⌈ 5 ⌉ hence 2k ℓ 2k (1 √5)k (1+ 2√5) − −⌈ − 5 − 5 ⌉ (cid:18) ℓ+1 (cid:19) ≤ (cid:18) ℓ+1 (cid:19) ≤ 22k−⌈(1−√55)k−(1+2√55)⌉ 8 2(1+√55)k. ≤ ≤ · The soul of the proof of our main result is the following Lemma. Lemma 2.4 Let be an ℓ-intersecting, k-uniform family of subsets of [n] F such that does not contain any sunflowers with three petals. Suppose that F there exist F ,F distinct subsets such that F F = ℓ. Let M := 1 2 1 2 ∈ F | ∩ | F F . Then 1 2 ∪ F M > ℓ | ∩ | for each F . ∈ F Proof. Clearly F F F M for each F , hence 1 ∩ ⊆ ∩ ∈ F F M ℓ | ∩ | ≥ for each F . ∈ F We prove by an indirect argument. Suppose that there exists an F ∈ F such that F M = ℓ. Clearly F = F and F = F . Let G := F F . Then 1 2 1 2 | ∩ | 6 6 ∩ G = ℓ by assumption. It follows from F F F M and ℓ F F 1 1 | | ∩ ⊆ ∩ ≤ | ∩ | ≤ F M = ℓ that F F = F M. Similarly F F = F M. Consequently 1 2 | ∩ | ∩ ∩ ∩ ∩ F F = F F . We get that F F = F G = F F . Since ℓ = F F = 1 2 2 1 1 ∩ ∩ ∩ ∩ ∩ | ∩ | 6 F G G = ℓ and F G G, hence G = F G = F F = F F , so 2 1 | ∩ | ≤ | | ∩ ⊆ ∩ ∩ ∩ F,F ,F is a sunflower with three petals, a contradiction. 1 2 { } Proof of Theorem 1.7: We apply induction on L = s. If s = 1, then our result follows from | | Theorem 1.6. Suppose that Theorem 1.7 is true for s 1 and now we attack the case − L = s. | | If F F = ℓ holds for each distinct F,F , then is actually an ′ 1 ′ | ∩ | 6 ∈ F F L := ℓ ,...,ℓ -intersecting system and the much stronger upper bound ′ 2 s { } (k2 k +2)8(s−2)2(1+√55)k(s−2). |F| ≤ − follows from the induction. Hence we cansuppose that there exist F ,F such that F F = ℓ . 1 2 1 2 1 ∈ F | ∩ | Let M := F F . Clearly is an ℓ -intersecting family. It follows from 1 2 1 ∪ F Lemma 2.4 that F M > ℓ (1) 1 | ∩ | for each F . Clearly M = 2k ℓ . 1 ∈ F | | − Let T be a fixed subset of M such that T = ℓ +1. Define the family 1 | | (T) := F : T M F . F { ∈ F ⊆ ∩ } Let L := ℓ ,...,ℓ . Clearly L = s 1. Then (T) is an L-intersecting, ′ 2 s ′ ′ { } | | − F k-uniform family, because is an L-intersecting family and T F for each F ⊆ F (T). The following Proposition follows easily from (1). ∈ F Proposition 2.5 = (T). F F [ T M,T =ℓ1+1 ⊆ | | Let T be a fixed, but arbitrary subset of M such that T = ℓ + 1. 1 | | Consider the set system (T) := F T : F (T) . G { \ ∈ F } 7 Clearly (T) = (T) . Let L := ℓ ℓ 1,...,ℓ ℓ 1 . Here 2 1 s 1 |G | |F | { − − − − } L = s 1. Since (T) is an L-intersecting, k-uniform family, thus (T) is ′ | | − F G an L-intersecting, (k ℓ 1)-uniform family. It follows from the inductional 1 − − hypothesis that (T) = (T) (k2 k +2)8(s−2)2(1+√55)k(s−2). |F | |G | ≤ − Finally Proposition 2.5 implies that (T) 2k −ℓ1 (k2 k +2)8(s−2)2(1+√55)k(s−2). |F| ≤ |F | ≤ (cid:18) ℓ +1 (cid:19) − X 1 T M,T =ℓ1+1 ⊆ | | But 2k ℓ − 8 2(1+√55)k (cid:18) ℓ+1 (cid:19) ≤ · by Lemma 2.3, hence (k2 k +2)8(s−2)2(1+√55)k(s−2) 8 2(1+√55)k = |F| ≤ − · · = (k2 k +2)8(s−1)2(1+√55)k(s−1), − which was to be proved. Proof of Theorem 1.8: Let F be a fixed subset. Clearly F F ℓ for each F , since 0 0 ∈ F | ∩ | ≥ ∈ F is an ℓ-intersecting family. F Let T be a fixed, but arbitrary subset of F such that T = ℓ. Consider 0 | | the set system (T) := F : T F . F { ∈ F ⊆ } It is easy to see the following Proposition. Proposition 2.6 = (T). F F [ T F0,T =ℓ ⊆ | | Define the set system (T) := F T : F (T) . G { \ ∈ F } 8 Obviously (T) = (T) and (T) is a (k ℓ)-uniform family. |G | |F | G − It is easy to see that (T) does not contain any sunflowers with r petals, G because does not contain any sunflowers with r petals. Hence for each α F (logloglog(k ℓ))2 k ℓ (T) = (T) D(r,α)(k ℓ)! − − |F | |G | ≤ − αloglog(k ℓ) (cid:16) (cid:17) − by Theorem 1.2. Finally Proposition 2.5 implies that (T) |F| ≤ |F | ≤ X T F0,T =ℓ ⊆ | | k (logloglog(k ℓ))2 k ℓ D(r,α) (k ℓ)! − − . ≤ (cid:18)ℓ(cid:19) − αloglog(k ℓ) (cid:16) (cid:17) − Proof of Theorem 1.9: If ℓ := k k , then it is easy to verify that ⌈ − logk⌉ k D(r) (k ℓ)! D(r)4k. (cid:18)ℓ(cid:19) − ≤ 3 Remarks Define f(k,r,s) as the least number so that if is an arbitrary k-uniform, F L-intersecting family, where L = s, then > f(k,r,s) implies that | | |F| F contains a sunflower with r petals. In Theorem 1.7 we proved the following recursion for f(k,r,s): 2k ℓ f(k,3,s) max − f(k 1,3,s 1). ≤ 0 ℓ k 1(cid:18) ℓ+1 (cid:19) − − ≤ ≤ − Our upper bound in Theorem 1.7 was a clear consequence of this recur- sion. It would be very interesting to give a similar recursion for f(k,r,s) for r > 3. On the other hand, it is easy to prove the following Proposition from Theorem 1.3. Proposition 3.1 Let 1 s < k be integers. Then there exists a c > 0 ≤ positive constant such that f(k,3,s) > 2 10s/2 clogs − · 9 References [1] H. L. Abbott, D. Hanson and N. Sauer, 1972. Intersection theorems for systems of sets. Journal of Combinatorial Theory, Series A, 12(3), (1972) 381-389. [2] L. Babai and P. Frankl, Linear algebra methods in combinatorics, September 1992. [3] M. Deza, Solution d’un probl`eme de Erd¨os-Lova´sz. Journal of Com- binatorial Theory, Series B, 16(2), (1974)166-167. [4] P. Erd˝os, Problems and results on finite and infinite combinatorial analysis, in: Infinite and finite sets (Colloq. Keszthely 1973), Vol. I, Colloq. Math. Soc. J. Bolyai, 10, North Holland, Amsterdam, 1975, 403-424. [5] P. Erd˝os, C. Ko and R. Rado, Intersection theorems for systems of finite sets. The Quarterly Journal of Mathematics, 12(1), (1961) 313- 320. [6] P. Erd˝os and R. Rado, Intersection theorems for systems of sets. Jour- nal of the London Mathematical Society, 1(1), (1960) 85-90. [7] P. Erd˝os, and E. Szemer´edi, Combinatorial properties of systems of sets.Journal of Combinatorial Theory, Series A,24(3), (1978)pp.308- 313. [8] P. Frankl and Z. Fu¨redi, Families of finite sets with missing inter- sections. In Colloquia Mathematica Societatis Janos Bolyai (Vol. 37) (1981) 305-320 [9] A. V. Kostochka, An intersection theorem for systems of sets. Random Structures and Algorithms, 9(1-2), (1996) 213-221. [10] S. Jukna, Extremal combinatorics: with applications in computer sci- ence. Springer Science and Business Media. (2011) [11] D. K. Ray-Chaudhuri and R. M. Wilson, On t-designs. Osaka Journal of Mathematics, 12(3),(1975) 737-744. 10