On the shadow of squashed families of k-sets

Frédéric Maire

                            maire@fit.qut.edu.au

Neurocomputing Research Center Queensland University of Technology Box 2434 Brisbane Qld 4001, Australia

Abstract: The shadow of a collection A of k-sets is defined as the collection of the (k − 1)-sets which are contained in at least one k-set of A. Given |A|, the size of the shadow is minimum when A is the family of the first k-sets in squashed order (by definition, a k-set A is smaller than a k-set B in the squashed order if the largest element of the symmetric difference of A and B is in B). We give a tight upper bound and an asymptotic formula for the size of the shadow of squashed families of k-sets.

Submitted: January 15, 1995; Accepted: August 25, 1995.

AMS Subject Classification. 04A20,03E05,05A20.

1 Introduction

A hypergraph is a collection of subsets (called edges) of a finite set S. If a hypergraph A is such that A_{i}, A_{j} ∈ A implies A_{i} ⊈ A_{j}, then A is called an antichain. In other words A is a collection of incomparable sets. Antichains are also known under the names simple hypergraph or clutter.

The shadow of a collection A of k-sets (set of size k) is defined as the collection of the (k − 1)-sets which are contained in at least one k-set of A. The shadow of A is denoted by Δ(A).

In the following we assume that S is a set of integers. The squashed order is defined on the the set of k-sets. Given two k-sets A and B, we say that A is smaller than B in the squashed order if the largest element of the symmetric difference of A and B is in B. The first 3-sets in the squashed order are

{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 5}, {1, 3, 5}, ⋯

Let F_{k}(x) denote the family of the first x k-sets in the squashed order. We will prove the following.

Theorem 1 If x ≤ \binom{n}{k} then

|Δ(F_{k}(x))| ≤ kx − x(x − 1) × q_{n,k} where q_{n,k} = \frac{k}{\binom{n}{k} − 1} × \frac{n − k}{n − k + 1}

Equality holds when x = 0 or x = \binom{n}{k}.

Theorem 2 When x → ∞, |Δ(F_{k}(x))| ∼ \frac{k}{\sqrt[k]{k!}} x^{1− \frac{1}{k}}

The squashed order is very useful when dealing with the size of the shadow of a collection of k-sets. The main result is that if you want to minimize the shadow then you have to take the first sets in the squashed order. This is a consequence of the Kruskal-Katona theorem [4, 3]. Before stating their theorem, recall the definition of the l-binomial representation of a number.

Theorem 3 Given positive integers x and l, there exists a unique representation of x (called the l-binomial representation) in the form

x = \binom{x_{l}}{l} + \binom{x_{l−1}}{l − 1} + ⋯ + \binom{x_{t}}{t}

where x_{l} > x_{l−1} > ⋯ > x_{t} ≥ t.

See [1] or [2] for more details.

Theorem 4 (Kruskal-Katona) Let A be a collection of l-sets, and suppose that the l-binomial representation of |A| is

|A| = \binom{x_{l}}{l} + \binom{x_{l−1}}{l − 1} + ⋯ + \binom{x_{t}}{t}

where x_{l} > x_{l−1} > ⋯ > x_{t} ≥ t. Then

|Δ(A)| ≥ \binom{x_{l}}{l − 1} + \binom{x_{l−1}}{l − 2} + ⋯ + \binom{x_{t}}{t − 1}

There is equality when A is the collection of the first |A| l-sets in the squashed order.

Though the above theorem gives the exact values of the shadow when the antichain is squashed, it is awkward to manipulate. Because of this, theorem 1 may be more useful for some problems such as those of construction of completely separating systems (see [5], for example). the electronic journal of combinatorics 2 (1995) #R16 3

2 Proofs

2.1 Proof of theorem 1

We need a few lemmas before proving theorem 1. Lemma 1 The inequality of theorem 1 holds when n ≤ 6. Proof of lemma 1: Done by computer check. Can be done by hand too. □

Lemma 2 The inequality of theorem 1 holds when k = 1. Proof of lemma 2: We have q_{n,1} = 1/n. So the inequality to prove is;

|Δ(F_{1}(x))| ≤ x − x(x − 1) × \frac{1}{n}

The right hand side of the inequality can be rewritten as

\frac{x}{n}(n − x + 1)

As |Δ(F_{1}(x))| is equal to 1 (because Δ(F_{1}(x)) = {∅}), all we have to prove is that

\frac{n}{x} ≤ n − x + 1

i.e.

x^{2} − (n + 1)x + n ≤ 0

The zeroes of this polynomial are 1 and n. This implies that for x in the interval [1, \binom{n}{1}], the inequality holds.□

Lemma 3 The inequality of theorem 1 holds when k = n − 1. Proof of lemma 3: We have q_{n,n−1} = \frac{1}{2}. So the inequality to prove is;

|Δ(F_{n−1}(x))| ≤ x[n − 1 − \frac{x − 1}{2}]

The value of x is in the range [1, n]. If x = n then both sides of the inequality are equal to \binom{n}{2}. Now, assume that x is in the range [1, n − 1]. The (n − 1)-binomial representation of x is:

x = \binom{x_{n−1}}{n − 1} + \binom{x_{n−2}}{n − 2} + ⋯ + \binom{x_{t}}{t}

where x_{n−1} > x_{n−2} > ⋯ > x_{t} ≥ t. As x ≤ n−1, we have x_{n−1} = n−1. And, therefore x_{n−i} = n − i for all i ∈ [1, n − t]. Hence x = n − t. Because of the (n − 1)-binomial representation of x, the size of the shadow of F_{n−1}(x) is given by the formula:

|Δ(F_{n−1}(x))| = \binom{n − 1}{n − 2} + \binom{n − 2}{n − 3} + ⋯ + \binom{t}{t − 1}

i.e.

|Δ(F_{n−1}(x))| = \binom{n − 1}{1} + \binom{n − 2}{1} + ⋯ + \binom{t}{1}

Finally, we have

|Δ(F_{n−1}(x))| = \frac{n(n − 1)}{2} − \frac{t(t − 1)}{2} = \frac{1}{2}(n − t)(n + t − 1)

As x = n − t. By substituting n − x to t in the right hand side, we find that

|Δ(F_{n−1}(x))| = x[n − 1 − \frac{x − 1}{2}]

Which is what we wanted to prove. □

Lemma 4 The inequality of theorem 1 holds when k = n.

Proof of lemma 4: obvious. □

Lemma 5 The function n ⟼ q_{n,k} is decreasing on [k + 1, ∞].

Proof of lemma 5:

q_{n+1,k} − q_{n,k} = \frac{k}{\binom{n+1}{k} − 1} × \frac{n + 1 − k}{n + 2 − k} − \frac{k}{\binom{n}{k} − 1} × \frac{n − k}{n + 1 − k}

which has the same sign as

k(n + 1 − k)^{2} × (\binom{n}{k} − 1) − k(n − k)(n + 2 − k) × (\binom{n + 1}{k} − 1)

which has the same sign as

(n + 1 − k)^{2} × (\binom{n}{k} − 1) − (n − k)(n + 2 − k) × (\binom{n}{k} + \binom{n}{k − 1} − 1)

= \binom{n}{k} − 1 − (n − k)(n − k + 2) × \binom{n}{k − 1}

= \binom{n}{k} − 1 − \binom{n}{k}\frac{k(n − k)(n − k + 2)}{n − k + 1} < 0

□

To prove theorem 1, we use a double induction on k then n. The case k = 1 has been considered in lemma 2. If x ≤ \binom{n−1}{k} then as the function n ⟼ q_{n,k} is decreasing, using the induction hypothesis we are done. Thus, we can assume that x = \binom{n−1}{k} + j with j ≤ \binom{n−1}{k−1}. It is a classical result (see [2] or [1]) that

|Δ(F_{k}(x))| = \binom{n − 1}{k − 1} + |Δ(F_{k−1}(j))|

By induction hypothesis

|Δ(F_{k−1}(j))| ≤ j(k − 1) − j(j − 1) × q_{n−1,k−1}

Combining these inequalities we get:

Claim 1

|Δ(F_{k}(x))| ≤ \binom{n − 1}{k − 1} + j(k − 1) − j(j − 1)q_{n−1,k−1}

If theorem 1 is true then |Δ(F_{k}(x))| ≤ kx − x(x − 1) × q_{n,k} with equality when j = \binom{n−1}{k−1}. Hence, to prove theorem 1 it is sufficient to prove that we have:

\binom{n − 1}{k − 1} + j(k − 1) − j(j − 1)q_{n−1,k−1} ≤ kx − x(x − 1) × q_{n,k}  (⋆)

As k\binom{n−1}{k} = (n − k)\binom{n−1}{k−1} and x = \binom{n−1}{k} + j, (⋆) is equivalent to

x(x − 1)q_{n,k} ≤ (n − k − 1)\binom{n − 1}{k − 1} + j + j(j − 1)q_{n−1,k−1}

To simplify the expressions we introduce some new variables. Let q_{0} = q_{n,k} and q_{1} = q_{n−1,k−1}. Let y = \binom{n−1}{k−1}. We will use later the facts that \binom{n}{k} = \frac{n}{k}y, and that

\binom{n−1}{k} = \frac{n−k}{k}y. With this notation (⋆) is equivalent to

x(x − 1)q_{0} ≤ (n − k − 1)y + j(j − 1)q_{1} + j

As x = \frac{n−k}{k}y + j, we have

x(x − 1)q_{0} = q_{0}j^{2} + q_{0}(2\frac{n − k}{k} y − 1)j + q_{0}(\frac{n − k}{k} y)^{2} − \frac{n − k}{k} yq_{0}

Therefore, (⋆) is equivalent to

0 ≤ j^{2}(q_{1} − q_{0}) − j(−1 + q_{1} − q_{0} + 2\frac{n − k}{k} yq_{0}) + (n − k − 1)y − q_{0}(\frac{n − k}{k} y)^{2} + \frac{n − k}{k} yq_{0}

Finally we have, Claim 2 (⋆) is equivalent to

0 ≤ j^{2}(q_{1} − q_{0}) − j(−1 + q_{1} − q_{0} + 2\frac{n − k}{k} yq_{0}) + (n − k − 1)y + q_{0} \frac{n − k}{k} y(1 − \frac{n − k}{k} y)

Let Φ(j) = j^{2}(q_{1} −q_{0})−j(−1+q_{1} −q_{0} +2\frac{n−k}{k}yq_{0})+(n−k−1)y+q_{0} \frac{n−k}{k}y(1− \frac{n−k}{k}y). We will prove that this polynomial in j is positive on the interval [0, \binom{n−1}{k−1}], by proving that Φ′′ ≥ 0, Φ′(y) ≤ 0 and Φ(y) = 0. Let’s prove that Φ′′ = q_{1} − q_{0} is positive.

q_{0} − q_{1} = [\frac{k}{\binom{n}{k} − 1} − \frac{k − 1}{\binom{n−1}{k−1} − 1}]\frac{n − k}{n − k + 1}

i.e.

q_{0} − q_{1} = [ \frac{k}{\frac{n}{k}y − 1} − \frac{k − 1}{y − 1}]\frac{n − k}{n − k + 1}

The sign of q_{0} − q_{1} is the same as the sign of

k(y − 1) − (k − 1)(\frac{n}{k}y − 1) = ky − k − ny + k + \frac{n}{k}y − 1 = y(k − n + \frac{n}{k}) − 1

Notice that k − n + \frac{n}{k} is negative because k ∈ [2, n − 2]. Indeed, the sign of k − n + \frac{n}{k} is the same as the sign of k^{2} − nk + n. It’s easy to check that this polynomial in k is negative on [2, n − 1] as soon as n ≥ 5. Hence, q_{0} − q_{1} is negative.

Let’s check that (⋆) becomes an equality when j takes the value of y = \binom{n−1}{k−1}. By substituting \binom{n}{k} to x in the right hand side of the inequality of theorem 1, we get \binom{n}{k−1} as expected. By substituting y = \binom{n−1}{k−1} to j in the inequality of claim 1, we obtain also \binom{n}{k−1} (use the induction hypothesis that |Δ(F_{k−1}(y))| = \binom{n−1}{k−2}). This implies that \binom{n−1}{k−1} is a root of the polynomial Φ(j).

To finish the proof of theorem 1 we will prove that y = \binom{n−1}{k−1} is the smaller root of Φ(j), by showing that at that point the derivative of Φ(j) is negative. This will sufficient as we already know that the second derivative is positive. We have

Φ′(y) = 2y(q_{1} − q_{0}) − (−1 + q_{1} − q_{0} + 2\frac{n − k}{k} yq_{0})

the electronic journal of combinatorics 2 (1995) #R16 7 Φ′(y) ≤ 0 is equivalent to

2y(q_{1} − q_{0}) ≤ −1 + q_{1} − q_{0} + 2\frac{n − k}{k} yq_{0}

which is equivalent to

2y(\frac{k − 1}{y − 1} − \frac{k}{\frac{n}{k}y − 1})\frac{n − k}{n − k + 1} ≤ −1 + q_{1} − q_{0} + 2\frac{n − k}{k} y \frac{k}{\frac{n}{k}y − 1} \frac{n − k}{n − k + 1}

which is equivalent to

2y(\frac{k − 1}{y − 1} − \frac{k^{2}}{ny − k}) + \frac{n − k + 1}{n − k} ≤ (q_{1} − q_{0})\frac{n − k + 1}{n − k} + \frac{2(n − k)ky}{ny − k}

i.e.

\frac{2y(k − 1)}{y − 1} + \frac{n − k + 1}{n − k} ≤ (q_{1} − q_{0})\frac{n − k + 1}{n − k} + \frac{2nky}{ny − k}

It is sufficient to prove that

\frac{2y(k − 1)}{y − 1} + \frac{3}{2} ≤ \frac{2nky}{ny − k}

The left hand side is equal to 2k− \frac{1}{2} + \frac{2(k−1)}{y−1}. The right hand side is equal to 2k+ \frac{2k^{2}}{ny−k}. The function t ↦ \frac{−1}{2} + \frac{2(k−1)}{t−1} is negative as soon as t ≥ 4(k − 1) + 1. As n ≥ 7 and k ∈ [2, n − 2], we have y = \binom{n−1}{k−1} ≥ 4(k − 1) + 1. Therefore,

\frac{2y(k − 1)}{y − 1} + 3/2 ≤ \frac{2nky}{ny − k}

This finishes the proof of theorem 1. □

2.2 Proof of theorem 2

Consider the k-binomial representation of x :

x = \binom{x_{k}}{k} + \binom{x_{k−1}}{k − 1} + ⋯ + \binom{x_{t}}{t} where x_{k} > x_{k−1} > ⋯ > x_{t} ≥ t

It is easy to prove that

when x → ∞, x ∼ \binom{x_{k}}{k} and similarly , |Δ(F_{k}(x))| ∼ \binom{x_{k}}{k − 1}

As x ∼ \binom{x_{k}}{k}, we have x ∼ \frac{x_{k}^{k}}{k!} . This implies that x_{k} ∼ (x(k!))^{\frac{1}{k}}. Therefore

\frac{|Δ(F_{k}(x))|}{x} ∼ \begin{matrix}( & {x_{k} \atop k−1} & ) \\ ( & {x_{k} \atop k} & ) \end{matrix} ∼ \frac{k}{x_{k} − k + 1}

Hence \frac{|Δ(F_{k}(x))|}{x} ∼ \frac{k}{(x(k!))^{\frac{1}{k}}} □

References

[1] Anderson I. : Combinatorics of finite sets, Oxford science publication, 1987.

[2] Berge C. : Graphs and Hypergraphs, North-Holland, 1985.

[3] Katona, G. O. H. (1966) : A theorem on finite sets. In ’Theory of Graphs’. Proc. Colloq. Tihany, 1966, pp. 187-207. Akademia Kiado. Academic Press, New York.

[4] Kruskal, J. B. (1963) : The number of simplices in a complex. In ’Mathematical optimization techniques’ (ed. R. Bellman), pp. 251-78. University of California Press, Berkeley.

[5] Ramsey, C., Roberts I. (1994) : Minimal completely separating systems of k-sets. To appear in ’Proc. Colloq. of the 20th Australasian Conference on Combinatorial Mathematics’, Auckland 1994.