New Bounds for Union-free Families of Sets

Don Coppersmith (email: copper@watson.ibm.com) James B. Shearer (email: jbs@watson.ibm.com) Mathematical Sciences Department IBM Research Division T. J. Watson Research Center P.O. Box 218 Yorktown Heights, NY 10598 U.S.A.

Submitted: April 11, 1997; Accepted: July 24, 1998

Abstract: Following Frankl and Füredi [1] we say a family, F, of subsets of an n-set is weakly union-free if F does not contain four distinct sets A, B, C, D with A ∪ B = C ∪ D. If in addition A ∪ B = A ∪ C implies B = C we say F is strongly union-free. Let f(n) (g(n)) be the maximum size of strongly (weakly) union-free families. In this paper we prove the following new bounds on f and g: 2^{[0.31349+o(1)]n} ≤ f(n) ≤ 2^{[0.4998+o(1)]n} and g(n) ≤ 2^{[0.5+o(1)]n}.

AMS Subject Classification. 05B10

1 Introduction

Let F be a family of subsets of an n-set. Suppose F does not contain four distinct sets A, B, C, D such that A ∪ B = C ∪ D. Then following Frankl and Füredi [1] we say F is weakly union-free. If A ∪ B = A ∪ C implies B = C then we say F is cancellative. If F is both weakly union-free and cancellative we say F is strongly union-free. Let f(n) (respectively g(n)) be the maximum size of a strongly (respectively weakly) union-free family of subsets of an n-set. In this paper we prove new bounds on f(n) and g(n). We show 2^{[0.31349+o(1)]n} ≤ f(n) ≤ 2^{[0.4998+o(1)]n} and g(n) ≤ 2^{[0.5+o(1)]n}. The best bounds previously known were 2^{[0.2534+o(1)]n} ≤ f(n) ≤ 2^{[0.5+o(1)]n} and 2^{[0.3333+o(1)]n} ≤ g(n) ≤ 2^{[0.75+o(1)]n} (see Frankl and Füredi [1]). We were unable to improve the lower bound for g(n).

We will need the following result of Fredman and Komlós ([3], see also [2]). Consider an alphabet consisting of k ordinary symbols a_{1}, …, a_{k} and one special symbol ∗ (∗ can be thought of as a “don’t-care” indicator). Following Fredman and Komlós we will say two vectors (x_{1}, …, x_{n}) and (y_{1}, …, y_{n}) with elements chosen from this alphabet are strongly different if there exists a j (1 ≤ j ≤ n) such that x_{j} ≠ y_{j} and x_{j} ≠ ∗, y_{j} ≠ ∗. Suppose we have m pairwise strongly different vectors (with elements {x_{ij}|1 ≤ i ≤ m, 1 ≤ j ≤ n}). Let h_{jℓ} be the number of vectors with jth element a_{ℓ}. Let h_{j∗} be the number of vectors with jth element ∗. Note m = h_{j1} + ⋯ + h_{jk} + h_{j∗} for 1 ≤ j ≤ n. Let p_{jℓ} = \frac{h_{jℓ}}{m}. Let p_{j∗} = \frac{h_{j∗}}{m}. Let q_{jℓ} = \frac{h_{jℓ}}{h_{j1}+···+h_{jk}}. Then we need the following bound on m which is a special case of Theorem 1 in ([3]). We include a proof.

Theorem 1 m ln(m) ≤ ∑_{j=1}^{n} (∑_{ℓ=1}^{k} h_{jℓ}) (∑_{ℓ=1}^{k} −q_{jℓ} ln q_{jℓ}) .

Proof: Intuitively this bound arises as follows. Let R be a random variable which selects one of the m pairwise strongly different vectors (with equal probability). Since there are m choices for R it has entropy m ln(m). Suppose we can ask about any position of R. If the symbol in that position is ordinary we are told its value. If the symbol in that position is ∗ we are randomly told it is an ordinary symbol with random distribution chosen to match the distribution of ordinary symbols in that position of R. (If R is always ∗ in that position the reply can be a_{1} always.) Replying in this way conveys no information about R when the symbol is ∗. So the information about R conveyed is the probability the symbol is ordinary multiplied by the entropy of the distribution of ordinary symbols in that position of R. This is

(∑_{ℓ=1}^{k} p_{jℓ}) ∑_{ℓ=1}^{k} − (\frac{p_{jℓ}}{∑_{r=1}^{k} p_{jr}} ) ln (\frac{p_{jℓ}}{∑_{r=1}^{k} p_{jr}} )

Clearly asking about every position of R determines its value (since the possibilities strongly differ). So the entropy of R must not exceed the sum of the information about R conveyed by each of the position queries. Thus

ln m ≤ ∑_{j=1}^{n} (∑_{ℓ=1}^{k} p_{jℓ}) ∑_{ℓ=1}^{k} − (\frac{p_{jℓ}}{∑_{r=1}^{k} p_{jr}} ) ln (\frac{p_{jℓ}}{∑_{r=1}^{k} p_{jr}} )

or

ln m ≤ ∑_{j=1}^{n} (\frac{∑_{ℓ=1}^{k} h_{jℓ}}{m} ) ∑_{ℓ=1}^{k} −q_{jℓ} ln q_{jℓ},

which can be rewritten as

m ln m ≤ ∑_{j=1}^{n} (∑_{ℓ=1}^{k} h_{jℓ}) ∑_{ℓ=1}^{k} −q_{jℓ} ln q_{jℓ},

which is the bound we wish to prove.

A more rigorous proof follows. Note we have ∑_{ℓ=1}^{k} q_{jℓ} = 1. So we have ∏_{j=1}^{n} (∑_{ℓ=1}^{k} q_{jℓ}) = 1. Now let σ_{j}(x_{ij}) = q_{jℓ} if x_{ij} = a_{ℓ} and let σ_{j}(x_{ij}) = ∑_{ℓ=1}^{k} q_{jℓ} = 1 if x_{ij} = ∗. Associate the ith vector {x_{ij}|j = 1, …, n} with the product ∏_{j=1}^{n} σ_{j}(x_{ij}). Since the m vectors are strongly different the products associated with the different vectors must consist of non-overlapping groups of terms of the product ∏_{j=1}^{n} (∑_{ℓ=1}^{k} q_{jℓ}). Hence we have

∑_{i=1}^{m} ∏_{j=1}^{n} σ_{j}(x_{ij}) ≤ ∏_{j=1}^{n} (∑_{ℓ=1}^{k} q_{jℓ}) = 1.

The rest follows from the arithmetic-geometric mean:

1 ≥ ∑_{i=1}^{m} ∏_{j=1}^{n} σ_{j}(x_{ij})
= ∑_{i=1}^{m} exp (ln ∏_{j=1}^{n} σ_{j}(x_{ij}))
= m ∑_{i=1}^{m} \frac{1}{m} exp (∑_{j=1}^{n} ln σ_{j}(x_{ij}))
≥ m exp (\frac{1}{m} ∑_{i=1}^{m} ∑_{j=1}^{n} ln σ_{j}(x_{ij}))
= m exp (\frac{1}{m} ∑_{j=1}^{n} ∑_{ℓ=1}^{k} h_{jℓ} ln q_{jℓ})

This is readily seen to be equivalent to the inequality in the statement of theorem 1.

As noted above (∑_{ℓ=1}^{k} p_{jℓ}) ∑_{ℓ=1}^{k} − (_{\frac{p_{jℓ}}{∑_{r=1}^{k} p_{jr}}} ) ln (_{\frac{p_{jℓ}}{∑_{r=1}^{k} p_{jr}}} ) can be thought

of as a kind of generalized entropy of column j when the rows are chosen with equal probability. We will need the following lemma about this generalized entropy function.

Lemma 1 Let J(x_{1}, …, x_{n}) = (x_{1} + ⋯ + x_{n})H(\frac{x_{1}}{(x_{1}+···+x_{n})}, …, \frac{x_{n}}{(x_{1}+···+x_{n})}) where H is the ordinary entropy function, 0 < x_{1}, …, x_{n} < 1 and 0 < x_{1} + ⋯ + x_{n} ≤ 1. Then J, like H, is a convex cap function.

Proof: Let a = \frac{λ(x_{1}+···+x_{n})}{λ(x_{1}+···+x_{n})+(1−λ)(y_{1}+···+y_{n})}. Then since H is convex cap

aH (\frac{x_{1}}{(x_{1} + ⋯ + x_{n})}, …, \frac{x_{n}}{(x_{1} + ⋯ + x_{n})})

+(1 − a)H (\frac{y_{1}}{(y_{1} + ⋯ + y_{n})}, …, \frac{y_{n}}{(y_{1} + ⋯ + y_{n})}) ≤

H (\frac{ax_{1}}{(x_{1} + ⋯ + x_{n})} + \frac{(1 − a)y_{1}}{(y_{1} + ⋯ + y_{n})}, …, \frac{ax_{n}}{(x_{1} + ⋯ + x_{n})} + \frac{(1 − a)y_{n}}{(y_{1} + ⋯ + y_{n})})

or multiplying through by λ(x_{1} + ⋯ + x_{n}) + (1 − λ)(y_{1} + ⋯ + y_{n}) and simplifying:

λJ(x_{1}, …, x_{n})+(1−λ)J(y_{1}, …, y_{n}) ≤ J(λx_{1}+(1−λ)y_{1}, …, λx_{n}+(1−λ)y_{n})

which shows J is convex cap.

Identify subsets of an n-set with 0-1 vectors of length n in the usual way. Define ⊖ as follows:

1 ⊖ 0 = 1, 0 ⊖ 0 = 0, 0 ⊖ 1 = −1, 1 ⊖ 1 = ∗.

Let ⊖ operate on vectors componentwise. The definition of ⊖ is motivated by the following lemma.

Lemma 2 Suppose A⊖B is not strongly different from C⊖D. Then A∪D = C ∪ B.

Proof: For each x ∈ {1, …, n}, if (A ⊖ B)_{x} = ∗, then x ∈ A and x ∈ B, so that x ∈ A ∪ D and x ∈ C ∪ B. Similarly if (C ⊖ D)_{x} = ∗, then x ∈ A ∪ D and x ∈ C ∪ B. Otherwise (A ⊖ B)_{x} = (C ⊖ D)_{x} ∈ {−1, 0, 1}, so that x ∈ A ⇔ x ∈ C, and x ∈ B ⇔ x ∈ D. In either case, x ∈ A∪D ⇔ x ∈ C∪B. This holds for all x, and we have A ∪ D = C ∪ B.

Lemma 2 combined with theorem 1 will allow us to bound the number of “nearby” (in the Hamming sense) pairs {A, B} in an union-free family. This in turn will yield bounds on the size of union-free families.

2 Weakly Union-Free Upper Bound

We consider first weakly union-free families. We need the following lemma.

Lemma 3 Let F be a weakly union-free family of subsets of an n-set. Suppose we have four or more pairs (A_{i}, B_{i}) such that A_{i} ∪ B_{i} = X. Then some A ∈ F is a member of every pair (A_{i}, B_{i}).

Proof: It is easy to see the only way to avoid having a common member of every pair is if we have three pairs (A, B), (A, C) and (B, C) with A∪B = A ∪ C = B ∪ C. This is impossible if we have more than three pairs.

We are now ready to prove an upper bound on g(n) which improves the bound g(n) ≤ 2^{[0.75+o(1)]n} of Frankl and Füredi [1]. We will use lg for log_{2}.

Theorem 2

g(n) ≤ 2^{[0.5+o(1)]n}.

Proof: We now use H to denote the binary entropy function. Let F be a weakly union-free family of subsets of an n-set. Suppose F contains 2^{αn} subsets and that each subset in F contains pn elements. Let ϕ(p) be the convex hull of the function H(2p − p^{2})(0 ≤ p ≤ 1). (i.e. ϕ(p) = max {λH(2p_{1} − p_{1}^{2}) + (1 − λ)H(2p_{2} − p_{2}^{2}) | λp_{1} + (1 − λ)p_{2} = p, 0 ≤ λ ≤ 1, 0 ≤ p_{1} ≤ p_{2} ≤ 1\}) Note ϕ(p) ≤ 1. Let β(p) = max[0, \frac{8}{11}p − \frac{3}{11}ϕ(p)]. Note β(p) ≤ p. Consider unions X = A ∪ B of sets A, B ∈ F. Say a union X is good if there are at most 2n2^{nβ(p)} ways of expressing it as X = A_{i} ∪ B_{i} (A_{i}, B_{i} ∈ F). Otherwise say the union is bad.

Suppose first A ∪ B is bad for at most a fraction \frac{1}{n} of the ordered pairs (A, B) (A, B ∈ F). Consider the random variable X = A∪B. It has entropy at least (1 − \frac{1}{n}) lg (\frac{2^{2αn}}{2n2^{nβ(p)}} ) or (2α − β(p))n + o(n) as n → ∞. Consider X to be a 0-1 vector (x_{1}, …, x_{n}). Let p_{i} be the fraction of the sets of F which contain element i. Let h(x_{i}) be the entropy of the ith component of X. Clearly as n → ∞, h(x_{i}) → H(2p_{i} − p_{i}^{2}). Therefore we have

[2α − β(p) + o(1)]n ≤ ∑_{i=1}^{n} H(2p_{i} − p_{i}^{2}) ≤ nϕ(p)

(since pn = ∑ p_{i}). Therefore

αn ≤ \frac{1}{2}[β(p) + ϕ(p) + o(1)]n.

Now β(p) + ϕ(p) = max[ϕ(p), \frac{8}{11}(p + ϕ(p))]. A calculation shows p + ϕ(p) < 1.35 and (\frac{8}{11})(1.35) < 0.982. Therefore β(p) + ϕ(p) ≤ 1. Hence α ≤ \frac{1}{2}[1 + o(1)].

Suppose next A ∪ B is bad for at least \frac{1}{n} of the ordered pairs (A, B) (A, B ∈ F). By Lemma 3 every bad union X has associated with it some set, A_{X}, which is involved in every expression of X. It follows that there is some fixed set A so that at least \frac{1}{2n} of the 2^{αn} (unordered) unions X involving A are bad (with A_{X} = A). Fix some β(p)n of the pn elements of A. Let A′ be the remaining (p − β(p))n elements of A.

Consider the partition, P, of the elements of F into groups depending on the value of A ∪ B, B ∈ F. By the choice of A at least \frac{1}{2n}2^{αn} elements of F lie in groups of size at least 2n2^{nβ(p)}. Now consider the refined partition P′ formed by using the value of A′ ∪ B rather than the value of A ∪ B. Clearly each group of P will be divided into at most 2^{nβ(p)} parts in P′ (since |A − A′| = β(p)n). Hence any group, G, of size at least 2n2^{nβ(p)} in P will be divided into at most 2^{nβ(p)} subgroups of average size at least 2n. Say a subgroup is large iff it has size at least n. It is easy to see this means at least half the sets in the group G will lie in large subgroups in P′ (since 2^{nβ(p)} subgroups of size less than n can account for at most n2^{nβ(p)} elements of G).

Thus we have that at least \frac{1}{4n}2^{αn} sets of F lie in subgroups G′ of size at least n in P′. Divide each such large subgroup G′ into pairs of elements (uniformly) at random. (If the size of G′ is odd leave one element unpaired.) Let m be the total number of pairs. Then we have m ≥ \frac{(1− \frac{1}{n})}{8n}2^{αn}. (The \frac{1}{n} term is due to the possibly unpaired elements.) Let \{(B_{i}, C_{i})\} be the collection of these pairs.

Consider the collection of vectors D_{i} where D_{i} = B_{i} ⊖ C_{i}. Suppose D_{i} ∼ D_{j} (where ∼ means “not strongly different from”). Then B_{i} ⊖ C_{i} ∼ B_{j} ⊖ C_{j}. Then by Lemma 2, B_{i} ∪ C_{j} = B_{j} ∪ C_{i}. Since we are assuming F is weakly union-free, and B_{i}, C_{i}, B_{j}, C_{j} are all distinct, this cannot occur. Therefore all the vectors {D_{i}} must strongly differ. Note since A′ ∪ B_{i} = A′ ∪ C_{i}, B_{i} ⊖ C_{i} will be 0 or ∗ on the complement of A′. So in fact the restrictions of the {D_{i}} to A′ all strongly differ. Fix x ∈ A′. Let random variables n_{1}, n_{2}, n_{3}, n_{4} be the number of times position x of D_{i} is equal to ∗, 1, −1, 0 respectively for our random pairing (B_{i}, C_{i}). We are interested in bounding the expected value, S̄_{x}, of the generalized column entropy S_{x}. Now n_{1} + n_{2} + n_{3} + n_{4} = m.

Set p_{i} = \frac{n_{i}}{n_{2}+n_{3}+n_{4}} , i = 2, 3, 4. Then

\begin{matrix}S_{x} = \frac{n_{2}+n_{3}+n_{4}}{m} × \\ [−\frac{n_{2}}{n_{2}+n_{3}+n_{4}} lg \frac{n_{2}}{n_{2}+n_{3}+n_{4}} − \frac{n_{3}}{n_{2}+n_{3}+n_{4}} lg \frac{n_{3}}{n_{2}+n_{3}+n_{4}} − \frac{n_{4}}{n_{2}+n_{3}+n_{4}} lg \frac{n_{4}}{n_{2}+n_{3}+n_{4}} ] \end{matrix}

= \frac{1}{m} [(n_{2} + n_{3} + n_{4}) lg(n_{2} + n_{3} + n_{4}) − n_{2} lg n_{2} − n_{3} lg n_{3} − n_{4} lg n_{4}] .

It follows from Lemma 1 that S_{x} is a convex cap function of n_{2}, n_{3} and n_{4}.

Therefore the expected value, S̄_{x}, of S_{x} is less than or equal to this function of the expected values of n_{2}, n_{3} and n_{4}. Let n̄_{i} be the expected value of n_{i} (i = 1, …, 4). So we have

S̄_{x} ≤ \frac{1}{m} [(n̄_{2} + n̄_{3} + n̄_{4}) lg(n̄_{2} + n̄_{3} + n̄_{4}) − n̄_{2} lg n̄_{2} − n̄_{3} lg n̄_{3} − n̄_{4} lg n̄_{4}] .

The expected values n̄_{1}, n̄_{2}, n̄_{3} and n̄_{4} are the sums of the corresponding expected values of these quantities for pairs in each large subgroup G′ of P′. The values in each subgroup depend on how many sets in the group contain x. Let the fraction of sets in G′ which contain x be p(G′). Let n̄_{1}(G′), …, n̄_{4}(G′) be the expected counts for pairs in G′. Let G′ have m(G′) pairs. Then

\begin{aligned}n̄_{1}(G′) & = & p(G′)^{2}m(G′) + O(1) \\ n̄_{2}(G′) & = & n̄_{3}(G′) = [p(G′) − p(G′)^{2}]m(G′) + O(1) \\ n̄_{4}(G′) & = & [1 − 2p(G′) + p(G′)^{2}]m(G′) + O(1) \end{aligned}

The O(1) terms arise because we are considering pairs of distinct terms. Since we are considering large subgroups with m(G′) ≥ n they will become negligible as n goes to infinity.

Now the values of n̄_{1}, …, n̄_{4} will be determined by the weighted average values of p(G′) and p(G′)^{2} (weighted by m(G′) for all large subgroups G′ in P′). Let p be the weighted average value of p(G′) and p^{2} + ϵ be the weighted average value of p(G′)^{2} (ϵ ≥ 0 because x^{2} is convex cup). Then

S̄_{x} ≤ \frac{1}{m}[(1 − p^{2} − ϵ)m lg(1 − p^{2} − ϵ)m − 2(p − p^{2} − ϵ)m lg(p − p^{2} − ϵ)m
− (1 − 2p + p^{2} + ϵ)m lg(1 − 2p + p^{2} + ϵ)m + O(m/n)]
= (1 − p^{2} − ϵ) lg(1 − p^{2} − ϵ) − 2(p − p^{2} − ϵ) lg(p − p^{2} − ϵ)
− (1 − 2p + p^{2} + ϵ) lg(1 − 2p + p^{2} + ϵ) + O(1/n).

The right hand side is maximized when p = \frac{1}{3} and ϵ = 0. Hence

S̄_{x} ≤ \frac{4}{3} + O(1/n)

This will be true for each x ∈ A′. Therefore by Theorem 1

lg(m) ≤ \frac{4}{3}(p − β(p))n + O(1)

Now m ≥ (\frac{1− \frac{1}{n}}{8n} ) 2^{αn} so as n → ∞ we have

α ≤ \frac{4}{3}(p − β(p)) + o(1).

Now β(p) = max[0, \frac{8}{11}p − \frac{3}{11}ϕ(p)] so [p − β(p)] = min[p, \frac{3}{11}(p + ϕ(p)] and α ≤ min[\frac{4}{3}p, \frac{4}{11}(p + ϕ(p))] ≤ \frac{4}{11}(p + ϕ(p)).

As above p + ϕ(p) < 1.35 and \frac{4}{11}(p + ϕ(p)) < 0.491. Therefore α < 0.491 + o(1).

Hence, in either case, we have shown α ≤ 0.5 + o(1) as n → ∞.

We assumed that all members of F contained the same number of elements. However, removing this assumption will increase the size of F by at most a factor of n + 1. Thus

g(n) ≤ (n + 1)2^{αn} ≤ (n + 1)2^{[0.5+o(1)]n} = 2^{[0.5+o(1)]n}

which completes the proof.

3 Strongly Union-Free Upper Bound

We now consider strongly union-free families. Recall f(n) is the maximum size of a strongly union-free family of subsets of an n-set. It is easy to see that f(n) ≤ 2^{[0.5+o(1)]n} (see Frankl and Füredi [1]). We show below how to improve this slightly to f(n) ≤ 2^{[0.4998+o(1)]n}. We need the following lemma.

Lemma 4 Let F be a strongly union-free family of subsets of an n-set. Suppose all members of F contain exactly pn elements and that there are 2^{βn} pairs A, B ∈ F such that | A ∩ B |= tn. Then β ≤ (1 − t)H(\frac{p−t}{1−t}, \frac{p−t}{1−t}, \frac{1−2p+t}{1−t}).

Proof: Consider the 2^{βn} vectors A ⊖ B constructed from the 2^{βn} pairs with | A∩B |= tn. Clearly each such vector will contain tn ∗’s, (p−t)n 1’s, (p−t)n −1’s and (1−2p+t)n 0’s. By Lemma 2 these vectors must be strongly different. So by Theorem 1, βn ≤ ∑_{j=1}^{n} J_{i} where J_{i} is the generalized entropy of column i (considering the 2^{βn} vectors as a 2^{βn} by n array). However by Lemma 1 the generalized column entropy function is convex. It follows that ∑_{j=1}^{n} J_{i} ≤ nJ(p−t, p−t, 1−2p+t) = (1−t)nH(\frac{p−t}{1−t}, \frac{p−t}{1−t}, \frac{1−2p+t}{1−t}). The lemma follows.

We can now prove our theorem.

Theorem 3

f(n) ≤ 2^{[0.4998+o(1)]n}.

Proof: Let F be a strongly union-free family of subsets of an n-set. Suppose F contains 2^{(α+o(1))n} subsets. We may neglect terms which can be buried in the o(1) term. So we may assume each subset in F contains exactly pn elements. For each i ∈ {1, …, n} let p_{i} be the fraction of sets in F containing i, so that p = \frac{1}{n} ∑ p_{i}.

As before, let ϕ(p) be the convex hull of the function H(2p−p^{2}) (0 ≤ p ≤ 1). Consider the random variable X = A ∪ B with A, B chosen uniformly and independently from F. Since F is strongly union-free X will take on 2^{[2α+o(1)]n} distinct values and will have entropy (2α + o(1))n. This entropy is upper-bounded by the sum of the entropies of the entries of the random vector X. Thus

(2α + o(1))n ≤ ∑_{i} H(2p_{i} − p_{i}^{2}) ≤ ∑_{i} ϕ(p_{i}) ≤ nϕ(p).

Therefore

α ≤ .5ϕ(p) + o(1) as n → ∞

We will show below how the above bound can be improved by using Lemma 4 for values of p ≤ .3014−. Since .5ϕ(p) attains its maximum of .5 when p = 1 − \sqrt{.5} = .2929− this yields a slight improvement in the overall bound. To apply Lemma 4 we need to show F must contain many pairs of subsets with some relatively large intersection tn. This can be done as follows. Choose the maximal s so that

| F | \binom{pn}{sn} > 2\binom{n}{sn}.  (1)

In the worst case (by which we mean the case for which we will prove the weakest bound), with p = 0.3014− we would have s = 0.2179+. The lefthand side of (1) counts the tuples (B, S) where B ∈ F, S ⊆ B and |S| = sn. The right-hand side of (1) is twice the number of sets S ⊆ {1, …, n} with |S| = sn. A counting argument shows that some tuples must share the same set S: There are at least 2^{[α+o(1)]n}\binom{pn}{sn} triples (B, C, S) with B, C ∈ F; S ⊆ B; S ⊆ C; and |S| = sn, with the two triples (B, C, S) and (C, B, S) counting as one. So we have found pairs of subsets with large intersection. However such pairs may have intersection tn greater than sn. Every such pair will contribute \binom{tn}{sn} triples. Fix a value of t which contributes at least \frac{1}{n} of the triples. Let 2^{βn} be the number of pairs of subsets of F with intersection of size tn. Then we have

2^{βn}\binom{tn}{sn} > 2^{[α+o(1)]n}\binom{pn}{sn}  (2)

where some terms have been incorporated in the o(1). Taking logs and letting n → ∞ equations (1) and (2) become

α + pH (\frac{s}{p}) = H(s)  (3)

β + tH (\frac{s}{t}) ≥ α + pH (\frac{s}{p})  (4)

Furthermore by Lemma 4 we have

β ≤ (1 − t)H (\frac{p − t}{1 − t}, \frac{p − t}{1 − t}, \frac{1 − 2p + t}{1 − t})  (5)

Calculations show that for p ≤ .3014− if we set α = .5ϕ(p), the first bound obtained above, it is impossible to find a value of t, s ≤ t ≤ p so that equations (3), (4) and (5) are satisfied. Let α = ψ(p) be defined as the maximum value of α (as a function of p) which allows equations (3),

(4) and (5) to be satisfied. Further calculations show ψ(p) is increasing for p ≤ .3014−. Therefore the maximum of the combined bounds occurs at p = .3014− at which point α = .4998− = .5ϕ(p), s = .2117+ and t = .2144−. This suffices to prove the theorem.

4 Lower bound on f

We give a construction of a (strongly) union-free family of subsets of an n−set N = {1, …, n}, containing 2^{[δ+o(1)]n} members, where δ > 0.31349. This improves Frankl and Füredi’s [1] bound with δ = \frac{1}{2} lg(\frac{27}{19}) = .2534+.

Theorem 4

f(n) ≥ 2^{[0.31349+o(1)]n}.

Proof: The idea behind our construction is the following. Frankl and Füredi [1] use a simple random construction which shows g(n) ≥ 2^{[0.33333+o(1)]n} which is the best lower bound known for weakly union-free families. However this construction does not work so well for strongly union-free families yielding f(n) ≥ 2^{[0.2534+o(1)]n} as noted above. The problem seems to be the cancellative property. Cancellative families produced by the random construction are much smaller than those which can be explicitly constructed. This suggests trying a combined construction. By basing the random construction on explicitly constructed cancellative families we find it easier to ensure the cancellative property thereby bringing the lower bound for f(n) closer to that for g(n). The details are a little complicated because simpler versions of the idea do not seem to give the best results.

We start by defining constants

α = \frac{1}{63} lg(21 × 3^{19}) ≈ 0.5477238879

β = \frac{1}{63} lg(861 × 15^{19}) ≈ 1.333028425

p = 0.28765
q = 1 − p = 0.71235

ν = solution of [(p − ν)^{4} = ν^{2}(1 − 2p + ν)(2p − ν)] ≈ 0.083426

τ = 4H(p) − 2H(ν, p − ν, p − ν, 1 − 2p + ν) + H(2p − ν) ≈ 0.9992855

Find constants

\begin{aligned}ϵ & ≈ & 0.14521 \\ γ & ≈ & 0.418076 \\ s & ≈ & 0.1106935 \\ δ & ≈ & 0.31349 \end{aligned}

which solve the four equations

ϵ = 2H(p) − H(s, s, p − s, 1 − p − s)
δ = αγ + ϵ(1 − γ)
δ = βγ − τ(1 − γ) + 4ϵ(1 − γ)
δ = (1 − γ) [H(p) − (1 − 2s)H((p − 2s)/(1 − 2s))]

Let k ≈ nγ be a multiple of 63, and set ℓ = n − k. Let K be a specific k−element subset of N, and L its complement. For instance K = {1, ⋯, k} and L = {k + 1, ⋯, n}.

We will use the fact that a violation A ∪ B = A ∪ C of the cancellative property is equivalent to A containing the symmetric difference BΔC = (B − C) ∪ (C − B).

Following Shearer [4], we construct a cancellative family of subsets of K as follows: Break K into k/63 blocks of 63 elements, and further break each 63-block into 21 triplets. Within each triplet, assign the elements labels 0,1,2. For each subset in our family, for each block, select one of the triplets and take all three of its elements; select one element from each other triplet in the block, in such a way that a parity condition holds: the sum of the 20 labels is divisible by 3. The number of choices for each block is then 21×3^{19}, and the total number of subsets is

M_{1} = (21 × 3^{19})^{k/63} = 2^{αk}.

This family is cancellative because if A ∪ B = A ∪ C with B ≠ C, in each block on which B and C differ, there are at least two triplets where (BΔC) contains two members each. (If B and C selected different triplets to take all three members, those two triplets suffice; otherwise the parity condition is used.) But then (BΔC) ⊂ A is impossible.

Corresponding to each member A of this family, select

M_{2} = 2^{ϵℓ}ℓ^{−1}

different subsets R_{A,i} of L, uniformly from those subsets of size

h = ⌊pℓ⌋.

Remark: The factor ℓ^{−1} is chosen to help with the “deletion method” [5]. At each stage below, the expected number of deletions is quadratic or quartic in M_{2}, so that the fraction of elements deleted is linear or cubic in M_{2}. We want each fraction to be bounded by 1/10, and we make M_{2} small accordingly.

For each member A, the expected number of pairs {i, j} such that

|R_{A,i} ∩ R_{A,j}| ≥ (p − s)ℓ.

is

O (M_{2} \frac{M_{2}}{2^{ϵℓ}ℓ^{1/2}} ) ,

and will be bounded by M_{2}/10 for n sufficiently large. Delete one member R_{A,i} of each such pair. We retain at least 0.9M_{2} elements R_{A,i} for each A, all enjoying the small-intersection property

|R_{A,i} ∩ R_{A,j}| < (p − s)ℓ.

This implies a large symmetric difference (|R_{A,i}ΔR_{A,j}| > 2sℓ), unlikely to be contained in some third element R_{B,k}.

Define the family

S = {A ∪ R_{A,i}| all A, i where R_{A,i} retained}

It has M members, denoted A, B, C, D, where 0.9M_{1}M_{2} ≤ M ≤ M_{1}M_{2}.

We will delete some more elements. Whenever A ∩ K = C ∩ K and A ≠ C, we have |AΔC| > 2sℓ, by the small-intersection property. Given any triple (A, B, C) of distinct elements with A ∩ K = C ∩ K and (AΔC) ⊂ B, we delete B. The expected number of such triples is bounded by

∑_{m>sℓ} M_{1}M_{2}^{2} \begin{matrix}( & {ℓ \atop m,m,h−m,ℓ−h−m} & ) \\ \binom{ℓ}{h} & 2 \end{matrix}M_{1}M_{2} \begin{matrix}( & {ℓ−2m \atop h−2m} & ) \\ ( & {ℓ \atop h} & ) \end{matrix}

where m = |A−C|. The summand is clearly maximized when m is minimized (near sℓ); for this value of m we have

M_{2} \begin{matrix}( & {ℓ \atop m,m,h−m,ℓ−h−m} & ) \\ \binom{ℓ}{h} & 2 \end{matrix} = O(ℓ^{−3/2})

and

M_{1}M_{2} \begin{matrix}( & {ℓ−2m \atop h−2m} & ) \\ ( & {ℓ \atop h} & ) \end{matrix} = O(ℓ^{−1}).

So the total number of deletions for m = sℓ is O(M_{1}M_{2}ℓ^{−5/2}), and this number decreases geometrically as m increases. For n sufficiently large, the total number of deletions for all m, namely O(M_{1}M_{2}ℓ^{−5/2}), is bounded by 0.1M_{1}M_{2}, leaving at least 0.8M_{1}M_{2} elements R_{A∩K,i}.

By now S is cancellative: for any instance of A ∪ B = C ∪ B, the cancellative property on K tells us A ∩ K = C ∩ K, and in that case we have deleted any instance where (AΔC) ⊂ B. This ensures A ∪ B ≠ C ∪ B.

To make S weakly union-free (and thus strongly union-free), we first estimate the number of 4-tuples (A, B, C, D) of distinct members violating the weakly union-free property: A ∪ B = C ∪ D.

Let A′ = A ∩ K, B′ = B ∩ K, C′ = C ∩ K and D′ = D ∩ K be among the M_{1} subsets of K being considered. The number of 4-tuples (A′, B′, C′, D′) (with repetition allowed) whose unions agree:

A′ ∪ B′ = C′ ∪ D′

is upper-bounded as follows.

Consider a particular block of 63 elements. If there is only one triplet on which A′ ∪ B′ has all three elements, then the special triplet chosen by A′ is the same one chosen by B′, C′ and D′. There are 21 choices of location for this triplet. For each of 19 other triplets, either the union has one element (in which case B′, C′ and D′ agreed with the choice made by A′), or the union has two elements, in which case B′ disagreed with A′, C′ agreed with either B′ or A′, and the choice of D′ is forced. The total number of choices on this triplet is

3 × 1 × 1 × 1 + 3 × 2 × 2 × 1 = 15.

Values on the last triplet are forced. (Because we want an upper bound, we can ignore the chance that these forced values might cause a disagreement in the unions; taking this into consideration would improve our bound in the fifth decimal place.) The number of choices for one block, in this case, is then at most 21 × 15^{19}.

If A′ ∪ B′ contains all elements of two triplets, then B′ made a different choice of triplet than did A′, and also C′ and D′ made the same choices in some order; the number of such choices is

21 × 20 × 2 × 1 = 840.

The other 19 triplets again allow 15^{19} choices. The triplet chosen by A′ masks one of the triplets of B′, and we let that triplet take care of the parity condition for B′. The number of choices for the block, in this case, is 840 × 15^{19}. Summing, the number of choices of (A′, B′, C′, D′) on one block is bounded by 861 × 15^{19}; and on all k/63 blocks, by

(861 × 15^{19})^{k/63} = 2^{βγn}.

Given a 4-tuple (A, B, C, D) of distinct members whose unions agree on K, we evaluate the probability ρ that the unions agree on L. Consider the contribution to ρ due to instances (A, B, C, D) where |A ∩ B ∩ L| = |C ∩ D ∩ L| = ν′ℓ. Its logarithm, namely,

−ℓ [4H(p) − 2H(ν′, p − ν′, p − ν′, 1 − 2p + ν′) + H(2p − ν′)]− \frac{1}{2} log ℓ+O(1),

is maximized when we select ν′ = ν to be the solution of

(p − ν)^{4} = ν^{2}(1 − 2p + ν)(2p − ν)

lying between 0 and p. With ν and τ as defined above, this gives

ρ = O(2^{−τℓ}ℓ^{−1/2}) = O(2^{−τ(1−γ)n}n^{−1/2}).

So the total number of violations (4-tuples of distinct members satisfying A ∪ B = C ∪ D) is upper-bounded by

O (2^{βγn}2^{−τ(1−γ)n}n^{−1/2}2^{4ϵ(1−γ)n}n^{−4}) = O (Mn^{−7/2})

by our choice of parameters.

For n sufficiently large, this number is less than M/10. For each violation, discard one of the four sets A, B, C, D. Then we retain more than M/2 sets.

Our resulting family has size at least M/2 = 2^{[δ+o(1)]n} and is strongly union-free. This proves the lower bound.

The authors acknowledge the efforts of the referee to improve the presentation of the results in this paper.

References

[1] P. Frankl and Z. Füredi, “Union-free Hypergraphs and Probability Theory”, European Journal of Combinatorics, 5 (1984), pp. 127-131.

[2] M. L. Fredman, “The Complexity of Maintaining an Array and Computing its Partial Sums”, JACM, 29(1982), pp. 250-260.

[3] M. L. Fredman and J. Komlós, “On the Size of Separating Systems and Families of Perfect Hash Functions”, SIAM J. Alg. Disc. Meth., 5 (1984), pp. 61-68.

[4] J. B. Shearer, “A New Construction for Cancellative Sets”, The Electronic Journal of Combinatorics 3(1996), # R15.

[5] J. Spencer, Ten Lectures on the Probabilistic Method, SIAM CBMS 52