A Note on Planar and Dismantlable Lattices

Karen L. Collins Dept. of Mathematics, Wesleyan University Middletown, CT 06459-0128

Keywords: dismantlable, lexicographically shellable, Cohen–Macaulay, planar, lattice.

All lattices are assumed to be finite. Björner [2] has shown that a dismantlable (see Rival, [5]) lattice L is Cohen-Macaulay (see [6] for definition) if and only if L is ranked and interval-connected. A lattice is planar if its Hasse diagram can be drawn in the plane with no edges crossing. Baker, Fishburn and Roberts have shown that planar lattices are dismantlable, see [1]. Lexicographically shellable lattices are Cohen-Macaulay, see [3]. In a recent paper, [4], the author proved that a planar lattice L is lexicographically shellable if and only if L is rank-connected.

[figure: (a); (b); (c); (d); Figure 1]

We prove a conjecture of Björner that a dismantlable, rank-connected lattice is lexicographically shellable. We also show that an ranked and interval-connected lattice must be rank-connected. Hence, if L is a dismantlable lattice, L ranked and is interval-connected if and only if L is rank-connected. However, a rank-connected lattice need not be interval-connected. Figure 1(a) is a rank-connected lattice that is neither interval-connected nor planar. Not every dismantlable lattice is planar, see, for instance, Figure 1(d).

In [4] it was conjectured that planar, rank-connected lattices are admissible (see Stanley, [7]). However, Figure 1(b) is a counterexample to that conjecture. Figure 1(c) is a planar, rank-connected lattice that is neither upper nor lower semi-modular.

A lattice must have a least element ˆ0, and a greatest element ˆ1. A lattice that contains only a least element and a greatest element is trivial. A lattice is ranked if every maximal chain from ˆ0 to ˆ1 has the same length. For element x, r(x) is defined to be the length of a maximal chain from the least element to x. Let R_{i} be the set of elements of rank i. A lattice is rank-connected if it is ranked and the subgraph of the Hasse diagram induced by R_{i} and R_{i+1} forms a connected graph for all 0 ≤ i < r(ˆ1).

An element in a lattice is said to be join-irreducible if it covers exactly one element, and meet-irreducible if it is covered by exactly one element. An element that is both join- and meet-irreducible is said to be doubly irreducible. A lattice L is dismantlable if there is a chain L_{1} ⊆ L_{2} ⊆ ⋯ ⊆ L_{n} = L of sublattices of L such that the lattice L_{i} has i elements for 1 ≤ i ≤ n. Each single element in L_{k} − L_{k−1} is doubly irreducible in L_{k}. Equivalently, a lattice is dismantlable if and only if every non-trivial sublattice has a doubly irreducible element, see [5].

Let L be a ranked lattice. Let C(L) equal the set of covering relations of L. Then L is lexicographically shellable if there exists a labeling f : C(L) → R such that

1. in every interval [x, y] of L there is a unique unrefinable chain x = x_{0} < x_{1} < … < x_{n} = y such that f(x_{0}, x_{1}) ≤ f(x_{1}, x_{2}) ≤ … ≤ f(x_{n−1}, x_{n}).

2. for every interval [x, y] of L, if x = x_{0} < x_{1} < … < x_{n} = y is the unique unrefinable chain with rising labels, and if z ∈ [x, y] covers x with z ≠ x_{1}, then f(x, x_{1}) < f(x, z).

Theorem 1. Let L be a rank-connected, dismantlable lattice. Then L is lexicographically shellable.

Proof. We prove this by induction. First, we make a reduction. Suppose that some rank other than the top and bottom rank contains a single vertex x. Then the lattices [ˆ0, x], [x, ˆ1] are dismantlable and rank-connected. Any lexicographic shelling of [ˆ0, x] and separately of [x, ˆ1] will be a lexicographic shelling of L as long as all labels in [x, ˆ1] are greater than all labels of [ˆ0, x]. By induction, therefore, we may assume that every rank except the very top and the very bottom contains at least two elements.

Since L is dismantlable, every non-trivial sublattice of L contains a doubly irreducible element. We show that the covers of doubly irreducible elements and the vertices covered by doubly irreducible elements cannot themselves be doubly irreducible. Let x be doubly irreducible in L. Suppose r(x) = i. Let the unique vertex that x covers be z and the unique vertex that covers x be y. Let G be the induced bipartite graph of the Hasse diagram with vertices R_{i} ∪ R_{i+1}. Then both x and y are in G, and G is a connected graph because L is rankconnected. Since x is doubly irreducible, x is a degree 1 vertex in G, hence G − x is still connected. Since R_{i} contains at least two vertices, G − x must contain y and at least one vertex in R_{i}, hence y has an edge to another vertex of rank i. Therefore y (and similarly z) cannot be doubly irreducible in L.

For rest of the proof, we rely on the following definition and previous result. We say that w is a corner of x in L if there exist z and y such that x, w both cover z and are covered by y, and x is doubly irreducible. Theorem 1 of [4] guarantees that L is lexicographically shellable if L − x is lexicographically shellable. We prove that there must always exist a doubly irreducible element of L that has a corner, hence L is lexicographically shellable by induction.

Let the doubly irreducible vertices of L be D := {x_{1}, x_{2}, x_{3}, …, x_{t}}. Suppose that no element of D has a corner. Let x_{j} cover z_{j} and be covered by y_{j} in L for 1 ≤ j ≤ t. As seen before, rank connectedness guarantees that z_{j} and y_{j} are not doubly irreducible in L. Consider the relation z_{j} ≤ y_{j} (which is true in L) in the sublattice L − D. There must be a chain from z_{j} to y_{j} in L − D.

However in L, the rank of z_{j} and y_{j} differs by exactly 2. Therefore, any chain between z_{j} and y_{j} in L − D must have length less than or equal to 2, since removing vertices cannot make chains longer. If the length of the chain is 2, then the middle vertex of the chain will be a corner of x_{j}. By our assumption, x_{j} has no corners, hence y_{j} must cover z_{j} in L − D.

Suppose that y_{j} covers both x_{j} and x_{k} for some k. Now x_{k} is not a corner of x_{j}, so z_{j} ≠ z_{k}. Therefore, y_{j} covers both z_{j} and z_{k} in L − D. Thus if element u covers s vertices in L, after removing the doubly irreducible vertices, u still covers s vertices in L − D. Each doubly irreducible vertex x_{j} is replaced by the unique vertex z_{j} that it covers. Similarly, if element u is covered by s vertices in L, it is still covered by s elements in L − D.

Hence the sublattice L − D is composed entirely of elements that are not doubly irreducible. It is not empty, since L must contain at least one doubly irreducible element x and therefore contains both the unique element that covers and the unique element that is covered by x. Since L is dismantlable, L − D must be the trivial lattice that contains only a top and bottom element. Thus, L must have rank 2 and all its doubly irreducible elements have rank 1. Each of these rank 1 elements is a corner of every other, contradicting our assumption that no doubly irreducible element has a corner.

Define [x, y] = {z|x ≤ z ≤ y}. A lattice is interval-connected if for every pair x, y with r(y) ≥ 2 + r(x) the Hasse diagram of [x, y] − {x, y} is connected.

Theorem 2. Let L be an interval-connected, ranked lattice. Then L is rank-connected.

Proof. Any sublattice [x, y] of L must be interval-connected. Assume by induction that every interval [x, y] ≠ [ˆ0, ˆ1] is rank-connected. We will show that [ˆ0, ˆ1] is rank-connected.

Let L̂ be the subposet of L that contains all vertices except ˆ0, ˆ1. Let G be the subgraph of the Hasse diagram induced by R_{i} and R_{i+1}. Since L is interval-connected, there must be some path between any two vertices in G in L̂. Suppose that G is not connected. Let u, v be elements of G such that u and v are not in the same connected component of G and such that p(u, v) is the shortest possible path between any two elements in different connected components of G that is contained in L̂. Let P be the set of vertices in p(u, v) − {u, v}. Then P does not intersect the vertices in G, so u, v both have rank i or both have rank i + 1, and the rank of all vertices in P must be less than i or greater than i + 1, respectively. Without loss of generality, assume that u, v have rank i and let a be the last element of p(u, v) that is strictly less than u.

We observe that if u ∧ v > ˆ0, then [u ∧ v, ˆ1] is smaller than L, and therefore is rank-connected by induction. This means there is a path from u to v in G ∩ [u ∧ v, ˆ1], which is clearly a path in G. Therefore we may assume that u ∧ v = ˆ0. Similarly, we can assume u ∨ v = ˆ1. Now a < u and a ≠ v since r(v) = r(u). Let b be the next element after a in p(u, v). Then a and b are comparable, hence b ≥ a, since u ≱ b. If v ≥ b ≥ a, then ˆ0 = u ∧ v ≥ a > ˆ0, a contradiction. So b is incomparable to both u and v.

There exists a path from b to ˆ1 in L that is strictly rank increasing. Let p(b, ˆ1) be such a path. Now r(b) = r(a) + 1 ≤ r(u) = i. Let b(i) be the element on p(b, ˆ1) that has rank equal to i. Then b(i) ≥ b ≥ a and u ≥ a imply that b(i) ∧ u ≥ a > ˆ0. Therefore, b(i) and u must be in the same connected component of G.

If b(i) is in the same connected component of G as v, then by transitivity u and v are in the same component. If b(i) and v are in different components, then we replace the pair u and v by the pair b(i) and v and take a path from b(i) to v that consists of starting at b(i) and following a strictly rank decreasing path to b and then following the portion of p(u, v) from b to v. This must be a shorter path than p(u, v) between a rank i element and a rank i + 1 element in different connected components of G, because the portion of p(u, v) from u to b goes through a and is therefore longer than the strictly rank decreasing path from b(i) to b. We bypass a, and a has lower rank than b. This contradicts the selection of p(u, v) as the shortest possible path.

Admissible lattices are lexicographically shellable, but not all lexicographically shellable lattices are admissible. See Stanley’s paper for details [7]. We define admissible lattices and show that there is a planar, rank-connected lattice which is lexicographically shellable, but not admissible. Let J be the set of join-irreducibles of a lattice. Define a natural labeling ω of J to be a map ω : J → N where N is the positive integers such that if z, w ∈ J and z ≤ w, then ω(z) ≤ ω(w). Let γ be derived from ω by γ(x < y) = min{ω(z)|z ∈ J, x < x ∨ z ≤ y}. A lattice L is admissible if whenever x < y in L, there is a unique unrefinable chain x = x_{0} < x_{1} < … < x_{m} = y such that γ(x_{0}, x_{1}) ≤ γ(x_{1}, x_{2}) ≤ … ≤ γ(x_{m−1}, x_{m}).

The planar, rank-connected lattice in Figure 1(b) is lexicographically shellable, but it is not admissible. Label the vertices with 0 to 11 starting at the lowest rank and moving left to right. Then the join irreducibles are 1, 2, 3, 4, 6, 7. Suppose we have an admissible labeling of the poset. Then ω(3), ω(4) ≥ ω(1), hence γ(10 < 11) = ω(1). Clearly γ(7 < 10) = ω(6). Since there is a unique chain from 7 to 11, it must be rising and ω(6) ≤ ω(1) ≤ ω(4). By left-right symmetry, ω(4) ≤ ω(2) ≤ ω(6). Thus ω(1) = ω(2), which cannot happen, since the two chains from 0 to 5 will then both be rising.

The author would like to thank the referees for their helpful suggestions.

References

[1] K. A. Baker, P. C. Fishburn and F. S. Roberts (1971) Partial orders of dimension 2, Networks 2 pp. 11-28.

[2] A. Björner (1981) Homotopy type of posets and lattice complementation, JCT(A) 30, pp. 90-100.

[3] A. Björner (1980) Shellable and Cohen-Macaulay partially ordered sets, Trans. of the AMS 260, pp. 159-184.

[4] K. L. Collins (1992) Planar lattices are lexicographically shellable, Order 8 pp. 375-381.

[5] I. Rival (1974) Lattices with doubly irreducible elements, Can. Math. Bull. 17, pp. 91-95.

[6] R. P. Stanley (1983) Combinatorics and Commutative Algebra, Vol. 41 in Progress in Mathematics, Birkhaüser, Boston.

[7] R. P. Stanley (1974) Finite lattices and Jordan-Hölder sets, Algebra Universalis 4, pp. 361-371.