An Inequality for Macaulay Functions

Bernardo M. Ábrego and Silvia Fernández-Merchant Department of Mathematics California State University, Northridge 18111 Nordhoff Street Northridge, CA 91330 USA

               bernardo.abrego@csun.edu
               silvia.fernandez@csun.edu

Bernardo Llano Departamento de Matemáticas Universidad Autónoma Metropolitana, Iztapalapa San Rafael Atlixco 186 Colonia Vicentina, 09340, México, D.F. México

                  llano@xanum.uam.mx

Abstract

Given integers k ≥ 1 and n ≥ 0, there is a unique way of writing n as n = \binom{n_{k}}{k} + \binom{n_{k−1}}{k−1} + ⋯ + \binom{n_{1}}{1} so that 0 ≤ n_{1} < ⋯ < n_{k−1} < n_{k}. Using this representation, the k^{th} Macaulay function of n is defined as ∂^{k}(n) = \binom{n_{k}−1}{k−1} + \binom{n_{k−1}−1}{k−2} + ⋯ + \binom{n_{1}−1}{0}. We show that if a ≥ 0 and a < ∂^{k+1}(n), then ∂^{k}(a) + ∂^{k+1}(n − a) ≥ ∂^{k+1}(n). As a corollary, we obtain a short proof of Macaulay’s theorem. Other previously known results are obtained as direct consequences.

1 Introduction

Given integers k ≥ 1 and n ≥ 0, there is a unique way of writing n as

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

so that 0 ≤ n_{1} < n_{2} < ⋯ < n_{k−1} < n_{k}. Using this representation, called the k-binomial representation of n, the k^{th} Macaulay function of n is defined as

∂^{k} (n) = \binom{n_{k} − 1}{k − 1} + \binom{n_{k−1} − 1}{k − 2} + ⋯ + \binom{n_{2} − 1}{1} + \binom{n_{1} − 1}{0}.

(See [2, 6, 12, 14] for details.) The main goal of this paper is to prove the following inequality for Macaulay functions and show some of its consequences.

Theorem 1. Let k, a, and n be integers such that k ≥ 1 and n ≥ a ≥ 0. If a < ∂^{k+1}(n), then

∂^{k} (a) + ∂^{k+1} (n − a) ≥ ∂^{k+1} (n) .  (2)

Moreover, if n = \binom{N}{k+1} for some N ≥ k + 1, then the equality occurs only when a = 0.

Macaulay functions and the related Kruskal–Katona functions (defined below) are relevant for their applications to the study of antichains in multisets (see for example [12, 2]), posets, rings and polyhedral combinatorics (see [5] and the survey [3]). In particular, they play an important role in proving results, extensions and generalizations of classical problems concerning the Kruskal–Katona [13, 11, 16], Macaulay [14], and Erdős-Ko-Rado [9] theorems. More recently, the authors [1] applied Theorem 1 to the problem of finding the maximum number of translated copies of a pattern that can occur among n points in a d-dimensional space, a typical problem related to the study of repeated patterns in Combinatorial Geometry. For every P ⊆ ℝ^{d}, a fixed finite point set (called a pattern), we say that P is a rational simplex if all the points of P are rationally affinely independent. We proved [1] that the maximum number of translated copies of a rational simplex P with |P | = k + 1 determined by a set of n points of ℝ^{d} is equal to n − ∂^{k}(n).

We now introduce some terminology needed to state the Kruskal–Katona and Macaulay theorems. Let M_{k} and S_{k} denote the set of nonincreasing, respectively decreasing, sequences of natural integers of length k, i.e.,

M_{k} = {(x_{1}, x_{2}, …, x_{k}) ∈ ℕ^{k} : x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{k} ≥ 1}
S_{k} = {(x_{1}, x_{2}, …, x_{k}) ∈ ℕ^{k} : x_{1} > x_{2} > ⋯ > x_{k} ≥ 1}.

If A ⊆ M_{k} (or S_{k}), then the shadow of A, denoted by ∂A, consists of all nonincreasing (decreasing) subsequences of length k − 1 of elements of A (∂(∅) = ∅). That is,

∂A = {x : x is a subsequence of y of length k − 1, for some y ∈ A} .

By analogy, one can think of M_{k} (or S_{k}) as multisets (or sets) of size k, with positive integers as elements. In this context ∂A consists of the subsets of multisets (or sets) in A of cardinality k − 1.

The Kruskal–Katona function ∂_{k} (defined below) is the analogue of the Macaulay function defined before. For n as in Identity (1),

∂_{k} (n) = \binom{n_{k}}{k − 1} + \binom{n_{k−1}}{k − 2} + ⋯ + \binom{n_{2}}{1} + \binom{n_{1}}{0}.

The sets of sequences M_{k} and S_{k} are lexicographically ordered. That is, for x and y in M_{k} (or S_{k}), x ≺ y if for some index i, x_{i} < y_{i}, and x_{j} = y_{j} whenever j < i. There is an important relationship between shadows of multisets and sets and the functions ∂^{k} and ∂_{k}. Namely, if we denote by F M_{k}(n) and F S_{k}(n) the first n members, in lexicographic order, of M_{k} and S_{k}, respectively; then

|∂F M_{k} (n)| = ∂^{k} (n) and |∂F S_{k} (n)| = ∂_{k} (n) ..  (3)

The Kruskal–Katona and Macaulay theorems show that in fact ∂_{k}(n) and ∂^{k}(n) are the best lower bounds for the shadow of a set with n elements. Theorem K. (Kruskal [13]–Katona [11]) Let k ≥ 0; for every A ⊆ S_{k+1},

|∂A| ≥ |∂F S_{k+1} (|A|)| = ∂_{k+1} (|A|) .

Theorem M. (Macaulay [14]) Let k ≥ 0; for every A ⊆ M_{k+1},

|∂A| ≥ |∂F M_{k+1} (|A|)| = ∂^{k+1} (|A|) .

The theorems just stated correspond only to the necessity of their polyhedral versions, where f-vectors of complexes or multi-complexes are characterized by these inequalities.

We present, in Section 2, a short and simple proof of Theorem M obtained as a corollary of Theorem 1. For a short textbook proof of Theorem K, see Frankl’s proof [10]. For an approach similar to ours, we point out that Eckhoff and Wegner [8], (see also Daykin [7]) obtained a proof of Theorem K as a consequence of an inequality similar to Inequality (2). Namely, for n ≥ a ≥ 0,

max (∂_{k}(a), n − a) + ∂_{k+1} (n − a) ≥ ∂_{k+1} (n) .  (4)

The equivalent inequality to Inequality (4) for the functions ∂^{k} and ∂^{k+1} is true, and it was in fact generalized by Björner and Vrećica [5] to a larger number of terms (see Corollary 3). The proof of their result depends on Macaulay’s theorem. However, we are not aware of, nor could we find, a proof of Theorem M obtained as a consequence of this result. We show, in Section 2, how Björner and Vrećica’s inequalities follow easily from Theorem 1.

Our proof of Theorem 1, presented in Section 3, is elementary as it only relies on properties of binomial coefficients. Some of the ideas are similar to those used in [8] for the proof of Inequality (4).

The condition a < ∂^{k+1}(n) in Theorem 1 cannot be strengthened. For instance, whenever k ≥ 2, a = ∂^{k+1}(n), and the last three coefficients of the (k + 1)-binomial representation of n are n_{1} = 1, n_{2} = 2, and n_{3} = 4; it follows that

∂^{k} (a) + ∂^{k+1} (n − a) = ∂^{k+1} (n) − 1 < ∂^{k+1} (n) .

Finally, it is an interesting open problem to determine the pairs (n, a) with a < ∂^{k+1}(n) that achieve equality in Inequality (2). So far we were able to classify the pairs when n is of the form \binom{N}{k+1}. The solution to this problem would be the first step to classify all patterns P for which the maximum number of translates of P, among n points in ℝ^{d}; is equal to n − ∂^{k}(n).

2 Consequences of the theorem

We first prove Macaulay’s theorem as a corollary of Theorem 1.

Proof of Theorem M. Let A ⊆ M_{k+1}. We proceed by induction on k + |A|. If k = 0 or A = ∅, the result is trivially true. Suppose k ≥ 1 and A ≠ ∅. Set A_{11} = {x ∈ M_{k} : x_{k} = 1 and x ∗ 1 ∈ A}, A_{12} = {x ∈ M_{k} : x_{k} ≥ 2 and x ∗ 1 ∈ A}, and A_{2} = {x ∈ A : x_{k+1} ≥ 2}. Here x ∗ 1 denotes the concatenation of x and 1, that is x ∗ 1 is the k-tuple x with an entry 1 appended in the (k +1)^{th} position. Clearly, A = (A_{11} ∗1)∪(A_{12} ∗1)∪A_{2} and the terms in the union are pairwise disjoint. Moreover, we can assume that A_{11} ∪ A_{12} ≠ ∅. Otherwise, since all entries of members of A are ≥ 2, we can work with the set A′ obtained by subtracting 1 to every entry in the sequences of A (|A′| = |A| and |∂A′| = |∂A|.) Let a = |A_{11}| + |A_{12}| and b = |A_{2}|. Note that |A| = a + b and a ≥ 1.

If x = (x_{1}, x_{2}, …, x_{k}) ∈ A_{11}, then (x_{1}, x_{2}, …, x_{k−1}) ∈ ∂A_{11} and (x_{1}, x_{2}, …, x_{k−1}, 1) = x ∈ ∂A_{11} ∗ 1. That is, A_{11} ⊆ ∂A_{11} ∗ 1. We now calculate ∂A in terms of A_{11}, A_{12}, and A_{2}. We use the property that ∂(A ∪ B) = ∂A ∪ ∂B.

∂A = ∂A_{2} ∪ A_{12} ∪ A_{11} ∪ (∂A_{11} ∗ 1) ∪ (∂A_{12} ∗ 1)
= ∂A_{2} ∪ A_{12} ∪ (∂A_{11} ∗ 1) ∪ (∂A_{12} ∗ 1)
= (∂A_{2} ∪ A_{12}) ∪ (∂(A_{11} ∪ A_{12}) ∗ 1) .

If x ∈ (∂A_{2} ∪ A_{12}), then x_{k} ≥ 2. Thus

(∂A_{2} ∪ A_{12}) ∩ (∂(A_{11} ∪ A_{12}) ∗ 1) = ∅,

and consequently

|∂A| = |∂A_{2} ∪ A_{12}| + |∂(A_{11} ∪ A_{12})|.  (5)

We consider two cases. If a ≥ ∂^{k+1}(|A|), then

|∂A| = |∂A_{2} ∪ A_{12}| + |∂(A_{11} ∪ A_{12})| ≥ |A_{12}| + |A_{11}| = a ≥ ∂^{k+1}(|A|).

Assume a < ∂^{k+1}(|A|). Since a ≥ 1 then b < |A| and thus, by induction and Identity (3),

|∂A_{2} ∪ A_{12}| ≥ |∂A_{2}| ≥ |∂F_{k+1} (b)| = ∂^{k+1}(b) and
|∂(A_{11} ∪ A_{12})| ≥ |∂F_{k} (a)| = ∂^{k}(a).

Therefore, by Identity (5), Theorem 1, and Identity (3); it follows that

|∂A| ≥ ∂^{k+1}(b) + ∂^{k}(a) ≥ ∂^{k+1}(|A|) = |∂F_{k+1} (|A|)| .

In terms of shadows of sets, and using our previous corollary, Theorem 1 can be generalized as follows.

Corollary 2. Given sets A ⊆ M_{k} and B ⊆ M_{k+1} with |A| < |∂F_{k+1}(|A| + |B|)| we have

|∂A| + |∂B| ≥ |∂F_{k+1} (|A| + |B|)| .

Proof. By the previous corollary and Identity (3), |∂A| + |∂B| ≥ ∂^{k}(|A|)+ ∂^{k+1}(|B|) and |A| < ∂^{k+1}(|A| + |B|). Thus, by Theorem 1, ∂^{k}(|A|)+ ∂^{k+1}(|B|) ≥ |∂F_{k+1}(|A| + |B|)|.

The following inequality, proved by Björner and Vrećica, follows directly from our Theorem. We recall that their proof makes use of Macaulay’s theorem. Note that r = 1, n_{0} = a, and n_{1} = n − a give the equivalent inequality to Inequality (4) for the function ∂^{k}.

Corollary 3. (Lemma 3.2 [4], also Lemma 2.1 [15]). For k > 0, the function ∂^{k} satisfies that

∂^{k} (∑_{i=0}^{r} n_{i}) ≤ ∑_{i=0}^{r} max {n_{i+1}, ∂^{k−i} (n_{i})} ,

∂^{k} (1 + ∑_{i=0}^{k} n_{i}) ≤ 1 + ∑_{i=0}^{k−1} max {n_{i+1}, ∂^{k−i} (n_{i})}.

for all nonnegative integers n_{i} and r < k.

Proof. By induction on k. If k = 1 the inequalities are trivially true.

Let r < k + 1, a = ∑_{i=1}^{r} n_{i}, and n = ∑_{i=0}^{r} n_{i}. If a ≥ ∂^{k+1}(n), then

∂^{k+1} (∑_{i=0}^{r} n_{i}) = ∂^{k+1} (n) ≤ a = ∑_{i=1}^{r} n_{i} ≤ ∑_{i=0}^{r−1} max {n_{i+1}, ∂^{k+1−i} (n_{i})}

≤ ∑_{i=0}^{r} max {n_{i+1}, ∂^{k+1−i} (n_{i})}.

If on the other hand, a < ∂^{k+1}(n), then by Theorem 1,

∂^{k+1} (∑_{i=0}^{r} n_{i}) = ∂^{k+1} (n) ≤ ∂^{k+1} (n − a) + ∂^{k} (a) = ∂^{k+1} (n_{0}) + ∂^{k} (∑_{i=0}^{r−1} n_{i+1});

then by induction,

∂^{k+1} (∑_{i=0}^{r} n_{i}) ≤ ∂^{k+1} (n_{0}) + ∑_{i=0}^{r−1} max {n_{i+2}, ∂^{k−i} (n_{i+1})}

≤ ∑_{i=0}^{r} max {n_{i+1}, ∂^{k+1−i} (n_{i})}.

This proves the first inequality. The second inequality is proved exactly the same way by letting a = 1 + ∑_{i=1}^{k+1} n_{i} and n = 1 + ∑_{i=0}^{k+1} n_{i}.

3 Proof of the theorem

We first present a simple observation. If n > k ≥ 0 then by Pascal’s identity

\binom{n}{k} = \binom{n − 1}{k} + \binom{n − 2}{k − 1} + ⋯ + \binom{n − k}{1} + \binom{n − k − 1}{0}.  (6)

Let a = ∑_{i=1}^{k} \binom{a_{i}}{i} be the k-binomial representation of a. We say that a is k-long if a_{1} ≥ 1, and k-short if a_{1} = 0.

Lemma 4. Let a ≥ 0 be an integer. If a is k-short, then ∂^{k}(a + 1) = ∂^{k}(a) + 1, otherwise ∂^{k}(a + 1) = ∂^{k}(a).

Proof. The result is clear for a = 0. If a ≥ 1 is k-short, then a = ∑_{i=v}^{k} \binom{a_{i}}{i} for some v ≥ 2 and a_{v} ≥ v. Thus a + 1 = ∑_{i=v}^{k} \binom{a_{i}}{i} + \binom{v−1}{v−1} is the k-binomial representation of a + 1 where all the zero terms have been omitted. Then ∂^{k}(a + 1) = ∂^{k}(a) + \binom{v−2}{v−2} = ∂^{k}(a) + 1.

Now suppose a is k-long. There is v ≥ 2 such that a_{j} = a_{1} + j − 1 for j < v, and either v = k + 1 or v ≤ k and a_{v} > a_{1} + v − 1. Then

a + 1 = \binom{a_{k}}{k} + ⋯ + \binom{a_{v}}{v} + \binom{a_{1} + v − 2}{v − 1} + ⋯ + \binom{a_{1} + 1}{2} + \binom{a_{1}}{1} + \binom{a_{1} − 1}{0}

and by Identity (6) the k-binomial representation of a + 1 is

a + 1 = \binom{a_{k}}{k} + ⋯ + \binom{a_{v}}{v} + \binom{a_{1} + v − 1}{v − 1}.

Then, again by Identity (6),

∂^{k}(a + 1) − ∂^{k}(a) = \binom{a_{1} + v − 2}{v − 2} − (\binom{a_{1} + v − 3}{v − 2} + ⋯ + \binom{a_{1}}{1} + \binom{a_{1} − 1}{0}) = 0.

To prove the Theorem, we need to consider the extended k-binomial representation of a positive integer a, by requiring an a_{0} coefficient. That is, we write

a = \binom{a′_{k}}{k} + \binom{a′_{k−1}}{k − 1} + ⋯ + \binom{a′_{2}}{2} + \binom{a′_{1}}{1} + \binom{a′_{0}}{0},

with 0 ≤ a′_{0} = a′_{1} − 1 < a′_{1} < ⋯ < a′_{k}. The condition a′_{0} = a′_{1} − 1 is necessary to make this representation unique when it exists. Clearly a = 0 does not have an extended representation. In general the following is true.

Lemma 5. Let a = ∑_{i=v}^{k} \binom{a_{i}}{i} ≥ 1 be the k-binomial representation of a, where the terms equal to zero have been omitted. The extended k-binomial representation of a exists (and it is unique), if and only if a_{v} ≥ v + 1.

Proof. If a_{v} ≥ v + 1, then, by Identity (6),

\binom{a_{v}}{v} = \binom{a_{v} − 1}{v} + \binom{a_{v} − 2}{v − 1} + ⋯ + \binom{a_{v} − v − 1}{0}.

Thus

a = ∑_{i=v+1}^{k} \binom{a_{i}}{i} + ∑_{i=0}^{v} \binom{a_{v} − v − 1 + i}{i}

is an extended k-representation of a. Reciprocally, if a = ∑_{i=0}^{k} \binom{a′_{i}}{i} is an extended krepresentation, then \binom{a′_{0}}{0} = \binom{a′_{1}−1}{0}, and there is v ≥ 1 such that a′_{j} = a′_{1} + j − 1 for 0 ≤ j ≤ v with either v = k or a′_{v+1} > a′_{1} + v. Then, by Identity (6 ),

a = ∑_{i=v+1}^{k} \binom{a′_{j}}{j} + ∑_{j=0}^{v} \binom{a′_{1} + j − 1}{j} = ∑_{i=v+1}^{k} \binom{a′_{j}}{j} + \binom{a′_{1} + v}{v},

is the k-representation of a. Thus a_{v} = a′_{1} + v ≥ v + 1.

We can define ∂_{e}^{k}(a) = ∑_{i=1}^{k} \binom{a′_{i}−1}{i−1} for the extended k-representation of a (if it exists). It turns out that both definitions agree, i.e., ∂^{k}(a) = ∂_{e}^{k}(a). Indeed, if a = ∑_{i=v}^{k} \binom{a_{i}}{i} with a_{v} ≥ v + 1, then by Identity (6) and the last proof,

∂^{k}(a) − ∂_{e}^{k}(a) = \binom{a_{v}−1}{v−1} − ∑_{i=0}^{v} \binom{a_{v} − v − 2 + i}{i − 1} = 0.

Let n = ∑_{i=1}^{k+1} \binom{n_{i}}{i}, a = ∑_{i=1}^{k} \binom{a_{i}}{i}, and n−a = b = ∑_{i=1}^{k+1} \binom{b_{i}}{i} be binomial representations.

Lemma 6. If 0 ≤ a < ∂^{k+1}(n), then a_{k} < n_{k+1} ≤ b_{k+1} + 1.

Proof. We prove the contrapositives. If a_{k} ≥ n_{k+1}, then

a ≥ \binom{a_{k}}{k} ≥ \binom{n_{k+1}}{k} = ∂^{k+1} (\binom{n_{k+1} + 1}{k + 1}) ≥ ∂^{k+1} (n) ,

since \binom{n_{k+1}+1}{k+1} ≥ n and ∂^{k+1} is a non-decreasing function by Lemma 4. Now, if b_{k+1} + 1 ≤ n_{k+1} − 1, then b < \binom{b_{k+1}+1}{k+1} ≤ \binom{n_{k+1}−1}{k+1}. Thus

a = n − b > n − \binom{n_{k+1} − 1}{k + 1} = \binom{n_{k+1} − 1}{k} + \binom{n_{k}}{k} + \binom{n_{k−1}}{k − 1} + ⋯ + \binom{n_{1}}{1},

but

∂^{k+1} (n) = \binom{n_{k+1} − 1}{k} + \binom{n_{k} − 1}{k − 1} + \binom{n_{k−1} − 1}{k − 2} + ⋯ + \binom{n_{1} − 1}{0},

and clearly \binom{n_{i}}{i} ≥ \binom{n_{i}−1}{i−1}. Thus a ≥ ∂^{k+1} (n) .

Proof of Theorem 1. Recall that b = n − a. Clearly Inequality (2) holds if a = 0, and the case a = 1 is a consequence of Lemma 4. We consider two cases. Case 1. a_{k} < b_{k+1}.

Let a = ∑_{i=v}^{k} \binom{a_{i}}{i} ≥ 2 be the k-binomial representation of a without the zero terms. Assume that the pair (a, b) minimizes ∂^{k}(a)+ ∂^{k+1}(b) with a as small as possible.

(i) Suppose first that a_{v} ≥ v + 1. Then, by Lemma 5, a has an extended representation, say a = ∑_{i=0}^{k} \binom{a′_{i}}{i}. Let

α = ∑_{i=1}^{k} \binom{min(a′_{i}, b_{i})}{i} and β = \binom{b_{k+1}}{k + 1} + ∑_{i=1}^{k} \binom{max(a′_{i}, b_{i})}{i} + \binom{a′_{0}}{0}.

Note that a + b = α + β and α < a. Also

0 ≤ min(a′_{1}, b_{1}) < min(a′_{2}, b_{2}) < ⋯ < min(a′_{k}, b_{k}) and
0 ≤ a′_{0} < max(a′_{1}, b_{1}) < ⋯ < max(a′_{k}, b_{k}) < b_{k+1}

(since a′_{k} ≤ a_{k} < b_{k+1} by assumption). Therefore the definitions we gave for α and β are k-binomial representations (extended for β). This means that

∂^{k} (α) + ∂^{k+1} (β) = ∂^{k} (α) + ∂_{e}^{k+1} (β) = ∂^{k} (a) + ∂^{k+1} (b) ,

a contradiction to the minimality of a.

(ii) Assume now that a_{v} = v. This means that a − 1 = a − \binom{a_{v}}{v} = ∑_{i=v+1}^{k} \binom{a_{i}}{i} ≥ 1 is the k-representation of a − 1, and thus a − 1 is short. Then by Lemma 4,

∂^{k}(a − 1) + ∂^{k+1}(b + 1) = ∂^{k}(a) − 1 + ∂^{k+1}(b + 1) ≤ ∂^{k}(a) + ∂^{k+1}(b),

again a contradiction to the minimality of a.

Case 1 is settled. Case 2. b_{k+1} ≤ a_{k}.

Since a < ∂^{k+1}(n) then, by Lemma 6, a_{k} < n_{k+1} ≤ b_{k+1}+1. That is, a_{k} = b_{k+1} = n_{k+1}−1. We proceed by induction on k. If k = 1, then a_{1} = b_{2} = n_{2} − 1. Thus

\binom{n_{2}}{2} + \binom{n_{1}}{1} = n = a + b = \binom{n_{2} − 1}{1} + \binom{n_{2} − 1}{2} + \binom{b_{1}}{1},

i.e., b_{1} = n_{1}. Hence,

∂^{1} (a) + ∂^{2} (b) = \binom{n_{2} − 2}{0} + \binom{n_{2} − 2}{1} + \binom{n_{1} − 1}{0} = ∂^{2} (n) .

Assume k ≥ 2 and that the result holds for k−1. Let n′ = n−\binom{n_{k+1}}{k+1}, b′ = b−\binom{n_{k+1}−1}{k+1}, and a′ = a − \binom{n_{k+1}−1}{k}. Because a ≥ \binom{a_{k}}{k} = \binom{n_{k+1}−1}{k}, it follows that a′ ≥ 0. Clearly, a′ + b′ = n′, and a′ < ∂^{k}(n′) since a < ∂^{k+1}(n) = \binom{n_{k+1}−1}{k}+ ∂^{k}(n′). By induction on k the result holds for a′, b′, n′, and thus

∂^{k+1} (b) + ∂^{k} (a) − ∂^{k+1} (n) = \binom{n_{k+1} − 2}{k} + ∂^{k} (b′) + \binom{n_{k+1} − 2}{k − 1} + ∂^{k−1} (a′)

− \binom{n_{k+1} − 1}{k} − ∂^{k} (n′)

= ∂^{k} (b′) + ∂^{k−1} (a′) − ∂^{k} (n′) ≥ 0.

Case 2 is now proved.

It is only left to be shown that if n = \binom{N}{k+1} for some N ≥ k + 1, then there is equality in Inequality (2), i.e.,

∂^{k} (a) + ∂^{k+1} (\binom{N}{k + 1} − a) = ∂^{k+1} (\binom{N}{k + 1}) ,  (7)

occurs only when a = 0.

If N = k + 1 (and thus a = 0) or a = 0, the equality trivially holds. Suppose that N ≥ k + 2, a ≥ 1, and Identity (7) holds. Let b = \binom{N}{k+1} − a; as before, we consider two cases. First suppose that a_{k} < b_{k+1}. Assume that a and b are the smallest integers such that Identity (7) is satisfied with a ≥ 1. If a = 1, then by Identity (6),

\binom{N}{k + 1} − 1 = \binom{N − 1}{k + 1} + \binom{N − 2}{k} + ⋯ + \binom{N − k − 1}{1}

is (k+1)-long. Thus, by Lemma 4, ∂^{k+1}(\binom{N}{k+1}−1) = ∂^{k+1}(\binom{N}{k+1}) < 1+∂^{k+1}(\binom{N}{k+1}−1), which is a contradiction. If a ≥ 2, then we proceed as in Case 1 to get a contradiction. Now assume that b_{k+1} ≤ a_{k}. In this case, a_{k} < N ≤ b_{k+1} + 1 and following the proof of Case 2, we have that a_{k} = b_{k+1} = N − 1, a contradiction since \binom{N−1}{k} = \binom{a_{k}}{k} ≤ a < ∂^{k+1}(\binom{N}{k+1}) = \binom{N−1}{k}.

4 Acknowledgements

We are grateful to Hans Fetter and A. Paulina Figueroa for their valuable help during the preparation of this paper as well as to Eduardo Rivera-Campo for useful comments and suggestions.

References

[1] B. M. Ábrego, S. Fernández-Merchant and B. Llano, On the maximum number of translates in a point set, Discrete Comput. Geom. 43 (2010), 1–20.

[2] I. Anderson, Combinatorics of Finite Sets, Dover Publications, 2002.

[3] S. L. Bezrukov and U. Leck, Macaulay posets (dynamic survey), Electron. J. of Combin. (2005) #DS12, 40 pp.

[4] A. Björner and S. Vrećica, On f-vectors and Betti numbers of multicomplexes, Combinatorica 17 (1997), 53–65.

[5] L. J. Billera and A. Björner, Face numbers of polytopes and complexes, in J. E. Goodman and J. O’Rourke, eds., Handbook of Discrete and Computational Geometry, CRC Press Ser. Discrete Math., 1997, pp. 291–310.

[6] G. F. Clements and B. Lindström, A generalization of a combinatorial theorem of Macaulay. J. Combinatorial Theory 7 (1969), 230–238.

[7] D. E. Daykin, Antichains in the lattice of subsets of a finite set. Nanta Math. 8 (1975), 78–83.

[8] J. Eckhoff and G. Wegner, Über einen Satz von Kruskal, Periodica Math. Hung. 6 (1975), 137–142.

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

[10] P. Frankl, A new short proof of the Kruskal–Katona theorem, Discrete Math. 48 (1984), 327–329.

[11] G. O. H. Katona, A theorem of finite sets, in Theory of Graphs. (Proc. Colloq., Tihany, 1966), Academic Press, 1968, pp. 187–207.

[12] D. E. Knuth, The Art of Computer Programming, Vol. 4, Fasc 3. Generating all combinations and partitions. Addison-Wesley, 2005.

[13] J. B. Kruskal, The number of simplices in a complex, in R. Bellman ed., Mathematical Optimization Techniques, Univ. of California Press, 1963, pp. 251–278.

[14] F. S. Macaulay, Some properties of enumeration in theory of modular systems. Proc. London Math. Soc. 26 (1927), 531–555.

[15] E. Nevo, A generalized Macaulay theorem and generalized face rings. J. Combin. Theory Ser. A 113 (2006), 1321–1331.

[16] G. Wegner, Kruskal–Katona’s theorem in generalized complexes, in Finite and Infinite Sets, Vol. II , North-Holland, 1984, pp. 821–828.

2000 Mathematics Subject Classification: Primary 05A05; Secondary 05A20. Keywords: Macaulay function, Macaulay’s theorem, binomial representation of a positive integer, shadow of a set.

(Concerned with sequences \underline{A123578}, \underline{A123579}, \underline{A123580}, and \underline{A123731} .)

Received December 18 2010; revised version received July 8 2011. Published in Journal of Integer Sequences, September 5 2011.

Return to Journal of Integer Sequences home page.