Binomial posets with non-isomorphic intervals

Jörgen Backelin

Abstract

The confluent binomial posets with the atomic function A(n) = max(1, 2^{n−2}) are classified. In particular, it is shown that in general there are non-isomorphic intervals of the same length.

1 Introduction

Recall that (following [5]) a binomial poset (P, ≤) is a graded locally finite poset, where the number of maximal chains in an interval only depends on the length of that interval. In this article, we always consider directed infinite downwards bounded binomial posets. In other word, any poset P will have a minimal element ˆ0; for any x, y ∈ P, there is a z ∈ P with x ≤ z and y ≤ z; for any (by definition non-empty) interval [x, y] ⊂ P; each interval is a finite set; all inclusion maximal chains in [x, y] have the same length ℓ([x, y]); and the number of such chains for a given interval [x, y] is only depending on P and ℓ([x, y]). In fact, we mostly consider (strongly) confluent such posets, where in addition there is an infinite chain x_{1} < x_{2} < x_{3} < … in P, such that P = ⋃_{i}[ˆ0, x_{i}]. (The reader may verify that a downward bounded directed locally finite poset is strongly confluent if and only if it is countable as a set.)

Call [x, y] an n-interval, if ℓ([x, y]) = n; and let B(P, n) (or B(n), if there is no ambiguity) denote the number of maximal chains in an n-interval of P. The numbers B(P, 0) = 1, B(P, 1) = 1, B(P, 2), B(P, 3), …, behave as a kind of generalised factorial functions, in the following senses: For any n-interval [x, y], the number of elements therein that cover x is an integer A(P, n) (or A(n)), only

depending on P and n; B(P, n) = ∏_{i=1}^{n} A(P, n); and for any integers j and n, such that 0 < j < n, the

number B(P, n)/(B(P, j) B(P, n − j)) counts the number of 2-chains x < z < y in [x, y], such that z has local rank j (i.e., such that ℓ([x, z]) = j), and thus in particular is a positive integer, a ‘generalised binomial coefficient’.

In the sequel, we ignore B(0) = 1 and A(0) = 0, but consider posets X with a given fixed sequence B(1), B(2), …, and thus a fixed atomic sequence A(1) = a_{1} = 1, A(2) = a_{2}, et cetera. The atomic sequence A := (a_{i})_{i=1}^{∞} must satisfy the first binomial poset compatibility condition

(1)  1 = a_{1} ≤ a_{2} ≤ a_{3} ≤ …,  and  \frac{∏_{l=j+1}^{j+i} a_{l}}{∏_{l=1}^{i} a_{l}} ∈ ℕ = \{0, 1, 2, …\}

for all i, j ∈ ℙ = {1, 2, 3, …}.

Note that by the Ehrenborg-Readdy theorem [3], there are but two isomorphism classes of Eulerian (strongly confluent infinite binomial) posets, with the atomic sequences (1, 2, 2, 2, 2 …) = (1, 2^{∞}) and (1, 2, 3, 4, 5, …) = (i)_{i}, respectively. In contrast, we may classify the strongly confluent infinite binomial posets with A = (1^{2}, 2^{∞}) = (1, 1, 2, 2, 2, …), by means of the infinite binary strings without consecutive 1’s. In particular, there is an uncountable number of isomorphism classes of them.

Formally, given a poset X as above, we shall define a string ϕ(X) = (ι_{j})_{j=1}^{∞} ∈ [2]^{ℙ}, such that ϕ(X) = ϕ(X′) ⟺ X ≃ X′, and that S := Im ϕ = {(ι_{j})_{j} ∈ [2]^{ℙ} : max_{j∈ℙ}(ι_{j} + ι_{j+1}) ≤ 3}.

2 The main results

For any (strongly confluent infinite downwards bounded) binomial poset X, let X_{i} := {x ∈ X :

rank(x) = ℓ([ˆ0, x]) = i}. For 0 ≤ i ≤ j, let the section X_{i,j} be ⋃_{l=i}^{j} X_{l}. Name X of bounded atomic

number type, if a := lim A := lim_{n→∞} a_{i} < ∞. Call A realised by X. We have the following lemma:

Lemma. For a strongly confluent infinite downwards bounded poset X with atomic sequence A, et cetera, as above, we have

(a) The following conditions are equivalent:

i. a < ∞;

ii. |X_{i}| < ∞ for some i ∈ ℙ;

iii. All |X_{i}| < ∞; iv. sup_{i} |X_{i}| < ∞.

(b) If indeed X is of bounded atomic number type (i.e., the conditions in (a) are fulfilled), then

|X_{i}| = \frac{a^{i}}{B(i)}; sup_{i} |X_{i}| = lim_{i→∞} |X_{i}| = ∏_{i=1}^{∞}(aa_{i}^{−1}) ;

X is countable; and every element in X is covered by exactly a elements.

Proof. By the confluency condition, there is a chain (x_{i})_{i}, such that for any finite sequence of different elements y_{1}, …, y_{r} ∈ X_{1}, there is an i_{r} ∈ ℙ, such that y_{1}, …, y_{r} cover ˆ0 in [ˆ0, x_{i_{r}}]; and without loss of generality, we may assume that x_{i_{r}} ∈ X_{j_{r}} for some j_{r} ≥ i_{r}. Hence, if there is an infinite sequence y_{1}, y_{2}, … ∈ X_{1}, then on the one hand a = lim_{i} a_{j_{i}} ≥ lim_{i} i = ∞, while on the other |X_{i}| ≥ |X_{1}| and thus is infinite, for each i ∈ ℙ.

Conversely, assume that X_{1} = {y_{1}, …, y_{r}}. Then a_{i} = |X_{1}| for i ≥ j_{r}, whence a = |X_{1}|, indeed. Moreover, similar arguments hold for the elements covering any fixed x ∈ X, instead of X_{1}; whence then indeed x is covered by a elements. In particular, there are exactly a^{i} saturated chains of length i, starting at ˆ0. On the other hand, such a chain is a maximal chain in [ˆ0, x] for some x ∈ X_{i}; whence there are |X_{i}| B(i) different such chains. In particular indeed |X_{i}| = a^{i}B(i)^{−1} < ∞. Now, the remaining claims follow easily.

Now, fix a_{1} = a_{2} = 1, a_{3} = … = a = 2. Then |X_{1}| = 2, and |X_{2}| = |X_{3}| = … = 4. For any i ∈ ℙ, (the Hasse graph of) the section X_{i+1,i+2} is a bipartite, 2-regular graph on 8 vertices, and thus is isomorphic to either C_{8} or to C_{4} ∪ C_{4} (distinguishable by the number of components). Put ι_{i} := 3 − comp(X)_{i+1,i+2}, and ϕ(X) := (ι_{i})_{i}.

Obviously, (X ≃ X′ ⟹ ϕ(X) = ϕ(X′)).

For the moment, fix i ∈ ℙ. Recall that there are three possible 2 + 2 partitions of a given 4-set. Now, any y ∈ X_{i+2} covers exactly two elements in x_{i+1}; and if y covers x_{1} and x_{2}, then there is a y′ ∈ X_{i+2} that covers X \ {x_{1}, x_{2}}, defining a 2 + 2 ‘cover’ partition {{x_{1}, x_{2}}, X \ {x_{1}, x_{2}}} of X_{i+1}. Thus, X_{i+1,i+2} induces 3 − comp(X)_{i+1,i+2} different cover partitions of X_{i+1}; and symmetrically equally many ‘cocover’ partitions of X_{i+2}. Likewise, X_{1,2} induces one co-cover partition of X_{2}. More precisely, up to isomorphisms X_{0,2} = {ˆ0, z_{1}, z_{2}, w_{1}, w_{2}, w_{3}, w_{4}} with the cover relations ˆ0 < z_{ν}, and z_{ν} < w_{μ} for μ ≡ ν (mod 2); inducing the partition {{w_{1}, w_{3}}, {w_{2}, w_{4}}}. Given this, and given all sets X_{j} (and again letting i float), we get

Lemma. A definition of C_{8} or C_{4} ∪ C_{4} covering structures for all segments X_{i+1,i+2} (i ∈ ℙ) defines a type (1, 1, 2, 2, 2, …) confluent binomial poset structure on X, iff there is no i and 2 + 2 partition of X_{i+1} which is at the same time an induced cover and an induced co-cover partition.

Proof. If the partition {{b, c}, {d, e}} of X_{i+2} is both a cover and a co-cover partition, then there are f ∈ X_{i} and g ∈ X_{i+2}, such that the interval [f, g] = {f, b, c, g}, contradicting A(2) = 1 ≠ 2. Thus the partition avoidance condition is necessary. For the sufficiency, inspect all interval maximal chain numbers, employing the fact that the partition avoidance condition in particular implies that ((j − i ≥ 2 and b ∈ X_{i} and c ∈ X_{j}) ⟹ b < c).

With X and (ι_{i})_{i} as above, the lemma immediately yields that ι_{i}+ι_{i+1} ≤ |{2 + 2 partitions of X_{i+2}}| ≤ 3; but that this condition is sufficient for the existence of X. Finally, the implication (ϕ(X) = ϕ(X′) ⟹ X ≃ X′) may be proved by constructing isomorphisms X_{0,i} ≃ X′_{0,i} by induction on i. Thus the claim is proved.

Remark. Note, that the two kinds of sections, C_{8} and C_{4} ∪ C_{4} were employed in order to construct non-isomorphic strongly confluent finite binomial posets with the same ‘factorial functions’, or with non-isomorphic intervals of the same size, already in [1, Section 8.2]; cf. e.g. Figure 5 (p. 309) therein.

The following figure illustrates the posets with ϕ = (1^{∞}) or ϕ = (1, 2, 1, 2, 1, 2, …), respectively. In a sense, these are the extremal possibilities. There are as many non-isomorphic posets (with atomic sequence A = (1^{2}, 2^{∞})) as there are different ϕ, i.e., ℵ_{0} many. Moreover, there is a ϕ, say \overline{ϕ}, with the ‘versal property’ to contain each finite substring of [2]^{∞} without consecutive 2’s. (You may e.g. enumerate all such substrings as s_{1}, s_{2}, …, and put \overline{ϕ} := (s_{1}, 1, s_{2}, 1, s_{3}, …).) The corresponding poset contains copies of all possible intervals in posets with the given A; and in particular contains a Fibonacci number of non-isomorphic intervals of any given positive length.

[figure]

3 Further questions

This section contains some comments and questions that the ‘experts’ couldn’t answer right on the spot, but seem to have thought of. Thus, I strongly suspect that the results I mention, or similar examples, are known (even if not published).

As is well-known, the first binomial compatibility condition (1) is not sufficient to guarantee realisability. I shall provide a brief proof, based on the following two lemmata:

Lemma. The infinite sequence A is realisable iff it is realised by some strongly confluent binomial poset.

Proof. Suppose A is realised by P. For any n ∈ ℕ, let I_{n} be the set of isomorphism classes of intervals of length n in P. Each such interval has a fixed finite size, whence each I_{n} is finite. For each n > 0 and Q ∈ I_{n}, choose one element f(Q) ∈ I_{n−1}, such that any interval [x, y] of type Q has a subinterval [x, z] of type f(Q). Make I := ⋃_{n} I_{n} to an infinite directed tree, by letting the children of Q ∈ I_{n} be f^{−1}(Q) ⊆ I_{n+1}. By König’s lemma, there is an infinite path in I. The direct limit of this path (in the natural sense) indeed is a strongly confluent binomial poset realising A.

Lemma. If the finite sequence (a_{1}, a_{2}, …, a_{n}) satisfies (1) for all i, j ∈ ℙ such that i + j ≤ n, then it may be extended to an infinite sequence A satisfying (1); and A may be chosen with lim A < ∞.

Proof. Put a_{n+1} := a_{n+2} := …:= lcm(a_{1}, …, a_{n}).

Now, note that (1, 2, 3, 4, 4) fulfils the assumptions of the lemma, but cannot be the atomic numbers sequence for any binomial poset interval X = [ˆ0, ˆ1] of rank 5. In fact, for any integers n ≥ 3 and a_{n} ≥ n − 1, the sequence (1, 2, …, n − 1, a_{n}) is realisable if and only if n divides a_{n}. (If a_{n} = kn, say, with k ∈ ℙ, then we may construct such an interval by stripping the boolean lattice on n atoms of its top and bottom elements, taking k disjoint copies of the resulting poset, and adding new top and bottom elements. Conversely, if we have a realising interval X = [ˆ0, ˆ1] of the sequence, then we may define a binary relation R on the a_{n}-set X_{1} by xRx′ ⟺ ∃ y ∈ X_{2} : x, x′ ∈ [ˆ0, y]. Now, by means of the fact that any proper subinterval of X is boolean,, we may prove that R is an equivalence relation, and that each equivalence class has the size n. Thus, if k is the number of equivalence classes, indeed we get a_{n} = kn.)

Thus and by the lemmata, there is an infinite sequence A = (1, 2, 3, 4, 4, …) and fulfilling (1) but non-realisable as the atomic numbers sequence of any binomial poset whatsoever. In fact, the sequence (1, 2, 3, 4^{2}, 6^{∞}) satisfies (1).

Another example is provided by the fact that the atom number sequence (a_{1}, a_{2}, a_{3}) = (1, m, m+1) is (uniquely) realised by the interval {ˆ0; x_{1}, …, x_{m+1}; y_{1}, …, y_{m+1}; ˆ1}, with x_{i} < y_{j} if and only if i ≠ j; but that for m ≥ 3 this is not extendable to any binomial interval of larger length. Thus, (1, m, m + 1, (m(m + 1))^{∞}) satisfies (1), but is not realisable.

It would be interesting to find further general conditions that (finite or infinite) atomic number sequences must fulfil in order to be realisable; and optimally a necessary and sufficient set of numerical conditions.

It is fairly easy to see that (1) & lim A ≤ 3 imply that A is realisable. In fact, any prime number A limit is covered by

Lemma. For any m, n ∈ ℙ, the sequence (1^{m}, n^{∞}) is realised by X = ⋃_{i} X_{i}, defined by X_{i} := {i} × [n]^{min(i,m)}, with a cover relation (i, s) < (i + 1, t) iff the maximal proper left substring of t is a right substring of s.

It is also fairly easy to extend this construction to any sequence A = (a_{i})_{i=1}^{∞} ∈ {1} × ℙ^{∞} such that a_{i}|a_{i+1} for all i ∈ ℙ. In particular, this covers any sequence satisfying (1) and with a prime power limit. Thus and by the example supra, the smallest limit a for which (1) is not a sufficient condition is a = 6. I suspect that there are similar counterexamples for any limit a which has different prime factors.

4 Acknowledgements

I thank Margaret Readdy, Richard Stanley, and Richard Ehrenborg for introducing me to this subject, in seminairs and stimulating conversation at the Mittag-Leffler Institute; and especially the latter Richard for TEXnical assistance with the illustration.

References

[1] P. Doubilet, G.-C. Rota and R. Stanley, On the foundation of combinatorial theory (VI). The idea of generating functions, in Sixth Berkeley Symp. on Math. Stat. and Prob., vol. 2: Probability Theory, Univ. of California (1972), pp. 267–318.

[2] R. Ehrenborg and M. Readdy, Sheffer posets and r-signed permutations, Annales des Sciences Mathématiques du Québec 19 (1995), 173–196.

[3] R. Ehrenborg and M. Readdy, Characterization of the factorial functions of Eulerian binomial and Sheffer posets, preprint 2005.

[4] V. Reiner, Upper binomial posets and signed permutation statistics, European J. Combin. 14 (1993), 581–588.

[5] R. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combin. Theory Ser. A 20 (1976), 336–356.

[6] R. Stanley, “Enumerative Combinatorics, Vol. I,” Wadsworth and Brooks/Cole, Pacific Grove, 1986.

Matematiska Institutionen Stockholms Universitet SE-106 91 Stockholm SWEDEN

joeb@math.su.se