            Comments, corrections, and related references welcomed, as always!

TEXed June 8, 2018

SOME RESULTS ON COUNTING LINEARIZATIONS OF POSETS

GEORGE M. BERGMAN

Abstract. In section 1 we consider a 3-tuple S = (|S|, ≼, E) where |S| is a finite set, ≼ a partial ordering on |S|, and E a set of unordered pairs of distinct members of |S|, and study, as a function of n ≥ 0, the number of maps φ : |S| → {1, …, n} which are both isotone with respect to the ordering ≼, and have the property that φ(x) ≠ φ(y) whenever {x, y} ∈ E. We prove a number-theoretic result about this function, and use it in section 8 to recover a ring-theoretic identity of G. P. Hochschild.

In section 2 we generalize a result of R. Stanley on the sign-imbalance of posets in which the lengths of all maximal chains have the same parity.

In sections 3-6 we study the linearization-count and sign-imbalance of a lexicographic sum of n finite posets P_{i} (1 ≤ i ≤ n) over an n-element poset P_{0}. We note how to compute these values from the corresponding counts for the given posets P_{i}, and for a lexicographic sum over P_{0} of chains of lengths card(P_{i}). This makes the behavior of lexicographic sums of chains over a finite poset P_{0} of interest, and we obtain some general results on the linearization-count and sign-imbalance of these objects.

This material is far from my areas of expertise. The referees for two journals were not enthusiastic about it, so I have decided not to publish it, but I am keeping it available online in case it should prove of interest to someone.

1. Denominators of order-chromatic polynomials

In this section, for S = (|S|, ≼, E) as in the first paragraph of the abstract, we show that the function of n defined in that sentence is a polynomial with rational coefficients, and we obtain a bound on the primes dividing its denominator. This bound is used, as indicated, in section 8 (an appendix, which depends only on the present section).

Some background: Recall that the chromatic polynomial of a finite graph G is the function f associating to every positive integer n the number of colorings of the vertices of G with n colors (not all of which need be used), such that adjacent vertices have different colors. (We will recover below the fact that f is indeed a polynomial function.)

Richard Stanley notes in [4] that if P = (|P |, ≼) is a finite poset (partially ordered set), then the function e associating to every positive integer n the number of isotone maps φ : P → {1, …, n} (i.e., maps φ : |P | → {1, …, n} such that x ≼ y ⟹ φ(x) ≤ φ(y)) is also given by a polynomial, conceptually similar to the chromatic polynomial of a graph, and that the same is true of the function \overline{e} associating to n the number of strictly isotone maps P → {1, …, n} (maps such that for distinct x, y, one has x ≼ y ⟹ φ(x) < φ(y)).

To see the above fact for the function e, let us break the process of choosing an isotone map φ : P → {1, …, n} into three steps. First, decide which elements will fall together under φ. Calling the quotient poset arising from these identifications P′, choose, next, the linear order which the embedded image of |P′| in {1, …, n} is to have. Finally, choose a way of embedding the resulting linearly ordered set into {1, …, n}. Now if we write

(1)  m = card(P),

then the number of elements of each P′ will be some m′ ≤ m, and once a linear ordering of such a |P′| has been chosen, the number of embeddings of the resulting linearly ordered set in {1, …, n} will be the number of ways of choosing m′ out of n elements, which is the binomial coefficient \binom{n}{m′} = n(n − 1) … (n − m′ + 1)/m′! . This is a polynomial in n of degree m′ over the rational numbers. Summing the polynomials arising in this way from all linearly ordered sets obtained as in the first two steps above, we get a polynomial of degree m.

2010 Mathematics Subject Classification. Primary: 05C31, 06A07. Secondary: 05A10, 16U99.

Key words and phrases. linearization-count of a poset, sign-imbalance of a poset, lexicographic sum of posets, integer polynomial.

This note is readable online at /~gbergman/papers/unpub and http://arxiv.org/abs/arXiv:

1802.01712 .

Now the coefficients of this polynomial can clearly be written to the common denominator m!, so every prime dividing the least common denominator of those coefficients is ≤ m. But we can get a better bound on such primes if the Hasse diagram of P has more than one connected component.

To do so, let us modify the procedure described above. The first step, choosing which elements of |P | fall together, remains the same; again let P′ denote the set so obtained, given with the weakest partial ordering making the map P → P′ isotone. (Here we are assuming that |P′| is a set-theoretic image of |P | which admits a partial ordering making the map |P | → |P′| isotone. The weakest such partial ordering is then the intersection of all such partial orderings.) At the second step, rather than strengthening that ordering to a linear ordering on |P′|, let us strengthen it to an ordering which is linear on each connected component of the Hasse diagram of P′, but leaves elements of distinct connected components incomparable. Finally, we choose a one-to-one isotone map of the resulting poset into {1, …, n}.

How many choices are there at that last step? If, under the ordering chosen at the second step, the connected components of P′ are chains P′_{1}, …, P′_{k}, of cardinalities m′_{1}, …, m′_{k} respectively, then there are \binom{n}{m′_{1}}

isotone embeddings of P′_{1} in \{1, …, n\}, then \binom{n−m′_{1}}{m′_{2}} such embeddings of P′_{2} in the remaining elements

of \{1, …, n\}, and so on. So the total number of isotone embeddings is \binom{n}{m′_{1}}\binom{n−m′_{1}}{m′_{2}} … \binom{n−m′_{1}−...−m′_{k−1}}{m′_{k}}, which, writing m′_{1} + ⋯ + m′_{k} = m′ = card(|P′|), is the multinomial coefficient

(2)  n(n − 1) … (n − m′ + 1)/m_{1}! … m_{k}! .

This is a polynomial in n whose denominator is divisible only by primes that are less than or equal to one of the m′_{i}, so we need to know how large the m′_{i}, the cardinalities of the components of P′, can be.

Suppose the original poset P had c connected components. Each identification of two elements of P reduces the number of connected components by at most one, hence if P′ has m′ elements, and so has undergone m − m′ identifications, it still has at least c − (m − m′) components. The largest that such a component can be is m′ minus the number of other components, so each component has at most m′ − (c − (m − m′) − 1) = m − c + 1 elements.

Thus, m − c + 1 is an upper bound on the primes that can occur in the denominator of (2). Summing over all choices of our image P′ of P, and all componentwise linearizations thereof, we conclude that the polynomial giving the number of isotone maps P → {1, …, n} has denominator divisible only by primes less than or equal to m − c + 1.

As noted in the abstract, we actually want to count the smaller set of such maps φ : P → {1, …, n} that satisfy an additional set of restrictions on which pairs of elements of P can fall together under φ. But such restrictions do not affect the above argument: they limit the set of images P′ that we enumerate at the first step, while our bound on primes in the denominator comes from the last step. So we have

Theorem 1. Let S be a 3-tuple (|S|, ≼, E), where |S| is a finite set, ≼ a partial ordering on |S|, and E a set of unordered pairs of distinct members of |S|. Let c be the number of connected components of the Hasse diagram of the poset (|S|, ≼), and for each n ≥ 0, let C(S, n) be the number of maps φ : |S| → {1, …, n} which are both isotone with respect to the ordering ≼, and have the property that φ(x) ≠ φ(y) whenever {x, y} ∈ E.

Then C(S, n) is a polynomial in n with rational coefficients, such that all primes dividing the denominators of those coefficients are ≤ card(|S|) − c + 1. □

Note that in the case of the above result where ≼ is the trivial ordering, i.e., where S is an antichain, C(S, n) is the chromatic polynomial of the graph (|S|, E). In that case c = card(|S|), so the theorem says C(S, n) is a polynomial with integer coefficients; which is indeed true of chromatic polynomials [7, §IX.2].

Theorem 1 actually remains true if we allow arbitrary Boolean conditions on which elements fall together. For instance, for particular x_{1}, x_{2}, y_{1}, y_{2} ∈ |S|, the condition, “if x_{1} falls together with y_{1}, then x_{2} falls together with y_{2} ” would cause no difficulties with the proof. I have assumed the conditions to have the simple form stated in the theorem because such conditions seem to occur naturally; in particular, the problem that motivated this result, studied in section 8 below, has conditions of that form. The result for arbitrary Boolean expressions in such conditions is, in any case, easily deduced from Theorem 1 by inclusion-exclusion considerations.

On the other hand, Theorem 1 does not remain true if we allow our additional restrictions to involve the order relations among elements φ(x); for instance, if for some particular x, y ∈ |S| we consider only maps φ such that φ(x) ≤ φ(y). To impose such a condition is equivalent to replacing the P of our introductory discussion by a poset with its order relation ≼ strengthened; and this can fuse distinct connected components without reducing the number of elements. So, for instance, if (|S|, ≼) is an m-element antichain, then an obvious set of conditions of the above form restricts us to maps |S| → {1, …, n} which are isotone with respect to a particular total ordering ≼′ of |S|, and the number of such maps is \binom{n+m−1}{m}, a polynomial with denominator m! , despite the fact that the original antichain ordering ≼ satisfies m − c + 1 = 1.

The following consequence of Theorem 1 will be used in section 8. Recall that the chromatic number of a graph is the least positive integer n at which the chromatic polynomial of the graph is nonzero.

Corollary 2. Let S = (|S|, ≼, E) and c be as in Theorem 1, and p be any prime greater than card(|S|) − c + 1.

Then for every positive integer n whose residue modulo p is less than the chromatic number of the graph (|S|, E), the integer C(S, n) is divisible by p. In particular, if |S| is nonempty, then C(S, n) is divisible by p whenever n is divisible by p.

Proof. By Theorem 1 we may write C(S, n) = f(n)/r, where f is a polynomial with integer coefficients, and r an integer not divisible by p. The residue of f(n) modulo p depends only on the residue of n modulo p, hence as r is invertible modulo p, the same is true of the residue of C(S, n) = f(n)/r. Now for positive n_{0} less than the chromatic number of (|S|, E), there are no maps of |S| into {1, …, n_{0}} which distinguish x and y whenever {x, y} ∈ E, in particular, no isotone maps with that property; hence C(S, n_{0}) = 0 for such n_{0}. Hence for n congruent to a value n_{0} in that range, we have C(S, n) ≡ _{(mod p)} C(S, n_{0}) = 0.

The final sentence follows because every nonempty graph has chromatic number greater than zero. □

The remaining sections of this paper, other than the appendix section 8, are related to this one only in that they involve counting linear images of posets, and use somewhat similar methods.

A belated remark on notation: At the end of the third paragraph of this section, I spoke of the condition that “for distinct x, y, one has x ≼ y ⟹ φ(x) < φ(y) ”, where it would be more natural to say that for all x, y, one has x ≺ y ⟹ φ(x) < φ(y). But I am avoiding the use of “ ≺ ” for strict ≼-inequality because many authors use x ≺ y for the condition that y covers x with respect to a partial order ≤, i.e., that x < y and there is no element z with x < z < y. At a few places below, we will indeed consider the covering relation, though we will not introduce any notation for it. However, I felt it best to avoid confusion with a notation commonly used by others.

2. The sign-imbalance of a bicolorable poset

If X is a set of n < ∞ elements, then there are precisely n! bijections X → {1, …, n}, and given one such bijection b, we can write any other as π b for a unique permutation π of {1, …, n}. In this situation, one calls a bijection X → {1, …, n} “even” or “odd” (relative to b), or equivalently, of sign +1 or −1, according to whether π is an even or an odd permutation. Clearly, replacing b with another bijection X → {1, …, n} either preserves or reverses this classification of bijections.

If P = (|P |, ≼) is an n-element poset, then the isotone bijections |P | → {1, …, n} correspond naturally to linearizations of P (total orderings refining ≼), and one calls a linearization even or odd if the corresponding bijection is so. The number of linearizations that are even minus the number that are odd is called the sign-imbalance of the poset P (see [5] and papers referenced there). If that number is zero, P is called sign-balanced. The sign-imbalance is, of course, unique only up to sign, unless a particular ordering b relative to which it is calculated has been specified.

In studying the sign-imbalance of a finite poset P, our method will again be to break the choice of a linearization of P into steps, such that for each partial ordering achieved at the next-to-last step, the number of choices available at the final step is easy to describe.

Since only one-to-one images of P are considered, we have no use for a graph structure E on |P | restricting which elements fall together. We will, however, make use of the graph structure of the Hasse diagram of P, via Definition 3. A bicoloring of a finite poset P = (|P |, ≼) will mean a coloring of its Hasse graph with two colors; that is, a partition of |P | into two subsets, such that whenever one element of |P | covers another, the elements belong to different members of the partition (“have opposite colors”).

Thus, P admits a bicoloring if and only if every cycle in its Hasse diagram has an even number of vertices. If P = (|P |, ≼) is a finite poset on which we have a bicoloring, and ≤ is some total ordering refining

the given partial ordering ≼, let us break |P | into the “blocks” of elements of the same color that are consecutive under ≤ . That is, let |P |_{1} be the subset of |P | consisting of the least element under ≤ , and all elements of the same color (if any) that follow it under ≤ without an intermediate element of the opposite color; let |P |_{2} consist of the first element of the other color, and those that similarly follow it, |P |_{3} the next block (which has the same color as |P |_{1}), and so on. Note that within each |P |_{i}, all elements are incomparable under ≼, since by the definition of a bicoloring, any two comparable elements of the same color have an element of the opposite color between them under ≼ , and hence under ≤ .

In the above situation, we can define an intermediate partial ordering ≤_{pre} on |P |, under which members of each |P |_{i} are incomparable, as they are under ≼, while whenever x ∈ |P |_{i} and y ∈ |P |_{j} with i < j, we let x ≤_{pre} y. We shall call the partial ordering ≤_{pre} the “prelinearization” of ≼ determined by the linearization ≤ .

Let us call linearizations ≤ and ≤′ of ≼ “block-equivalent” if the prelinearizations ≤_{pre} and ≤′_{pre} are the same. Given a prelinearization of P, with block decomposition |P | = |P |_{1} ∪ |P |_{2} ∪ ⋯ ∪ |P |_{m}, the set of linearizations ≤ of ≼ that determine that prelinearization (a block-equivalence-class of linearizations of ≼) will have exactly card(|P |_{1})! card(|P |_{2})! … card(|P |_{m})! elements, every such linearization being obtained by choosing an arbitrary linearization of each |P |_{i}. The sign of each such linearization of P will be, up to a fixed factor ±1, the product of the signs of the linearizations of these subsets.

Now if any |P |_{i} has cardinality greater than 1, then the card(|P |_{i})! choices for the ordering of that block will be half even and half odd, so the parities of the linearizations in the whole block-equivalence class will be equally split between odd and even. Hence in computing the summation of +1’s and −1’s that gives the sign-imbalance of P, it suffices to look at linearizations in which each same-color block is a singleton; in other words, linearizations for which the given coloring of P is still a bicoloring. Let us call such a linearization compatible with the given bicoloring. Then the above discussion yields

Theorem 4. If P = (|P |, ≼) is a finite bicolored poset, then the sign-imbalance of the set of all linearizations of P (relative to any fixed indexing of |P |) is equal to the sign-imbalance (relative to the same indexing) of the set of linearizations compatible with the given bicoloring.

In particular, if P has no linearizations compatible with the given bicoloring, then it is sign-balanced. □

Easy examples of bicolored posets P with no compatible linearizations are those in which the difference between the numbers of elements of the two colors is greater than 1. If a poset P has only one connected component, then a bicoloring of P, if one exists, is unique up to interchange of colors; an example in which this essentially unique bicoloring has the property just mentioned is [figure], with three elements of one color and just one of the other. So that poset is sign-balanced.

If a bicolorable poset has more than one connected component, we have a larger choice of bicolorings. For instance, if P consists of two connected components, each of which is a chain with an odd number of elements, and we bicolor those chains so that their least elements have the same color, then we find that the difference between the total numbers of elements of the two colors is 2; so this poset, too, is sign-balanced. If instead we color the two chains so that their least elements have opposite colors, then P has the same number of elements of each color; so though we have just seen that it is sign-balanced, this second bicoloring does not give a proof of that fact.

Examples of non-sign-balanced posets are [figure] and [figure]; as one can quickly check by counting.

Theorem 4 allows us to give an alternative proof of the following result of R. Stanley. (The formulation of that result in [5] refers to the length of chains, i.e., the number of steps, which is one less than the cardinality of the chain, in terms of which I state it here.)

Lemma 5 (R. Stanley [5, Corollary 2.2]). If a finite poset P = (|P |, ≼) has the property that the cardinalities of its maximal chains all have the same parity, and this is the opposite of the parity of the cardinality of P, then P is sign-balanced.

Proof. The fact that the cardinalities of all maximal chains of P have the same parity implies in particular that for each x ∈ |P |, the cardinalities of all maximal chains in the downset generated by x have a common parity. (Otherwise, by combining two such chains of different parities with a common maximal chain in the upset generated by x, one would get two maximal chains in P of different parities.) Classifying elements x according to whether maximal chains below x all have odd or even cardinality, we get a bicoloring of P, under which all minimal elements have a common color. From this we see that if the common parity of the cardinalities of all maximal chains of P is odd, the maximal elements of P will all be of the same color as the minimal elements, while if it is even, they will all have the other color.

Suppose now that P has a linearization compatible with the above bicoloring. Because the parity of P is the opposite of that of its maximal chains, the relationship between the colors of the elements at the bottom and top of this linearization (same-color versus different-color) will be the opposite of what is the case for maximal chains of P.

On the other hand, the bottom element of the linearization must be the bottom element of one of those maximal chains, and hence must be of the color which all those bottom elements have, and the top element must similarly be the color of the top elements of all the maximal chains, so, in contradiction to the preceding paragraph, the relationship between the colors of elements at the top and bottom of this linearization must be the same as for maximal chains of P. This contradiction shows that no compatible linearization of P can exist; so by Theorem 4, P is sign-balanced. □

An easy example to which the above lemma applies is that in which P has two connected components, each a chain of odd cardinality (for which we got the same conclusion in the second paragraph after Theorem 4). Two more easy examples are the posets [figure]and [figure].

3. Bringing sign-imbalance and linearization-count together

If P is a finite poset, let L_{0}(P) denote the number of even linearizations of P, and L_{1}(P) the number of odd linearizations (relative to some fixed linearization). Then it is natural to associate to P the element L(P) = L_{0}(P) + L_{1}(P) ζ of the group ring ℤ{1, ζ}, where {1, ζ} is the 2-element group, written multiplicatively.

ℤ{1, ζ} admits two ring homomorphisms to ℤ, taking ζ to +1 and −1 respectively; thus, the former carries L(P) to L_{0}(P) + L_{1}(P), the number of linearizations of P, which we shall denote L_{+}(P), while the latter carries it to L_{0}(P) − L_{1}(P), the sign-imbalance of P, which we shall denote L_{−}(P). These homomorphisms together yield an embedding of ℤ{1, ζ} in ℤ × ℤ, whose image is {(a, b) ∈ ℤ × ℤ | a ≡ b (mod 2)}. The image of L(P) = L_{0}(P) + L_{1}(P) ζ under this embedding, (L_{+}(P), L_{−}(P)), will be denoted L_{±}(P).

For any finite poset P, the element L(P) lies in the subsemiring ℕ{1, ζ} of ℤ{1, ζ} consisting of elements in which the coefficients of 1 and ζ are both nonnegative. The image of this semiring under the above ring embedding is

(3)  {(a, b) ∈ ℤ × ℤ | a ≡ b (mod 2) and |b| ≤ a}.

It will follow from Theorem 7 below that for various finite posets P and P′, we can say that the number of linearizations L_{+}(P) is a multiple of L_{+}(P′). (For instance, this is true if P′ is any of the connected components of P.) In such situations, it is not surprising to find that the sign-imbalance L_{−}(P) is, likewise, a multiple of L_{−}(P′). But in fact, one typically has the stronger statement that L(P) is a multiple of L(P′) in ℕ{1, ζ}, equivalently, that the ordered pair L_{±}(P) is a multiple of L_{±}(P′) in the semiring (3).

So, for instance, if L_{±}(P′) = (4, 2), then L_{±}(P) cannot be (12, 0) or (8, 2) or (8, 8). Separate consideration of the numbers L_{+}(P) and L_{−}(P) would not exclude these values; but the pairs of integers by which (4, 2) would have to be multiplied to get them would be (3, 0), (2, 1) and (2, 4), of which the first two don’t have coordinates of the same parity, while the last fails to satisfy the inequality |b| ≤ a of (3). (The element (2, 4) ∈ ℤ × ℤ corresponds to 3 − ζ ∉ ℕ{1, ζ}.)

We will, in the next three sections, consider L_{+} and L_{−} together. We will encounter both parallelisms and contrasts between their behaviors.

We remark that the element L(P) ∈ ℕ{1, ζ} defined above is the image, under the homomorphism taking q to ζ, of the polynomial I_{P,ω}(q) defined by Stanley in [5, p.881, display (1)]. That polynomial depends in a much stronger way than L(P) on the reference linearization (expressed there by an indexing ω of |P |), and, as Stanley notes, does not seem easy to understand.

4. The linearization-count and sign-imbalance of a lexicographic sum

4.1. Review of lexicographic sums. Suppose P_{0} = (|P_{0}|, ≼_{0}) is a poset, and that for each x ∈ |P_{0}| we are given a poset P_{x} = (|P_{x}|, ≼_{x}). Then we can form the disjoint union of the sets |P_{x}|, say constructed as {(x, x′) | x ∈ |P_{0}|, x′ ∈ |P_{x}|}, and give this set a partial ordering under which, for each x ∈ |P_{0}|, the copy {(x, x′) | x′ ∈ |P_{x}|} of |P_{x}| is made order-isomorphic to P_{x} via the correspondence (x, x′) ↦ x′, while for x ≠ y in |P_{0}|, the order-relation between elements (x, x′) and (y, y′) (x′ ∈ |P_{x}|, y′ ∈ |P_{y}|) is determined solely by their first components: (x, x′) ≼ (y, y′) if and only if x ≼_{0} y.

For finite posets, considered below, we shall find it convenient to assume |P_{0}| indexed as {x_{1}, …, x_{m_{0}}}. We shall then abbreviate P_{x_{i}} = (|P_{x_{i}}|, ≼_{x_{i}}) to P_{i} = (|P_{i}|, ≼_{i}), and assume that each |P_{i}| is indexed as {x_{i,1}, …, x_{i,m_{i}}}, with distinct symbols x_{i,j} (i ≤ m_{0}, j ≤ m_{i}) denoting distinct elements. This makes the |P_{i}| disjoint, so we can forego the construction of their disjoint union by ordered pairs, and simply take the underlying set of our lexicographic sum to be their union. Choosing a notation for such a lexicographic sum, and summarizing the above description of it, we have

(4)

P_{0} ∗ (P_{1}, …, P_{m_{0}}) = (|P |, ≼) = P, where
|P | = {x_{i,j} | 1 ≤ i ≤ m_{0}, 1 ≤ j ≤ m_{i}}, and
x_{i,j} ≼ x_{i′,j′} if and only if either
i ≠ i′ and x_{i} ≼_{0} x_{i′} (in P_{0}), or
i = i′ and x_{i,j} ≼_{i} x_{i,j′} (in P_{i}).

Two easy classes of examples: A poset P decomposed into its connected components P_{i} can be regarded as the lexicographic sum of the P_{i} over an antichain P_{0}; in particular, the next-to-last steps in the construction of section 1 were lexicographic sums of chains over antichains. On the other hand, the “prelinearizations” that occurred at the next-to-last step in section 2 were lexicographic sums of antichains over chains.

In a lexicographic sum P_{0} ∗ (P_{1}, …, P_{m_{0}}), some or all of the P_{i} may be empty. Occasionally, such cases will require special consideration.

Let us make

Convention 6. In the context of (4), for the purpose of defining the parities of linearizations, we define on each |P_{i}| (0 ≤ i ≤ m_{0}) the linear reference order x_{i,1} ≼_{i,ch} … ≼_{i,ch} x_{i,m_{i}} (where ch is mnemonic for “chain”), and for each i we shall write P_{i,ch} = (|P_{i}|, ≼_{ch}).

On |P_{0} ∗ (P_{1}, …, P_{m_{0}})| we likewise define the reference order

(5)  x_{1,1} ≼_{ch} … ≼_{ch} x_{1,m_{1}} ≼_{ch} … ≼_{ch} x_{m_{0},1} ≼_{ch} … ≼_{ch} x_{m_{0},m_{m_{0}}} .

4.2. Computing L of a lexicographic sum. Sections 1 and 2 both used the idea, “linearize the pieces, and see how you can combine the resulting chains”. This idea is abstracted in the following easy result.

Theorem 7. In the context of (4) and Convention 6, we have

(6)  L(P_{0} ∗ (P_{1}, …, P_{m_{0}})) = (∏_{1≤i≤m_{0}} L(P_{i})) · L(P_{0} ∗ (P_{1,ch}, …, P_{m_{0},ch})).

(Hence, the same is true with L everywhere replaced by L_{±}, or by L_{+}, or by L_{−}.)

Sketch of proof. To obtain the general linearization of the poset P_{0} ∗ (P_{1}, …, P_{m_{0}}) = (|P |, ≼), let us first choose the linear order to be used on each |P_{i}|, which can be any linearization of ≼_{i}, then specify how the union of the resulting chains is to be ordered. By the definition of lexicographic sum, the order-relation in P_{0} ∗ (P_{1}, …, P_{m_{0}}) = (|P |, ≼) between any element of P_{i} and any element of P_{j} with i ≠ j, depends only on i and j; hence for each way of linearizing the separate P_{i}, the ways of linearizing their union which are compatible with those linearizations and with the ordering of P_{0} ∗ (P_{1}, …, P_{m_{0}}) = (|P |, ≼) correspond to the ways of linearizing a lexicographic sum over P_{0} of a family of chains of the corresponding lengths, of which P_{0} ∗ (P_{1,ch}, …, P_{m_{0},ch}) is one. It is also not hard to check that the parity of a linearization of P_{0} ∗ (P_{1}, …, P_{m_{0}}) (relative to the reference-ordering ≼_{ch}) is the product of the parities of the induced linearizations of the P_{i} (relative to the reference-orderings ≼_{i,ch}) and that of the corresponding linearization of P_{0} ∗ (P_{1,ch}, …, P_{m_{0},ch}) (again relative to ≼_{ch}). The equality (6) follows.

The final parenthetical assertion follows because the operator L_{±} is the composite of the operator L with a ring homomorphism ℤ{1, ζ} → ℤ × ℤ, and L_{+}, L_{−} are in turn the composites of L_{±} with the projection homomorphisms ℤ × ℤ → ℤ. □

4.3. Results on lexicographic sums of chains. For Theorem 7 to be useful, we need to be able to compute L(P) for P a lexicographic sum of chains. We obtain results in this direction below. Since in these results, the chains in question are not given as listings of the elements of other posets, we adjust our notation slightly.

Definition 8. Let P_{0} = (|P_{0}|, ≼_{0}) be a finite poset, with |P_{0}| = {x_{1}, …, x_{m_{0}}}. Then for nonnegative integers m_{1}, …, m_{m_{0}}, we define

(7)  L(P_{0}; m_{1}, …, m_{m_{0}}) = L(P_{0} ∗ (C_{1}, …, C_{m_{0}}))

where for 1 ≤ i ≤ m_{0}, C_{i} = (|C_{i}|, ≼_{i}) is a chain of m_{i} elements x_{i,1} ≼_{i} … ≼_{i} x_{i,m_{i}}, these chains being understood to be pairwise disjoint, and the parities of linearizations of their lexicographic sum being taken relative to the reference ordering (5)

We will also use the notation corresponding to (7) with L_{0}, L_{1}, L_{+}, L_{−} and L_{±} in place of L.

A trivial case is

Proposition 9. Suppose, in Definition 8, that P_{0} is a chain, x_{1} ≼_{0} … ≼_{0} x_{m_{0}}. Then for all m_{1}, …, m_{m_{0}}, L(P_{0}; m_{1}, …, m_{m_{0}}) = 1. Equivalently, L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) = L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) = 1.

Proof. With P_{0} and all of C_{1}, …, C_{m_{0}} being chains, we see that P_{0} ∗ (C_{1}, …, C_{m_{0}}) is a chain, so it has just one linearization. This is our reference ordering, so it has even parity, giving our first conclusion, which is equivalent to the final equation. □

If P_{0} is an antichain we can also get an exact result. In the proofs of Proposition 10 below, and of Theorem 11, which will generalize the hard part of that result, we shall, following [5], use the imagery of “dominoes”. Namely, to partly or completely cover a poset P with dominoes means to distinguish certain non-overlapping pairs of elements (x, y) such that y covers x (i.e., x and y are distinct elements, such that x ≼ y and there are no elements strictly between these). If (x, y) is a pair which we have so distinguished, we will speak of there being a domino lying over x and y.

(Richard Stanley has pointed out to me that Proposition 10 is essentially known: Parts (i) and (ii) can be obtained by setting q = −1 in formula (1.68) of [6], and calling on (1.66) and (1.87) thereof.)

Proposition 10. Suppose, in the context of Definition 8, that P_{0} is an antichain.

Then the linearization count L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) is the multinomial coefficient

(8)  (∑_{1≤i≤m_{0}} m_{i}) ! / ∏_{1≤i≤m_{0}} m_{i}! .

On the other hand, the sign-imbalance L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) is described as follows:

(i) If at most one of m_{1}, …, m_{m_{0}} is odd, then L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) is the multinomial coefficient

(9)  (∑_{1≤i≤m_{0}}⌊m_{i}/2⌋) ! / ∏_{1≤i≤m_{0}}⌊m_{i}/2⌋! .

(ii) If more than one of m_{1}, …, m_{m_{0}} are odd, then L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) = 0.

Proof. The number L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) of linearizations of our lexicographic sum of chains is the number of ways of partitioning the ∑_{1≤i≤m_{0}} m_{i} positions available in such a linearization into subsets of cardinalities m_{1}, …, m_{m_{0}}, and (8) is a standard description of this number [6, p.20].

To get information on L_{−}(P_{0}; m_{1}, …, m_{m_{0}}), let us cover as much as we can of each linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}) with dominoes, starting from the bottom. Thus, if ∑ m_{i} is even, each linearization of our lexicographic sum will be entirely covered, while if it is odd, all but the top element of each linearization will be covered.

I claim that the set of linearizations which, when dominoes are so placed, have the property that at least one domino lies over two elements that are incomparable under ≼ is sign-balanced. Indeed, let us pair off these linearizations as follows. Given such a linearization, find, among dominoes that lie over ≼-incomparable pairs, the top one, and form a new linearization by reversing the positions of the pair of elements it lies over. Because those elements are ≼-incomparable, the result will again be a linearization of ≼; and because exactly one pair has been interchanged, the new linear order has parity opposite to the old one. It is also clear that the above construction, applied to the new linearization, returns the original one, so we indeed have a pairing. Hence the contributions to the sign-imbalance of those linearizations sum to zero.

Thus, to determine the sign-imbalance of P_{0} ∗ (C_{1}, …, C_{m_{0}}), it suffices to consider linearizations which, when dominoes are set down as above, have the property that every domino lies over a pair of comparable elements. Let us call such a linearization of ≼ distinguished.

Since elements from different chains C_{i} are incomparable, a distinguished linearization will have the property that every domino lies over a pair of elements from the same C_{i}. More precisely, we see by induction, working up from the bottom, that every domino will lie over a pair of the form (x_{i,2j−1}, x_{i,2j}). From this it easily follows that any distinguished linearization can be turned into our reference ordering (5) by repeatedly switching the places of two adjacent dominoes (hence, reordering a string w < x < y < z as y < z < w < x), or moving a domino past the lone dominoless element, if there is one (reordering a string x < y < z as z < x < y.) A movement of either sort can be done using 2 transpositions of elements, so in each case, the parity of the linearization does not change. Hence every distinguished linearization is even, so the sign-imbalance of P_{0} ∗ (C_{1}, …, C_{m_{0}}) equals the number of distinguished linearizations.

From the above considerations, we can see that if there exists a distinguished linearization, at most one of the C_{i} can have odd cardinality (the C_{i} to which the “lone element”, if any, at the top of a distinguished linearization belongs). This immediately gives statement (ii).

To get statement (i), suppose first that all the m_{i} are even. Then it is not hard to see that each distinguished linearization is determined by noting how the (∑ m_{i})/2 dominoes are partitioned into m_{1}/2 dominoes lying over pairs of members of C_{1}, m_{2}/2 lying over pairs of members of C_{2}, etc.. By the same counting principle used in getting (8), the number of such partitions is (∑ m_{i}/2) !/ ∏(m_{i}/2) ! , which agrees with (9) in this case.

Now suppose instead that exactly one of the m_{i}, say m_{i_{0}}, is odd. Then in a distinguished linearization, the one element not under any domino, namely, the top element of our linearization, is necessarily the largest element of the chain C_{i_{0}}. So a distinguished linearization will be determined by the arrangement of the dominoes covering the remaining elements, and as before, the number of possibilities is described by (9). □

For general P_{0}, we do not have an exact formula for L_{+}(P_{0}; m_{1}, …, m_{m_{0}}); but we can again get a result on L_{−}(P_{0}; m_{1}, …, m_{m_{0}}), in the spirit of the above proposition.

Theorem 11. Given P_{0} as in Definition 8, and nonnegative integers m_{1}, …, m_{m_{0}}, let

(10) S = {x_{i} | m_{i} is odd } ⊆ |P_{0}|.

Then

(i) If S forms a chain under ≼_{0} (possibly the empty chain), then we have

(11) L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) = ± L_{+}(P_{0}; ⌊m_{1}/2⌋, …, ⌊m_{m_{0}}/2⌋),

with the + sign applying if the reference ordering of P_{0} is isotone on S. (ii) If, on the other hand, S contains two elements x_{i_{0}} and x_{i_{1}} which are incomparable, and which are majorized by exactly the same set of other elements of P_{0}, or alternatively, which majorize exactly the same set of other elements of P_{0}, then

(12) L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) = 0.

Proof. Let us place dominoes on each linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}), say with ordering ≤, as follows, working upward from the bottom.

Suppose inductively that we have specified where dominoes are to be placed on our linearization up to a certain point, but not all the way to the top. Let x_{i,j} be the least element such that we have not specified whether a domino is to be placed on it. If x_{i,j} is the greatest element of our linearization, then clearly we can put down no more dominoes; in particular, x_{i,j} will remain uncovered. If, rather, x_{i,j} is followed immediately either by another element from same chain C_{i}, or by an element which belongs to a different chain C_{i′}, and is ≼-incomparable with x_{i,j}, let us put a domino over this pair of elements. Finally, if x_{i,j} is followed in our linearization by an element x_{i′,j′} with i′ ≠ i and x_{i} ≼_{0} x_{i′}, we put no domino over x_{i,j} (so that our recursive construction will continue with x_{i′,j′} in the role that x_{i,j} had).

Having placed dominoes in this manner on every linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}), we note that, as in the proof of Proposition 10, if a linearization has a domino placed over two incomparable elements, then looking at the highest domino with this property, and reversing the order of the elements under it, we get another linearization, of the opposite parity, on which the dominoes will have been placed over the same pairs of elements. This again pairs off linearizations of opposite parities, hence we can again ignore linearizations so paired in determining L_{−}(P_{0}; m_{1}, …, m_{m_{0}}).

Let us again call those linearizations which are not so paired, i.e., which involve dominoes only over pairs (x_{i,j}, x_{i,j+1}) of elements of the same chain C_{i}, “distinguished”.

Note that the way we have placed dominoes on our linearizations insures that if an element x_{i,j} is not under a domino, then it must be the largest element of the chain C_{i} to which it belongs, namely, x_{i,m_{i}}. (Indeed, otherwise, the larger elements of C_{i} would lie above it, so it could not be the top element of the linearization; and they would lie between it and the elements of any C_{i′} with x_{i} ≼_{0} x_{i′}, so it would not get skipped in the process of setting down dominoes.) Clearly, also, if such an element is not the largest element in the whole linearization, then the element that follows it must have the form x_{i′,1}. Finally, if our linearization is distinguished, then all pairs of elements under dominoes must have the form (x_{i,j}, x_{i,j+1}); and for each i, we again see by induction that dominoes will cover precisely the pairs (x_{i,2j−1}, x_{i,2j}) for 1 ≤ j ≤ ⌊m_{i}/2⌋. Thus, the top element x_{i,m_{i}} of a chain C_{i} will not lie under a domino if and only if m_{i} is odd.

Now in every distinguished linearization of P_{0}∗(C_{1}, …, C_{m_{0}}), the ∑_{1≤i≤m_{0}}⌊m_{i}/2⌋ dominoes must be arranged in one of the L_{+}(P_{0}; ⌊m_{1}/2⌋, …, ⌊m_{m_{0}}/2⌋) ways corresponding to linearizations of the lexicographic sum over P_{0} of a family of chains of lengths ⌊m_{i}/2⌋. I claim that if, as in the hypothesis of statement (i), the set S defined in (10) forms a chain in P_{0}, then (a) each of the above arrangements of dominoes appears in one and only one distinguished linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}), and (b) if the reference ordering of P_{0} is isotone on S, then all distinguished linearizations have even parity. This will prove (i).

To see assertion (a), assume we are given a linearization of the indicated family of dominoes, and let us see why there is a unique way of placing the “lone” elements x_{i,m_{i}} (x_{i} ∈ S) among them so as to get a distinguished linearization of P. Note that since S is a chain in P_{0}, the relative ordering of those lone elements is predetermined.

We first describe the unique position at which the highest lone element x_{i,m_{i}} can appear in such a linearization: If there is no x_{i′} in P_{0} with x_{i} ≼_{0} x_{i′}, then by our description of distinguished linearizations, x_{i,m_{i}} can only appear at the very top; while if there are such elements x_{i′}, they will necessarily belong to |P_{0}| − S, and x_{i,m_{i}} will necessarily appear just below the element x_{i′,1} with x_{i} ≼_{0} x_{i′} that appears lowest among such elements in our given domino-covered chain.

We now repeat this idea, working down the chain of elements x_{i} ∈ S : for each x_{i}, we place x_{i,m_{i}} just below the lowest element x_{i′,1} such that x_{i} ≼_{0} x_{i′} that we have already positioned. (This x_{i′,1} may or may not lie under a domino. It will not if x_{i′} ∈ S and m_{i′} happens to be 1; but in this case, by the order in which we have chosen to do things, it will be an element whose position we have already determined.) It is easy to see that the resulting ordering is indeed a linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}), in fact a distinguished linearization, and is the only distinguished linearization compatible with the given arrangement of dominoes.

Assuming now that the reference ordering of P_{0} is isotone on S, we see that each of the distinguished linearizations described above can be obtained from the reference linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}) by a series of steps, each of which either moves one domino past another, or moves a domino past a lone element. (By our assumption that the reference ordering of P_{0} is isotone on S, we never have to move one lone element past another.) Again, each of these steps acts by an even permutation, so our distinguished orderings indeed have even parity, proving (b), and hence proving (i) in the case where the reference ordering is isotone on S. In the contrary case, a change in the reference ordering will multiply L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) by ±1, giving the general case of (i).

Turning to (ii), suppose first that S contains incomparable elements x_{i_{0}} and x_{i_{1}} which are majorized by the same sets of other elements of P_{0}. Then in a distinguished linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}), the descriptions of where the elements x_{i_{0},m_{i_{0}}} and x_{i_{1},m_{i_{1}}} must occur are the same – at the top if the set of elements x_{i} ∈ |P_{0}| strictly greater than x_{i_{0}} (equivalently, strictly greater than x_{i_{1}}) is empty; otherwise, immediately below the lowest element x_{i,1} of the linearization such that x_{i} which is strictly greater than these elements. But x_{i_{0},m_{i_{0}}} and x_{i_{1},m_{i_{1}}} cannot both be in that position, so P_{0} ∗ (C_{1}, …, C_{m_{0}}) has no distinguished linearizations, and (12) follows.

If, rather, S has incomparable elements x_{i_{0}} and x_{i_{1}} which majorize the same set of other elements of P_{0}, the result follows from the above case by the invariance of the property of sign-balance under reversal of order. This completes the proof of (ii).

(Since our rule for placing dominoes, and hence our concept of distinguished linearization, are not invariant under reversal of order, we can’t claim in the last case that P_{0} ∗ (C_{1}, …, C_{m_{0}}) has no distinguished linearizations. Rather, a direct proof of (12) for that case would involve defining “reverse-distinguished” linearizations, and showing that P_{0} ∗ (C_{1}, …, C_{m_{0}}) has none of these.) □

If we apply the above theorem to the case where P_{0} is an antichain, then every subset S ⊆ |P_{0}| clearly falls under one of cases (i) or (ii) above, depending on whether it has ≤ 1 or > 1 elements, and we get the description of L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) in Proposition 10. The simplest examples of posets P_{0} for which not every subset S is covered by our theorem are the 4-element posets [figure]and [figure] , with S consisting, in each case, of the lower left and upper right elements. In the former case, the function L_{±}(P_{0}; m_{1}, m_{2}, m_{3}, m_{4}) is nevertheless easily evaluated. The second case looks harder, but I have not examined it closely.

5. Some properties of L_{±}(P_{0}; m_{1}, …, m_{m_{0}}) as a function of m_{0}, …, m_{m_{0}}

5.1. Motivation: the case where P_{0} is a 2-element antichain. Let us consider the simplest nontrivial case of Proposition 10, where m_{0} = 2. Then P_{0} ∗ (C_{1}, C_{2}) is the disconnected union of a chain of m_{1} elements and a chain of m_{2} elements, so its linearizations correspond to the ways of partitioning a chain of m_{1} + m_{2} elements into two sets, of m_{1} and m_{2} elements respectively. The number of these is the binomial coefficient \binom{m_{1}+m_{2}}{m_{2}}, so the values of L_{+}(P_{0}; m_{1}, m_{2}) are the entries of Pascal’s triangle. We display in (13) the first few rows of that triangle, and likewise, the values of L_{−}(P_{0}; m_{1}, m_{2}) given by that same proposition. In each array in (13), the rows correspond to the values of m_{1} + m_{2}, the diagonals going downward to the left to the values of m_{1}, and the diagonals going downward to the right to the values of m_{2}.

(13)  \begin{matrix}L_{+}(P_{0}; m_{1}, m_{2}) & L_{−}(P_{0}; m_{1}, m_{2}) \\ 1 & 1 \\ 1 1 & 1 1 \\ 1 2 1 & 1 0 1 \\ 1 3 3 1 & 1 1 1 1 \\ 1 4 6 4 1 & 1 0 2 0 1 \\ 1 5 10 10 5 1 & 1 1 2 2 1 1 \\ 1 6 15 20 15 6 1 & 1 0 3 0 3 0 1 \\ 1 7 21 35 35 21 7 1 & 1 1 3 3 3 3 1 1 \\ 1 8 28 56 70 56 28 8 1 & 1 0 4 0 6 0 4 0 1 \end{matrix}

The familiar rule for producing Pascal’s triangle, that each entry is the sum of the two above it in the preceding row, can be interpreted in terms of L_{+}(P_{0}; m_{1}, m_{2}) : If we classify linearizations of P_{0} ∗ (C_{1}, C_{2}) according to whether the top element belongs to C_{1} or C_{2}, then in the former case, the ordering of the remaining elements constitutes a linearization of the union of a chain of m_{1} − 1 elements and a chain of m_{2} elements, in the latter case, a linearization of a union of a chain of m_{1} elements and a chain of m_{2} − 1 elements.

The sign-imbalances L_{−}(P_{0}; m_{1}, m_{2}) turn out to satisfy a similar law: every entry that lies an even number of steps from the left-sloping edge of the array is, as in Pascal’s triangle, the sum of the two entries above it, while if an entry lies an odd number of steps from that edge, it is the difference of those two entries (the one to the left minus the one to the right). The reader can justify this rule by classifying linearizations of our union of chains as in the preceding paragraph, and examining how the parity of a linearization compares with the parity of the linearization of the one-element-smaller poset that we get on dropping the element at the top of that linearization.

(In fact, I discovered the formulas of Proposition 10(i)-(ii) by first studying the case m_{0} = 2, and obtaining the above recursive rule for L_{−}(P_{0}; m_{1}, m_{2}), then noticing the way values from Pascal’s triangle occurred in the resulting array, and thinking about how to justify that pattern.)

5.2. L_{±}(P_{0}; m_{1}, …, m_{m_{0}}) and one-variable polynomials. In general, L_{±}(P_{0}; m_{1}, …, m_{m_{0}}) is not a polynomial function of m_{1}, …, m_{m_{0}}. For instance, if P_{0} is a 2-element antichain as in the preceding subsection, we have L_{+}(P_{0}; m, m) = \binom{2m}{m} ≥ 2^{m}, so it grows too fast to be polynomial. But note also that if, in L_{+}(P_{0}; m_{1}, m_{2}) = \binom{m_{1}+m_{2}}{m_{1}}, we hold m_{2} constant, the resulting function is a polynomial in m_{1} (of degree m_{2}), while if we hold m_{1} constant, it is a polynomial in m_{2} (of degree m_{1}). Here is a similar result about L_{+} for general P_{0}, and a somewhat more complicated statement about L_{−}.

Proposition 12. Let P_{0} = (|P_{0}|, ≼_{0}) be a finite poset, with |P_{0}| = {x_{1}, …, x_{m_{0}}}, let i_{0} ∈ {1, …, m_{0}}, and for each i ≠ i_{0} in {1, …, m_{0}}, let us fix a value for m_{i}. Then, regarding L_{±}(P_{0}; m_{1}, …, m_{m_{0}}) as a function of m_{i_{0}}, we have

(a) L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) is a polynomial in m_{i_{0}}, whose degree is the sum of those values of m_{i} (i ≠ i_{0}) such that x_{i} is ≼_{0}-incomparable with x_{i_{0}}.

(b) The values of L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) are given by two polynomials in m_{i_{0}}, one for m_{i_{0}} even, the other for m_{i_{0}} odd. Each has degree less than or equal to ⌊∑ m_{i}/2⌋, where the summation is again over those i such that x_{i} is ≼_{0}-incomparable with x_{i_{0}}.

Proof. Again let C_{1}, …, C_{m_{0}} be disjoint chains of lengths m_{1}, …, m_{m_{0}}. Then a linearization of P = P_{0} ∗ (C_{1}, …, C_{m_{0}}) can be determined by first choosing an arbitrary linearization of the subposet with underlying set |P | − |C_{i_{0}}|, then specifying where to insert the elements of |C_{i_{0}}|.

To see where those elements can go, let us partition {1, …, m_{0}} − {i_{0}} into three subsets: the set I_{<} of those i such that x_{i} ≼_{0} x_{i_{0}}, the set I_{>} of those i such that x_{i_{0}} ≼_{0} x_{i}, and the set I_{∼} of those i such that x_{i} is ≼_{0}-incomparable with x_{i_{0}}. Then given any linearization ≤ of ≼ on |P | − |C_{i_{0}}|, the elements of |C_{i_{0}}| can be inserted within the range bounded below by the highest location, under that linearization, of an element of ⋃_{i∈I_{<}} |C_{i}|, and above by the lowest location of an element of ⋃_{i∈I_{>}} |C_{i}|; where we understand the former restriction to be vacuous if ⋃_{i∈I_{<}} |C_{i}| is empty, and the latter if ⋃_{i∈I_{>}} |C_{i}| is empty.

In our linearization of |P | − |C_{i_{0}}|, the interval we have described will be populated by some subset (possibly empty) of ⋃_{i∈I_{∼}} |C_{i}|. If d is the number of elements of that set in that interval, then clearly

(14) 0 ≤ d ≤ ∑_{i∈I_{∼}} m_{i},

and we see that the number of ways the m_{i_{0}} elements of the chain C_{i_{0}} can be interspersed among those d elements is \binom{m_{i_{0}} +d}{d}, which, as a function of m_{i_{0}}, is a polynomial of degree d. The maximum value allowed by (14), d = ∑_{i∈I_{∼}} m_{i}, does in fact occur, since we can linearize |P | − |C_{i_{0}}| so that all members of ⋃_{i∈I_{<}} |C_{i}| precede all members of ⋃_{i∈I_{∼}} |C_{i}|, and these precede all members of ⋃_{i∈I_{>}} |C_{i}|. Summing the polynomials in m_{i_{0}} obtained from all our linearizations of |P | − |C_{i_{0}}|, we get a polynomial f(m_{i_{0}}) describing L_{+}(P_{0}; m_{1}, …, m_{d}). Since the leading coefficients of the polynomials we have summed are all positive, the terms of degree ∑_{i∈I_{∼}} m_{i} cannot cancel, so that is the degree of f(m_{i_{0}}), completing the proof of (a).

If, instead, we look at the sign-imbalance, then the polynomials \binom{m_{i_{0}} +d}{d} are replaced by the functions described in parts (i) and (ii) of Proposition 10 for m_{0} = 2 (the diagonals of the right-hand array of (13)), multiplied by ±1 depending on the details of our linearization of |P | − |C_{i_{0}}|. Each of these is given by one polynomial of degree ≤ d/2 (possibly the zero polynomial) on odd inputs and another polynomial of degree ≤ d/2 on even inputs, yielding (b). Because of the varying signs, we cannot say in this case that the leading terms of the highest-degree polynomials will not cancel, hence we cannot specify the exact degrees of the polynomials we get. □

Comparing with Proposition 10, we might wonder whether, of the two polynomials referred to in (b) above, the one that gives the sign-imbalance for m_{i_{0}} odd must have degree less than or equal to that of the one that does so for m_{i_{0}} even. But this is not the case. For instance, suppose P_{0} is the poset [figure: x_{1}; x_{2}; x_{3}] , let i_{0} = 2, and take m_{1} and m_{3} odd. Then for any value of m_{2}, the union of the posets C_{2} and C_{3} will be a chain of length m_{2} + m_{3}, which has the opposite of the parity of m_{2}, whence we see from Proposition 10 that for m_{2} even, L_{−}(P_{0}; m_{1}, m_{2}, m_{3}) will be zero, while for m_{2} odd, it will be a polynomial of degree ⌊m_{1}/2⌋.

5.3. Chains in P_{0} again. At the beginning of the preceding subsection, we noted that for P_{0} a 2-element antichain, the function L_{+}(P_{0}; m_{1}, m_{2}) was not a polynomial in its two variables. More generally, if x_{i_{1}} and x_{i_{2}} are incomparable elements of a finite poset P_{0}, and we fix values for all m_{i} other than m_{i_{1}} and m_{i_{2}}, we find that as a function of those two variables, L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) cannot be a polynomial. Indeed, one can strengthen the ordering of P_{0} to get an “almost-chain” P′_{0}, in which the only pair of incomparable elements is \{x_{i_{1}}, x_{i_{2}}\}. Then L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) ≥ L_{+}(P′_{0}; m_{1}, …, m_{m_{0}}) = \binom{m_{i_{1}} +m_{i_{2}}}{m_{i_{1}}}. But again, for

m_{i_{1}} = m_{i_{2}} = m we have \binom{m_{i_{1}} +m_{i_{2}}}{m_{i_{1}}} = \binom{2m}{m} ≥ 2^{m}, which grows too rapidly for a polynomial function. It follows that L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) is not a polynomial function in any subset of its arguments two of which correspond to incomparable elements of P_{0}.

Can L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) ever be a polynomial function of more than one of its arguments? Yes – in precisely the cases not excluded by the above observations:

Theorem 13. Let P_{0} = (|P_{0}|, ≼_{0}) be a finite poset, with |P_{0}| = {x_{1}, …, x_{m_{0}}}, and S any subset of |P_{0}|. Suppose that in L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) we fix nonnegative values for all the m_{i} such that x_{i} ∉ S. Then (regardless of the values so chosen) the resulting function of the remaining variables (the m_{i} with x_{i} ∈ S) is given by a polynomial if and only if S is a chain in P_{0}.

Sketch of proof. We have just seen “only if”; I shall sketch the proof of “if”.

Alongside the fixed values for the m_{i} with x_{i} ∉ S, let us choose arbitrary values for the m_{i} with x_{i} ∈ S. Now let Q denote the lexicographic sum over (|P_{0}| − S, ≼_{0}) of the chains C_{i} (x_{i} ∈ |P_{0}| − S), and C the lexicographic sum over (S, ≼_{0}) of the chains C_{i} (x_{i} ∈ S). Thus, C is a chain of ∑_{x_{i}∈S} m_{i} elements. To specify a linearization of P_{0} ∗ (C_{1}, …, C_{m_{0}}), we can first specify a linearization Q′ of Q, then specify how the elements of the chain C are to be inserted among those of Q′. To complete the proof of the theorem, it will suffice to show that for each of the finitely many linearizations Q′ of Q, the number of ways of positioning the members of C among the members of Q′ is a polynomial in the variables m_{i} (x_{i} ∈ S).

Given Q′, we shall first show that there is a polynomial which gives that number whenever positive integer values are assigned to the m_{i} (i ∈ S), then show that a polynomial with this property must continue to give that linearization-count when its arguments are allowed to be zero.

The complication in counting ways that members of C can be positioned is that the regions of Q′ where the elements of the various subchains C_{i} of C can be inserted are possibly overlapping intervals, so that information on where members of one of those subchains are distributed within its allowed interval may or may not restrict where other subchains C_{i′} can be distributed within theirs.

But suppose now that the m_{i} with x_{i} ∈ S are all nonzero, so that the C_{i} are all nonempty. In this case, let us further classify linearizations of Q′ ∪ C according to the positions, relative to the elements of Q′, of the greatest elements of each of the chains C_{i} (x_{i} ∈ S); i.e., according to which successive pair of the finitely many elements of Q′ each of these greatest elements lies between, or whether it lies above or below all of Q′. Once such a set of positions has been specified, we know the linear ordering of the union of Q′ with the set of maximal elements of those chains (since S is linearly ordered, hence so is the set of maximal elements of the C_{i} with m_{i} ∈ S). Let us call that union, so ordered, Q′′. Then the intervals of Q′′ in which the remaining elements of each C_{i} can be inserted are disjoint. If, for a given C_{i}, that interval of Q′′ contains d_{i} elements (where d_{i} may be 0 if, for instance, the top members of C_{i} and of the next lower C_{i′} have been placed between the same pair of elements of Q′), then there are \binom{m_{i}−1+d_{i}}{d_{i}} ways to populate it with the m_{i} − 1 nonmaximal members of C_{i}. This is a polynomial in m_{i} (of degree d_{i}), hence the total number of linearizations of P_{0} ∗ (C_{1}, …, C_{m_{0}}) extending our linearization of Q′′ is

(15) ∏_{x_{i}∈S} \binom{m_{i}−1+d_{i}}{d_{i}},

which is a polynomial in the variables m_{i} (x_{i} ∈ S). Summing over the finitely many linearizations Q′ of Q, and the finitely many ways of positioning within each Q′ the highest members of the chains C_{i}, we get a polynomial f which yields the value of L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) – provided that, as assumed above, none of m_{i} with x_{i} ∈ S is zero.

The key to proving that the same polynomial works if one or more of those m_{i} is zero is Proposition 12(a), which says that if we fix all but one of the m_{i}, then L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) is a polynomial in that variable. Hence, if we choose for all of our m_{i} other than some particular m_{i_{0}} nonzero values, then the resulting polynomial function in the variable m_{i_{0}} must agree with the polynomial obtained in the preceding paragraph at all values of m_{i_{0}} except possibly 0. But two 1-variable real polynomials which agree at infinitely inputs are equal, so in fact they will also agree when m_{i_{0}} = 0. This shows that the result of the preceding paragraph extends to the case where at most one of the m_{i} is zero. An obvious induction on the number of zero arguments gives the general case. □

The easy part of the above result, saying that if S is not a chain, then L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) does not yield polynomial functions of the corresponding set of variables, does not have an obvious analog for the sign-imbalance function L_{−}(P_{0}; m_{1}, …, m_{m_{0}}), since it is based on finding a summand that is too big to be a polynomial; but in the computation of L_{−}, “big” summands of opposite sign can cancel. And indeed, we have seen classes of cases where the resulting function is 0, which is certainly a polynomial.

However, the hard part of the above theorem, concerning the case where S is a chain, does go over to L_{−}, mutatis mutandis:

Corollary 14 (to proof of Theorem 13). Let P_{0} = (|P_{0}|, ≼_{0}) be as in Theorem 13, and let S ⊆ |P_{0}| be a chain. Then if we fix nonnegative values for all the m_{i} with x_{i} ∉ S, the values of L_{−}(P_{0}; m_{1}, …, m_{m_{0}}) are given by 2^{card(S)} polynomials in the m_{i} such that x_{i} ∈ S, one for each choice of the parities of these card(S) variables.

Idea of proof. Mimic the argument in the proof of Theorem 13 using, in place of the polynomials giving binomial coefficients as functions of one of their variables, the pairs of polynomials similarly describing the sign-imbalance of a union of two chains, illustrated by the right-hand side of (13) and formalized in Proposition 12(b). □

5.4. The total degrees of our multivariable polynomials. Proposition 12(a) described the degree of the one-variable polynomial it referred to. We can similarly determine the total degree of the card(S)-variable polynomial of Theorem 13. In doing so, we will use the following curious lemma, which says that one can strengthen the ordering of a poset so as to get rid of one class of incomparability conditions, while preserving “enough of” another related class of such conditions.

Lemma 15. Let P = (|P |, ≼) be a finite poset, and S a chain in P. Then the ordering ≼ of P can be strengthened to an ordering ≼′ under which the complement of S in P also becomes a chain, while every element of P that is incomparable with at least one element of S under ≼ remains incomparable with at least one element of S under ≼′.

Proof. Given any pair of incomparable elements x, y ∈ |P | − S, consider the strengthenings ≼_{x,y} and ≼_{y,x} of ≼ obtained by imposing the relation x ≼_{x,y} y, respectively y ≼_{y,x} x. We shall show that

(16)

At least one of ≼_{x,y}, ≼_{y,x} has the property that every element of P that is incomparable under ≼ with at least one element of S remains incomparable under that strengthened ordering with at least one element of S.

Repeatedly strengthening our partial order in this way, we eventually get an ordering under which |P | − S has no incomparable elements, i.e., is a chain, as desired.

It is easy to check (and probably well-known – reference, anyone?) that the relation ≼_{x,y} can be characterized by the condition that for all w, z ∈ |P |,

(17) w ≼_{x,y} z if and only if either w ≼ z, or w ≼ x and y ≼ z.

Thus, if an element u ∈ |P | satisfies a relation under ≼_{x,y} that it does not satisfy under ≼, we must have either u ≼ x or y ≼ u. (Note, incidentally, that these two cases are mutually exclusive, since x and y were assumed ≼-incomparable.)

Suppose now that we have an element u ∈ |P | such that

(18) u is ≼-incomparable with at least one element of S, but is ≼_{x,y}-comparable with all elements of S.

Of the two alternatives noted at the end of the sentence following (17), let us begin by assuming

(19) u ≼ x.

Let us write ↓u for {z ∈ |P | | z ≼ u} and ↓_{x,y} u for {z ∈ |P | | z ≼_{x,y} u}, and make the obvious corresponding definitions of ↑u and ↑_{x,y} u. The statement that u is ≼_{x,y}-comparable with all elements of S thus says that

(20) (↓_{x,y} u ∩ S) ∪ (↑_{x,y} u ∩ S) = S.

Now from (17) and (19), it follows that

(21) ↓_{x,y} u = ↓u and ↑_{x,y} u = ↑u ∪ ↑y.

(The first relation is gotten by putting u in the role of z in (17), and letting w range over P; the second by putting u in the role of w and letting z range over P.) Since S is a chain, (↑u ∪ ↑y) ∩ S must be either ↑u ∩ S or ↑y ∩ S. If it were ↑u ∩ S, then in view of (21), (20) would say that u was ≼-comparable with all elements of S, contrary to the first condition of (18). Hence it is ↑y ∩ S, and (20) instead says

(22) (↓u ∩ S) ∪ (↑y ∩ S) = S.

In view of (19), ↓u ⊆ ↓x, so (22) implies

(23) (↓x ∩ S) ∪ (↑y ∩ S) = S.

If, rather than (19) we are in the other case, y ≼ u, we get the variant of (23) with ↑ and ↓ reversed and the roles of x and y interchanged – which is again (23). So (23) holds in either case.

Now suppose that in addition to an element u satisfying (18), there is also an element v ∈ |P | such that

(24) v is ≼-incomparable with at least one element of S, but is ≼_{y,x}-comparable with all elements of S.

Then we get the variant of (23) with only the roles of x and y interchanged:

(25) (↓y ∩ S) ∪ (↑x ∩ S) = S.

From (23) and (25), it is not hard to deduce that ↓x ∩ S = ↓y ∩ S and ↑x ∩ S = ↑y ∩ S, and that these are complementary subsets of S; i.e., that both x and y are ≼-comparable with all elements of S, and that the order relation of each element of S with x is the same as its order relation with y. (Quick Venn diagram proof: Draw a square, to represent properties of an element s ∈ S. Divide it by vertical lines into three regions according to the ≼-relation of s to x : “smaller”, “incomparable”, or “greater”; and similarly by horizontal lines according to its ≼-relation to y. Interpret each of (23) and (25) as saying that every s ∈ S lies in a certain region of this diagram. Shade those regions, and note their intersection.)

It follows from this and (17) that passing from ≼ to ≼_{x,y} does not affect the order-relation or lack of it between any element of P and any element of S (and similarly for ≼_{y,x}). This contradicts our assumption (18) (and also (24)). Thus, our assumption that there existed both u satisfying (18) and v satisfying (24) has led to a contradiction, proving (16), and completing the proof of the lemma. □

Some further observations related to the above lemma are noted in an appendix, section 7.

We can now get the result we are aiming for. Recall that the total degree of a polynomial f in several variables means the maximum, over the monomials occurring in f, of the sum of the exponents of the variables.

Corollary 16 (to proof of Theorem 13). Let P_{0} be a finite poset and S a chain in P_{0}, and, as in Theorem 13, consider the function L_{+}(P_{0}; m_{1}, …, m_{m_{0}}) with fixed values chosen for all the m_{i} with x_{i} ∉ S, as a function of the values of m_{i} with x_{i} ∈ S. Let f be the polynomial in the latter card(S) variables which, by that theorem, gives this function.

Then the total degree of f is equal to the sum of m_{i} over those x_{i} that are incomparable in P_{0} with at least one element of S.

Sketch of proof. The degree we are looking for will be the maximum of the total degrees, in the variables corresponding to the elements of S, of the leading terms of the polynomials (15) that are summed to get f. (A general multivariable polynomial does not have a well-defined “leading term”, but the meaning of that phrase for the polynomials (15) is clear. When we sum the terms (15), the leading terms of some of these polynomials may be cancelled by negative-coefficient non-leading terms of higher-degree polynomials; but this cannot happen to any of the leading terms that have maximum total degree.) Now for each such polynomial, its total degree in the variables we are interested in is the sum over x_{i} ∈ S of the number called d_{i} in the proof of Theorem 13; i.e., the number of elements of Q lying in the range into which the non-maximal members of the subchain C_{i} can be placed. Every element in one of those ranges must belong to a C_{i} (x_{i} ∈ |P | − S) such that x_{i} is incomparable with at least one member of S; so the sum of the cardinalities of those chains C_{i}, i.e., the sum of the corresponding m_{i}, is indeed an upper bound for the desired degree.

To get a linearization Q′ of the Q of that proof with the help of which we can realize that upper bound, we apply Lemma 15, taking for the P of that lemma the lexicographic sum over P_{0} having a chain of length m_{i} in the i-th position for all i with x_{i} ∉ S, while for x_{i} ∈ S, it has a singleton, which we continue to denote x_{i}. Taking the set of these singletons for the S of that lemma, we get an ordering ≼′ of P that makes |P | − S = |Q| a chain, and we take this linearization of Q to be our Q′.

To single out a polynomial (15), we now need to choose for each i with x_{i} ∈ S the position where, in the construction of Theorem 13, we will locate the largest element of the chain C_{i} relative to the elements of Q′. Let us place each of these as high as we can consistent with the order ≼′ . I.e., for the top x_{i} ∈ S, we place x_{i,m_{i}} just below the least element of Q′ that, under the ordering constructed, is above x_{i}, if there is one; if not, we place it above all elements of Q′; and we then place the top elements of successively lower chains C_{i} for x_{i} ∈ S as high as they can go relative to Q′ and the elements we have put down so far. One finds that every element of Q′ incomparable under ≼′ with at least one member of S is in the range which, in the construction of Theorem 13, can be populated by elements of C_{i} for some x_{i} ∈ S; so the asserted total degree is achieved. □

6. Associativity of the lexicographic sum, and its consequences

Suppose, as in our general description of lexicographic sums, that P_{0} = (|P_{0}|, ≼_{0}) is a poset with |P_{0}| = {x_{1}, …, x_{m_{0}}}, and that for each i ∈ {1, …, m_{0}} we are given a poset P_{i} = (|P_{i}|, ≼_{i}) with |P_{i}| = {x_{i,1}, …, x_{i,m_{i}}}, where x_{i,j} and x_{i′,j′} are distinct unless (i, j) = (i′, j′).

Now suppose further that for each pair (i, j) with 1 ≤ i ≤ m_{0} and 1 ≤ j ≤ m_{i}, we are given a poset P_{i,j} = (|P_{i,j}|, ≼_{i,j}) with |P_{i,j}| = {x_{i,j,1}, …, x_{i,j,m_{i,j}}}, such that x_{i,j,k} and x_{i′,j′,k′} are distinct unless (i, j, k) = (i′, j′, k′). Then we can define a partial ordering on

(26) |P | = {x_{i,j,k} | 1 ≤ i ≤ m_{0}, 1 ≤ j ≤ m_{i}, 1 ≤ k ≤ m_{i,j}}

by letting

(27)

x_{i,j,k} ≼ x_{i′,j′,k′} if and only if either
i ≠ i′ and x_{i} ≼_{0} x_{i′} in P_{0}, or
i = i′ but j ≠ j′, and x_{i,j} ≼_{i} x_{i,j′} in P_{i}, or
i = i′ and j = j′, and x_{i,j,k} ≼_{i,j} x_{i,j,k′} in P_{i,j}.

Clearly, the resulting poset P can be looked at both as the lexicographic sum over P_{0} of the posets P_{i} ∗ (P_{i,1}, …, P_{i,m_{i}}) and as the lexicographic sum over P_{0} ∗ (P_{1}, …, P_{m_{0}}) of the posets P_{i,j}. Denoting their common value P_{0} ∗ (P_{i})_{1≤i≤m_{0}} ∗ (P_{i,j})_{1≤i≤m_{0}, 1≤j≤m_{i}}, we thus have

(28) P_{0} ∗ ((P_{i}) ∗ (P_{i,j})_{1≤j≤m_{i}})_{1≤i≤m_{0}} ; = P_{0} ∗ (P_{i})_{1≤i≤m_{0}} ∗ (P_{i,j})_{1≤i≤m_{0}, 1≤j≤m_{i}} ; = (P_{0} ∗ (P_{i})_{1≤i≤m_{0}}) ∗ (P_{i,j})_{1≤i≤m_{0}, 1≤j≤m_{i}}.

The equality between the first and last lines of (28) constitutes an associative law for lexicographic sums. (Of course, if one is given families of posets essentially as above, but without the disjointness assumptions on their underlying sets, one can construct lexicographic sums using ordered tuples, as at the beginning of section 4.1, and one gets natural isomorphisms, rather than equalities, in (28).)

Now let us suppose each of the posets P_{i,j} is a chain C_{i,j} of m_{i,j} elements, but make no such assumption on P_{0} or the P_{i}. Then if we apply the function L_{±} to the expressions in (28), the final expression is the function L_{±}(P_{0} ∗ (P_{i})_{1≤i≤m_{0}}; m_{1,1}, …, m_{m_{0},m_{m_{0}}} ), while the initial expression can be computed using Theorem 7 from the functions L_{±}(P_{0}; m_{1}, …, m_{m_{0}}) and L_{±}(P_{i}; m_{i,1}, …, m_{i,m_{i}}) (i = 1, …, m_{0}).

Thus, if we know the functions L_{±}(P; m_{1}, …) for some family of finite posets P, we can compute using Theorem 7 the corresponding function for any poset constructed as a lexicographic sum of members of that family over a member of that family; and, more generally, for any poset obtained in that way by iterated lexicographic sums.

In particular, since Propositions 9 and 10 give formulas for L_{±}(P; m_{1}, …) when P is a finite chain or antichain, we can use the above technique to get such formulas for all posets constructed from chains and antichains by iterated lexicographic sums.

For example, consider the poset P = [figure]. If we name the bottom two elements x_{1,1} and x_{1,2}, and the top two x_{2,1} and x_{2,2}, then our poset is the lexicographic sum of two antichains with underlying sets {x_{1,1}, x_{1,2}} and {x_{2,1}, x_{2,2}}, over a chain whose element-set we may label {x_{1}, x_{2}}. With the help of Propositions 9 and 10, we find that L_{+}(P; m_{1,1}, m_{1,2}, m_{2,1}, m_{2,2}) = \binom{m_{1,1}+m_{1,2}}{m_{1,1}}\binom{m_{2,1}+m_{2,2}}{m_{2,1}}, while L_{−}(P; m_{1,1}, m_{1,2}, m_{2,1}, m_{2,2}) is zero if either both m_{1,1} and m_{1,2} are odd, or both m_{2,1} and m_{2,2} are odd, while it is \binom{⌊(m_{1,1}+m_{1,2})/2⌋}{⌊m_{1,1}/2⌋}\binom{⌊(m_{2,1}+m_{2,2})/2⌋}{⌊m_{2,1}/2⌋} otherwise. Using iterated lexicographic sums, one can build up from chains and antichains arbitrarily complicated posets for which these functions can similarly be computed. These are called “series-parallel” posets in [2, Chapter 9, Exercise 6].

But “most” finite posets are not series-parallel; the simplest example is P = [figure] . In fact, it is shown in [2, Chapter 9, Exercises 6–7] that a finite poset is series-parallel if and only if it does not contain a copy of that 4-element poset. For further results on the characterization of classes of posets arising as iterated lexicographic sums in terms of “forbidden subposets”, see [3].

As mentioned at the end of section 4, I have not studied the function L_{±}(P; m_{1}, m_{2}, m_{3}, m_{4}) determined by the above 4-element poset [figure] . It would be interesting to describe it.

7. Appendix: notes on Lemma 15

I don’t know whether Lemma 15 has uses other than as a tool for proving Corollary 16; but it has piqued my curiosity, and I give below several related observations.

First, some quick examples. For a case of (16) in which one, but not the other of ≼_{x,y} and ≼_{y,x} has the property asserted there, let P be the 4-element poset [figure] , let S be the 2-element chain in the middle of that picture, and let x and y be (necessarily) the two elements of |P | − S. The reader can easily check the details.

For a case of the lemma in which the set of elements of S incomparable with one or more elements of P must always decrease when |P |−S is made a chain (in contrast to the assertion of the lemma, about elements of P incomparable with one or more elements of S), let P be the disconnected union of a 3-element chain and a singleton, and take for S the subchain consisting of the top and bottom elements of the 3-element component.

Finally, for an example showing that the statement of the lemma fails if we drop the assumption that S is a chain, let P be the disconnected union of two 2-element chains, and let S consist of the two minimal elements of P. Then under any strengthening of the ordering of P that makes |P | − S a chain, the larger element of |P | − S will lie above, and in particular, be comparable with, both elements of S, though it was incomparable with one of them under the original ordering.

It is not obvious from the proof we gave of Lemma 15 how to tell, given elements x and y, which of the orderings ≼_{x,y} and ≼_{y,x} has the property asserted in (16), or whether both do. The equivalence (a) ⟺ (c) of the next corollary, and its variant with the roles of x and y reversed, give the criteria for one or the other of those possibilities to be excluded.

Corollary 17 (to proof of Lemma 15). Let P = (|P |, ≼) be a finite poset and S a chain in P, let x and y be two ≼-incomparable elements of |P | − S, and let ≼_{x,y} be the strengthened partial ordering on P gotten by imposing the relation x ≼_{x,y} y, described in (17). Then the following three conditions are equivalent.

(a) There is some u ∈ |P | that is incomparable under ≼ with at least one element of S, but is comparable under ≼_{x,y} with every element of S.

(b) One of x or y has the above property of being incomparable under ≼ with at least one element of S, but comparable under ≼_{x,y} with every element of S.

(c) (↓x ∩ S) ∪ (↑y ∩ S) = S, but (↓y ∩ S) ∪ (↑x ∩ S) ≠ S. (Cf. (23), (25)).

Proof. We shall prove (a) ⟹ (c) ⟹ (b) ⟹ (a).

Given (a), the proof of Lemma 15 gives us the equality (23) with which (c) begins. On the other hand, if alongside (23) we have equality in place of the inequality in the second condition of (c) (i.e., if (25) also holds), then the two paragraphs of that proof following (25) show that ≼_{x,y} does not introduce any relations between elements of |P | − S and elements of S that don’t hold under ≼, contradicting (a). So we must also have that inequality; so (c) indeed holds.

Next, assume (c). Note that in the equality (↓x ∩ S) ∪ (↑y ∩ S) = S, the sets ↓x ∩ S and ↑y ∩ S must be disjoint, since if their intersection contained an element z, we would have y ≼ z ≼ x, contradicting our assumption that x and y are ≼-incomparable.

Let us use the inequality (↓y ∩ S) ∪ (↑x ∩ S) ≠ S to choose a w ∈ S in neither ↓y nor ↑x. By the preceding observation, w lies either in ↓x or in ↑y, but not in both. If it is in ↓x but not ↑y, then it is in neither ↑y nor ↓y, showing that y is incomparable with at least one element of S. Now every s ∈ S incomparable with y must, by the relation (↓x ∩ S) ∪ (↑y ∩ S) = S, lie in ↓x, hence s ≼_{x,y} x ≼_{x,y} y. So y, though ≼-incomparable with some elements s ∈ S, is ≼_{x,y}-comparable with all such elements, which is the “y” case of (b). If, on the other hand, our element w lies in ↑y rather than ↓x, the corresponding considerations give the “x” case of (b). Thus, we have proved (c) ⟹ (b).

The implication (b) ⟹ (a) is immediate. □

The proof of Lemma 15 shows how to build up all linearizations of |P | − S which extend to orderings of |P | of the sort asserted in the lemma, by making successive choices of order on unordered pairs of elements of |P | − S, taken in any order. The above corollary tells us at each such step which choices are available (those not satisfying (c)). We end this section with a more systematic construction of some ordering as in that lemma, based on a suggestion of Stefan Felsner (personal correspondence).

Sketch of an alternative proof of Lemma 15, after S. Felsner. Listing the elements of S as s_{1} ≼ … ≼ s_{r}, let us partition |P | − S into disjoint subsets

(29) |P | − S = T_{1} ∪ T_{2} ∪ … ∪ T_{2r+1}

as follows. If x ∈ |P |−S is already ≼-comparable with all elements of S, say with s_{i} ≼ x ≼ s_{i+1}, we assign x to T_{2i+1}, with the obvious modifications in the end-cases, namely, when x ≼ s_{1} we assign it to T_{1}, and when s_{r} ≼ x we assign x to T_{2r+1}. On the other hand, if x is incomparable with at least one element of S, let s_{i} be the largest such element, and assign x to T_{2i}.

It is not hard to check that for 1 ≤ i < j ≤ 2r + 1, no element of T_{j} is ≼ any element of T_{i}. Hence we can strengthen the ordering ≼ on |P | − S to make all elements of T_{i} precede all elements of T_{j} whenever i < j, keeping the relative order of elements within each T_{i}. We can then go further and linearize each T_{i}, getting a total order ≼′ on |P | − S.

On S, on the other hand, we let ≼′ agree with ≼, since ≼ is already a total order there.

It remains to specify how ≼′ should relate elements of |P | − S and elements of S. If x ∈ |P | − S belongs to a set T_{2i+1}, there is no choice: under ≼, x lies above all s_{j} with j ≤ i and below all s_{j} with j ≥ i + 1, so we give it these same relations under ≼′ .

If x ∈ T_{2i}, we must again let x lie below all s_{j} with j ≥ i + 1. In this case, there may or may not be choices as to how it should relate to lower members of S; but we make a choice that will always work: let x be incomparable with s_{i}, and lie above all s_{j} with j < i.

It is routine, though tedious, to verify that the relation ≼′ so defined is a partial ordering on |P |. By construction, it is a strengthening of the given ordering ≼, and has the property that every element of |P |−S that was ≼-incomparable with at least one element of S (i.e., which belongs to some |T_{2i}|), remains ≼′-incomparable with some element of S (namely, s_{i}). This completes the proof of the lemma. □

8. Appendix: a formula of G. Hochschild

The results of section 1 were motivated by a question Arthur Ogus asked me, on how one might understand, computationally, a formula of Gerhard Hochschild. In this appendix, which assumes only that section, we recover that formula.

Our development is far lengthier than Hochschild’s, so its interest (if any) lies in its different approach to the result, and in the possibility that the method may be applicable to questions not as easy to answer by other means.

Hochschild’s result (in which I have changed almost all the notation – but the translation between his and mine is straightforward) concerns an associative ring R of prime characteristic p, a commutative subring A of R, and an element r ∈ R such that the commutator map a ↦ ad_{r}(a) = ra − ar carries A into itself. What he shows is that for all a ∈ A,

(30) (ar)^{p} = a^{p}r^{p} + ad_{ar}^{p−1}(a) r.

Since every term of (30) ends with a factor r, Ogus suggested that the corresponding identity with those factors removed should hold, namely

(31) (ar)^{p−1}a = a^{p}r^{p−1} + ad_{ar}^{p−1}(a).

We shall see that this is true. Precisely, dropping the assumption that R has characteristic p, we shall prove

Lemma 18 (after Hochschild [1, Lemma 1]). Let R be an associative ring, r an element of R, A a commutative subring of R such that the operation ad_{r} : a ↦ ra − ar carries A into itself, and p a prime number. Then the function taking every a ∈ A to the element

(32) (ar)^{p−1}a − a^{p}r^{p−1} − ad_{ar}^{p−1}(a)

of R can be written as a noncommutative polynomial in r and the elements a, ad_{r}(a), ad_{r}^{2}(a), …, in which the coefficients of all monomials are divisible by p.

Proof. Let us consider the term (ar)^{p−1}a of (32), and repeatedly use the formula

(33) rx = xr + ad_{r}(x) for x ∈ A

to eliminate occurrences of r preceding elements of A. We begin with the rightmost occurrence of r, which precedes the final a; an application of (33) to that pair of factors turns (ar)^{p−1}a into a sum of two monomials, in one of which that r has jumped to the end, while in the other, it has been absorbed in the process of turning the final a to ad_{r}(a). We then apply (33) to the r that was originally second from the right. This can either be absorbed in the a immediately to its right, turning that into ad_{r}(a), or jump past it. In the latter case it can, in turn, either be absorbed in the next factor (which is a or ad_{r}(a) depending on which output of the first step we are looking at, and so is turned into ad_{r}(a) or ad_{r}^{2}(a) respectively), or jump past that factor, becoming an (additional) r at the far right. We proceed similarly with the third r from the right, and so on. Since there are two possibilities for the fate of the rightmost r, three for the next, etc., we get p! terms.

The choices leading to one of these p! terms can be represented visually by taking the given string

(34) a r a r … r a  (with p a’s and p − 1 r’s)

and drawing, from each member of some subset of the occurrences of r, an arrow to some occurrence of a to its right. In the resulting expression, each a that receives m arrows becomes ad_{r}^{m}(a) (with those receiving none remaining as a), and the r’s at the other ends of those arrows are deleted, while those r’s from which arrows were not drawn move to the far right.

Note that the output of this process has exactly one term in which none of the p − 1 r’s acts on any of the a’s, and that this term, a^{p}r^{p−1}, is cancelled by the −a^{p}r^{p−1} of (32).

At the opposite extreme are the (p − 1)! terms in which every occurrence of r acts on an element of A (either an a, or the image of a under previous actions of other occurrences of r). I claim that the sum of these is precisely ad_{ar}^{p−1}(a), and thus cancels the − ad_{ar}^{p−1}(a) of (32). To see this, note first that for any x ∈ A, we have ad_{ar}(x) = arx − xar = arx − axr = a ad_{r}(x), where the middle equality holds because A is commutative. Hence ad_{ar}^{p−1}(a) can be written as

(35) (a ad_{r}( … (a ad_{r}(a ad_{r}(a)))...)) .

Here the rightmost (better: innermost) occurrence of ad_{r} acts on its argument a. The next occurrence acts on the product a ad_{r}(a), so – since ad_{r} is a derivation, i.e., satisfies

(36) ad_{r}(xy) = ad_{r}(x) y + x ad_{r}(y) for x, y ∈ A,

– it turns a ad_{r}(a), into a sum of two terms, in one of which it acts on the first factor and in the other on the second. The action of the next ad_{r}, on the product of a with each of these two-factor terms, gives a sum of three terms; and so on. The resulting terms can be classified by writing out the string

(37) a ad_{r} … a ad_{r} a ad_{r} a (with p a’s and p − 1 ad_{r}’s)

and drawing an arrow from each ad_{r} to an arbitrary a to the right of it, on which it acts. The results are clearly the same as the subset of the expressions in our expansion of (ar)^{p−1}a in which an arrow comes out of every occurrence of r, so, as claimed, these terms cancel the − ad_{ar}^{p−1}(a) in (32).

What remains is to show that in the expansion of (ar)^{p−1}a, each monomial

(38) ad_{r}^{m_{1}}(a) ad_{r}^{m_{2}}(a) ad_{r}^{m_{p}}(a) r^{p−1−m_{1}−...−m_{p}}

that is not of either of the above two extreme sorts, i.e., which satisfies

(39) 0 < m_{1} + ⋯ + m_{p} < p − 1,

occurs with coefficient divisible by p. Since A is commutative, we are regarding monomials (38) as the same if they differ by a permutation of the string of exponents m_{1}, …, m_{p}. Thus, we may make the notational assumption that the nonzero exponents in (38) form an initial substring, say m_{1}, …, m_{ℓ}.

To determine the coefficient of a monomial (38), we need to count the ways of attaching arrows to (34) that lead to it. I claim such a system of arrows will be determined by an appropriately indexed family of elements of {1, …, p} (corresponding to the positions of the r’s from which arrows begin, and the a’s at which they end) subject to certain inequalities – and that the set of these indexed families can be identified with a set of maps of the sort whose cardinality was studied in section 1.

Indeed, consider any monomial (38), and let P be a partially ordered set consisting of ℓ connected components, namely, for each i ≤ ℓ, let the component P_{i} be a chain of m_{i} + 1 elements.

Let us, to begin with, assume for simplicity that the nonzero exponents in (38), m_{1}, …, m_{ℓ}, are distinct. Then for P so defined, let us, to each diagram of arrows on the string of symbols (34) that yields the monomial (38), associate the map φ : P → {1, …, p} such that for i = 1, …, ℓ, if the factor ad_{r}^{m_{i}}(a) in (38) arises from arrows drawn from the k_{1}-st, k_{2}-nd, through k_{m_{i}}-th occurrences of r to the k_{m_{i}+1}-st occurrence of a, then φ maps the successive terms of the chain P_{i} to the integers k_{1} < k_{2} < ⋯ < k_{m_{i}} < k_{m_{i}+1}. (Note the difference between the way k_{1}, …, k_{m_{i}} are specified in the above sentence, and way k_{m_{i}+1} is specified.)

Which maps P → {1, …, p} can arise in this way from arrow-diagrams giving the monomial (38)? It is not hard to see that they will be precisely those isotone maps such that no two elements of P fall together, except that the maximal element of a component P_{i} is permitted to fall together with a nonmaximal element of a component P_{j} if j ≠ i. (The images of non-maximal elements of P all have to be distinct because they represent the sources of distinct arrows, and the images of maximal elements must be distinct because they represent the recipients of distinct families of arrows. Finally, the images of a non-maximal element and the maximal element in the same component must be distinct because the i-th occurrence of r can’t have an arrow to the i-th occurrence of a, since the latter precedes it. On the other hand, there is no contradiction if for some i, the i-th a is the recipient of some family of arrows, and the i-th r is the source of an arrow with a different destination. These are the cases where elements of P are allowed to fall together.) So letting S = (|P |, ≼, E), where (|P |, ≼) is the poset P described above, and E consists of all two-element subsets of |P | other than those whose members are the maximal element of one component of P and a nonmaximal element of another component, we see that the coefficient of (38) in (ar)^{p−1}a is C(S, p), as defined in Theorem 1.

The partially ordered set P has (m_{1} + 1) + ⋯ + (m_{ℓ} + 1) = m_{1} + ⋯ + m_{ℓ} + ℓ elements, and ℓ connected components, so the term written card(|S|) − c + 1 in Corollary 2 is here m_{1} + ⋯ + m_{ℓ} + 1. By (39), m_{1} + ⋯ + m_{ℓ} < p − 1, hence m_{1} + ⋯ + m_{ℓ} + 1 < p, so p satisfies the condition in the first sentence of Corollary 2. By the first inequality of (39), P is nonempty, so we can apply the final statement of that corollary to conclude that C(S, p) is divisible by p, as desired.

What if the m_{i} are not all distinct? If a given value m occurs as h_{m} different m_{i}’s (i.e., if after collecting like factors in (38), ad_{r}^{m}(a) appears with exponent h_{m}), then the poset P constructed as above will have h_{m} m+1-element components. In this situation, for each way the h_{m} factors ad_{r}^{m}(a) can arise from an arrow-diagram, we can choose, arbitrarily, which of those h_{m} components of P is mapped to which family of m arrows. This gives h_{m}! possibilities. We see from this that the coefficient of our monomial (38) in the expansion of (ar)^{p−1}a will now be C(S, p)/ ∏_{m} h_{m}! . But this creates no problem, since each of the h_{m} is less than p. (Indeed, by (39), p − 1 > ∑ m_{i} ≥ h_{m}m ≥ h_{m} for each m.) So since C(S, p) is divisible by p, C(S, p)/ ∏_{m} h_{m}! is also, as required. □

9. Acknowledgements

I am indebted to Arthur Ogus for asking the question answered in the above appendix, which led me into these investigations; to Richard Stanley for patiently responding to my communications about this material and pointing me to relevant literature, and to Bernd Schröder and Stefan Felsner for valuable further correspondence.

References

[1] G. Hochschild, Simple algebras with purely inseparable splitting fields of exponent 1. Trans. Amer. Math. Soc. 79 (1955)

   477–489. http://www.jstor.org/stable/pdf/1993043.pdf . MR0070961

[2] Bernd S. W. Schröder, Ordered sets. An introduction with connections from combinatorics to topology, Second edition. Birkhäuser/Springer, 2016. xvi+420 pp. MR1944415. (First edition MR194441)

[3] Bernd S. W. Schröder, Characterizing iterated lexicographic sums via forbidden embedded subsets, preprint, 37 pp., 2018.

[4] Richard P. Stanley, A chromatic-like polynomial for ordered sets, pp. 421–427 in 1970 Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications, Univ. North Carolina, Chapel Hill, NC. MR0269545

[5] Richard P. Stanley, Some remarks on sign-balanced and maj-balanced posets, Adv. in Appl. Math., 34 (2005) 880–902.

   https://doi.org/10.1016/j.aam.2003.12.002 . MR2129003

[6] Richard P. Stanley, Enumerative combinatorics. Volume 1. Second edition. Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, 2012. xiv+626 pp. MR2868112

[7] W. T. Tutte, Graph theory. With a foreword by C. St. J. A. Nash-Williams, Encyclopedia of Mathematics and its Applications, 21. Addison-Wesley, 1984. Reprinted by Cambridge University Press, 2001. MR0746795, MR1813436

University of California, Berkeley, CA 94720-3840, USA

  E-mail address: gbergman@math.berkeley.edu