Weighted 3-wise 2-intersecting families

Peter Frankl CNRS, ER 175 Combinatoire, 2 Place Jussieu, 75005 Paris, France Peter111F@aol.com

Norihide Tokushige College of Education, Ryukyu University, Nishihara, Okinawa, 903-0213 Japan hide@edu.u-ryukyu.ac.jp

July 18, 2001

Abstract Let n and r be positive integers. Suppose that a family F ⊂ 2^{[n]} satisfies |F_{1} ∩ F_{2} ∩ F_{3}| ≥ 2 for all F_{1}, F_{2}, F_{3} ∈ F. We prove that if w < 0.5018 then ∑_{F ∈F} w^{|F |}(1 − w)^{n−|F |} ≤ w^{2}.

1 Introduction

Let n, r and t be positive integers. A family F of subsets of [n] = {1, 2, …, n} is called r-wise t-intersecting if |F_{1} ∩⋯∩F_{r}| ≥ t holds for all F_{1}, …, F_{r} ∈ F. For a real w ∈ (0, 1) let us define the weighted size W_{w}(F) of F by

W_{w}(F) := ∑_{F ∈F} w^{|F |}(1 − w)^{n−|F |}.

Note that W_{1/2}(F) = |F|/2^{n}. Further, define

f_{w,r,t}(n) := max{W_{w}(F) : F ⊂ 2^{[n]} is r-wise t-intersecting}.

Let us check

f_{w,r,t}(n) ≥ w^{t}.  (1)

Set F_{0} := {F ⊂ [n] : [t] ⊂ F }. Then F_{0} is r-wise t-intersecting for every r, and

W_{w}(F_{0}) = w^{t} ∑_{F ⊂[t+1,n]} w^{|F |}(1 − w)^{n−t−|F |}

= w^{t} ∑_{i=0}^{n−t} \binom{n − t}{i}w^{i}(1 − w)^{n−t−i} = w^{t}.

Problem 1 Does f_{w,r,t}(n) = w^{t} hold if w ≤ w(r, t) and t ≤ 2^{r} − r − 1?

For 1-intersecting families, the authors proved the following in [7].

Theorem 1 f_{w,r,1}(n) = w if w ≤ (r − 1)/r.

On the other hand, for all t ≥ 1 one has

lim_{n→∞} f_{w,r,t}(n) = 1 if w > (r − 1)/r.

To obtain an exact formula for f_{w,r,2}(n) seems to be much harder. In this paper, we shall prove

Theorem 2 f_{w,3,2}(n) = w^{2} if w < 0.5018.

This implies f_{w,r,2}(n) = w^{2} if r ≥ 3 and w < 0.5018, since w^{t} ≤ f_{w,r+1,t}(n) ≤ f_{w,r,t}(n). Using Theorem 2, the following variation of the Erdős–Ko–Rado theorem is deduced.

Theorem 3 Let F ⊂ \binom{[n]}{k} be a 3-wise 2-intersecting family with k/n <

0.501. Then |F| ≤ (1 + o(1))\binom{n−2}{k−2}.

A family F ⊂ 2^{[n]} is called a Sperner family if F ⊄ G holds for all distinct F, G ∈ F. The maximum size of 2-wise t-intersecting Sperner families was determined by Milner[17], it is given by the simply formula \binom{n}{⌈(n+t)/2⌉}. For 3-wise t-intersecting families, the situation becomes more complicated. For 3-wise 1-intersecting families, it was the subject of several papers of Frankl [3] and Gronau [9, 10, 11] and it is known that for n ≥ 54 the only optimal families are

\begin{matrix}F = \{F ∪ [n] : F ∈ \binom{[n−1]}{n/2}\} ∪ \{[n − 1]\} & n even, \\ F = \{F ∪ [n] : F ∈ \binom{[n−1]}{(n−1)/2}\} & n odd. \end{matrix}

This motivates the following conjecture.

Conjecture 1 Let F ⊂ 2^{[n]} be a 3-wise 2-intersecting Sperner family. Then,

|F| ≤ \{ \begin{matrix}\binom{n−2}{(n−2)/2} & if n even, \\ \binom{n−2}{(n−1)/2} + 2 & if n odd, \end{matrix}

holds for n ≥ n_{0}. The corresponding families are

\begin{matrix}F = \{F ∪ \{n − 1, n\} : F ∈ \binom{[n−2]}{(n−2)/2}\} & n even, \\ F = \{F ∪ \{n − 1, n\} : F ∈ \binom{[n−2]}{(n−1)/2}\} ∪ \{[n − 1]\} ∪ \{[n] − \{n − 1\}\} & n odd. \end{matrix}

Since F = \binom{[8]}{6} is 3-wise 2-intersecting Sperner and |F| = \binom{8}{6} > \binom{6}{3}, we need the condition n > n_{0} in the above conjecture.

As an application of Theorem 3, we prove the following weaker result, conjectured in [3].

Theorem 4 Let F ⊂ 2^{[n]} be a 3-wise 2-intersecting Sperner family. Then |F| ≤ (1 + o(1))\binom{n−2}{⌈(n−2)/2⌉}.

Using the same technique, we can remove the above o(1) term for 4-wise case as follows:

Theorem 5 Let F ⊂ 2^{[n]} be a 4-wise 2-intersecting Sperner family. Then |F| ≤ \binom{n−2}{⌈(n−2)/2⌉} holds for n > n_{0}.

Note that the same upper bound is valid for r-wise 2-intersecting Sperner families if r ≥ 4.

2 Tools

2.1 Shifting

For integers 1 ≤ i < j ≤ n and a family F ⊂ 2^{[n]}, define the (i, j)-shift S_{ij} as follows.

S_{ij}(F) := {S_{ij}(F) : F ∈ F},

where

S_{ij}(F) := \{ \begin{matrix}(F − \{j\}) ∪ \{i\} & if i ∉ F, j ∈ F, (F − \{j\}) ∪ \{i\} ∉ F, \\ F & otherwise. \end{matrix}

A family F ⊂ 2^{[n]} is called shifted if S_{ij}(F) = F for all 1 ≤ i < j ≤ n. We call F co-complex if G ⊃ F ∈ F implies G ∈ F. It is not difficult to check that f_{w,r,t}(n) (the maximal weighted size of r-wise t-intersecting families) is attained by a shifted co-complex. See [5] for details.

Let us introduce a partial order in 2^{[n]} by using shifting. Let A, B ⊂ [n]. Define A ≻ B if there exists A′ ⊂ [n] such that A ⊂ A′ and B is obtained by repeating a shifting to A′. The following fact is trivial but useful.

Fact 1 Let F ⊂ 2^{[n]} be a shifted co-complex. If A ∈ F and A ≻ B, then B ∈ F.

Let us see how to apply the above fact.

Fact 2 Let F ⊂ 2^{[n]} be a 3-wise 2-intersecting shifted co-complex. Set G_{0} := {1, 3, 4, 6, 7, …, 3i, 3i + 1, …} ∩ [n]. Then G_{0} ∉ F.

Proof. Set G_{1} := {1, 2, 4, 5, 7, …, 3i − 1, 3i + 1, …} ∩ [n], and G_{2} := {1, 2, 3, 5, 6, …, 3i − 1, 3i, …} ∩ [n]. Then, G_{0} ∩ G_{1} ∩ G_{2} = {1} and G_{0} ≻ G_{1} ≻ G_{2}. If G_{0} ∈ F then G_{1}, G_{2} ∈ F must hold by Fact 1. But this is impossible because F is 3-wise 2-intersecting.

In the same reason, an r-wise t-intersecting family can not contain the set [n] − {t, t + r, t + 2r, …}.

2.2 Random walk

Let w ∈ (0, 2/3) be a fixed real number, and let α ∈ (0, 1) be the root of the equation (1 − w)x^{3} − x + w = 0, more explicitly, α = \frac{1}{2}(\sqrt{\frac{1+3w}{1−w}} − 1). Consider the infinite random walk, starting from the origin, in which at each step we move one unit up with probability w or move one unit right with probability 1 − w. Then the probability that we ever hit the line y = 2x + s is given by α^{s}. (See [4] or [5] for details.)

Let F ∈ F ⊂ 2^{[n]}. We define the corresponding (finite) walk to F, denoted by walk(F), in the following way. If i ∈ F (resp. i ∉ F) then we move one unit up (resp. one unit right) at the i-th step.

The following example shows how to use the random walk to bound the weighted size of families.

Fact 3 Let F ⊂ 2^{[n]} be 3-wise 2-intersecting shifted co-complex. Then W_{w}(F) ≤ α^{2}.

Proof. Set G_{0} := {1, 3, 4, 6, 7, …, 3i, 3i + 1, …} ∩ [n]. Note that walk(G_{0}) is the maximal walk which does not touch the line ℓ : y = 2x + 2. We know that G_{0} ∉ F by Fact 2. Thus, if G ≻ G_{0} then G ∉ F by Fact 1. In other words, for every F ∈ F, walk(F) must touch the line ℓ. Therefore,

W_{w}(F) ≤ Prob(a random walk of n-steps touches the line ℓ) ≤ α^{2}.

For an r-wise t-intersecting family, we consider the equation (1 − w)x^{r} − x + w = 0, its root α_{r} ∈ (0, 1), and the line y = (r − 1)x + t. Then the weight of the family is at most α_{r}^{t}.

2.3 Shadow

For a family F ⊂ 2^{[n]} and a positive integer ℓ < n, let us define the ℓ-th shadow of F, denoted by Δ_{ℓ}(F), as follows.

Δ_{ℓ}(F) := \{G ∈ \binom{[n]}{ℓ} : G ⊂ ∃F ∈ F\}.

Suppose that F ⊂ \binom{[n]}{k} and |F| = \binom{m}{k} + \binom{x}{k−1} where m ∈ N, x ∈ R, x ≤ m − 1. Then, by the Kruskal–Katona theorem [15, 14] and its Lovász version [16], it follows that

|Δ_{ℓ}(F)| ≥ \binom{m}{ℓ} + \binom{x}{ℓ − 1}.

We shall use the above inequality to prove Theorem 3.

Let F ⊂ \binom{[n]}{k} be a 2-wise t-intersecting family. Katona[13] found the following bound for the ℓ-th shadow (t ≤ ℓ < k):

\frac{|Δ_{ℓ}(F)|}{|F|} ≥ \begin{matrix}( & {2k−t \atop ℓ} & ) \\ ( & {2k−t \atop k} & ) \end{matrix}.

We need the above inequality to prove Theorem 4.

See [5] or [6] for the detail of inequalities concerning the size of shadows.

3 Proof of Theorem 2

Let F ⊂ 2^{[n]} be 3-wise 2-intersecting. Further, we assume that F is shifted co-complex. Fix a constant w, 0 < w < 0.5018. In this section, we write W (F) instead of W_{w}(F). Set α := \frac{1}{2}(\sqrt{\frac{1+3w}{1−w}} − 1), v := 1 − w.

Let us define the following.

∗(i) := {i, i + 1, i + 3, i + 4, i + 6, i + 7, …} ∩ [n]
= [n] − ([i − 1] ∪ \{i + 3j + 2 : 0 ≤ j ≤ ⌊\frac{n − i − 2}{3}⌋\})
P_{i} := {1, 2} ∪ ∗(i + 4),
Q_{i} := {1, 2, i + 4} ∪ ∗(i + 6),
F_{12} := {F ∈ F : {1, 2} ⊂ F },
F_{1¯2} := {F ∈ F : 1 ∈ F, 2 ∉ F },
F_{¯12} := {F ∈ F : 1 ∉ F, 2 ∈ F },
F¯1¯2 := {F ∈ F : 1 ∉ F, 2 ∉ F }.

By definition, it follows that P_{i+1} ≻ Q_{i} ≻ P_{i}, |F| = |F_{12}|+|F_{1¯2}|+|F_{¯12}|+|F¯1¯2|. If {1, 2} = P_{n−3} ∈ F then F = {F ⊂ [n] : {1, 2} ⊂ F } and W (F) = w^{2}. From now on, we assume P_{n−3} ∉ F and we shall prove W (F) < w^{2}.

Case 1 P_{0} ∉ F Since P_{0} = ∗(1) ∉ F, we have W (F_{12}) ≤ w^{2}α. Since {1, 3} ∪ ∗(4) ≻ ∗(1), we have {1, 3} ∪ ∗(4) ∉ F, and W (F_{1¯2}) ≤ wvα^{4}. Since {2, 3} ∪ ∗(4) ≻ ∗(1), we have {2, 3} ∪ ∗(4) ∉ F, and W (F_{¯12}) ≤ vwα^{4}. In the same way, we have {3, 4, 5, 6} ∪ ∗(7) ∉ F, and W (F¯1¯2) ≤ v^{2}α^{7}. Therefore,

W (F) = W (F_{12}) + W (F_{1¯2}) + W (F_{¯12}) + W (F¯1¯2)
≤ w^{2}α + 2wvα^{4} + v^{2}α^{7} < w^{2}.

Case 2 P_{i} ∈ F, P_{i+1} ∉ F, i ≥ 1.

Case 2.1 Q_{i} ∉ F. Since Q_{i} ∉ F, we have

W (F_{12}) ≤ w^{2}(v^{i+1}α^{2} + (1 − v^{i+1}))
= w^{2}(1 − v^{i+1}(1 − α^{2})).

Set

F := [1, i + 3] ∪ {i + 6, i + 9, i + 12, …, 4i, 4i + 3} ∪ ∗(4i + 5),
G := {1} ∪ [3, 4i + 4] ∪ ∗(4i + 6).

Since P_{i} ∈ F and P_{i} = {1, 2} ∪ ∗(i + 4) ≻ F, we have F ∈ F. Note that P_{i} ∩ F ∩ G = {1}. Thus G ∉ F follows from the assumption that F is 3-wise 2-intersecting. Therefore,

W (F_{1¯2}) ≤ wvα^{4i+3}.

In the same way, we have W (F_{¯12}) ≤ wvα^{4i+3}. Next, set H := [3, 4i + 7] ∪ ∗(4i + 9). Since P_{i} ∩ F ∩ H = {4i + 5}, we have H ∉ F, which implies

W (F¯1¯2) ≤ v^{2}α^{4i+6}.

Therefore,

W (F) ≤ w^{2}(1 − v^{i+1}(1 − α^{2})) + 2wvα^{4i+3} + v^{2}α^{4i+6} < w^{2}.  (2)

(This is equivalent to (\frac{α^{4}}{v})^{i} < \frac{v(1−α^{2})}{α^{3}(2(v/w)+(v/w)^{2}α^{3})}.)

Case 2.2 Q_{i} ∈ F. Since P_{i+1} ∉ F, we have

W (F_{12}) ≤ w^{2}(v^{i+1}α + (1 − v^{i+1})) = w^{2}(1 − v^{i+1}(1 − α)).

Set

F := [1, i + 3] ∪ {i + 5, i + 8, i + 11, …, 4i + 5} ∪ ∗(4i + 7),
G := {1} ∪ [3, 4i + 6] ∪ ∗(4i + 8).

Since Q_{i} ∈ F and Q_{i} ≻ F, we have F ∈ F. Note that Q_{i} ∩ F ∩ G = {1}. Thus G ∉ F follows from the assumption that F is 3-wise 2-intersecting. Therefore,

W (F_{1¯2}) ≤ wvα^{4i+5}.

In the same way, we have W (F_{¯12}) ≤ wvα^{4i+5}. Set H := [3, 4i+9]∪∗(4i+11). Since Q_{i} ∩ F ∩ H = {4i + 7}, we have H ∉ F, which implies

W (F¯1¯2) ≤ v^{2}α^{4i+8}.

Therefore,

W (F) ≤ w^{2}(1 − v^{i+1}(1 − α)) + 2wvα^{4i+5} + v^{2}α^{4i+8} < w^{2}.  (3)

(This is equivalent to (\frac{α^{4}}{v})^{i} < \frac{v(1−α)}{α^{5}(2(v/w)+(v/w)^{2}α^{3})}.)

Now we may assume that P_{0} ∈ F and P_{1} ∉ F.

Case 3 P_{1} ∉ F, Q_{0} ∈ F. Set F := {1, 2, 3, 5} ∪ ∗(7), G := {1, 3, 4, 5, 6} ∪ ∗(8). Since Q_{0} ∈ F and Q_{0} ≻ F, we have F ∈ F. Note that Q_{0} ∩ F ∩ G = {1}. Thus, G ∉ F, and

W (F_{1¯2}) ≤ wvα^{5}.

In the same way, we have W (F_{¯12}) ≤ wvα^{5}. Next set H := {3, 4, 5, 6, 7}∪∗(8). Since Q_{0} ∩ F ∩ H = {7}, we have H ∉ F, which implies

W (F¯1¯2) ≤ v^{2}α^{8}.

Case 3.1 S_{1} := {1, 2, 5} ∪ ∗(6) ∉ F. Since S_{1} ∉ F, we have

W (F_{12}) ≤ w^{2}(w^{2} + 2wv + v^{2}α^{4}) =: W_{31}.

Therefore, we have

W (F) ≤ W_{31} + 2wvα^{5} + v^{2}α^{8} < w^{2}.

Case 3.2 S_{2} := {1, 2, 5, 6, 8, 9} ∪ ∗(10) ∉ F. Since S_{2} ∉ F, we have

W (F_{12}) ≤ w^{2}(w^{5} + 5w^{4}v + 10w^{3}v^{2} + w^{2}v^{3}(7 + 3α^{5})
+wv^{4}(2 + 3α^{8}) + v^{5}α^{11}) := W_{32}.

Therefore, we have

W (F) ≤ W_{32} + 2wvα^{5} + v^{2}α^{8} < w^{2}.

This is the hardest case and the above inequality fails if w ≥ 0.5019.

Case 3.3 S_{1}, S_{2} ∈ F. Set F := {1, 2, 3, 4, 8, 9}∪∗(10), G := {1, 3, 4, 5, 6, 7, 8}∪∗(11). Since S_{2} ∈ F and S_{2} ≻ F, we have F ∈ F. Note that S_{1} ∩ F ∩ G = {1} and G ∉ F. Thus, we have

W (F_{1¯2}) ≤ wv(w^{7} + v ∑_{i=1}^{7} w^{7−i}α^{i})
= wv(w^{7} + vα\frac{α^{7} − w^{7}}{α − w}) =: W_{33}.

In the same way, we have W (F_{¯12}) ≤ W_{33}. Next set H := {3, 4, 5, 6, 7, 8, 9} ∪ ∗(11). Since S_{1} ∩ F ∩ H = {9}, we have H ∉ F, which implies

W (F¯1¯2) ≤ v^{2}α^{8}.

Finally P_{1} ∉ F implies

W (F_{12}) ≤ w^{2}(w^{2} + 2wv + v^{2}α^{3}).

Therefore, we have

W (F) ≤ w^{2}(w^{2} + 2wv + v^{2}α^{3}) + 2W_{33} + v^{2}α^{8} < w^{2}.

Now we may assume P_{0} ∈ F and Q_{0} ∉ F.

Case 4 P_{0} ∈ F, Q_{0} ∉ F, R := {1, 2, 3} ∪ ∗(6) ∈ F. First, Q_{0} ∉ F implies

W (F_{12}) ≤ w^{2}(w + vα^{2}).

Set G := {1, 3, 4} ∪ ∗(5), H := {3, 4, 5, 6, 7} ∪ ∗(8). Since P_{0} ∩ R ∩ G = {1}, we have G ∉ F, which implies

W (F_{1¯2}) ≤ wvα^{5}.

In the same way, we have W (F_{¯12}) ≤ wvα^{5}. Since P_{0} ∩ R ∩ H = {7}, we have H ∉ F and

W (F¯1¯2) ≤ v^{2}α^{8}.

Therefore, we have

W (F) ≤ w^{2}(w + vα^{2}) + 2wvα^{5} + v^{2}α^{8} < w^{2}.

At this point, let us summarize what we have proved.

Proposition 1 Theorem 2 is true if P_{0} ∉ F or Q_{0} ∈ F or {1, 2, 3}∪∗(6) ∈ F.

In order to prove the remaining cases, we need some preparations. For a subset S ⊂ [5], let us define

F(S) := {F − S : F ∈ F, F ∩ [5] = S} ⊂ 2^{[6,n]},
f(S) := W (F(S)).

If S ≻ S′, the shiftedness of F implies F(S) ⊂ F(S′) (and f(S) ≤ f(S′)). For simplicity, we write F(123), f(123) instead of F({1, 2, 3}), f({1, 2, 3}).

Lemma 1 Let S ⊂ [5], |S| = 3, and F := {1, 3} ∪ ∗(4). If F ∈ F, then f(S) ≤ α^{3}.

Proof. Set G := {1, 2, 4} ∪ ∗(5), H := {1, 2, 3} ∪ ∗(6). Since F ∈ F and F ≻ G, we have G ∈ F. Note that F ∩ G ∩ H = {1}. Thus, we have H ∉ F and f(123) ≤ α^{3}. If S ⊂ [5] and |S| = 3 then S ≻ {1, 2, 3}. Thus, f(S) ≤ f(123) ≤ α^{3}.

Lemma 2 Let S ⊂ [5], |S| ≤ 3, and F := {1, 3} ∪ ∗(4). If F ∈ F, then f(S) ≤ α^{3(4−|S|)}.

Proof. Similar as proof of Lemma 1. Use the fact that F ∈ F implies {1, 2, 6, 7, 8} ∪ ∗(9) ∉ F, {1} ∪ [6, 11] ∪ ∗(12) ∉ F, [6, 14] ∪ ∗(15) ∉ F.

Lemma 3 Let S ⊂ [5] and |S| = 3. If [2] ⊄ S, then F(S) is 3-wise 3intersecting (on [6, n]).

Proof. By the shiftedness of F, it is sufficient to consider the case S = {1, 3, 4}. Suppose, on the contrary, that F(S) is not 3-wise 3-intersecting. Then, there exist T_{1}, T_{2}, T_{3} ∈ F(S) such that T_{1} ∩ T_{2} ∩ T_{3} = {x, y}. Set

F_{1} := {1, 3, 4} ∪ T_{1},
F_{2} := {1, 2, 4, 5} ∪ (T_{2} − {x}),
F_{3} := {1, 2, 3, 5} ∪ (T_{3} − {y}).

Since S ∪T_{2} ≻ F_{2} and S ∪T_{3} ≻ F_{3}, we have F_{1}, F_{2}, F_{3} ∈ F, but F_{1} ∩F_{2} ∩F_{3} = {1}. This contradicts our assumption that F is 3-wise 2-intersecting.

Using the same approach, we can extend the above lemma as follows.

Lemma 4 If [2] ⊄ S ⊂ [5] and |S| ≤ 3, then F(S) is 3-wise 3(4 − |S|)- intersecting (on [6, n]).

Now, let us leave the proof of Theorem 2 aside for a while, and concentrate on the following stronger proposition.

Proposition 2 Let G ⊂ 2^{[n]}, t ≥ 2, and w < 0.5018. If G is 3-wise tintersecting, then W (G) ≤ w^{2}α^{t−2}.

Note that the case t = 2 in Proposition 2 is exactly Theorem 2. We prove Proposition 2 by double induction on n and t.

First, let us check the cases t ≤ n ≤ t + 2. Set G_{0} := {G ⊂ [n] : [t] ⊂ G}. It is easy to verify that if t ≤ n ≤ t + 2 then

W (G) ≤ W (G_{0}) = w^{t} ≤ w^{2}α^{t−2}.

Another initial step of the induction is the case t = 2, i.e., Theorem 2. But we postpone this essential case, and check, in advance, that Theorem 2 actually implies the induction step.

Assume that Proposition 2 is true for t = 2. Let G ⊂ 2^{[n]} be 3-wise t-intersecting and t ≥ 3. (We also assume that G is shifted co-complex.) Define G_{1}, G¯1 ⊂ 2^{[2,n]} as follows.

G_{1} := {G − {1} : 1 ∈ G ∈ G},
G¯1 := {G ∈ G : 1 ∉ G}.

Note that G_{1} is 3-wise (t − 1)-intersecting, and since G is shifted, G¯1 is 3-wise (t + 2)-intersecting. Using the induction hypothesis, we have

W (G) = wW (G_{1}) + vW (G¯1) ≤ w^{3}α^{t−3} + vw^{2}α^{t}
= w^{2}α^{t−3}(vα^{3} + w) = w^{2}α^{t−2}.

(Remember that α is a root of the equation vx^{3} −x+w = 0.) This completes the induction step for the proof of Proposition 2.

Consequently, all we have to do is to prove the case t = 2 (Theorem 2) by induction on n. So let us return to the proof of Theorem 2 again. But this time, we can use the induction hypothesis of Proposition 2 i.e., we assume that Proposition 2 is true for all (n′, t′) if t′ ≤ n′ < n.

Lemma 5 If [2] ⊄ S ⊂ [5] and |S| ≤ 3, then f(S) ≤ w^{2}α^{10−3|S|}.

Proof. By Lemma 4, F(S) ⊂ 2^{[6,n]} is 3-wise 3(4 − |S|)-intersecting. Using the induction hypothesis, we have W (F(S)) ≤ w^{2}α^{3(4−|S|)−2} = w^{2}α^{10−3|S|}.

Case 5 {1, 3} ∪ ∗(4) ∈ F. Let S ⊂ [5]. Define

F̃(S) := {F ∈ F : F ∩ [5] = S} ⊂ 2^{[n]}.

For S = {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, we apply Lemma 1 and obtain f(S) ≤ α^{3}. For the remaining seven 3-sets S, we use Lemma 5 and obtain f(S) ≤ w^{2}α. Thus, we have

∑_{|S|=3} W (F̃(S)) ≤ (3α^{3} + 7w^{2}α) · w^{3}v^{2}.

Similarly,

∑_{|S|=2} W (F̃(S)) ≤ (α^{6} + 9w^{2}α^{4}) · w^{2}v^{3}.

In this way, we have

∑_{|S|≤3} W (F̃(S)) ≤ (3α^{3} + 7w^{2}α) · w^{3}v^{2} + (α^{6} + 9w^{2}α^{4}) · w^{2}v^{3}
+5w^{2}α^{7} · wv^{4} + w^{2}α^{10} · v^{5} =: W_{5}.

Case 5.1 {2, 3} ∪ ∗(4) ∉ F. Since f(2345) ≤ α, we have ∑_{|S|=4} W (F̃(S)) ≤ (4 + α)w^{4}v. We also use f(12345) ≤ 1, i.e., W (F̃(S)) ≤ w^{5}. Therefore, we have

W (F) = ∑_{S⊂[5]} W (F̃(S)) ≤ W_{5} + (4 + α)w^{4}v + w^{5} < w^{2}.

Case 5.2 {2, 3} ∪ ∗(4) ∈ F and {1, 3, 4, 5} ∪ ∗(8) ∉ F. Set F_{6} := {H ∈ F(1345) : 6 ∈ F }, F¯6 := {H ∈ F(1345) : 6 ∉ F }. Then we have W (F_{6}) ≤ w^{5}v and W (F¯6) ≤ w^{4}v^{2}α. Thus, we have

W (F̃(1345)) ≤ w^{4}v^{2}(w + vα).

We can apply the same thing to F̃(2345), because {2, 3, 4, 5} ∪ ∗(8) ∉ F follows from the shiftedness of F. Thus,

∑_{|S|=4} ≤ 2w^{4}v^{2}(w + vα) + 3w^{4}v =: W_{52}.

(The former corresponds to 1345, 2345, and the latter corresponds to 1234, 1235, 1245.) Therefore, we have

W (F) ≤ W_{5} + W_{52} + w^{5} < w^{2}.

Case 5.3 {2, 3} ∪ ∗(4) ∈ F and {1, 3, 4, 5} ∪ ∗(8) ∈ F. Since {2, 3} ∪ ∗(4) ≻ [2, 7] ∪ ∗(10), and

({1, 3, 4, 5} ∪ ∗(8)) ∩ ([2, 7] ∪ ∗(10)) ∩ ({1, 2, 3, 6, 7, 8} ∪ ∗(9)) = {3},

we have {1, 2, 3, 6, 7, 8} ∪ ∗(9) ∉ F. This implies that f(S) ≤ α^{6} if |S| = 3. If |S| = 2 and S ≠ {1, 2} then we have f(S) ≤ w^{2}α^{4} by Lemma 5. Thus, we have

W (F) ≤ w^{2}α^{10} · v^{5} + 5w^{2}α^{7} · wv^{4} + (9w^{2}α^{4} + α^{6})w^{2}v^{3}
+10α^{6} · w^{3}v^{2} + 5w^{4}v + w^{5} < w^{2}.

Case 6 {1, 3} ∪ ∗(4) ∉ F. By using Proposition 1, we may assume that R := {1, 2, 3} ∪ ∗(6) ∉ F. This implies that

f(123), f(124), f(125) ≤ α^{3}.

Since {1, 2, 6, 7, 8} ∪ ∗(9) ≻ R, we have {1, 2, 6, 7, 8} ∪ ∗(9) ∉ F, and thus, f(12) ≤ α^{6}. Therefore, (using Lemma 5) we have

W (F) ≤ w^{2}α^{10} · v^{5} + 5w^{2}α^{7} · wv^{4} + (9w^{2}α^{4} + α^{6})w^{2}v^{3}
+(7w^{2}α + 3α^{3})w^{3}v^{2} + (4 + α)w^{4}v + w^{5} < w^{2}.

This completes the proof of Proposition 2 and Theorem 2 at the same time.

Let F ⊂ \binom{[n]}{k} be a 3-wise 2-intersecting family. This family is clearly 2-wise 2-intersecting, too. Therefore, by the Erdős–Ko–Rado theorem it follows that |F| ≤ \binom{n−2}{k−2} if n ≥ 3(k − 1). So we may assume that n < 3k.

Let δ > 0 be given. We shall prove |F| < (1 + δ)\binom{n−2}{k−2} for sufficiently large n. Set w := 0.5017 and v := 1 − w. By Theorem 2, we must have W_{w}(G) ≤ w^{2} for any 3-wise 2-intersecting family G ⊂ 2^{[n]}. Choose ϵ > 0 sufficiently small so that

(1 + δ/2)(1 − ϵ)^{4} > 1,  (4)
0.501 < (1 − ϵ)w.  (5)

Define an open interval I := ((1 − ϵ)wn, (1 + ϵ)wn). Choose n_{0} = n_{0}(δ, ϵ) sufficiently large so that

∑_{i∈I} \binom{n}{i}w^{i}v^{n−i} > 1 − ϵ for all n > n_{0},  (6)
ϵ > 2/((1 − ϵ)wn) for all n > n_{0}.  (7)

Let F ⊂ \binom{[n]}{k} be a 3-wise 2-intersecting family with 1/3 < k/n < 0.501.

Suppose that |F| = (1 + δ)\binom{n−2}{k−2}. We shall derive a contradiction by constructing a 3-wise 2-intersecting family G ⊂ 2^{[n]} with W_{w}(G) > w^{2}. Set F^{c} := {[n] − F : F ∈ F}. Define

G := ⋃_{ℓ=0}^{n−k}(Δ_{ℓ}(F^{c}))^{c} (⊂ ⋃_{i=k}^{n} \binom{[n]}{i}).

Then,

W_{w}(G) = ∑_{ℓ=0}^{n−k} |Δ_{ℓ}(F^{c})|w^{n−ℓ}v^{ℓ}
= ∑_{i=k}^{n} |Δ_{n−i}(F^{c})|w^{i}v^{n−i}.

Since k < 0.501n < (1 − ϵ)wn by (5) and I ⊂ [k, n], we have

W_{w}(G) ≥ ∑_{i∈I} |Δ_{n−i}(F^{c})|w^{i}v^{n−i}.

Lemma 6 |Δ_{n−i}(F^{c})| ≥ (1 + \frac{δ}{2})\binom{n−2}{n−i} for i ∈ I.

Proof. Let x (x ≤ n − 3) be a real satisfying \binom{x}{n−k−1} = δ\binom{n−2}{n−k}. Then,

|F^{c}| = |F| = (1 + δ)\binom{n−2}{k−2} = \binom{n−2}{n−k} + \binom{x}{n−k−1}. By the Kruskal–Katona

theorem, we have |Δ_{n−i}(F^{c})| ≥ \binom{n−2}{n−i} + \binom{x}{n−i−1}. To prove \binom{x}{n−i−1} ≥ \frac{δ}{2} \binom{n−2}{n−i}, it is sufficient to show

\begin{matrix}( & {x \atop n−i−1} & ) \\ ( & {x \atop n−k−1} & ) \end{matrix} ≥ \frac{\frac{δ}{2} \binom{n−2}{n−i}}{δ\binom{n−2}{n−k}},

or equivalently,

\frac{(i − 2) ⋯ (k − 1)}{(x − n + i + 1) ⋯ (x − n + k + 2)} ≥ \frac{n − k}{2(n − i)}.

Let us check that LHS > 1 > RHS. Since LHS ≥ (\frac{i−2}{x−n+i+1})^{i−k} and x ≤ n−3, we have LHS > 1. On the other hand, 1 > RHS is equivalent to (n+k)/2 ≥ i. Using n < 3k and (5), we certainly have (n + k)/2 ≥ (n + n/3)/2 = 2n/3 ≥ (1 + ϵ)wn ≥ i. This completes the proof of the lemma.

By the lemma, we have

W_{w}(G) ≥ ∑_{i∈I}(1 + \frac{δ}{2})\binom{n − 2}{n − i}w^{i}v^{n−i}
= ∑_{i∈I}(1 + \frac{δ}{2})\frac{i}{n} · \frac{i − 1}{n − 1}\binom{n}{i}w^{i}v^{n−i}.

Note that

\frac{i}{n} · \frac{i − 1}{n − 1} ≥ (\frac{i − 1}{n})^{2} ≥ \frac{((1 − ϵ)wn − 1)^{2}}{n^{2}} ≥ (1 − ϵ)^{2}w^{2} − \frac{2(1 − ϵ)w}{n}
= (1 − ϵ)^{2}w^{2}(1 − \frac{2}{(1 − ϵ)wn}) > (1 − ϵ)^{3}w^{2} (by (7)).

Therefore,

W_{w}(G) ≥ (1 + \frac{δ}{2})(1 − ϵ)^{3}w^{2} ∑_{i∈I} \binom{n}{i}w^{i}v^{n−i}
> (1 + \frac{δ}{2})(1 − ϵ)^{4}w^{2} (by (6))
> w^{2} (by (4)),

which is a contradiction. This completes the proof of Theorem 3.

For a family F ⊂ 2^{[n]}, set F_{i} := F ∩\binom{[n]}{i}. First we prove the following version of the Erdős–Ko–Rado theorem. (See [3] for 3-wise 1-intersecting families.)

Proposition 3 Let F ⊂ 2^{[n]} be a 3-wise 2-intersecting Sperner family with k/n < 0.501. Then ∑_{i=1}^{k} |F_{i}|\binom{n−2}{i−2}^{−1} ≤ 1 + o(1).

Proof. Let δ > 0 be given. We prove ∑_{i=1}^{k} |F_{i}|\binom{n−2}{i−2}^{−1} ≤ 1 + δ for n > n_{0}(δ) by induction on the number of nonzero |F_{i}|’s.

If this number is one then the inequality follows from Theorem 3. If it is not the case then let p be the smallest and r the second-smallest index for which |F_{i}| ≠ 0. Set F_{p}^{c} := \{[n] − F : F ∈ F_{p}\}. Then F_{p}^{c} ⊂ \binom{[n]}{n−p} is (2-wise) (n − 2p + 2)-intersecting. By the Katona’s shadow theorem for intersecting family (see section 2.3), we have

\frac{|Δ_{n−r}(F_{p}^{c})|}{|F_{p}^{c}|} ≥ \begin{matrix}( & {2(n−p)−(n−2p+2) \atop n−r} & ) \\ ( & {2(n−p)−(n−2p+2) \atop n−p} & ) \end{matrix} = \begin{matrix}( & {n−2 \atop r−2} & ) \\ ( & {n−2 \atop p−2} & ) \end{matrix}.

Set G := \{G ∈ \binom{[n]}{r} : G ⊃ ∃F ∈ F_{p}\}. Since G = (Δ_{n−r}(F_{p}^{c}))^{c}, we have

|G|\binom{n−2}{r−2}^{−1} ≥ |F_{p}|\binom{n−2}{p−2}^{−1}. Note that H := (F − F_{p}) ∪ G is also 3-wise 2intersecting Sperner family, and the number of nonzero |H_{i}|’s is one less. Therefore, by the induction hypothesis we have

∑_{i=1}^{k} \frac{|F_{i}|}{\binom{n−2}{i−2}} ≤ ∑_{i=1}^{k} \frac{|H_{i}|}{\binom{n−2}{i−2}} ≤ 1 + δ,

which completes the proof of the proposition.

Let us now prove Theorem 4. Let δ > 0 be given. Suppose that F ⊂ 2^{[n]} is a 3-wise 2-intersecting Sperner family. We show |F| < (1 + δ)\binom{n−2}{⌈(n−2)/2⌉} for n > n_{0}(δ). Set k := ⌊0.501n⌋. By Proposition 3, we have

1 + \frac{δ}{2} > ∑_{i=1}^{k} \frac{|F_{i}|}{\binom{n−2}{i−2}} ≥ ∑_{i=1}^{k} \frac{|F_{i}|}{\binom{n−2}{⌈(n−2)/2⌉}}.

On the other hand, by the LYM inequality, we have

1 ≥ ∑_{i=k+1}^{n} \frac{|F_{i}|}{\binom{n}{i}} ≥ ∑_{i=k+1}^{n} \frac{|F_{i}|}{\binom{n}{k+1}}.

Therefore, we have

|F| ≤ (1 + \frac{δ}{2})\binom{n − 2}{⌈(n − 2)/2⌉} + \binom{n}{⌊0.501n⌋ + 1} < (1 + δ)\binom{n − 2}{⌈(n − 2)/2⌉}

for sufficiently large n.

6 Proof of Theorem 5

An r-wise t-intersecting family F ⊂ 2^{[n]} is called non-trivial if | ⋂_{F ∈F} F | < t. Define

g_{w,r,t}(n) := max{W_{w}(F) : F ⊂ 2^{[n]} is non-trivial r-wise t-intersecting}.

Proposition 4 g_{w,4,2}(n) ≤ 0.999w^{2} if w ≤ 0.5015.

Proof. Let F ⊂ 2^{[n]} be a 3-wise 2-intersecting family. In the proof of Theorem 2, we checked the inequality W_{w}(F) ≤ w^{2}. In the exactly the same way, we can check

W_{w}(F) < 0.999w^{2} for w ≤ 0.5015

in all cases but Case 2.

Now let F ⊂ 2^{[n]} be a non-trivial 4-wise 2-intersecting family. We follow the proof of Theorem 2 and all we have to deal with is only Case 2. Suppose that there exist F_{1}, F_{2}, F_{2} such that F_{1} ∩F_{2} ∩F_{3} = {1, 2}. Then every F ∈ F must contain {1, 2}, which is not possible because F is non-trivial. Thus we may assume that {F \ {1, 2} : {1, 2} ⊂ F ∈ F} is 3-wise 1-intersecting. Then, by Theorem 1, we have

W_{w}(F_{12}) ≤ w^{3} for w ≤ 2/3.

For F_{1¯2}, F_{¯12}, F¯1¯2 we use the same estimation in Case 2 of proof of Theorem 2, but this time we redefine α ∈ (0, 1) as the unique root (in the interval) of the equation (1 − w)x^{4} − x + w = 0. (cf. α ≈ 0.543689 if w = 1/2.) Then one can check in inequalities (2) and (3) that

W_{w}(F) < 0.93w^{2} for w ≤ 2/3.

This completes the proof. (Note that one can construct (see [8]) a non-trivial 4-wise 2-intersecting family F ⊂ 2^{[n]} with lim_{n→∞} W_{w}(F) = w^{2} if w > 2/3.)

Proposition 5 Let F ⊂ \binom{[n]}{k} be a 4-wise 2-intersecting family with k/n <

0.501, n > n_{0}. Then |F| ≤ \binom{n−2}{k−2}. Moreover if F is non-trivial then |F| <

0.9999\binom{n−2}{k−2}.

Proof. The proof is similar to the proof of Theorem 3, and we give a sketch here. Let F ⊂ \binom{[n]}{k} be a 4-wise 2-intersecting family. If F fix 2-

element set, then |F| ≤ \binom{n−2}{k−2}. So we may assume that F is non-trivial.

Suppose that |F| ≥ 0.9999\binom{n−2}{k−2}, and set w := 0.501, v := 1 − w. We shall derive a contradiction by constructing a non-trivial 4-wise 2-intersecting family G ⊂ 2^{[n]} with W_{w}(G) > 0.999w^{2}.

Choose ϵ > 0 sufficiently small so that

0.9998(1 − ϵ)^{4} > 0.999,  (8)
0.501 < (1 − ϵ)w.  (9)

Define an open interval I := ((1 − ϵ)wn, (1 + ϵ)wn). Choose n_{0} = n_{0}(δ, ϵ) sufficiently large so that

∑_{i∈I} \binom{n}{i}w^{i}v^{n−i} > 1 − ϵ for all n > n_{0},  (10)
ϵ > 2/((1 − ϵ)wn) for all n > n_{0}.  (11)

Set F^{c} := {[n] − F : F ∈ F} and define

G := ⋃_{ℓ=0}^{n−k}(Δ_{ℓ}(F^{c}))^{c} (⊂ ⋃_{i=k}^{n} \binom{[n]}{i}).

Then G is a non-trivial 4-wise 2-intersecting family, and since k < 0.501n < (1 − ϵ)wn by (9), we have

W_{w}(G) ≥ ∑_{i∈I} |Δ_{n−i}(F^{c})|w^{i}v^{n−i}.

Lemma 7 |Δ_{n−i}(F^{c})| ≥ 0.9998\binom{n−2}{n−i} for i ∈ I.

Proof. Let x (x < n − 2) be a real satisfying |F| ≥ 0.9999\binom{n−2}{k−2} = \binom{x}{n−k}. Then, by the Kruskal–Katona theorem, we have |Δ_{n−i}(F^{c})| ≥ \binom{x}{n−i}. To prove \binom{x}{n−i} ≥ 0.9998\binom{n−2}{n−i}, it is sufficient to show

\begin{matrix}( & {x \atop n−i} & ) \\ ( & {x \atop n−k} & ) \end{matrix} ≥ \frac{0.9998\binom{n−2}{n−i}}{0.9999\binom{n−2}{n−k}},

or equivalently,

\frac{(i − 2) ⋯ (k − 1)}{(x − n + i) ⋯ (x − n + k + 1)} ≥ \frac{0.9998}{0.9999}.

This is true, because LHS ≥ (\frac{i−2}{x−n+i})^{i−k} > 1 > LHS > 1. This completes the proof of the lemma.

Therefore,

W_{w}(G) ≥ 0.9998 ∑_{i∈I} \binom{n − 2}{n − i}w^{i}v^{n−i} (by the lemma)
= 0.9998 ∑_{i∈I} \frac{i}{n} · \frac{i − 1}{n − 1}\binom{n}{i}w^{i}v^{n−i}.
≥ 0.9998(1 − ϵ)^{3}w^{2} ∑_{i∈I} \binom{n}{i}w^{i}v^{n−i} (by (11))
> 0.9998(1 − ϵ)^{4}w^{2} (by (10))
> 0.999w^{2} (by (8)),

which is a contradiction. This completes the proof of Theorem 5.

For a family F ⊂ 2^{[n]}, set F_{i} := F ∩ \binom{[n]}{i}. One can prove the next proposition in the same way we proved Theorem 4. (The only difference is to use Proposition 5 instead of Theorem 3.) Proposition 6 Let F ⊂ 2^{[n]} be a 4-wise 2-intersecting Sperner family with k/n < 0.501, n > n_{0}. Then ∑_{i=1}^{k} |F_{i}|\binom{n−2}{i−2}^{−1} ≤ 1. Moreover if F is nontrivial then ∑_{i=1}^{k} |F_{i}|\binom{n−2}{i−2}^{−1} < 0.9999.

Let us now prove Theorem 5. Let F ⊂ 2^{[n]} be a 4-wise 2-intersecting Sperner family. First suppose that F fix 2-element set, say {1, 2}. Then G := {F \ {1, 2} : F ∈ F} ⊂ 2^{[3,n]} is a Sperner family. Thus we have

|F| = |G| ≤ \binom{n − 2}{⌈(n − 2)/2⌉}.

Next suppose that F is non-trivial. Set k := ⌊0.501n⌋. By Proposition 6, we have

0.9999 > ∑_{i=1}^{k} \frac{|F_{i}|}{\binom{n−2}{i−2}} ≥ ∑_{i=1}^{k} \frac{|F_{i}|}{\binom{n−2}{⌈(n−2)/2⌉}}.

On the other hand, by the LYM inequality, we have

1 ≥ ∑_{i=k+1}^{n} \frac{|F_{i}|}{\binom{n}{i}} ≥ ∑_{i=k+1}^{n} \frac{|F_{i}|}{\binom{n}{k+1}}.

Therefore, we have

|F| ≤ 0.9999\binom{n − 2}{⌈(n − 2)/2⌉} + \binom{n}{⌊0.501n⌋ + 1} < \binom{n − 2}{⌈(n − 2)/2⌉}

for sufficiently large n. This completes the proof of Theorem 5

As for 3-wise case, compared to Proposition 6, we have a following difficulty.

Example 1 Let w = \frac{1}{2} + ϵ, k = ⌊wn⌋, and set A = [3, k + 2]. Define a non-trivial 3-wise 2-intersecting family F_{n} ⊂ \binom{[n]}{k} as follows.

F_{n} := \{\{1, 2\} ∪ G : |G ∩ A| ≥ \frac{k + 2}{2}, G ∈ \binom{[3, n]}{k − 2}\} ∪ \{A\}.

Then one has lim_{n→∞} |F_{n}|/\binom{n−2}{k−2} = 1.

If we take all superset of F ∈ F_{n}, that is, G_{n} := {G ⊂ [n] : G ⊃ ∃F ∈ F_{n}}, then this family is clearly non-trivial 3-wise 2-intersecting. One can check that lim_{n→∞} W_{w}(G_{n}) = w^{2} for fixed w = \frac{1}{2} +ϵ. Thus, Proposition 4 fails for 3wise 2-intersecting family. However, we may still expect to refine Theorem 3 as follows:

Conjecture 2 Let F ⊂ \binom{[n]}{k} be a 3-wise 2-intersecting family with k/n <

0.501, n > n_{0}. Then |F| ≤ \binom{n−2}{k−2}.

References

[1] R. Ahlswede, G.O.H. Katona. Contributions to the theory of Hamming spaces. Discrete Math., 17:1–22, 1977.

[2] P. Erdős, C. Ko, R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford (2), 12:313–320, 1961.

[3] P. Frankl. On Sperner families satisfying an additional condition. J. Combinatorial Theory (A), 20:1–11, 1976.

[4] P. Frankl. Families of finite sets satisfying an intersection condition. Bull. Austral. Math. Soc., 15:73–79, 1976.

[5] P. Frankl. The shifting technique in extremal set theory. “Surveys in Combinatorics 1987” (C. Whitehead, Ed. LMS Lecture Note Series 123), 81–110, Cambridge Univ. Press, 1987.

[6] P. Frankl, N. Tokushige. The Kruskal–Katona Theorem, some of its analogues and applications. Conference on extremal problems for finite sets, 1991, Visegrád, Hungary, 92–108.

[7] P. Frankl, N. Tokushige. Weighted multiply intersecting families. preprint.

[8] P. Frankl, N. Tokushige. Weighted non-trivial multiply intersecting families. preprint.

[9] H.D.O.F. Gronau. On Sperner families in which no 3-sets have an empty intersection. Acta Cybernet., 4:213–220, 1978.

[10] H.D.O.F. Gronau. On Sperner families in which no k-sets have an empty intersection. J. Combinatorial Theory (A), 28:54–63, 1980.

[11] H.D.O.F. Gronau. On Sperner families in which no k-sets have an empty intersection II. J. Combinatorial Theory (A), 30:298–316, 1981.

[12] H.D.O.F. Gronau. On Sperner families in which no k-sets have an empty intersection III. Combinatorica, 2:25–36, 1982.

[13] G. O. H. Katona. Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hung., 15:329–337, 1964.

[14] G. O. H. Katona. A theorem of finite sets, in: Theory of Graphs, Proc. Colloq. Thihany, 1966 (Akademiai Kiadó, 1968) 187–207, MR 45 #76.

[15] J. B. Kruskal. The number of simplices in a complex, in: Math. Opt. Techniques (Univ. of Calif. Press, 1963) 251–278, MR 27 #4771.

[16] L. Lovász. Problem 13.31. In Combinatorial Problems and Exercises, North Holland, 1979.

[17] E.C. Milner. A combinatorial theorem on systems of sets. J. London Math. Soc., 43:204–206, 1968.