LINEAR INEQUALITIES FOR FLAGS IN GRADED POSETS^{∗}

LOUIS J. BILLERA^{†} AND GÁBOR HETYEI^{‡}

Abstract. The closure of the convex cone generated by all flag f-vectors of graded posets is shown to be polyhedral. In particular, we give the facet inequalities to the polar cone of all nonnegative chain-enumeration functionals on this class of posets. These are in one-to-one correspondence with antichains of intervals on the set of ranks and thus are counted by Catalan numbers. Furthermore, we prove that the convolution operation introduced by Kalai assigns extreme rays to pairs of extreme rays in most cases. We describe the strongest possible inequalities for graded posets of rank at most 5.

Introduction

An initial step in obtaining a characterization of f-vectors of some class of objects is to determine the linear equations and inequalities that they must satisfy. The former give a description of the linear span of all such f-vectors, while the latter describe the closure of the convex cone they generate. In most cases where this has been done successfully, the description of the linear equations proved to be the more difficult part. Once this was done, and an appropriate basis found for the linear span of all f-vectors (for example, the f-vector in the case of simplicial complexes, the h-vector in the case of Cohen-Macaulay simplicial complexes, or the g-vector in the case of simplicial convex polytopes), the desired cone turned out to be an orthant, that is, only nonnegativity of the basic invariants could be asserted. (See, for example, [6, Theorems II.2.1, II.3.3 & III.1.1].)

The situation of flag f-vectors seems to be be quite different. While it is true that flag h-vectors of balanced Cohen-Macaulay complexes (even Cohen-Macaulay ranked posets – see [6, §III.4]) span an orthant, the more basic case of flag f-vectors of graded posets behaves quite differently. Here, it is the first of these that is simple: there are no equations. However, the cone generated in this case turns out to be quite a bit more complicated. In this paper, we give a description of this cone by giving its minimal generating set. It is already a nontrivial statement that this generating set is finite. Equivalently, we give a finite list of linear inequalities that describe the cone polar to that generated by all flag f-vectors of graded posets. For posets of rank n + 1, these inequalities are in one-one correspondence with antichains of intervals in the linearly ordered set {1, 2, …, n}, an so are counted by a Catalan number. Thus while the space of flag f-vectors has dimension 2^{n}, the cone they generate will have on the order of (2n)^{n} generators.

∗Research at MSRI supported in part by NSF grant DMS-9022140.

†On leave from Cornell University, Ithaca, NY. Supported in part by NSF grant DMS-9500581.

‡On leave from the Mathematical Research Institute of the Hungarian Academy of Sciences.

Partially supported by Hungarian National Foundation for Scientific Research grant no. F 023436.

The proof of the fact that our list of linear inequalities describes a set of generators for the cone of flag f-vectors relies on two ingredients: an explicit construction of sequences of graded posets P (n, I, N) of rank n + 1 yielding the extreme rays of the closure as limits, and an explicit partitioning of the maximal chains of every graded poset P which allows to show the sufficiency of our list of conditions. The chain partitioning used may be generalized to a construction showing that every graded poset satisfies a generalized condition of lexicographic shellability, allowing an explicit description of the order complex of every graded poset. This will be the subject of a subsequent paper.

While the description of the extreme rays of the closure of the convex cone generated by the flag f-vectors of graded posets of a given rank is fairly tractable, finding even the number of the facets of the same cone seems to be highly difficult. These represent the strongest possible inequalities holding for flag f-vectors of graded posets of a given rank, and correspond to the extreme rays of the polar cone. In section 5 we show operations which yield higher-rank extremes from lower rank ones. There are lifting operations, embedding the cones of inequalities into each other as faces, and we give an exact description of those situation where the convolution operation introduced by Kalai in [5] assigns an extreme inequality to a pair of extreme inequalities. These results allow a short description of the extreme inequalities up to rank 5.

1. Preliminaries

Here we enumerate the basic definitions and results used in this paper.

1.1. Graded partially ordered sets.

Definition 1. A graded poset P is a finite poset with a unique minimum element ˆ0, a unique maximum element ˆ1, and a rank function rank : P ⟶ ℕ such that we have

(i) rank(ˆ0) = 0, and (ii) rank(y) − rank(x) = 1 whenever y ∈ P covers x ∈ P.

We call rank(ˆ1) ≥ 1 the rank of the poset P. Given a graded poset P of rank n+1, and a subset S of {1, 2, …, n} we define the S–rank selected subposet of P to be the poset

P_{S} := {x ∈ P : rank(x) ∈ S} ∪ {ˆ0, ˆ1}.

We denote by f_{S}(P) the number of maximal chains of P_{S}. Equivalently, f_{S}(P) is the number of chains x_{1} < ⋯ < x_{|S|} in P such that {rank(x_{1}), …, rank(x_{|S|})} = S. The function

\begin{aligned}f : & 2^{\{1,2,... ,n\}} & ⟶ & ℕ \\ & S & ⟼ & f_{S}(P) \end{aligned}

is called the flag f-vector of P. Whenever it does not cause confusion we will write f_{s_{1} ... s_{k}} rather than f_{{s_{1},... ,s_{k}}}; in particular, f_{{m}} will always be denoted f_{m}.

A simple example is perhaps helpful here. Consider graded posets of rank 2. In addition to elements ˆ0 and ˆ1 of rank 0 and 2, respectively, such a poset will have only elements of rank 1. For reasons that will become clear later, we wish to consider the closure of the convex cone generated by

{(f_{∅}(P), f_{1}(P)) | rank(P) = 2} = {(1, n) | n ≥ 0}.

The polar of this cone is generated by the functionals h_{∅} := f_{∅} and h_{1} := f_{1} − f_{∅}.

1.2. The ring of chain operators. We adopt the following terminology and results from [1]. The chain operators f_{S}^{n+1} assign f_{S}(P) to every graded poset P of rank n+1, and zero to all other graded posets. These operators are linearly independent and hence they generate a vector space A_{n+1} of dimension 2^{n} over ℝ. We set A_{0} = ℝ. The vector space A := ⨁_{n≥0} A_{n} may be made into a graded noncommutative ring by introducing the convolution operation (first considered by Kalai in [5])

f_{S}^{m} ∗ f_{T}^{n} := f_{S∪{m}∪(T +m)}^{m+n}

for m, n ≥ 1, and by making the generator 1 of A_{0} to be the unit of A. The interest of this convolution operation is the following. (cf. [1, Proposition 1.3])

Proposition 1. The convolution F ∗G of two linear combinations of chain operators is nonnegative on all graded posets if and only if both F and G are simultaneously nonnegative or nonpositive on all graded posets.

According to [1, Proposition 1.1] the chain operators are linearly independent. Moreover, in [1, Section 2] we find the following:

Proposition 2. The ring A is a free graded associative algebra over the set of variables {f_{∅}^{n} : n ≥ 1}.

It follows from [2, Theorem 3] that the semigroup of homogeneous polynomials of a a free graded associative algebra has unique factorization. Hence we have the following

Proposition 3. Up to nonzero linear factors, every form F ∈ A_{n} may be uniquely written as a product F = F^{n_{1}} ∗ ⋯ ∗ F^{n_{k}} of homogeneous forms F^{n_{i}} ∈ A_{n_{i}} such that we have n = n_{1} + ⋯ + n_{k} and the F^{n_{i}}’s can not be written as a product of two homogeneous forms of lower degree.

1.3. Blockers of families of sets.

Definition 2. Let S be an arbitrary family of subsets of a finite set X. A subset B ⊆ X is a blocker of S, if for every S ∈ S we have S ∩ T ≠ ∅.

We denote the set of blockers of S in X by B_{X}(S). In particular, for S = ∅ every subset of X is a blocker and so we have B_{X}(∅) = {T : T ⊆ X}.

Lemma 1. Let S_{1} and S_{2} be a family of subsets of the same finite set X. Then B_{X}(S_{1}) ⊆ B_{X}(S_{2}) if and only if every S_{2} ∈ S_{2} contains some S_{1} ∈ S_{1}.

Proof. If every set from S_{2} contains a set from S_{1} then every blocker of S_{1} also blocks S_{2}. Assume that there is an element S_{2} of S_{2} not containing any element of S_{1}. Then the set X \ S_{2} blocks S_{1}, but it is disjoint from S_{2} and so does not block S_{2}. Hence we have B_{X}(S_{1}) ⊈ B_{X}(S_{2}).

Corollary 1. Let S_{1} and S_{2} be a family of subsets of the same finite set X. Then B_{X}(S_{1}) = B_{X}(S_{2}) if and only if the minimal sets with respect to inclusion are the same in S_{1} and S_{2}.

The minimal sets in a family of sets form an antichain (or Sperner family, or clutter), i.e. a family of sets such that no set contains another one. On the other hand, a family of sets S on a set X is a dual ideal if for every S ∈ S all S′ ⊆ X containing S belong to S. For an arbitrary family of sets S on X the dual ideal generated by S is the family

S^{+} := {T ⊆ X : ∃S ∈ S(S ⊆ T)}.

Proposition 4. For any family of sets S on a set X, we have B_{X}(S) = B_{X}(S^{+}).

Proof. Since S is a subfamily of S^{+}, we have B_{X}(S) ⊇ B_{X}(S^{+}). The other inclusion follows from Lemma 1 using the fact that every set from S^{+} contains some set from S.

It is shown in [3] that whenever S is an antichain, then the family of minimal elements of B_{X}(B_{X}(S)) is S. This statement and repeated application of Proposition 4 yields

B_{X}(B_{X}(S)) = S^{+}

for every family of sets S. From this and Proposition 4 we have the following.

Proposition 5. Let S_{1} and S_{2} be families of sets on the same set X. Then

B_{X}(S_{1}) = B_{X}(S_{2}) if and only if S_{1}^{+} = S_{2}^{+}.

For more on blockers, we refer the reader to [3], or to Section 8.1 of [4].

2. The Main Theorem

This section contains our main result, which characterizes all linear inequalities holding for the flag f-vectors of all graded posets of rank n + 1. Every such linear inequality may be written as

F (P) := ∑_{S⊆{1,... ,n}} a_{S} · f_{S}^{n+1}(P) ≥ 0,

where the coefficients a_{S} are real numbers. Moreover, ∑_{S⊆{1,... ,n}} a_{S} · f_{S}^{n+1}(P) is zero if rank(P) ≠ n + 1. Hence we are interested in determining the subset

K_{n+1} := {F = ∑_{S⊆{1,... ,n}} a_{S} · f_{S}^{n+1} ∈ A_{n+1} : ∀P (F (P) ≥ 0)}

of A_{n+1}. For convenience, we will let K_{0} = A_{0}.

In this section we show that K_{n+1} is a polyhedral cone, that is, the intersection of finitely many half spaces. We give these half spaces in terms of interval systems on the linearly ordered set {1, 2, …, n} ⊂ ℕ.

A subset of a partially ordered set P is an interval, if it is empty, or of the form

[p, q] := {x ∈ P : p ≤ x ≤ q} for some p, q ∈ P.

In particular, an interval in ℕ is a finite (possibly empty) set of consecutive natural numbers. An interval system on a partially ordered set P is a family I of intervals. We consider the empty set also as an interval system. The following theorem gives the list of inequalities that determine A_{n+1}.

Theorem 1. An expression ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} is nonnegative on all graded posets of rank n + 1 if and only if we have

(1)  ∑_{S∈B_{[1,n]}(I)} a_{S} ≥ 0 for every interval system I on [1, n].

First we will show the necessity of condition (1) by constructing for every interval system I on {1, 2, …, n} a family of posets {P (n, I, N) : N ∈ ℕ} of rank n + 1 such that we have

lim_{N⟶∞} \frac{1}{f_{[1,n]}(P (n, I, N))} · ∑_{S⊆[1,n]} a_{S} · f_{S}(P (n, I, N))) = ∑_{S∈B_{[1,n]}(I)} a_{S}.

Then we will prove the sufficiency by using an appropriate partitioning of the set of maximal chains for every graded poset P.

Definition 3. Let n and N be positive integers, and let I = {I_{1}, I_{2} …, I_{k}} be an interval system on [1, n]. We define the elements of the poset P (n, I, N) to be all arrays (i; p_{1}, …, p_{k}) such that

[figure: (3; ∗, 2); (3; ∗, 1); (2; 1, 1); (2; 2, 1); (2; 2, 2); (2; 1, 2); (1; 1, ∗); (1; 2, ∗); (4; ∗, ∗); (0; ∗, ∗)] Figure 1. P (3, {[1, 2], [2, 3]}, 2)

(i) i ∈ [0, n + 1], and (ii) for every j ∈ [1, k] we have

p_{j} ∈ \{ \begin{matrix}[1, N] & whenever i ∈ I_{j}, \\ \{∗\} & otherwise \end{matrix}

Here ∗ is a special symbol, different from all integers.

We set (i; p_{1}, p_{2}, …, p_{k}) ≤ (i′; p′_{1}, p′_{2}, …, p′_{k}) if

(1) i ≤ i′, and

(2) for every j ∈ [1, k] we have either p_{j} = p′_{j} or ∗ ∈ {p_{j}, p′_{j}}.

Observe that P (n, I, N) has a unique minimum element ˆ0 = (0; ∗, …, ∗) and a unique maximum element ˆ1 = (n + 1; ∗, …, ∗).

Example 1. Let n = 3, I = {[1, 2], [2, 3]}, and N = 2. Then P (3, {[1, 2], [2, 3]}, 2) is the poset shown on Fig. 1.

Example 2. If I = ∅ then P (n, ∅, N) is the same chain ˆ0 = 0 < 1 < 2 ⋯ < n < n + 1 = ˆ1 for every positive integer N.

Proposition 6. Let n and N be positive integers and I := {I_{1}, …, I_{k}} a nonempty interval system on [1, n]. Then P (n, I, N) is a graded poset of rank n + 1 and we have

f_{S}(P (n, I, N)) = N^{|{j∈[1,k] : S∩I_{j}≠∅}|} for all S ⊆ [1, n].

Proof: First we show that P is graded with the rank function given by

rank((i; p_{1}, …, p_{k})) = i.

Obviously, for every (i; p_{1}, …, p_{k}) < (j; q_{1}, … q_{k}) we have i < j. We only need to show that whenever i + 1 < j also holds then there is an element (i + 1; p′_{1}, …, p′_{k}) ∈ P (n, I, N) strictly between (i; p_{1}, …, p_{k}) and (j; q_{1}, … q_{k}). Let us set

p′_{l} = \{ \begin{matrix}∗ & if i + 1 ∉ I_{l}, \\ p_{l} & if i + 1 ∈ I_{l} and i ∈ I_{l}, \\ q_{l} & if i + 1 ∈ I_{l} and j ∈ I_{l}, \\ an arbitrary element of \{1, 2, …, N\} & if i + 1 ∈ I_{l} and i, j ∉ I_{l}. \end{matrix}

Observe that whenever we have {i, j} ⊆ I_{l} we also have i + 1 ∈ I_{l} and p_{l} = q_{l}, hence there is no contradiction in this definition of p′_{l}. It is easy to verify that (i + 1; p′_{1}, …, p′_{k}) ∈ P (n, I, N) is strictly between (i; p_{1}, …, p_{k}) and (j; q_{1}, … q_{k}).

Next we compute f_{S}(P (n, I, N)), which is, by definition, the number of chains x_{1} < ⋯ < x_{|S|} satisfying {rank(x_{1}), …, rank(x_{|S|})} = S. If for some j ∈ [1, k] we have S ∩ I_{j} = ∅ then every element x_{t} = (i, p_{1}, …, p_{k}) of such a chain must satisfy p_{j} = ∗. If S ∩ I_{j} ≠ ∅ then for the elements x_{t} = (i, p_{1}, …, p_{k}) satisfying rank(x_{t}) ∈ S ∩ I_{j} we must have p_{j} ∈ {1, 2, …, N}, and by the definition of the partial order on P (n, I, N) the value of p_{j} must be the same for all such x_{t}’s. All other x_{t}’s must satisfy p_{j} = ∗. Conversely, let us fix a vector (q_{1}, …, q_{k}) such that q_{j} is an arbitrary element of {1, 2, …, N} whenever S ∩ I_{j} ≠ ∅ and q_{j} = ∗ otherwise. Then the set {(s; p(s)_{1}, …, p(s)_{k}) : s ∈ S} defined by

p(s)_{j} = \{ \begin{matrix}q_{j} & if s ∈ I_{j}, \\ ∗ & otherwise \end{matrix}

is a chain in P (n, I, N) satisfying {rank((s; p(s)_{1}, …, p(s)_{k})) : s ∈ S} = S. This shows that f_{S}(P (n, I, N)) equals to the number of possible choices of (q_{1}, …, q_{k}), i.e., N^{|{j : S∩I_{j}≠∅}|}.

Corollary 2. Let n be a positive integer, and I an interval system on [1, n]. Then we have

lim_{N⟶∞} \frac{1}{f_{[1,n]}(P (n, I, N))} · ∑_{S⊆[1,n]} a_{S} · f_{S}(P (n, I, N))) = ∑_{S∈B_{[1,n]}(I)} a_{S}.

In fact, for a non-empty interval system I = {I_{1}, …, I_{k}} we have

\frac{1}{f_{[1,n]}(P (n, I, N))} · ∑_{S⊆[1,n]} a_{S} · f_{S}(P (n, I, N))) = \frac{1}{N^{k}} · ∑_{S⊆[1,n]} a_{S} · N^{|\{j : S∩I_{j}≠∅\}|}.

In this expression a_{S} is multiplied by 1 if and only if S intersects every interval of the system I, otherwise it is multiplied by a negative power of N. Finally, when I = ∅ then, as it was observed in Example 2, every poset P (n, ∅, N) is a chain of rank n+1, and we have

\frac{1}{f_{[1,n]}(P (n, ∅, N))} · ∑_{S⊆[1,2,... ,n]} a_{S} · f_{S}(P (n, ∅, N))) = ∑_{S⊆[1,n]} a_{S}

immediately. We can conclude that condition (1) is necessary:

Corollary 3. Suppose ∑_{S⊆[1,n]} a_{S} · f_{S}(P) ≥ 0 for every graded poset of rank n + 1. Then for every interval system I on [1, n],

∑_{S∈B_{[1,n]}(I)} a_{S} ≥ 0.

Hence we are left to show the sufficiency of (1).

Proposition 7. Assume that the set of coefficients {a_{S} : S ⊆ [1, n]} satisfies condition (1). Then we have

∑_{S⊆[1,n]} a_{S} · f_{S}(P) ≥ 0

for every graded poset of rank n + 1.

Proof: Let P be a graded poset of rank n + 1. For every i ∈ [1, n] let us fix an arbitrary numbering of the elements of rank i. Given an interval [p, q] of P, let ϕ([p, q]) denote the first atom in [p, q]. (Note that all atoms of [p, q] have the same rank, namely rank(p) + 1.) We will need the following two elementary observations:

1. If y covers x then ϕ([x, y]) = y.

2. If p ∈ [x, y] ⊆ [x, z] and p = ϕ([x, z]) then x = ϕ([x, y]).

For every S ⊆ [1, n] we define an operation M_{S} : [1, n] ⟶ [1, n] by

M_{S}(i) := min{j ∈ [i, n + 1] : j ∈ S ∪ {n + 1}}.

In other words, M_{S} assigns to i the smallest element of S which is not less than i, if such an element exists. Otherwise, it assigns n + 1 to i.

Consider the set of maximal chains

F_{S} := {ˆ0 = p_{0} < p_{1} < ⋯ < p_{n} < p_{n+1} = ˆ1 : ∀i ∈ [1, n] (p_{i} = ϕ ([p_{i−1}, p_{M_{S}(i)}]))} .

We claim that F_{S} contains exactly f_{S}(P) elements. For every i ∈ S we have M_{S}(i) = i and so, by our second elementary observationp_{i} = ϕ ([p_{i−1}, p_{M_{S}(i)}]) = ϕ ([p_{i−1}, p_{i}]) is trivially satisfied. Hence it is sufficient to show that every chain {p_{s} : s ∈ S} satisfying {rank(p_{s}) : s ∈ S} = S may be uniquely extended to a maximal chain {p_{0}, p_{1}, …, p_{n}} ∈ F_{S}. The only possible choice for p_{0} is ˆ0. Assume by induction that we have found a unique possible value for p_{0}, …, p_{m}. Let i be the smallest rank above m such that i ∉ S. Then the only possible value of p_{i} is ϕ([p_{i−1}, p_{M_{S}(i)}]), and choosing this value we obtain that {p_{1}, …, p_{i}}∪{p_{s} : s ∈ S} is a chain. This recursive algorithm shows that we have at most one extension of {p_{s} : s ∈ S} to a maximal chain in F_{S}. On the other hand, at the end of the algorithm we obtain a maximal chain belonging to F_{S}, since all defining conditions are satisfied. In particular, we obtain that F_{[1,n]} contains all maximal chains, while F_{∅} contains the unique maximal chain for which every p_{i} (i = 1, 2, …, n) is the first element among all elements of rank i covering p_{i−1}.

Let us fix now a maximal chain C := {ˆ0 = p_{0} < p_{1} < ⋯ < p_{n} < p_{n+1} = ˆ1}, and determine all those sets of ranks S ⊆ [1, n] for which C belongs to F_{S}. In view of our two trivial observations, for every i ∈ [1, n] there is a largest j ∈ [i, n + 1] such that p_{i} = ϕ ([p_{i−1}, p_{j}]). Let us denote this largest j by ψ(C, i). Obviously, p_{i} = ϕ ([p_{i−1}, p_{M_{S}(i)}]) is satisfied if and only if we have M_{S}(i) ≤ ψ(C, i), or equivalently

(S ∪ {n + 1}) ∩ [i, ψ(C, i)] ≠ ∅.

Introducing

I_{C} := {[i, ψ(C, i)] : i ∈ [1, n], ψ(C, i) ≠ n + 1}

we may say that C ∈ F_{S} if an only if S blocks the system I_{C}.

For every S ⊆ [1, n], let us put a weight a_{S} on every C ∈ F_{S}. On the one hand, the sum of all weights put on the chains is ∑_{S⊆[1,n]} a_{S} · f_{S}. On the other hand, the total weight associated to an individual chain C is ∑_{S∈B_{[1,n]}(I)} a_{S}. Hence we obtain

∑_{S⊆[1,n]} a_{S} · f_{S} = ∑_{C∈F_{[1,n]}} ∑_{S∈B_{[1,n]}(I)} a_{S},

and so ∑_{S⊆[1,n]} a_{S} · f_{S} is a sum of nonnegative terms, if (1) is satisfied.

3. The Facets of the Cone K_{n+1}

In this section we show that the inequalities in (1) give facets of the cone K_{n+1}. We also show that the number of facets is a Catalan number.

Proposition 8. Every condition of the form ∑_{S∈B_{[1,n]}(I)} a_{S} ≥ 0 defines a facet of the cone K_{n+1}.

Proof: Assume by way of contradiction that ∑_{S∈B_{[1,n]}(I)} a_{S} ≥ 0 is not a facet. Then, by Farkas’ lemma, there exists nonnegative numbers c_{1}, …, c_{k} and interval systems I_{1}, …, I_{k} such that we have

∑_{S∈B_{[1,n]}(I)} a_{S} = ∑_{i=1}^{k} c_{i} · ∑_{S∈B_{[1,n]}(I_{i})} a_{S},

and the conditions ∑_{S∈B_{[1,n]}(I_{i})} a_{S} ≥ 0 are different from ∑_{S∈B_{[1,n]}(I)} a_{S} ≥ 0. Since the set [1, n] blocks every interval system, the coefficient of a_{[1,n]} is 1 on the left hand side and ∑_{i=1}^{k} c_{i} on the right hand side. Hence we must have

∑_{i=1}^{k} c_{i} = 1.

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} [1,4] [2,4] [3,4] [4,4] [1,3] [1,2] [1,1] [2,3] [2,2] [3,3]

Figure 2. Representation of the dual ideal {[1, 2], [2, 3], [4, 4]}^{+} on [1, 4].

The coefficient of every other a_{S} is zero or one one the left hand side, and a convex combination of zeros and ones on the right hand side. Hence we must have

B_{[1,n]}(I) = B_{[1,n]}(I_{1}) = B_{[1,n]}(I_{2}) = ⋯ = B_{[1,n]}(I_{k}),

contradicting our assumption.

More directly, Proposition 8 follows from the fact that a subset of vertices of the 2^{n}-dimensional cube are vertices of their convex hull.

The number of facets is thus equal to the number of families of sets of the form B_{[1,n]}(I) where I is an arbitrary interval system on [1, n]. In order to count the number of these families, observe that by Proposition 5 we may replace I by I^{+}. Hence the number of facets of the cone K_{n+1} is equal to the number of dual ideals of subsets of [1, n] generated by intervals. There is a bijection between such dual ideals and Ferrers shapes contained in the shape of the partition (n, n − 1, …, 1), defined as follows. Given an n × n square, write the interval [i, j] ⊆ [1, n] into the box in the jth row and ith column. The boxes into which we have written an interval form the Ferrers shape of the partition (n, n − 1, …, 1). Clearly an interval system I on [1, n] is the family of all intervals in a dual ideal, if and only if for every box representing an interval I ∈ I all boxes above and to the left are marked with an interval from I. Equivalently, the boxes representing I form a Ferrers shape. Figure 2 shows the Ferrers shape representation for the dual ideal {[1, 2], [2, 3], [4, 4]}^{+} on [1, 4].

The number of Ferrers shapes contained in the shape of the partition (n, n − 1, …, 1) is equal to the number of those lattice paths from the lower left corner of the box marked with [1, 1] to the upper right corner of the box marked with [n, n] which use only unit steps up and to the right and which never leave the shape of the partition (n, n − 1, …, 1).

Corollary 4. The number of facets of the cone K_{n+1} is the Catalan number \frac{1}{n+1} · \binom{2·(n+1)}{n}.

\begin{matrix}I & ∑_{S∈B_{[1,3]}(I)} a_{S} & I & ∑_{S∈B_{[1,3]}(I)} a_{S} \\ ∅ & 0 & \{[1], [2, 3]\}^{+} & 1 \\ \{[1, 3]\}^{+} & 0 & \{[2]\}^{+} & 1 \\ \{[1, 2]\}^{+} & 1 & \{[1, 2], [3]\}^{+} & 1 \\ \{[2, 3]\}^{+} & 1 & \{[1], [2]\}^{+} & 0 \\ \{[1]\}^{+} & 0 & \{[1], [3]\}^{+} & 1 \\ \{[1, 2], [2, 3]\}^{+} & 1 & \{[2], [3]\}^{+} & 0 \\ \{[3]\}^{+} & 0 & \{[1], [2], [3]\}^{+} & 0 \end{matrix}

Table 1. The value of ∑_{S∈B_{[1,3]}(I)} a_{S} for ∑_{S⊆[1,3]} a_{S} · f_{S} = f_{1,3} − f_{1} +
f_{2} − f_{3}

Let us also note the following consequence of Corollary 1 which gives a practically more useful description of the facets of K_{n+1}

Corollary 5. Every inequality in (1) may be written as

∑_{S∈B_{[1,n]}(I)} a_{S} ≥ 0

for some antichain of intervals I on [1, n].

Example 3. This inequality was found by Billera and Liu (see [1]). For every graded poset P of rank 3 we have

f_{1,3}(P) − f_{1}(P) + f_{2}(P) − f_{3}(P) ≥ 0.

In fact, we may apply Theorem 1 for a_{1,3} = 1, a_{1} = −1, a_{2} = 1, a_{3} = −1, and a_{S} = 0 for every other subset S of {1, 2, 3}. There are 14 dual ideals generated by intervals on the set [1, 3], which are given by the antichain of their minimal intervals in Table 1. Evaluating ∑_{S∈B_{[1,3]}(I)} a_{S} for these 14 interval systems we see that Condition (1) is satisfied.

4. Projections and Convolutions

In this section we present linear projections π_{m}^{n+1} : A_{n+1} ⟶ A_{n} which allow us to describe the cone K_{n+1} in terms of the cone K_{n}. We show that these projections are nicely compatible with the convolution operation defined in [1].

Definition 4. Let n > 0 and m ∈ [0, n] be integers. For an arbitrary form ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} ∈ A_{n+1} we define its m-th projection into A_{n} by

π_{m}^{n+1} ( ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1}) := ∑_{S⊆[1,n−1]} (χ((S ∪ {0}) ∩ [m, n − 1] ≠ ∅) · a_{S} + a_{S∪{n}})·f_{S}^{n}.

We extend this definition to n = 0 and to negative m’s by setting π_{0}^{1} (f_{∅}^{1}) := 1 and π_{m}^{n+1} := π_{0}^{n+1} whenever m < 0.

Equivalently, the effect of the projections π_{m}^{n+1} on the operators f_{S}^{n+1} may be given by

π_{m}^{n+1} (f_{S}^{n+1}) = \{ \begin{matrix}f_{S\\{n\}}^{n} & if n ∈ S, \\ χ((S ∪ \{0\}) ∩ [m, n − 1] ≠ ∅) · f_{S}^{n} & if n ∉ S. \end{matrix} (2)

In particular, for m = 0, (S ∪ {0}) ∩ [0, n − 1] ≠ ∅ holds for every S ⊆ [1, n − 1], and we have

π_{0}^{n+1} ( ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1}) = ∑_{S⊆[1,n−1]} (a_{S} + a_{S∪{n}}) · f_{S}^{n}.

and

π_{0}^{n+1} (f_{S}^{n+1}) = f_{S\{n}}^{n}. (3)

At the other extreme, for m = n the interval [m, n − 1] is the empty set, and we have

π_{n}^{n+1} ( ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1}) = ∑_{S⊆[1,n−1]} a_{S∪{n}} · f_{S}^{n}.

Given an arbitrary interval system I on [1, n − 1] and m ∈ [1, n], a set T ⊆ [1, n] blocks I ∪ {[m, n]} if and only if S := T \ {n} ⊆ [1, n − 1] blocks I and either n ∈ T, i.e., T = S ∪ {n}, or n ∉ T and S = T blocks [m, n − 1]. Moreover, (S ∪ {0}) ∩ [m, n − 1] ≠ ∅ is equivalent to S ∩ [m, n − 1] ≠ ∅. Hence we have

∑_{T ∈B_{[1,n]}(I∪{[m,n]})} a_{T} = ∑_{S∈B_{[1,n−1]}(I)} (χ((S ∪ {0}) ∩ [m, n − 1] ≠ ∅) · a_{S} + a_{S∪{n}}) . (4)

Similarly, for m = 0, a set T ⊆ [1, n] blocks I if and only if S := T \ {n} ⊆ [1, n − 1] blocks I. Moreover, as noted earlier, χ((S ∪ {0}) ∩ [0, n − 1] ≠ ∅) = 1 for every S ⊆ [1, n − 1]. These observations yield

∑_{T ∈B_{[1,n]}(I)} a_{T} = ∑_{S∈B_{[1,n−1]}(I)} (χ((S ∪ {0}) ∩ [0, n − 1] ≠ ∅) · a_{S} + a_{S∪{n}}) . (5)

Using equations (4) and (5) we may show the following.

Theorem 2. A form ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} ∈ A_{n+1} belongs to K_{n+1} if and only if for

every m ∈ [0, n] the projection π_{m}^{n+1} (∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1}) belongs to K_{n}.

Proof: The necessity is evident in view of of the equations (4) and (5). To prove sufficiency observe that by Corollary 5 it suffices to verify the nonnegativity conditions

∑_{T ∈B_{[1,n]}(J)} a_{T} ≥ 0 (6)

for every antichain of intervals J on [1, n]. Such an antichain is either also an interval system on [1, n−1] or the union of the antichain I := {I ∈ J : I ⊆ [1, n−1]} and of the singleton {[m.n]} where [m, n] is the unique interval in J containing n. In either case, we may use (5) or (4), respectively, to show that (6) holds.

We now introduce some linear operators acting on A which will be useful in giving a simple expression for π_{m}^{n+1} for m > 0.

Definition 5. Let n be a positive integer and k ∈ [0, n − 1]. We define ρ_{k}^{n+1} : A_{n+1} ⟶ A_{n} by setting

ρ_{k}^{n+1}(f_{S}^{n+1}) := χ(S ⊆ [1, k]) · f_{S∩[1,k]}^{n}

for every S ⊆ [1, n]. We extend this definition to n = 0 and to negative k′s by setting ρ_{0}^{1}(f_{∅}^{1}) := 0 and ρ_{k}^{n+1} := 0 whenever k < 0.

In particular, for n > 0 we have

ρ_{0}^{n+1} (f_{S}^{n+1}) = \{ \begin{matrix}f_{∅}^{n} & if S = ∅, \\ 0 & otherwise. \end{matrix}

It is an easy consequence of (2) that we have

π_{m}^{n+1} = π_{0}^{n+1} − ρ_{m−1}^{n+1} for n ∈ ℕ and m ∈ [0, n]. (7)

Let us consider now the effect of the projection operations π_{m}^{n+1} on a convolution of two chain operators.

Proposition 9. We have

π_{0}^{m+n} (f_{S}^{m} ∗ f_{T}^{n}) = f_{S}^{m} ∗ π_{0}^{n} (f_{T}^{n})

for all positive m, n and sets S ⊆ [1, m − 1], T ⊆ [1, n − 1].

Proof: Assume first that we have n ≥ 2. A simple substitution into the definitions and (3) yields

π_{0}^{m+n} (f_{S}^{m} ∗ f_{T}^{n}) = π_{0}^{m+n} (f_{S∪{m}∪(T +m)}^{m+n}) = f_{S∪{m}∪(T +m)\{m+n−1}}^{m+n−1}
= f_{S∪{m}∪(T \{n−1})+m}^{m+n−1} = f_{S}^{m} ∗ π_{0}^{n} (f_{T}^{n}) .

For n = 1 we have

π_{0}^{m+1} (f_{S}^{m} ∗ f_{∅}^{1}) = π_{0}^{m+1} (f_{S∪{m}}^{m+1}) = f_{S∪{m}\{m}}^{m} = f_{S}^{m} = f_{S}^{m} ∗ 1 = f_{S}^{m} ∗ π_{0}^{n} (f_{∅}^{1})

by π_{0}^{n} (f_{∅}^{1}) = 1.

Proposition 10. Let m and n be positive integers, S ⊆ [1, m − 1], T ⊆ [1, n − 1]. Then for every k ∈ [0, m + n − 2] we have

ρ_{k}^{m+n} (f_{S}^{m} ∗ f_{T}^{n}) = f_{S}^{m} ∗ ρ_{k−m}^{n} (f_{T}^{n}) .

Proof: If k is negative then both sides are identically zero. Assume 0 ≤ k ≤ m − 1. Then we have

ρ_{k}^{m+n} (f_{S}^{m} ∗ f_{T}^{n}) = ρ_{k}^{m+n} (f_{S∪{m}∪(T +m)}^{m+n})
= χ(S ∪ {m} ∪ (T + m) ⊆ [1, k]) · f_{(S∪{m}∪(T +m))∩[1,k]}^{m+n−1} = 0

since m ∉ [1, k]. On the other hand, ρ_{k−m}^{n} is identically zero by definition, and so the equality of the both sides holds trivially.

Assume finally that m ≤ k ≤ m + n − 2 holds. Then we must have n ≥ 2, S is a subset of [1, k] and S ∪ {m} ∪ (T + m) ⊆ [1, k] is equivalent to T ⊆ [1, k − m]. Therefore we have

ρ_{k}^{m+n} (f_{S}^{m} ∗ f_{T}^{n}) = ρ_{k}^{m+n} (f_{S∪{m}∪(T +m)}^{m+n})
= χ(S ∪ {m} ∪ (T + m) ⊆ [1, k]) · f_{(S∪{m}∪(T +m))∩[1,k]}^{m+n−1}
= χ(T ⊆ [1, k − m]) · f_{S∪{m}∪(T ∩[1,k−m]+m)}^{m+n−1}
= χ(T ⊆ [1, k − m]) · f_{S}^{m} ∗ f_{T ∩[1,k−m]}^{n−1}
= f_{S}^{m} ∗ ρ_{k−m}^{n} (f_{T}^{n}) .

As a corollary of Propositions 9 and 10, and of equation (7) we obtain

Corollary 6. The equality

π_{k}^{m+n} (f_{S}^{m} ∗ f_{T}^{n}) = f_{S}^{m} ∗ π_{k−m}^{n} (f_{T}^{n})

holds for m, n > 0, k ∈ [0, m + n − 1], S ⊆ [1, m − 1], and T ⊆ [1, n − 1].

In section 5 we will need to consider the maximum element of the support of a form ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1}.

Definition 6. The support of a form F = ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} ∈ A_{n+1} is the family of sets

supp(F) := {S ⊆ [1, n] : a_{S} ≠ 0}.

We call the maximum element of ⋃_{S∈supp(F)} S the largest letter occurring in F.

Lemma 2. The projections π_{m}^{n+1} do not increase the largest letter occurring in a form.

Proof: Let us denote the largest occurring letter in F = ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} ∈ A_{n+1} by l. If l = n then there is nothing to prove, so we may assume l < n. Evidently k ∈ [1, n] is greater than l if and only if for every S ⊆ [1, n] containing k we have a_{S} = 0. Hence it is sufficient to show the following: if for every S ⊆ [1, n] containing some k > l we have a_{S} = 0 then for every S ⊆ [1, n − 1] containing some k > l we have

χ((S ∪ {0}) ∩ [m, n − 1] ≠ ∅) · a_{S} + a_{S∪{n}} = 0.

The second term in this sum is zero since S ∪ {n} contains the letter n which larger than l by assumption. The first term is zero too, since S contains some k > l.

5. Extreme Rays of K_{n+1}

In this section we study the extreme rays of the cones K_{n+1} where n ∈ ℕ. First we show that f_{∅}^{n+1} is an extreme ray of the cone K_{n+1} for every n ≥ 0. Then we show for k = 1, 2, …, n that the inclusions

\begin{aligned}σ_{k}^{n+1} : & A_{n+1} & ⟶ & A_{n+2} \\ & f_{S}^{n+1} & ⟼ & f_{σ_{k}(S)}^{n+2} \end{aligned} (8)

induced by the shift operators

\begin{aligned}σ_{k} : & ℙ & ⟶ & ℙ \\ & i & ⟼ & \{ \begin{matrix}i & if i ≤ k \\ i + 1 & if i ≥ k + 1 \end{matrix} \end{aligned} (9)

embed K_{n+1} into A_{n+2} as a face of K_{n+2}. Finally we describe completely those situations when the convolution F ∗ G of an extreme ray F of the cone K_{m} and an extreme ray G of the cone K_{n} is an extreme ray of the cone K_{n+m}. The main result of this section is the following theorem.

Theorem 3. Let F ∈ K_{m} and G ∈ K_{n} be extreme rays in their respective cones. Then the convolution F ∗ G ∈ K_{m+n} is an extreme ray, unless F = F′ ∗ f_{∅}^{k} and G = f_{∅}^{l} ∗ G′ for some k ≤ m, l ≤ n, F′ ∈ K_{m−k}, and G′ ∈ K_{n−l}.

To interpret this result, note that Proposition 1 is equivalent to the following.

Proposition 11. Let F ∈ A_{m} and G ∈ A_{n}. The convolution F ∗ G ∈ A_{m+n} belongs to K_{n+m} if and only if exactly one of the following holds:

(i) F ∈ K_{m} and G ∈ K_{n}, or (ii) −F ∈ K_{m} and −G ∈ K_{n}.

Thus the convolution of two extreme rays is surely in the cone of valid inequalities. If, say, G is a positive linear combination of G′ and G′′ from K_{n} then F ∗ G will be the positive linear combination of F ∗ G′ and F ∗ G′′ from K_{m+n}. (Recall that according to Proposition 2 the ring A is a free associative algebra, and so it has no zero divisors.) Thus only the convolution of extreme rays may yield an extreme ray. It may happen that the convolution of extremes is not extreme: for every m, n > 0 the operators f_{∅}^{m} and f_{∅}^{n} are extreme rays in K_{m} and K_{n} respectively, yet

f_{∅}^{m} ∗ f_{∅}^{n} = f_{m}^{m+n} = (f_{m}^{m+n} − f_{∅}^{m+n}) + f_{∅}^{m+n}

where both f_{m}^{m+n} − f_{∅}^{m+n} and f_{∅}^{m+n} belong to K_{m+n}. Theorem 3 affirms that, essentially, only such anomalies may occur.

According to Proposition 3 the semigroup of homogeneous polynomials of A has unique factorization. In view of Proposition 11, an expression F ∈ A_{n} belongs to K_{n} if and only if every factor F_{i} ∈ A_{n_{i}} in its complete homogeneous factorization F = F_{1} ∗ ⋯ ∗ F_{k} may be chosen to belong to K_{n_{i}}. (Since uniqueness holds up to a choice of nonzero constant factors, we may change the signs of the factors of two F_{i}’s at a time.) When F is an extreme ray of K_{n} then every F_{i} must be an extreme ray in its cone, and no two consecutive factors can be of the form F_{i} = f_{∅}^{n_{i}}, F_{i+1} = f_{∅}^{n_{i+1}}. Theorem 3 implies that the converse is true as well: every convolution of extreme rays such that no two consecutive factors are of the form F_{i} = f_{∅}^{n_{i}}, F_{i+1} = f_{∅}^{n_{i+1}}, is an extreme ray.

One way of showing F ∈ K_{n+1} is an extreme ray is to give 2^{n} − 1 linearly independent facets of K_{n+1} containing F. (Note that since K_{n+1} contains the positive orthant of A_{n+1}, it is full dimensional.) Hence it is useful to introduce the following operators.

Definition 7. Let P be an arbitrary graded poset of rank n + 1, and I an arbitrary interval system on [1, n]. The operators ε_{P}^{n+1}, ε_{I}^{n+1} ∈ A_{n+1}^{∗} are given by

ε_{P}^{n+1}(f_{S}^{n+1}) := f_{S}^{n+1}(P), and

ε_{I}^{n+1}(f_{S}^{n+1}) := \{ \begin{matrix}1 & if ∀I ∈ I (S ∩ I ≠ ∅), \\ 0 & otherwise. \end{matrix}

As a consequence of this definition we have for F = ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} ∈ A_{n+1} that

ε_{I}^{n+1}(F) = ∑_{S∈B[1,n](I)} a_{S},

hence the hyperplanes determining the facets of K_{n+1} are the kernels of the ε_{I}^{n+1}’s. Let us also note that Corollary 2 may be rewritten as

ε_{I}^{n+1} = lim_{N⟶∞} \frac{1}{f_{[1,n]}(P (n, I, N))} · ε_{P (n,I,N)}^{n+1}.

It is easy to show that the operators ε_{I}^{n+1}, where I runs over all interval systems on [1, n], contain a basis of the vector space A_{n+1}^{∗}.

Definition 8. For every S ⊆ [1, n] let I_{S} denote the interval system {{s} : s ∈ S}. As a shorthand for ε_{I_{S}}^{n+1} we will use ε_{S}^{n+1}.

Lemma 3. For every S, T ⊆ [1, n] we have

ε_{S}^{n+1} (f_{T}^{n+1}) = \{ \begin{matrix}1 & if S ⊆ T, \\ 0 & otherwise. \end{matrix}

The proof is straightforward.

Corollary 7. The set {ε_{S}^{n+1} : S ⊆ [1, n]} is a basis of A_{n+1}^{∗}.

Proposition 12. The chain operator f_{∅}^{n+1} is an extreme ray of the cone K_{n+1} for every n ≥ 0.

Proof: Since f_{∅}^{n+1}(P) > 0 holds for every partially ordered set of rank n + 1, we have f_{∅}^{n+1} ∈ K_{n+1}. We only need to show that f_{∅}^{n+1} lies on at least 2^{n} − 1 linearly independent facets of K_{n+1}. This is true, since by Lemma 3 we have ε_{S}^{n+1}(f_{∅}^{n+1}) = 0, whenever S is not the empty set.

The facets of the form Ker(ε_{S}^{n+1}) are also useful in proving the following proposition.

Proposition 13. Let n > 0 be an integer and k ∈ [1, n]. Then the set σ_{k}^{n+1}(K_{n+1}) is a face of K_{n+2}.

Proof: Evidently we have

Im(σ_{k}^{n+1}) = ⋂_{{S⊆[1,n+1] \atop k∈S}} Ker(ε_{S}^{n+1}),

since both vector spaces are spanned by those chain operators f_{S}^{n+2} for which k ∉ S. Thus we only need to show that σ_{k}^{n+1}(K_{n+1}) ⊆ K_{n+2}. The cone σ_{k}^{n+1}(K_{n+1}) is then contained in the 2^{n}-dimensional face

K_{n+2} ∩ ( ⋂_{{S⊆[1,n+1] \atop k∈S}} Ker(ε_{S}^{n+1}))

of K_{n+2}, and, having the same dimension, it is also equal to it. Equivalently, we have to prove that

ε_{I}^{n+2}(σ_{k}^{n+1}(F)) ≥ 0

holds for every interval system I on [1, n + 1].

Assume first that I contains the interval {k}. Then we have

ε_{I}^{n+2}(σ_{k}^{n+1}(F)) = 0

for every F ∈ A_{n+1}. If I does not contain {k} then consider the interval system

I′ := {(I ∩ [1, k − 1]) ∪ (I ∩ [k, n + 1] − 1) : I ∈ I}

on [1, n]. It is easy to verify that we have

ε_{I}^{n+2}(σ_{k}^{n+1}(F)) = ε_{I′}^{n+1}(F)

for every F ∈ A_{n+1}, and so F ∈ K_{n+1} implies ε_{I}^{n+2}(σ_{k}^{n+1}(F)) ≥ 0.

Corollary 8. Given n ≥ 1 and k ∈ [1, n], the form F ∈ A_{n+1} belongs to K_{n+1} if and only if σ_{k}^{n+1}(F) belongs to K_{n+2}. Moreover, F ∈ K_{n+1} is an extreme ray if and only if σ_{k}^{n+1}(F) ∈ K_{n+2} is an extreme ray.

Corollary 8 implies that every extreme ray F ∈ K_{n+2} with supp(F) ≠ [1, n + 1] is obtained by lifting an extreme ray of K_{n+1} using an embedding σ_{k}^{n+1}. Iterated use of Corollary 8 yields the following.

Theorem 4. Let F = ∑_{S⊆[1,n]} a_{s} · f_{S}^{n+1} ∈ A_{n+1} be a form with support supp(F) = {i_{1}, i_{2}, …, i_{k}} and let γ : [1, k] ⟶ supp(F) be the bijection j ↦ i_{j}. Then F belongs to K_{n+1} if and only if

F′ := ∑_{S⊆supp(F)} a_{γ^{−1}(S)} · f_{γ^{−1}(S)}^{k+1}

belongs to K_{k+1}. Moreover F ∈ K_{n+1} is an extreme ray if and only if F′ ∈ K_{k+1} is an extreme ray.

It follows from Theorem 4 and our calculation of the rank 2 case in subsection 1.1 that the functionals h_{i} := f_{i} − f_{∅}, 1 ≤ i ≤ n, will all be extreme in rank n + 1.

The crucial step in the proof of Theorem 3 is the following.

Lemma 4. Let F = ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} ≠ f_{∅}^{n+1} be an extreme ray of K_{n+1} and let m be the largest letter occurring in F. Assume that F cannot be written as G ∗ f_{∅}^{n+1−m} for some G ∈ K_{m}. Then there exists integers k, l satisfying 0 ≤ k < l ≤ m and an interval system I on [1, m − 1] such that

∑_{S∪{0}∈B[0,n](I∪{[k,m]}} a_{S} = 0 and ∑_{S∈B[1,n](I∪{[l,m]}} a_{S} ≠ 0 hold.

Proof: Let us show first that, without loss of generality, we may restrict ourselves to the case m = n. Since m is the largest occurring letter, we have

F = ∑_{S⊆[1,n]} a_{S} · f_{S}^{n+1} = ∑_{S⊆[1,m]} a_{S} · f_{S}^{n+1}.

The form F is of the form G ∗ f_{∅}^{n+1−m} for some G ∈ K_{m} if and only if the form

F̃ := ∑_{S⊆[1,m]} a_{S} · f_{S}^{m+1}

is of the form G ∗ f_{∅}^{1} for the same G ∈ K_{m}. Given an arbitrary interval system J on [1, m] we have

ε_{J}^{n+1}(F) = ε_{J}^{m+1}(F̃).

Therefore, if the lemma holds for the case m = n then we may use the result on F̃ to prove the same result for F.

Hence we may assume that m = n holds. The statement is equivalent to saying that there exists a facet Ker (ε_{I}) of K_{n} and integers 0 ≤ k < l ≤ n such that π_{k}^{n+1}(F) belongs to this facet but π_{l}^{n+1}(F) does not.

In the contrary event every facet of K_{n} containing some π_{k}^{n+1}(F) also contains all forms π_{l}^{n+1}(F) for every l > k. Let G ∈ A_{n} be an extreme ray of the intersection of all facets containing π_{n}^{n+1}(F). (Note that n being the largest occurring letter, π_{n}^{n+1}(F) = ∑_{S⊆[1,n−1]} a_{S∪{n}} · f_{S}^{n} is not the zero form.) By our assumptions, this form is also an extreme ray of the intersection of all facets containing π_{i}^{n+1}(F) for i = 0, 1, …, n − 1. Hence we may choose a small positive number q ∈ ℝ such that

π_{i}^{n+1}(F) − q · G ∈ K_{n} holds for i = 0, 1, …, n.

By Corollary 6 we have π_{i}^{n+1}(G ∗ f_{∅}^{1}) = G for i = 1, 2, …, n and so we obtain

π_{i}^{n+1} (F − q · G ∗ f_{∅}^{1})) ∈ K_{n}

for i = 0, 1, …, n. By Theorem 2 we obtain that F − q · G ∗ f_{∅}^{1} belongs to K_{n+1}. Since F is an extreme ray, and by Proposition 1 we have G ∗ f_{∅}^{1} ∈ K_{n+1}, F must be equal to a nonzero constant multiple of G ∗ f_{∅}^{1}, contrary to our assumptions.

Corollary 9. Let F ∈ K_{n+1} be an extreme satisfying the conditions of Lemma 4. Then there exists integers k, l satisfying 0 ≤ k < l ≤ m and an interval system I on [1, m − 1] such that

∑_{S∪{0}∈B[0,n](I∪{[k,n]}} a_{S} = 0 and ∑_{S∈B[1,n](I∪{[l,n]}} a_{S} ≠ 0 hold.

In fact, replacing the intervals [k, m] and [l, m] with [k, n] and [l, n] respectively does not change the sums involved, since whenever S contains a letter larger than m, a_{S} is zero.

We now proceed to the proof of Theorem 3. Since applying the chain operators to the dual of every poset yields an anti-isomorphism of the graded ring A which sends products of the form F ∗ f_{∅}^{l} into products of the form f_{∅}^{l} ∗ F̂, it is sufficient to show the following “half” of the original statement.

Proposition 14. Assume F ∈ K_{m} and G ∈ K_{n} are extreme rays such that F is not a convolution of the form F′ ∗ f_{∅}^{l}. Then F ∗ G is an extreme ray of K_{m+n}.

Proof: By Proposition 11 we know that F ∗ G belongs to K_{m+n}. In order to show that it is an extreme ray, it is sufficient to find 2^{m+n−1} − 1 interval systems I_{1}, I_{2}, …, I_{2^{m+n−1}−1} such that the operators ε_{I_{1}}^{m+n}, ε_{I_{2}}^{m+n}, …, ε_{I_{2^{m+n−1}−1}}^{m+n} are linearly independent, and they all vanish on F ∗ G.

Assume we have

F = ∑_{S⊆[1,m−1]} a_{S}^{m} · f_{S}^{m} and G = ∑_{S⊆[1,n−1]} a_{S}^{n} · f_{S}^{n}.

Then

F ∗ G = ∑_{S⊆[1,m+n−1]} a_{S}^{m+n} · f_{S}^{m+n}

is given by the following formula:

a_{S}^{m+n} = \{ \begin{matrix}a_{S∩[1,m−1]}^{m} · a_{(S∩[m+1,m+n−1])−m}^{n} & if m ∈ S, \\ 0 & if m ∉ S. \end{matrix}

Since for every nonzero a_{S}^{m+n} we must have m ∈ S, for an arbitrary interval system I on [1, m + n − 1] we have

ε_{I}^{m+n}(F ∗ G) = ε_{{I∈I : m∉I}}^{m+n}(F ∗ G),

i.e., we may remove every interval containing m from I without changing the effect of ε_{I}^{m+n} on F ∗ G. The remaining intervals are either contained in [1, m − 1] or in [m + 1, m + n − 1]. Introducing

I′ := {I ∈ I : I ⊆ [1, m − 1]} and I′′ := {I − m : I ∈ I, I ⊆ [m + 1, m + n − 1]}

we obtain

ε_{I}^{m+n}(F ∗ G) = ε_{I′}^{m}(F) · ε_{I′′}^{n}(G). (10)

Since F ∈ K_{m} is an extreme ray, there exist interval systems I′_{1}, I′_{2}, …, I′_{2^{m−1}} on [1, m − 1] such that the operators ε_{I′_{1}}^{m}, ε_{I′_{2}}^{m}, …, ε_{I′_{2^{m−1}}}^{m} are linearly independent, ε_{I′_{j}}^{m}(F) = 0 for j ≤ 2^{m−1} − 1, and ε_{I′_{2^{m−1}}}^{m}(F) is strictly positive. Similarly, the fact of G ∈ K_{n} being an extreme ray implies that there exist interval systems I′′_{1}, I′′_{2}, …, I′′_{2^{n−1}} on [1, n − 1] such that the operators ε_{I′′_{1}}^{n}, ε_{I′′_{2}}^{n}, …, ε_{I′′_{2^{n−1}}}^{n} are linearly independent, ε_{I′′_{j}}^{n}(F) = 0 holds for j ≤ 2^{n−1} − 1, and ε_{I′_{2^{n−1}}}^{n}(F) is strictly positive.

Moreover, since F is not of the form F′ ∗ f^{l}, by Corollary 9 we may assume that I′_{2^{m−1}} is of the form J′ ∪ {[l, m − 1]} where J′ is an interval system on [1, m − 1], l ∈ [1, m − 1] and either we have ε_{J′}^{m}(F) = 0, or there exist a k ∈ [1, l − 1] such that ε_{J′∪{[k,m−1]}}^{m}(F) = 0 holds.

Consider now the following interval systems:

(i) All interval systems of the form I′_{i} ∪ (I′′_{j} + m), where at least one of i ≠ 2^{m−1} and j ≠ 2^{n−1} holds.

(ii) All interval systems of the form I′_{i} ∪ {m} ∪ (I′′_{j} + m), where at least one of

i ≠ 2^{m−1} and j ≠ 2^{n−1} holds. (iii) The interval system J′ ∪ {[l, m]} ∪ (I′′_{2^{n−1}} + n) if we have ε_{J′}^{m}(F) = 0, or the

interval system J′ ∪ {[k, m − 1]} ∪ {[l, m]} ∪ (I′′_{2^{n−1}} + m) if ε_{J′∪{[k,m−1]}}^{m}(F) = 0 holds.

The above list contains 2^{m+n−1} − 1 interval systems: 2^{m+n−2} − 1 of them are of type (i), 2^{m+n−2} − 1 of them are of type (ii), and there is exactly one system listed at item (iii). It is easy to see using (10) that they all vanish on F ∗ G. We are left to show that the operators they define are linearly independent.

First we show that the operator defined by the last system is not in the span of the operators defined by all others. For this purpose consider the form H := ∑_{S⊆[1,m+n−1]} ã_{S} · f_{S}^{m+n} given by

ã_{S} = \{ \begin{matrix}0 & if m ∈ S, \\ a_{S∩[1,m−1]}^{m} · a_{(S∩[m+1,m+n−1])−m}^{n} & if m ∉ S. \end{matrix}

It is easy to see that we have

ε_{I′_{i}∪(I′′_{j}+m)}^{m+n}(H) = ε_{I′_{i}}^{m}(F) · ε_{I′′_{j}}^{n}(G)

and so the operators defined by the systems of type (i) vanish on H. The operators defined by the systems of type (ii) vanish on H too, since we have ã_{S} = 0 whenever m ∈ S. By the same reason we also have

ε_{J′∪{[k,m−1]}∪{[l,m]}∪(I′′_{2^{n−1}}+m)}^{m+n}(H) = ε_{J′∪{[k,m−1]}∪{[l,m−1]}∪(I′′_{2^{n−1}}+m)}^{m+n}(H)

Since k is less than l, the dual ideal of intervals generated by J′ ∪ {[k, m − 1]} ∪ {[l, m − 1]} ∪ (I′′_{2^{n−1}} + m) is the same as the dual ideal generated by J′ ∪ {[l, m − 1]} ∪ (I′′_{2^{n−1}} + m) = I′_{2^{m−1}} ∪ (I′′_{2^{n−1}} + m). Hence we have

ε_{J′∪{[k,m−1]}∪{[l,m]}∪(I′′_{2^{n−1}}+m)}^{m+n}(H) = ε_{I′_{2^{m−1}}}^{m}(F) · ε_{I′′_{2^{n−1}}}^{m}(G) ≠ 0.

Next we show that the intersection of the subspace generated by the operators associated to the interval systems listed in (i) with the subspace generated by the operators associated to the interval systems listed in (ii) is zero. For this purpose observe that A_{n} may be written as a direct sum of two 2^{m+n−2}-dimensional vector spaces, A_{n} = A′_{n} ⊕ A′′_{n}, where

A′_{n} := ⟨f_{S∪{m}}^{m+n} − f_{S}^{m+n} : S ⊆ [1, m + n − 1], m ∉ S⟩

and

A′′_{n} := ⟨f_{S∪{m}}^{m+n} : S ⊆ [1, m + n − 1], m ∉ S⟩.

Evidently, linear combinations of operators associated to interval systems of type (i) vanish on A′_{n} while linear combinations of operators associated to interval systems of type (ii) have the same values on the respective generators of A′_{n} and A′′_{n}. Assume now that ε ∈ A_{n}^{∗} is simultaneously a linear combination of operators associated to interval systems of type (i) and of operators associated to interval systems of type (ii). Then ε vanishes on A′_{n} and hence on A′′_{n}, so ε = 0.

Finally, let F_{1}, …, F_{2^{m−1}} ∈ A_{m} and G_{1}, …, G_{2^{n−1}} ∈ A_{n} be dual bases to {ε_{I′_{i}}^{m}} and {ε_{I′′_{i}}^{n}}, respectively, that is, ε_{I′_{i}}^{m}(F_{j}) = δ_{ij} and ε_{I′′_{k}}^{m}(G_{l}) = δ_{kl}. Then by (10) we have

ε_{I′_{i}∪(I′′_{k}+m)}(F_{j} ∗ G_{l}) = ε_{I′_{i}∪{m}∪(I′′_{k}+m)}(F_{j} ∗ G_{l}) = δ_{ij}δ_{kl},

showing the interval systems of types (i) and (ii) to be linearly independent.

We can describe all extremes of the cone K_{n} for n ≤ 5. Equivalently, these represent the strongest linear inequalities holding for the flag f-vectors of graded posets of these ranks.

n = 1: The only extreme ray of K_{1} is h_{∅}^{1} = f_{∅}^{1}. n = 2: As seen in subsection 1.1, the extreme rays for K_{2} are h_{∅}^{2} = f_{∅}^{2} and h_{1}^{2} =

f_{1}^{2} − f_{∅}^{2}. n = 3: By repeated use of Theorems 3 and 4, we may generate five extremes for

K_{3}: h_{∅}^{3}, h_{1}^{3}, h_{2}^{3}, h_{∅}^{1} ∗ h_{1}^{2} = f_{12}^{3} − f_{1}^{3} and h_{1}^{2} ∗ h_{∅}^{1} = f_{12}^{3} − f_{2}^{3}. Direct computation shows these are all the extremes in this case.

n = 4: Direct calculation shows that there are 13 extremes for K_{4}. All except one can be obtained by repeated use of Theorems 3 and 4. The remaining one is f_{13}^{4} − f_{1}^{4} + f_{2}^{4} − f_{3}^{4}, which represents the inequality given in Example 3.

n = 5: Again, direct calculation reveals that K_{5} has 41 extremes. All but seven of these arise from lifting and convolution as above. The remainder are

1. f_{134}^{5} − f_{14}^{5} + f_{24}^{5} − f_{34}^{5} − f_{2}^{5} + f_{3}^{5}

2. f_{124}^{5} − f_{12}^{5} + f_{13}^{5} − f_{14}^{5} + f_{2}^{5} − f_{3}^{5}.

3. f_{1234}^{5} − f_{123}^{5} − f_{234}^{5} + f_{13}^{5} − f_{14}^{5} + f_{23}^{5} + f_{24}^{5} − f_{2}^{5}.

4. f_{1234}^{5} − f_{123}^{5} − f_{234}^{5} + f_{13}^{5} − f_{14}^{5} + f_{23}^{5} + f_{24}^{5} − f_{3}^{5}.

5. f_{124}^{5} + f_{234}^{5} − f_{12}^{5} + f_{13}^{5} − f_{14}^{5} − f_{23}^{5} − f_{24}^{5} + f_{2}^{5}.

6. f_{123}^{5} + f_{134}^{5} − f_{34}^{5} + f_{24}^{5} − f_{14}^{5} − f_{23}^{5} − f_{13}^{5} + f_{3}^{5} .

7. f_{134}^{5} + f_{124}^{5} − f_{13}^{5} − f_{14}^{5} + f_{23}^{5} − f_{24}^{5}.

For rank 6 direct calculation yields 796 extreme rays. Only 131 of them come from earlier extremes via lifting and convolution; the remaining 665 are new. An interesting problem would be to a find a reasonable characterization of the extreme rays of K_{n}.

References

[1] L. J. Billera and N. Liu, Noncommutative enumeration in ranked posets, preprint 1996.

[2] P. M. Cohn, On subsemigroups if free semigroups, Proc. Amer. Math. Soc. 13 (1962), 347–351.

[3] J. D. Edmonds and D. R. Fulkerson, Bottleneck extrema, J. Combinatorial Theory 8 (1970) 299–306.

[4] M. Grötschel, L. Lovász, and A. Schrijver, “Geometric Algorithms and Combinatorial Optimization,” Springer-Verlag, Berlin, 1988.

[5] G. Kalai, A new basis for polytopes, J. Combinatorial Theory, Ser A 49 (1988), 191–208.

[6] R. P. Stanley, Combinatorics and Commutative Algebra, Second Edition, Birkhäuser, Boston, 1996.

MSRI, 1000 Centennial Drive, Berkeley, CA 94720-5070