Electronic Journal: Southwest Journal of Pure and Applied Mathematics Internet: http://rattler.cameron.edu/swjpam.html ISSN 1083-0464 Vol. No. 01, 1996, pp. 42–50. Submitted: January 12, 1996. Published: May 28, 1996.

When is a Poset Isomorphic to the Poset of Connected Induced Subgraphs of a Graph?

André E. Kézdy and Steve Seif

Abstract

Suppose G is a finite connected graph. Let C(G) denote the inclusion ordering on the connected vertex-induced subgraphs of G. Resolving a problem posed by Steve Steinsaltz, we characterize posets that arise in this way. In particular, we show that, for a finite poset P, there exists a finite graph G such that C(G) ≅ P if and only if P is atom-height and properly semimodular. We present a similar characterization for infinite posets.

(1991) A.M.S. (MOS) Subject Classification Codes. 05. Key Words and Phrases. Graph, poset, vertex induced.

1 Introduction

Suppose G is a finite connected graph. Let C(G) denote the inclusion ordering on the connected vertex-induced subgraphs of G.

Partially ordered sets arising in this manner have come under study within the last ten years [7, 9, 8, 10]. In recent work with Michael Jacobson [5] the authors proved that these posets need not be Sperner. In this paper we solve a problem posed by S. Steinsaltz [9] by characterizing those posets that arise as the inclusion ordering on the connected vertex-induced subgraphs of some graph. Our characterization links commonly studied properties of posets with commonly studied properties of graphs.

In the next section we give preliminary definitions and notation. In section three, we prove that for a finite poset P, there exists a finite graph G such that C(G) ≅ P if and only if P is atomheight and properly semimodular. In section four we integrate the familiar lattice concepts of meet semidistributivity and local distributivity into this characterization. In section five we extend the characterization to infinite posets.

Department of Mathematics University of Louisville Louisville, KY 40292. E-mail Address: swseif01@homer.louisville.edu Copyright \begin{matrix}c \\ ◯ \end{matrix}1996 by Cameron University

2 Preliminaries

A partially ordered set (or poset) P = (P, ≤) is a set P of elements together with a binary relation ≤ on P that is reflexive, antisymmetric, and transitive. An element x ∈ P is an upper bound for a subset S ⊆ P if s ≤ x for all s ∈ S. An element x ∈ P is a least upper bound for S ⊆ P if x is an upper bound for S and, for any upper bound z ∈ P for S, x ≤ z. Lower bounds and greatest lower bounds for S are defined dually. If a subset S ⊆ P has a least upper bound (greatest lower bound) then we denote it by ⋁ S (⋀ S). A lattice is a poset in which every pair of elements has a least upper bound and greatest lower bound. If arbitrary subsets of elements have least upper bounds and greatest lower bounds, then the lattice is complete. A lattice is distributive if a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), for all elements a, b, and c in the poset.

If the poset P has a unique least element, we will refer to it as 0. Given two elements a and b of a poset, if a ≤ b and a ≤ c ≤ b implies c ∈ {a, b}, then we say that b covers a and write a ≺ b or b ≻ a. If a poset P has a 0 and 0 ≺ a ∈ P, then a is said to be an atom of P.

Two elements a, b ∈ P are comparable if a ≤ b or b ≤ a; otherwise they are incomparable. A subset of pairwise comparable elements is called a chain. A chain C is saturated if there does not exist a z ∈ P − C such that x ≤ z ≤ y for some x, y ∈ C. The length of a chain is one less than the number of elements in the chain. The interval between two comparable elements a, b ∈ P is defined as [a, b] = {c ∈ P : a ≤ c ≤ b}. A poset is graded (or ranked) if, for all comparable pairs a ≤ b, all saturated chains with least element a and greatest element b have the same length. In a finite, graded poset with 0, the height of the element p, denoted ht(p) is the length of a saturated chain from 0 to p.

Two posets P and Q are isomorphic if there exists an order-preserving bijection ϕ : P → Q; that is,

x ≤ y  ⇔  ϕ(x) ≤ ϕ(y).

If P and Q are isomorphic, then we write P ≅ Q.

A lattice L = (L, ≤) is semimodular if for any a, b, c ∈ L, a ≺ b, a < c and b ≰ c implies c ≺ b ∨ c. It is well-known that semimodular finite lattices are graded. The converse is not true.

Given an element p from a poset P, the symbol p↑ denotes the principal filter of P determined by p; that is, p↑ = {q ∈ P : p ≤ q}. The set of atoms below an element x ∈ P is denoted A_{x}. Hence A_{x} = {a ∈ P : a ≤ x and a is an atom of P}. A poset P is atomic if x = ⋁ A_{x}, for all x ∈ P.

We now give two definitions specific to this paper. A graded, atomic poset is atom-height if for all x ∈ P, ht(x) = |A_{x}|. If P is a lattice property, then a poset is said to be properly P if every proper, principal filter is a lattice and satisfies P.

3 A characterization of C(G) posets

Suppose that G = (V, E) is a (not necessarily finite) connected graph with vertex set V and edge set E. Let C(G) denote the inclusion ordering on the connected vertex-induced subgraphs of G. In this section we characterize posets that arise as the inclusion ordering on the connected vertex-induced subgraphs of some finite graph.

Theorem 3.1 Let P be a finite poset. The following are equivalent:

(i) There exists a finite, connected graph G such that P ≅ C(G), (ii) P is atom-height and properly semimodular.

Our proof of Theorem 3.1 requires several lemmas.

We shall consistenly represent elements of C(G) with lower case letters. Vertices of G are denoted by bold lower case letters. If x ∈ C(G), the corresponding subset of V is denoted by V_{x}. In the special case when x is an atom of C(G), x will denote the vertex of G corresponding to x. If S ⊂ V (G), then the subgraph of G induced by S is denoted G[S].

A few simple observations: for any x ∈ C(G), |V_{x}| = |A_{x}|; and, x ≤ y in C(G) if and only V_{x} ⊆ V_{y}. Suppose 0 ≠ x ∈ C(G). For any y, z contained in x↑, the induced subgraph G[V_{y} ∪ V_{z}] is connected because both G[V_{y}] and G[V_{z}] are connected, and V_{x} ⊆ V_{y} ∩ V_{z}. Indeed, for any y, z contained in x↑ (for x > 0), we have

V_{y∨z} = V_{y} ∪ V_{z}  (1)
V_{y∧z} = max{S : V_{x} ⊆ S ⊆ V_{y} ∩ V_{z} and G[S] is connected.}  (2)

Observe that the maximum taken in (2) exists and does not depend upon the finiteness of G.

Lemma 3.2 If G is a connected graph, then x ≺ y in C(G) if and only if |V_{y} − V_{x}| = 1 and x ≤ y.

Proof. Suppose that x ≺ y in C(G). Clearly V_{y} ≠ V_{x}. If |V_{y} − V_{x}| > 1, then because V_{y} is connected and contains V_{x}, there must be some vertex u in G such that H = V_{x} ∪ {u} induces a connected graph. No element of C(G) could correspond to H because any such element z ∈ C(G) must satisfy x < z < y, contradicting x ≺ y. We conclude that |V_{y} − V_{x}| = 1.

Conversely, suppose that |V_{y} − V_{x}| = 1 and x ≤ y. Any subset of V_{y} properly containing V_{x} must contain V_{y}. The result follows. □

Lemma 3.3 If G is a finite, connected graph, then C(G) is an atom-height poset.

Proof. Suppose u ∈ C(G). Because u is an upper bound for each element in A_{u} and |V_{u}| = |A_{u}|, it follows that u = ⋁ A_{u}. So C(G) is atomic.

Suppose x, y ∈ C(G) with x < y. By lemma 3.2, x ≺ y if and only if |V_{y} − V_{x}| = 1. By straight-forward induction on |V_{x}|, it also follows that any saturated chain from 0 to x has length |V_{x}| = |A_{x}|. In other words, C(G) is graded, and for x ∈ C(G), ht(x) = |A_{x}|. This proves that C(G) is atom-height. □

Lemma 3.4 Suppose that G is a connected graph. For any 0 ≠ x ∈ C(G), the principal filter generated by x is a complete semimodular lattice.

Proof. Suppose 0 ≠ x ∈ C(G). For any {x_{i}}_{i∈I} ⊆ x↑, the join ⋁_{i∈I} x_{i} exists because G [⋃_{i∈I} V_{x_{i}}] is connected. The presence of a unique least element in x↑ (namely x) and the existence of arbitrary joins guarantees the existence of arbitrary meets: ⋀_{i∈I} x_{i} = ⋁{y ∈ x↑ : y ≤ x_{i} for all i ∈ I}. Hence x↑ is a complete lattice.

To show that x↑ is semimodular, suppose that i, j, k ∈ x↑ and i ≺ j, i ≤ k, j ≰ k. Now V_{i} ⊆ V_{j} and V_{i} ⊆ V_{k}. Because i ≺ j, lemma 3.2 implies |V_{j} − V_{i}| = 1. From (1) we know that the vertex set of j ∨ k is V_{j} ∪ V_{k}. Because |V_{j} ∪ V_{k} − V_{k}| = 1, lemma 3.2 guarantees that k ≺ k ∨ j as desired. □

Observe that this last result actually does not depend upon the finiteness G. Indeed we shall use this result later in the case that G is infinite.

Consider a finite, atom-height, properly semimodular poset P. From P construct a graph G_{P} whose vertices are the atoms of P, and whose edges are pairs of distinct atoms a, b ∈ P for which the join a∨b exists and has height two. In the following two lemmas, we show that there is a natural isomorphism P ≅ C(G_{P}).

Lemma 3.5 Suppose that P is an atom-height, properly semimodular poset. If x ∈ P, then G_{P} [A_{x}] is connected.

Proof. The proof is an induction on the ht(x). Recall that A_{x} is the set of atoms of P less than or equal to x. If ht(x) = 1, then A_{x} = {x} and so the subgraph of G_{P} induced by this set is clearly connected. Similarly, if ht(x) = 2, then |A_{x}| = 2 because P is atom-height. Let {a, b} = A_{x}. Since P is atomic, x = ⋁ A_{x} = a ∨ b. By definition of the graph G_{P}, ab is an edge of G_{P}; hence G[{a, b}] is connected.

Suppose that the lemma is true for all elements of P with height at most n. Let x ∈ P with ht(x) = n + 1 > 2.

We claim that if w ∈ P and ht(w) ≥ 2, then either w is the unique largest element of P or |{y ∈ P : y ≺ w}| ≥ 2. If not, a non-maximum element w ∈ P exists with ht(w) ≥ 2 and |{y ∈ P : y ≺ w}| ≤ 1. Let y be the unique element covered by w. Now A_{w} = A_{y}, but because P is atomic w = ⋁ A_{w} = ⋁ A_{y} = y, contradicting y ≺ w.

By the previous paragraph, we may assume that there are two distinct elements w, y ∈ P such that w ≺ x and y ≺ x. Because P is atom-height, |A_{w}| = |A_{y}| = n. By the induction hypothesis, the subgraphs of G_{P} induced by the vertex sets A_{w} and A_{y} are connected. Because |A_{x}| = n + 1, A_{w} ∪ A_{y} = A_{x} and |A_{w}| = |A_{y}| = n > 2, we conclude that A_{w} ∩ A_{y} ≠ ∅. Hence the subgraph of G_{P} induced by A_{w} ∪ A_{y} = A_{x} is connected. □

Lemma 3.6 Suppose that P is an atom-height, properly semimodular poset. If S is a set of atoms of P and G_{P} [S] is connected, then there exists some x ∈ P such that A_{x} = S.

Proof. The proof is by induction on |S|. If |S| = 1, then S = {a}, for some atom a ∈ P; hence S = A_{a}. If |S| = 2, then S = {a, b}, for some pair of atoms a, b ∈ P such that ab is an edge of G_{P}. Because ab is an edge of G_{P}, the element a ∨ b exists and has height 2. By the atom-height property, A_{a∨b} = {a, b} = S.

Suppose the lemma is true for all sets of atoms with at most n ≥ 2 elements. Consider a set S of n + 1 atoms from P such that G_{P} [S] is connected. By considering a spanning tree of G_{P} [S], we can find two leaves of G_{P} [S], and hence we can find two atoms a_{1}, a_{2} of P such that G_{P} [S − {a_{1}}], G_{P} [S − {a_{2}}], and G_{P} [S − {a_{1}, a_{2}}] are all connected graphs. Note that n ≥ 2 implies that G_{P} [S − {a_{1}, a_{2}}] contains at least one vertex. By the induction hypothesis, there exist x, y, z ∈ P such that S − {a_{1}} = A_{x}, S − {a_{2}} = A_{y}, and S − {a_{1}, a_{2}} = A_{z}. Because P has the atom-height property, ht(x) = n = ht(y), z ≺ x, and z ≺ y. In particular, z ≠ 0 so the proper semimodularity of P implies z↑ is a semimodular lattice. Hence, x ≺ x ∨ y, y ≺ x ∨ y, and ht(x ∨ y) = n + 1 = |A_{x∨y}|. Observing that A_{x} ⊂ A_{x∨y} and A_{y} ⊂ A_{x∨y}, we conclude that A_{x∨y} = S. □

\underline{Theorem 3.1}: Proof. By Lemma 3.3 and Lemma 3.4, if G is a finite connected graph, then C(G) is an atom-height, properly semimodular poset.

Conversely, suppose that P is an atom-height, properly semimodular poset. By Lemma 3.5, the mapping ϕ : P → C(G_{P}) defined by ϕ(x) = A_{x} is well-defined. By Lemma 3.6, the mapping ϕ is onto C(G_{P}). Because P is atomic, A_{x} = A_{y} implies that x = y so ϕ is one-to-one. If x ≤ y, then A_{x} ⊆ A_{y}. Conversely, if A_{x} ⊆ A_{y}, then x ≤ y because P is atomic. Therefore, C(G_{P}) ≅ P. □

4 SD_{∧} and Local Distributivity

Meet semidistributivite (SD_{∧}) and locally distributive lattices often arise when graph theory and combinatorics is the background setting (see [4, 6, 8]). We now integrate such lattices into our description of C(G) posets.

A lattice L = (L, ≤) is meet semidistributive (SD_{∧}) if a ∧ b = a ∧ c implies a ∧ b = a ∧ (b ∨ c), for all elements a, b, c, d from the lattice.

Lemma 4.1 Let G be a connected simple graph. The poset C(G) is properly SD_{∧}.

Proof. Suppose that 0 ≠ u ∈ C(G). We may assume that u is an atom of C(G). Consider u↑, and let x, y, z ∈ u↑ such that x ∧ y = x ∧ z. We must prove that x ∧ (y ∨ z) = x ∧ y, or equivalently V_{x∧(y∨z)} = V_{x∧y}. The vertex set V_{x∧y} is the maximal set in

{S ⊂ V (G) : U ⊆ S ⊆ V_{x} ∩ V_{y} and G[S] is connected.}.

as noted in (2). Because V_{x∧y} = V_{x∧z}, it follows that the vertex set V_{x∧y} is contained in V_{x} ∩V_{y} ∩V_{z}. Because of (1), the vertex set V_{y∨z} is V_{y} ∪V_{z}. This means that V_{x∧(y∨z)} is a subset of V_{x} ∩(V_{y} ∪V_{z}) = (V_{x} ∩ V_{y}) ∪ (V_{x} ∩ V_{z}).

Let {u} = V_{u}, and let v ∈ V_{x∧(y∨z)}. By symmetry, we may assume that v ∈ V_{x} ∩ V_{y}. Because u and v are in V_{x∧(y∨z)}, there must be a path from u to v using only vertices in this set. Let

u = v_{1}v_{2} ⋯ v_{n} = v

be the sequence of vertices in this path, where v_{i} ∈ (V_{x} ∪ V_{y}) ∪ (V_{x} ∩ V_{z}) and v_{i}v_{i+1} ∈ E(G) for each i. Note that both u = v_{1} and v = v_{n} are vertices of V_{x} ∩ V_{y}.

The subgraph of G[V_{u} ∪{v_{2}}] is connected and contains u. Suppose that w is the element of u↑ in C(G) corresponding to this induced subgraph. If v_{2} ∈ V_{x} ∩V_{y}, then it follows that w ≤ x∧y = x∧z. In particular, {u, v_{2}} ⊆ V_{x} ∩ V_{z}. We have shown that v_{2} ∈ V_{x} ∩ V_{y} implies that v_{2} ∈ V_{x} ∩ V_{z}. By induction, it follows that v ∈ V_{x} ∩ V_{y} ∩ V_{z}. That is, V_{x∧(y∨z)} is contained in V_{x} ∩ V_{y} ∩ V_{z} and contains u. Maximal among connected vertex subsets containing u and contained in V_{x} ∩ V_{y} ∩ V_{z} is V_{x∧y∧z} = V_{x∧y} = V_{x∧z}. Hence, x ∧ (y ∨ z) ≤ x ∧ y = x ∧ z. Consequently, x ∧ (y ∨ z) = x ∧ y, as desired. □

Let L = (L, ≤) be a lattice. For a ∈ L, define C_{a} = {b ∈ L : a ≺ b}. Let a^{+} = ⋁ C_{a}. If for all a ∈ L, the interval [a, a^{+}] is distributive, then L is said to be locally distributive. (In the literature, locally distributive lattices are sometims called upper locally distributive. See the paper by Monjardet [6] for more information.) The following result is well-known.

Proposition 4.2 If L is a finite lattice, then L is locally distributive if and only if L is both semimodular and SD_{∧}.

Here is an extension of Theorem 3.3.

Theorem 4.3 For a finite poset P the following are equivalent:

(i) There exists a connected graph G such that P ≅ C(G),

(ii) P is an atom-height, properly semimodular poset,

(iii) P is an atom-height, properly semimodular, and properly SD_{∧} poset,

(iv) P is an atom-height, and properly locally distributive poset.

Proof. By Theorem 3.3, (i) and (ii) are equivalent. By Lemma 4.1 and Theorem 3.3, (i) implies (iii). Proposition 4.2 and Theorem 3.3 shows that (iv) implies (i). □

Using (1) and Lemma 3.2, one can show directly that, for any graph C(G) is locally distributive. Infinte locally distributive lattices are not in general semimodular or SD_{∧}; hence, for infinite graphs, Lemmas 3.4 and 4.1 are not direct consequences of the local distributivity of C(G) as they are in the finite case via Proposition 4.2.

5 The Infinite Case

In this section we characterize those infinite partial orders that arise as the inclusion ordering on the connected vertex-induced subgraphs of an infinite graph. It is natural to try to reduce the infinite case to the finite case via compactness. Here, compactness arises in the context of lattices, and we are able to describe C(G) posets (G infinite), using Theorem 4.3 (the finite case) along with a compactness condition In this way we avoid having to deal with infinite cardinals.

By a connected infinite graph G we mean an infinite graph in which, for any pair of vertices u and v of G, there exists a finite connected subgraph of G containing u and v. A poset is graphic if it is isomorphic the inclusion ordering on the connected vertex-induced subgraphs of a graph.

It makes sense here to define the height of an element in a poset with a 0 to be the length of the shortest saturated chain from 0 to that element (Note that the usual definition of height of an element is the length of the longest saturated chain from 0 to that element). With this definition of height, we say that an infinite poset P with 0 is finitely graphic if for any element a ∈ P with finite height, the interval [0, a] is graphic.

Recall that a lattice L = (L, ≤) is complete if ⋁ S and ⋀ S exists for all S ⊆ L. Suppose that L is a complete lattice. An element k ∈ L is compact if, for every S ⊆ L, k ≤ ⋁ S implies that k ≤ ⋁ T, for some finite subset T ⊂ S. A lattice L is algebraic if, for each a ∈ L,

a = ⋁{k ∈ L|k is compact and k ≤ a}.

Now we are ready to state the characterization in the infinite case.

Theorem 5.1 Suppose that P is a poset with 0. The following are equivalent:

(i) P ≅ C(G), for some connected graph G (ii) P satisfies the following three conditions: (a) P is finitely graphic

(b) P is atomic

(c) for 0 < x ∈ P, x↑ is an algebraic semimodular lattice whose compact elements are the elements of finite height.

Proof. “(i) ⇒ (ii)” Suppose that P is a poset with 0, and G is a connected graph such that P ≅ C(G). For an element x ∈ P with finite height, the interval [0, x] in P is isomorphic to C(X), where X is the subgraph of G corresponding to x. Hence P is finitely graphic.

For an arbitrary element 0 < x ∈ P, the connected subgraph of G corresponding to x has a vertex set that is simply the union of its vertices. Therefore P is atomic. The completeness and semimodularity of x↑ follows from Lemma 3.4. Because every element of x↑ corresponds to the vertex set of a connected subgraph of G containing x, and such vertex sets are unions of finite subgraphs containing x, if follows that the compact elements of x↑ are precisely the elements of finite height. The filter x↑ is algebraic for the same reasons.

“(ii) ⇒ (i)” Suppose that P is a poset with 0 satisfying conditions (a), (b), and (c). Recall that, given a poset P, we define the graph G_{P} whose vertices are the atoms of P, and whose edges are pairs of distinct atoms a, b ∈ P for which the join a ∨ b exists and has height two. We prove (ii) implies (i) by showing P ≅ G_{P} in two steps. The first step is an analog of Lemma 3.5.

Step 1: For all w ∈ P, G_{P} [A_{w}] is connected.

If w has finite height, then condition (a) implies that G_{P} [A_{w}] is connected. Assume w does not have finite height. By condition (b), w is the join of atoms. In particular, w is in the filter of some atom a, so condition (c) guarantees that w = ⋁_{i∈I} p_{i}, where the p_{i}’s have finite height in a↑. Consequently, the p_{i}’s have finite height in P. Let A_{i} be the set of atoms below p_{i}, for i ∈ I. Condition (a) guarantees that each G_{P} [A_{i}] is connected. Hence,

G_{P} [A_{w}] = G_{P} [⋃_{i∈I} A_{i}]

The last subgraph is connected because it is the union of connected graphs containing the vertex a.

The next step is an analog of Lemma 3.6.

Step 2: Suppose that C is a set of atoms in P. If G_{P} [C] is connected, then some x ∈ P exists such that A_{x} = C.

Suppose first that |C| is finite. We prove the result by induction on |C|. The basis cases are |C| = 1, 2. If |C| = 1, then C = A_{a} where C = {a}. If |C| = 2, then C = {a, b} for atoms a ≠ b of P such that a ∨ b exists and a ∨ b has height two. Condition (a) implies that [0, a ∨ b] is graphic and, consequently C = A_{a∨b}. If |C| ≥ 3, then G_{P} [C] contains a vertex a such that C is the disjoint union of two sets C_{1} and C_{2} with C_{1} ∩ C_{2} = {a} and G_{P} [C_{i}] is connected for i = 1, 2 (consider a spanning tree T of G_{P} [C], and let b be a leaf T with neighbor a. Let C_{1} = {a, b} and let C_{2} = C − {b}.) By the inductive hypothesis, C_{1} = A_{w} and C_{2} = A_{z}, where w, z ≥ a and both w and z have finite height. Because a↑ is semimodular, it follows that w ∨ z has finite height. Therefore A_{w∨z} contains C. Moreover, G_{P} [C] is a connected subgraph of G_{P} [A_{w∨z}] so C = A_{w∨z}.

Suppose now that |C| is infinite. Let a ∈ C and consider a↑. Define

C = {S ⊂ C : |S| is finite, G_{P} [S] is connected, a ∈ S}.

By the previous paragraph, for all S ∈ C, an element s ∈ P exists such that S = A_{s} and s ≥ a. Because a↑ is complete, the join ⋁{s ∈ P |A_{s} ∈ C and s ≥ a} exists; let w ∈ P equal this join. We want to show A_{w} = C. Clearly C ⊆ A_{w}. It suffices to show A_{w} ⊆ C. Step 1 guarantees that G_{P} [A_{w}] is connected. Furthermore, G_{P} [A_{w}] contains C. Suppose, for a contradiction, that there exists some element b ∈ A_{w} − C. We may assume that b has a neighbor x in G_{P} [A_{w}] such that x ∈ C. Consider the set {s ∈ P |A_{s} ∈ C and s ≥ a and s ≥ x} = {w_{i}}_{i∈I}. Note that ⋁_{i∈I} w_{i} = w because every s ∈ P such that A_{s} ∈ C and s ≥ a is below some w_{i}. By assumption, b ∈ A_{w}. Hence b ≤ w = ⋁_{i∈I} w_{i}. Consequently,

x ∨ b ≤ x ∨ (⋁_{i∈I} w_{i})
≤ ⋁_{i∈I}(x ∨ w_{i})

≤ ⋁_{i∈I} w_{i}  (because x ≤ w_{i}, for all i ∈ I)
≤ ⋁_{i∈J⊂I,|J|<∞} w_{i}  (because x↑ is compact)
≤ v

where v = ⋁{w_{i} : i ∈ J}. The semimodularity of x↑ ensures that v has finite height. Because v has finite height, it is graphic. Hence A_{v} ∈ C, and b ∈ C. This shows that A_{w} = C.

The theorem now follows from steps 1 and 2 by the same reasoning as the proof of Theorem 2.1 (define a mapping ϕ : P → C(G_{P}) via ϕ(x) = A_{x} and show it is an order-preserving bijection). □

6 Acknowledgements

The authors would like to thank Michael Jacobson for stimulating discussions.

References

[1] Anderson I., Combinatorics of Finite Sets, Oxford University Press, New York, (1987).

[2] Chartrand G. and Lesniak L. , Graphs and Digraphs, 2nd Edition, Wadsworth Inc., Belmont, California, 1985.

[3] Davey B. A., and Priestley H. A., Introduction to Lattices and Order, Cambridge University Press, (1990).

[4] Edelman P. H. and Jamison R., The theory of convex geometries, Geom. Dedicata, 19 (1985) 247-274.

[5] Jacobson M. S., Kézdy A. E., and Seif S., The poset on connected induced subgraphs of a graph need not be Sperner, Order, 12 (1995) 315-318.

[6] Monjardet B., The Consequences of Dilworth’s Work on Lattices with Unique Irreducible Decompositions, in: The Dilworth Theorems (eds. K. P. Bogart, R. Freese, and J. P. S. Kung), Birhauser Verlag, (1990) 192-199.

[7] Steelman J. H., The Lattice of Connected Subgraphs of a Graph, solution to Problem E3281, Amer. Math. Monthly, 97 (1990) 924-925, proposed by S. Klavžar and M. Petkovšek, Amer. Math. Monthly, 95 (1988) 655.

[8] Trotter, W. T. , and Moore J.I., Some theorems on graphs and posets, Discrete Math., 15 (1976) 79-84.

[9] West D. B., Open Problems, Newsletter of the SIAM Activity Group on Disc. Math., Vol. 2 No. 3: Spring (1992).

[10] West D. B., Open Problems, Newsletter of the SIAM Activity Group on Disc. Math., Vol. 4 No. 1: Fall (1993).