Weighted multiply 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

October 31, 2002

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

1 Introduction

Let n and r be positive integers. A family F of subsets of [n] = {1, 2, …, n} is called r-wise intersecting if F_{1} ∩⋯∩F_{r} ≠ ∅ holds for all F_{1}, …, F_{r} ∈ F. For applications it is often important to consider weighted intersecting theorems, i.e., results where instead of |F| some different function is maximized. 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}. More generally, let v⃗ = (v_{1}, v_{2}, …, v_{n}) be a random 0-1 vector where v_{i} = 1 with probability w and v_{i} = 0 with probability 1 − w. Let F (v⃗) be the corresponding subset of [n], i.e., F (v⃗) = {i : v_{i} = 1}. Now W_{w}(F) is the probability that for a random 0-1 vector v⃗, F (v⃗) ∈ F holds.

Finally, define

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

Let us check

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

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

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

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

Actually, this is the maximal weight.

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

On the other hand, we will see

lim_{n→∞} f_{w,r}(n) = 1 if w > \frac{r−1}{r}.  (2)

2 Proof of the theorem

We distinguish two cases w = (r − 1)/r and w < (r − 1)/r.

For the first case, we need a preliminary result. Define a map p : {0, …, r − 1}^{n} → 2^{[n]} by p(g_{1}, …, g_{n}) = {i : g_{i} ≠ 0} and set p(G) = {p(g_{1}, …, g_{n}) : (g_{1}, …, g_{n}) ∈ G} for G ⊂ {0, …, r − 1}^{[n]}.

Proposition 1 Let G ⊂ {0, …, r − 1}^{[n]}. If p(G) is r-wise intersecting, then |G| ≤ (\frac{r−1}{r})r^{n}.

Proof For g = (g_{1}, …, g_{n}) ∈ G, define

φ(g) = ((g_{1} + 1) mod r, …, (g_{n} + 1) mod r),

and φ(G) = {φ(g) : g ∈ G}. If p(G) is r-wise intersecting, {g, φ(g), …, φ^{r−1}(g)} ⊄ G for any g ∈ {0, …, r−1}^{n}, and thus G∩φ(G)∩⋯∩φ^{r−1}(G) = ∅. Therefore,

r|G| = |G| + |φ(G)| + ⋯ + |φ^{r−1}(G)| ≤ (r − 1)r^{n},

or equivalently |G| ≤ (\frac{r−1}{r})r^{n}.

Now we assume that w = (r − 1)/r and prove the theorem in this case. Let F ⊂ 2^{[n]} be r-wise intersecting. Then,

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

On the other hand, using the proposition, we have

∑_{F ∈F}(r − 1)^{|F |} = |p^{−1}(F)| ≤ (\frac{r − 1}{r})r^{n}.

Therefore, W_{w}(F) ≤ \frac{r−1}{r} = w and f_{w,r}(n) = w.

Next we assume that w < (r − 1)/r. We use the following result proved by Frankl in [3].

Proposition 2 If G ⊂ \binom{[n]}{k} is r-wise intersecting and (r − 1)n ≥ rk, then

|G| ≤ \frac{k}{n} \binom{n}{k}.

Let ϵ > 0 be a small real and set an open interval I = ((1 − ϵ)nw, (1 + ϵ)nw). For any ϵ > 0 there exists n_{0} = n_{0}(ϵ) such that ∑_{k∉I} \binom{n}{k}w^{k}(1 − w)^{n−k} < ϵ for n > n_{0}. Thus,

f_{w,r}(n) < ∑_{k∈I} |F ∩ \binom{[n]}{k}| w^{k}(1 − w)^{n−k} + ϵ
≤ ∑_{k∈I} \frac{k}{n}\binom{n}{k}w^{k}(1 − w)^{n−k} + ϵ (by Prop. 2)
≤ (1 + ϵ)w ∑_{k=0}^{n} \binom{n}{k}w^{k}(1 − w)^{n−k} + ϵ
= (1 + ϵ)w + ϵ.

This implies

lim_{n→∞} f_{w,r}(n) = w.  (3)

Let us choose F ⊂ 2^{[n]} with W_{w}(F) = f_{w,r}(n), and define F′ ⊂ 2^{[n+1]} by F′ = F ∪ {F ∪ {n + 1} : F ∈ F}. Then W_{w}(F′) = f_{w,r}(n)((1 − w) + w) = f_{w,r}(n), which means

f_{w,r}(n + 1) ≥ f_{w,r}(n).  (4)

By (1), (3) and (4), we have f_{w,r}(n) = w. This completes the proof of the theorem.

If w > \frac{r−1}{r}, we can choose ϵ > 0 so that \frac{r−1}{r} < (1 − ϵ)w. In this case \binom{[n]}{k} is r-wise intersecting if k ∈ I = ((1 − ϵ)nw, (1 + ϵ)nw). Thus,

f_{w,r}(n) ≥ ∑_{k∈I} \binom{n}{k}w^{k}(1 − w)^{n−k} → 1 as n → ∞. This proves (2).

3 Concluding remarks

A family F ⊂ 2^{[n]} is called r-wise t-intersecting if |F_{1} ∩ ⋯ ∩ F_{r}| ≥ t holds for all F_{1}, …, F_{r} ∈ F. Let us define

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

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}. This means f_{w,r,t}(n) ≥ w^{t}. We have shown that f_{w,r,1}(n) = w if w ≤ (r − 1)/r.

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

In [4], the authors proved

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

The above result is used to prove the following, which settles a problem posed in [3].

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

A family F ⊂ 2^{[n]} is called non-trivial if ⋂_{F ∈F} F = ∅. Let us define

F_{1} = {F ⊂ [n] : |F ∩ [r + 1]| ≥ r}.

Then F_{1} is a non-trivial r-wise intersecting family. Brace and Daykin proved the following.

Theorem 3 [2] Suppose that F ⊂ 2^{[n]} is a non-trivial r-wise intersecting family. Then |F| ≤ |F_{1}|.

In other words, W_{1/2}(F) ≤ W_{1/2}(F_{1}) holds for any non-trivial r-wise intersecting family F. Can we expect the same inequality (W_{w}(F) ≤ W_{w}(F_{1})) for w = \frac{1}{2} + ϵ? In [5], the authors proved that the answer is “yes” for r ≥ 13 and “no” for r ≤ 5.

References

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

[2] A. Brace and D. E. Daykin. A finite set covering theorem. I,II,III,IV. Bull. Austral. Math. Soc., 5:197–202, 1971, 6:19–24, 417–433, 1972, Infinite and finite sets, I:199–203, 1975.

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

[4] P. Frankl, N. Tokushige. Weighted 3-wise 2-intersecting families. preprint.

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

[6] 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.

[7] 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.

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

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