Combinatorial Inequalities for Geometric Lattices Citation Stonesifer, John Randolph (1973) Combinatorial Inequalities for Geometric Lattices. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/7z4d-0j63. https://resolver.caltech.edu/CaltechTHESIS:06272025-201557863 Abstract A geometric lattice is a semimodular point lattice L. The i th Whitney number of Lis the number of elements of rank i in L. The logarithmic concavity conjecture states that W i (L) 2 /W i-1 (L)W i+1 (L) ≥ 1 for any finite geometric lattice L. In a finite nondirected graph without loops or double edges, a set of edges is closed if whenever it contains all but one edge of a cycle, it contains the whole cycle. With set containment as the order relation, the closed sets of such a graph form a geometric lattice. It is shown that any such lattice satisfies the first nontrivial case of the logarithmic concavity conjecture. In fact, W 2 (L) 2 /W 1 (L)W 3 (L) ≥ 3/2 · (W 1 (L)-1)/(W 1 (L)-2) · This is a best possible result since equality holds for graphs without cycles. The cut-contraction of a geometric lattice L with respect to a modular cut Q of L is the geometric lattice L - T where T = {x Є L : x Є Q, Ǝq Є Q Э x q}. It is shown that any geometric lattice L can be obtained from the Boolean algebra with W 1 (L) points by means of a sequence of k = W 1 (L) - dim(L) cut-contractions. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Dilworth, Robert P. Thesis Committee: Unknown, Unknown Defense Date: 2 May 1973 Funders: Funding Agency Grant Number U.S. Department of Health, Education and Welfare UNSPECIFIED Caltech UNSPECIFIED California State Scholarship and Loan Commission UNSPECIFIED Record Number: CaltechTHESIS:06272025-201557863 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:06272025-201557863 DOI: 10.7907/7z4d-0j63 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 17497 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 27 Jun 2025 21:53 Last Modified: 27 Jun 2025 22:20 Thesis Files PDF - Final Version See Usage Policy. 11MB Repository Staff Only: item control page

COMBINATORIAL INEQUALITIES FOR GEOMETRIC LATTICES Thesis by John Randolph Stonesifer In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology· Pasadena, California 1973 (Submitted May 2, 1973) ii ACKNOWLEDGMENTS I would like to thank God for the help and encouragement He has given me. During unproductive times especially, His assurance that the culmination of my work at Caltech, be it a Ph.D. or M. S. , would be for the best (Rom. 8:28) was invaluable. the inspirations in my research. I attribute to Him In addition I would like to thank my friends, especially those at Knox Presbyterian Church, for their many prayers. Dr. Dilworth has been very helpful as a thesis adviser. His patience and encouragement have meant a great deal to me, and his helpful comments in actually writing this thesis were sorely needed. I also appreciate the financial assistance given me by the U.S. Department of Health, Education, and Welfare through an NDEA Title IV Fellowship; by the California Institute of Technology through research and teaching assistantships; and by the California State Scholarship and Loan Commission. iii ABSTRACT A geometric lattice is a semimodular point lattice L. The i th Whitney number of Lis the number of elements of rank i in L. The logarithmic concavity conjecture states that for any finite geometric lattice L. In a finite nondirected graph without loops or double edges, a set of edges is closed if whenever it contains all but one edge of a cycle, it contains the whole cycle. With set containment as the order relation, the closed sets of such a graph form a geometric lattice. It is shown that any such lattice satisfies the first nontrivial case of the logarithmic concavity conjecture. In fact, This is a best possible result since equality holds for graphs without cycles. The cut-contraction of a geometric lattice L with respect to a modular cut Q of L is the geometric lattice L - T where T ={x E L : x f. Q, 3:q E Q 3 x -< q} . It is shown that any geometric lattice L can be obtained from the Boolean algebra with W1(L) points by means of a sequence of k = W1(L) - dim(L) cut-contractions. iv TABLE OF CONTENTS Page ACKNOWLEDGMENTS ii ABSTRACT . . . iii INTRODUCTION . 1 Chapter 1 EDGE LATTICES OF GRAPHS 6 2 CUT-CONTRACTIONS 29 APPENDIX . . 39 REFERENCES 42 1 INTRODUCTION Many combinatorial problems can be formulated in the framework of a collection (] of subsets of a finite set S, where this collection contains the whole set and is closed under intersections. With set containment as the partial ordering, e is a lattice. For two subsets A, B e e , the meet A /\ B is set intersection, and the join A v Bis the intersection of all subsets in e which contain both A and B. The sys- tems considered in this thesis are of this type with two restrictions: (i) each subset in e can be expressed as the set union of minimal subsets of e , and (ii) for A, P E (;, if P 1 A and Pis minimal in e., then there is no subset B E e properly between A and A v P. The lattice theoretic analog of such a system is called a geometric lattice. It is from the lattice perspective that we shall study some combinatorial problems. Projective planes have been the source of many combinatorial problems. They also provide examples of geometric lattices. The elements of the geometric lattice associated with a projective plane are the null set, the points and lines, and the plane itself. The order relation is set containment. Similarly, the subspaces of a projective geometry form a geometric lattice. In fact, any abstract finite geometry can be represented as a geometric lattice, and vice-versa. Geometric lattices arise naturally in other areas of mathematics. For example, the collection of partitions of a finite set S form a geometric lattice under the partial ordering 111 ~ rr2 if 1r1 is a refinement of ~. 2 This thesis will be concerned primarily with geometric lattices which arise from finite, nondirected graphs. A set S of edges is said to be closed if whenever S contains all but one edge of a cycle, it contains the whole cycle. The collection of closed sets of edges of a graph G forms a geometric lattice which will be denoted by L( G) and will be called the edge lattice of the graph G. A set of numerical invariants of particular combinatorial inter- est are the Whitney numbers Wi of L. Wi is defined as the number of elements of rank i in L. Rota has proposed two important conjectures regarding these Whitney numbers. The first is that they are unimodal, i.e., for i ~ j ~ k, Wj ~ min (Wi' Wk) [7]. The second is that they are logarithmically concave, i.e., w.1 w.1- 1 w.2 1 or W.1- lW.l+ 1 ~ 1 [ 5) . These two conjectures are related. In fact, lattices which are logarithmically concave are unimodal. For suppose L is not unimodal; then there exist i < j < k such that Wj < min (Wi, Wk). W = min i<m<k (W ) , m and let Let n = max (m) W =W m i<m<k w2 Then Wn+l > Wn ~ Wn-l' and W ~ < 1. Hence Lis not n-1 n+l logarithmically concave. If the geometric lattice is a Boolean algebra, then Wi is the 1 binomial coefficient (~ ) . The logarithmic concavity conjecture holds 3 in this case since w.2 i+l W.1- 1W·l+ 1 i l If the geometric lattice is derived from a finite projective plane, then w = 1, w 1 =W 2 and w 3 = 1. These numbers are clearly log0 arithmically concave. The Whitney numbers of the lattice of subspaces of a projective geometry of dimension three or greater are the Gaussian coefficients: where n is the dimension of the lattice, and q is the order of the field used to coordinatize the geometry [ 7] . Hence 2 wi (qn_ 1 )2 ... (qn-9.i-1)2 = _ _ _ __._(q_i__1 ~}~2~·-·-·(~q-i__9_1_-1_}_2_ _ _- - r - - - w.1- 1w.1l + 9 ( n - l) ... (qn -_g i-2) ( n - l) ... (qn -_g i) .9 (q i+f _1 ) ... (qi+f_ qi) (qi-1_ 1) ... (q i-f_ qi-2) = (qn_ i-1) 9 (qn -qi) (qi+l -l) (qi-1) = (9.n-i+ 1 _ l) (qn-1 _l) (qi+l -l) (ql- 1) >1 I . I q 4 Finally, the Whitney numbers of a partition lattice are the Stirling numbers of the second kind. This sequence of numbers has also been shown to be logarithmically concave [ 6] . The following theorem, whose proof is given in the appendix, shows that logarithmic concavity is preserved under direct products . Theorem A.1: Let L 1 and L 2 be logarithmically concave geo- met ric lattices. Then L = L 1 x L 2 is logarithmically concave . Since Birkhoff [1] has proved that any modular geometric lattice is the direct product of projective geometries and a Boolean algebra, the results above show that any modular geometric lattice is logarithmically concave. There are two further results which support these conjectures. A theorem of Greene [4] states that for a geometric lattice L, w1 ~Wm for m * 0, n where n = dim (L). A generalization due to Dowling and Wilson [ 3] asserts that k k I wi ~ ~ w . m-1 i=l for i=l For an arbitrary geometric lattice, only two cases of the logarithmic concavity conjecture have been proved. and i=n-1 where n is the dimension of the lattice. These cases are i=l To prove that this is true for i=l, we observe that each element of rank 2 can be represented r: as the join of two points. Since the join operation is unique, it follows 1 that w2 ) . Hence ~ 5 w2 1 The proof for i=n-1 is the dual of this proof. The main theorem of Chapter I treats the next case of logarithmic concavity, namely i =2. Theorem 1. 7 : For any finite graph G, 2 W 2 (G) (W 1 (G)-1) 3 w 1(G)W 3(G) ~ ~. (W 1(G)-2) ' where W/ G) is the i th Whitney number of L( G). This is a best possible result since equality holds for all graphs without cycles. 6 CHAPTER 1 EDGE LATTICES OF GRAPHS We begin with some definitions. A graph G consists of a set V of vertices and a set E of unordered pairs of vertices called edges. The vertices determining an edge are its endpoints. An edge will be denoted by e or by (v , v 2) where v 1 and v are the endpoints of the edge. 1 2 All graphs will be finite and without loops or double edges, i.e., there is no edge ( v, v) for any v E V, and there is at most one edge of the form (v , v 2) for v 1 , v 2 E V. 1 A subgraph G' of a graph G is a graph whose vertices are vertices of G and whose edges are edges of G such that if (v , v 2) is an 1 edge of G', then v 1 and v 2 are vertices of G' . There is a natural cor- respondence between sets of edges and subgraphs of a graph G. With a set of edges, associate the subgraph whose edges are the edges of the set and whose vertices are the endpoints of the edges in the set. When no confusion exists, a subgraph will be designated by the corresponding set of edges. A path is an ordered set of edges such that any edge of this set has one endpoint in common with the preceding edge and the other endpoint in common with the following edge. either the edges or the vertices. Note that a path P from v 1 to v 2 may be shortened to a path P' from v 1 to v repeated edges. Paths will be denoted by 2 such that P' ::: P and P' has no A cycle is a closed path with no repeated edges. Finally, a set S of edges is said to be closed if whenever S contains all but one edge of a cycle, S contains the whole cycle. 7 Let 81 and 82 be closed sets. If 8 1 n8 2 contains all but one edge of a cycle, then each of 81 and 82 contains the whole cycle, and so 8 1 n 82 contains the whole cycle. Thus the intersection of two closed sets is closed. Now, for an arbitrary set R of edges define the closure of Ras the intersection of all closed sets containing R. This is the smallest closed set containing R, and it will be denoted by cf(R). The following lemma gives an alternate characterization of the closure of a set. Lemma 1.1: Let G be a graph, and let R be a set of edges in G. Let R be the set of edges e such that there is a path Pe~ R from one endpoint of e to the other. Then R = cf.(R). Proof: If e ER, then {e} is a suitable choice for Pe, and hence R ~ R. By the definition of closure, it is clear that R <::_ cf (R). There- fore it is sufficient to prove that R is closed. Let {(v0 , v1), (v 1 , v 2), .. . . , (vn, v 0)} be a cycle such that {(v0 , v 1), ... , (vn-l' v n)} ~ R. Then there exist paths P0 , P 1 , ... , Pn-l such that Pi is a path from vi to vi+l and Pi c;_ R. Now the ordered sequence P 0 , P 1 , ... , Pn-l is a path from v0 to vn, and it is a path in R. Hence (vn, v 0 ) ER, and R is closed. Thus R = c.Q (R). Lemma 1. 2: Let G be a graph, and let 8 be a closed set of edges in G. Given an edge e 0 f. 8, let e E cf (8 U {eJ) - 8. Then there exist paths P 1 , P 2 c 8 such that the ordered sequence e, P 1 , e 0 , P 2 is a cycle in G. 8 Proof: Since e E c.Q(S U {ec)), by Lemma 1. 1 there exists a path P ~ S U {eJ from one endpoint of e to the other with no repeated edges. Since e ,JS, Pct:_ S; this implies e 0 E P . Denote by P 1 that part of P preceding e , and by P2' that part of P following e 0 . This choice 0 for P 1 and P 2 satisfies the lemma. Theorem 1. 3: Let G be a graph. Then L( G), the collection of closed sets of edges of G, is a semimodular point lattice. Proof: With the order relation defined by S ~ T if and only if S ::: T, it is clear that L( G) is a partially ordered set. Also ¢, the empty set, and E, the set of all edges, are both closed. It has been shown that if S and T are closed, then so is S n T. Thus S n T is the greatest lower bound of Sand Tin L(G), i.e., S n T = S /\ T. This is sufficient to show that L(G) is a lattice and hence has a join operation. The smallest closed set containing Sand T has already been denoted by c.Q(S UT). Hence S VT= c.Q(S UT). Sets which consist of a single edge are closed; these are exactly the points of L(G). Since each closed set Sis a set of edges, S is the join of the set of points contained in S. Hence L(G) is a point lattice. To prove semimodularity, first consider the case where S is a closed set and P = {eJ where e 0 i S. If there exists a closed set S' such that S < S' ~ S V P, let e ES' - S. Then e E S v P. By Lemma 1. 2, there is a cycle through e and e 0 with all other edges in S. Using the same cycle, we see that e 0 E S v {e} ~ S'. Hence S v P ~ S', and S-<SVP. 9 Now let S and T be any two closed sets such that S /\ T -< T. Let p be a point in L(G) such that p ~ T but p Is. Then p Is/\ T, and hence (S /\ T) v P = T. We thus have SV T = S V ( (S /\ T) v P) = (S v (S /\ T) ) V P = S V P > S Hence L( G) is semimodular. Since L( G) is a finite semimodular point lattice, it has a well defined rank function which can be characterized in terms of independent sets of edges. Definition: A set A of edges is independent if e ¢. cf (A-{e}) for all e EA. Lemma 1. 4: A is an independent set of edges if and only if A contains no cycles. Proof: If A contains a cycle, let e be an edge of that cycle. Then e E cf (A-{e}), and A is not independent. If A is not independent, let e E A be such that e E cl(A-{e}). By Lemma 1. 1, there is a path P from one endpoint of e to the other such that P ~ A - {e} and P has no repeated edges. Then P U {e} is a cycle in A. Lemma 1. 5: If A is an independent set of edges, then r(cf(A)) = /A /. Proof: Let A = {e 1 , e 2 , ... , en} . By semimodularity <f, -< {el} -< {el} v {e2} -< .•. -< {el} v {e2} v ... v {eJ = cf({e 1 , e 2, ... , en})= cf(A) 10 This chain has length n, so r(c.f (A)) = n = IA I. Corollary 1. 6: If A is a maximal independent subset of S, a closed set, then S = c.f(A) and r(S) = IA I• Now let W/G) represent the i th Whitney number of L(G); that is, W/G) = l{x E L(G) :r(x) =i} j. The main result can be stated as follows. Theorem 1. 7: For any graph G, w2(G) 2 (W 1(G)-1) \V (G)W (G) ~ 2"" • (W (G)-2) 1 1 3 3 It will be shown in the proof that equality holds if G has disconnected edges, i.e., if no two edges of G have a common endpoint. Hence this theorem is a best possible result. Proof: Throughout the proof, G will be some fixed graph. The proof is inductive and is based upon a method for constructing G from a graph G with the same number of edges as G, but with disconnected 0 edges. Pick any vertex of G of degree greater than 1. One by one, separate the edges at this vertex. Continue this process until all vertices are of degree 1. This is G . Reversing the procedure provides a method 0 for constructing G from G . In each step of the reverse process, two 0 vertices of G are identified. Any order of the identifications will pro0 duce G, but the proof will require a special order. Let v be a vertex in G of maximal degree. From among all vertices in G0 which are eventually to be identified to give v, select one and labe 1 it v. One by one, identify the other appropriate vertices with v. When the vertex v is completed, 11 continue this procedure at the vertex in G of next highest degree. Continue in this manner until the graph G is obtained. The following lemma is obvious from this construction, but it is of special importance. Lemma 1. 8: Let H and H' be consecutive graphs in this construction of G. If H' is obtained from H by identifying a vertex v* of degree 1 with the vertex v of degree n, then all other vertices in H are of degree 1 or of degree larger than n. Now let H and H' be any two consecutive graphs in a construction of G from G0 . If we can show (W 1 (G0)-l) (W 1 (G0)-2) and then by repeated application of the second formula, we have W2(G)2 W2(G0)2 W1(G)W3(G) ~ W1(Go)W3(Go) (W 1 (G0)-1) = 2" (W1 (G0 )-2) 3 3 (W 1 (G)-1) = 2" (W 1 (G)-2) and the theorem follows. In order to establish the first formula, consider any set S of edges in G0 . S is trivially closed in G0 since there are no cycles in G0 . Therefore, all sets of edges are closed in G0 , and L(G0) is a Boolean algebra. Hence 12 W2(GO) = c~(Gol) = Wl (Go)(Wl (Go)-1) 2 and W3(Go) = (w W l (Go)(Wl (Go)-l)(Wl (Go)-2) ~(G0)) = 6 But then 2 3 (W 1 ( Go)-1) W2(Go) W1 (Go)W3(Go) = 2 (W1 (Go)-2) In establishing the second formula for the graphs H and H', it 1, will be convenient to set Wi = W/H) and W{_ = Wi (H'). Since W1 = W it will suffice to show, that In order to relate w and w to w2 and w , it is necessary to 3 examine closely the relationship of the closed sets in H to the closed 2 3 sets in H'. Note first that any set S which is closed in H' is also closed in H. For any two edges with a common vertex in H also have this vertex in common in H', and hence any cycle in H is also a cycle in H'. On the other hand, there may be sets which are closed in H but not closed in H' . These sets will be characterized in the next lemma. Let v* denote the vertex of degree 1 in H which is identified with the vertex v in H to give the graph H'. Also let v' be the vertex which, in H, has an edge in common with v*, and let this edge be denoted by e* in both H and H' . 13 Lemma 1. 9: Let S be closed in H. Then Sis not closed in H' if and only if (i) S is covered in L(H) by a set S' which contains a path Pin H from v* to v such that P has no repeated edges and (ii) S does not contain a path in H from v* to v. Proof: Let S be closed in H but not closed in H' . Then there exist an edge e and a cycle C in H' containing e such that e ¢ S and C - { e} c.::_ S. C is not a cycle in H since Sis closed in H and e ¢ S. It follows that e* EC. Hence, in H, C forms a path P from v* to v with no repeated edges. Condition (i) follows by semimodularity since S -< c.fH (S U {e}) in L(H) and P = C c c£H (S U {e}). Assume that S contains a path P' in H from v* to v. Then e * e* and (P-{e}) UP' is a path in H, contained in S, from one endpoint of e to the other. Hence e E c..e.H(S) = S, a contradiction. Thus S does not contain a path in H from v* to v; this is condition (ii). Let S be a closed set in H which satisfies (i) and (ii). and P be the sets guaranteed by (i). Let S' P is a path in H from v* to v with no repeated edges, and S' is a closed set in H such that P <.::_ S' and S -< S'. Assume S is also closed in H'. Since by (ii) P 1-:._ S, and P is a cycle in H', there must be at least two edges of P which are not in S. Let the path P be described by its vertices let (xi' xi+l) be the first edge which is not in S, and let (xj, xj +l) be the last edge which is not in S. Since there are at least two edges of P not in S, (xi,xi+l) -:t (xj,xj+l). Then S'= clH(S U {(xj,xj+l)}) because S-< S' 14 and (xj, xj+l) E S' - S. If (xi' xi+l) = (v*, v'), then (v*, v') t/. S, and (xi,xi+l) = (v*,v') t/. cfH(S U {(xj,xj+l)}) = S' because (v*,v') is not on any cycle in H. This contradicts (x., x.l+ 1) E S', so (x., x.l+ 1) =1= ( v*, v'). 1 1 Now since (xi'~+l) E ciH(S U {(xj,xj+l)}), Lemma 1.2 guarantees that there exist paths P 1 , P 2 ~ S such that the ordered sequence (xi' xi+l), P 1 , (xj, xj+l), P 2 is a cycle in H. If xi is connected to xj by P 1 , then the ordered sequence (:xa,x1 ), ... , (~_ 1 ,xi), P 1 , (xj,xj+l), .. . . ,(~_ 1 ,xn), when appropriately shortened, is a cycle in H' with all but one edge, namely (xj,xj+l), in S. This contradicts the assumption that S is closed in H'. If, on the other hand, xi is connected to xj+l' by P 1 , then the ordered sequence (x0 , x 1), ... , (xi-l, xi), P 1 , (xj+l, xj+ 2), .. . . , (~_ 1 , xn) is a path in S from v* to v. This contradicts (ii). Like- wise the assumption that P 1 is a path from xi+l to xj or xj+l leads to a similar contradiction. Hence S is not closed in H'. If S" is another set which satisfies (i), then by this lemma, both S' and S" are closed in H'. Therefore S, which is the meet of S' and S" in L(H) and also the set intersection of S' and S", is closed in H'. Since this is not true, S' must be unique. It also follows that c.£H' (S) = S'. Lemma 1.10: Let S be a set of edges which is closed in both H and H'. Let r(S) and r' (S) denote the ranks of S in L(H) and L(H'), respectively. Then r' (S) = r(S) or r' (S) = r(S) - 1. Furthermore r(S) = r' (S) if and only if S does not contain a path in H from v* to v. Proof: Let A be a maximal independent subset of S in H. Then IA I = r(S). If S does not contain a path in H from v* to v, then A does 15 not contain a cycle in H' through e*. Since these are the only cycles in H' which are not cycles in H, A does not contain any cycles in H'. Hence A is independent in H'. Since cf H,(A) is clearly S, r' (S) = IA I = r(S). If S does contain a path in H from v* to v, we may choose A such that e* E A. Again, since all cycles in H' either are cycles in H or contain e*, the set A - {e*} does not contain any cycles in H'. Hence A - {e*} is independent in H'. To prove that r' (S) = IA-{e*} I = IA I - 1 = r(S) - 1, it is sufficient to show that cfH,(A - {e*}) = S. Since A - {e*} is independent in H, r(cfH(A-{e*})) = IA-{e*} I= r(S) - 1. S - {e*} is closed in H since no cycle in H contains e*. But A - {e*} ~ S - {e*} and r(S - {e*}) = r(S) - 1 = r(cfH(A - {e*})), so that cfH(A - {e*}) = S - {e*}. Hence since S contains a path in H' from one endpoint of e* to the other, i . e. , I from v to v. The following factors contribute to the relationship of the Wi to i. Some closed sets in H of rank i may remain closed and of the W rank i. Some of these sets may drop to rank i - 1 in L(H'), or they may not be closed in H'. Finally, some closed sets of rank i+ 1 in L(H) may drop to rank i in L(H'). In view of the foregoing discussion, each set of rank i in L(H) which is not closed in H' must be covered, in L(H), by a unique set of rank i + 1 which drops to rank i in L(H'). Conversely, if a set of rank i + 1 in L(H) drops to rank i in L(H'), then any 16 closed set covered by this set in L(H) either is not closed in H' or drops to rank i - 1 in L(H' ) . , Since W 1 and W 1' each represent the number of edges in G, W1 = W 1 and no closed set of rank 2 in L(H) drops to rank 1 in L(H'). Thus there are only two ways to change the number of sets of rank 2: closed sets of rank 3 in L(H) may drop to rank 2 in L(H'), and closed sets of rank 2 in L(H) may be deleted because they are not closed in H'. Let k denote the number of sets of rank 3 in L(H) which drop to rank 2 in L(H'). Now, since subgraphs corresponding to closed sets of rank 2 can only take the forms // /\ and Figure 1 each of the k subgraphs corresponding to these k sets of rank 3 in L(H) must have been isomorphic to Figure 2 in H. Note that each of these k subgraphs contains three subgraphs which correspond to sets of rank 2 in L(H), and none of these sets is closed in H'. Thus 17 Since for each new triangle formed, the number of closed sets of rank 2 1 decreases by two, w 2 = (~ ) - 2t where t is the number of triangles in H. We also need to know how the number of sets of rank 3 is changed. The number of sets of rank 3 in L(H) which drop to rank 2 in L(H') has already been denoted by k. Closed sets of rank 3 in L(H') must cor- respond to subgraphs which are isomorphic to one of the following graphs: /V, 0, Ill [> l [>-' <1> Figure 3 The first three graphs can not be derived from closed sets of rank 4 in L(H) since they have only three edges. However, the five remaining graphs can be derived from closed sets of rank 4 in L(H). There the corresponding subgraphs would have been isomorphic to one of the following: 18 V v* V type 1 I type 2 V v*r~ v'~ type 3 type 4 type 5 Figure 4 Any set which is deleted must be covered by exactly one set corresponding to one of these subgraphs, and the corresponding subgraph must not contain a path from v* to v. The numbers of such sets are 4; 3,3,3,3; 4,4; 5; 5, respectively. As an example, consider the graph of type 3 v*CSZv u Vl V I Figure 5 The four subgraphs of this graph which do not contain a path from v* to v and also correspond to closed sets of rank 3 are ~u v*I ~1 v' Figure 6. and 19 Since each of the k subsets which drop from rank 3 in L(H) to rank 2 in L(H') must correspond to a graph which contains the edge (v*,v') and some edge with v as an endpoint, the k subgraphs form the following configuration: V v* v' Figure 7 Let ai be the number of edges connecting vi to the other vj 's. this is the number of edges of the form (vi, vj). Let Let u 1 , u , ... , um be 2 vertices which have edges in common with some vi and also either v or v' but not both. (If a vertex has edges in common with both v and v', then that vertex is some vi.) Let bi be the number of edges from vi to the u 's, and let k b = ~ L, b.1 i=l Let c be the number of edges which do not occur in Figure 7 and are not counted in a or b. Since c does include the edges (v, ui) and (v', ui), it follows that kc ;,,. b since ui can have at most k edges which contribute to b. Applying Lemma 1. 8 to each vi and summing over i gives 2a + b + c ;,,. k 2 - k. 20 Now let d be the number of sets of type 1. There are b of k type 3, a of type 5 and ( 2 ) - a of type 4. There must be k L (W l -2k-1-ac2bi) = kW l - 2k2 - k-2a - 2b i=l of type 2. Thus the total number of sets of rank 4 in L(H) which drop to rank 3 in L(H') is and the total number of sets of rank 3 in L(H) which are not closed in H' is 2 4(d) + 3(kW 1-2k -k-2a-2b) + 4(b) + 5 ( ( ~) - a) + 5(a) Finally, w3 = W3 - k+( (d) + (kW1-2k2-k-2a-2b) + (b) + (<~) - a)+ (a)) 2 - (4(d) + 3(kW 1-2k -k-2a-2b) + 4(b) + 5((~) - a)+ 5(a)) = W 2 3 - 2kW l + 2k + 3k + 4a + b - 3d Some upper bounds for W will be needed. 3 hypothesis W2 2 3 (W1-l) w1w3 ~ 2 (W1-2) implies The induction 21 (W -2) 1 (W 1 -I) = w 1w 2 3 2W - 2 ---r 4 w 2 (W 1 -2) - 3 W l (W l -1) t • With these estimates, 2 (2 2 1 8 k(W i-2) ~ = W 2 3" kW l - 2k - 3 k- 4a - b + 3" W l (W l -l) (2t + kJ ~ 1 k - 4a - b + 8 W k(2riJ? (2t + k)j ~ W 22 (23" kW l •- 2k2 - 3" 3 l (1) 4 ( 2k-l) (2t k~ -- w 22 ( 23 kW 1- 2k2 -3l k - 4a- b +3 W + 1 i = w 2 (~ k(2k+l+a+b+c) - 2k2 - k- 4a- b + 4 2k-l 2t+k \ 2 (~ v + +a+ +c ij (2) 2 ( 2 2 1 2 2 2 (8k-4)(2t+k) ) = w 2 -3"k +3"k+(3"k-4)a+(3"k-l)b+3"kc+ 3(2k+l+a+b+c) (3) > - W 2 ( 2 k2 1 k ( 2 k 4) ( 2 k l)b 2 k (8k-4 4a+2b+k) 2 - 3" + :r + 3" - a+ 3" + 3" c + + +a+ +c 22 2 (4) = ~~ l ( (-2k2+k+ (2k-12) a+(2k- 3) b+ 2kc )(2k+ 1+a+b+c )+( 8k-4) ( 4a+2b+ k)) From here, the proof must be broken into cases: k ~ 6, k = 0, k = 1 and 2 ~ k ~ 5. Let k ~ 6: If also b+c ~ k+l, then c ~ 1 and by (3), · > w 22 (- 32 k 2 + 31 k+( 32 k-l)(b+c)+c) ~ W = 0 2 2 2 1 2 (- k + k+( k-l)(k+l)+l) 2 3 3 3 If b+c ~ k, then by Lemma 1. 8, the only vertices of degree greater than k are v, v', v , v 2 , ... , vk, and all others are of degree_1. 1 Since any u. must have degree at least 2, there are no u . 's. 1 b = 0. 1 Hence 2 Therefore, b+c ~ k and 2a+b+c ~ k -k reduce to c ~ k and 2 2a+c ~ k -k. 2 2 These imply 2a ~ k -k-c ~ k -2k. 2 inequalities, t ~ 2a and a ~ k -k , (2) becomes 2 Using these W 2W - W 2W . ~ W 2(2 - k 2 + 1 k + ( 2 k - 4) a + ( 2 k - 1) b + 2 kc 2 3 3 3 2 3 3 3 2 3 + >- W 2 ( --- 2 8k-4 2t+k ) k+ +a+ +c 2 2 2 k2 1 k ( 2 k 4 )( k -2k) (8k-4)(2(k -2k)+k)) -3 +3 + 3 2 + 2 3(2k+l+ + k) y w2 2 5 4 2 3 = (k - 5k - 3k - 19k + 50k) 2 3(k +5k+2) >0 for k ~ 6. 23 Let k = 0: Here and W 2 3 = W 3 - 2kW l + 2k + 3k + 4a + b - 3d = W 3 - 3d So Let k = 1: Here a= 0, and by (4) 2 W i 2 w 3 - W 22W i :, 3~~ ( (-2k2+k+ (2k- l 2)a+(2k- 3) b+2kc )(2k+ 1+a+ b+c) +(8k-4)( 4a+2b+k)) w2 = .J 3 1 ((-2+1-b+2c)(3+b+c)+4(2b+l~ w2 = 3W2 2 2 (1+4b+5c-b +bc+2c ) 1 > 0 since c = kc :;?:. bas showed earlier. Let 2 ~ k ~ 5: For these k, use (4) and minimize the factor 2 (-2k +k+(2k-12)a+(2k-3)b+2kc)(2k+l+a+b+c) + (8k-4)(4a+2b+k) with respect to the variable b. 24 in ((-2k2+k+(2k-12)a+(2k-3)b+2kc)(2k+l+a+b+c) + (8k-4)(4a+2b+k)) = 2 (-2k +k+(2k-12)a+(2k-3)b+2kc) + (2k-3)(2k+l+a+b+c) + (16k-8) 2 = 2k + 13k- ll + (4k-15)a+ (4k-6)b+ (4k-3)c ? 2 2k + 13k - 11 + ( 4k- l 5)a >0 for k = 4, 5. Fork= 2, 3, 2 2k + 13k- ll + (4k-15)a 2 2k2 + 13k- ll + (4k-15) (k -k) 2 1 3 2 = (4k -15k +41k-22) ? 2 1 2 2 = i(4k(k-2) +k +25k-22) >0 Thus this factor is minimized at b = 0. Now minimize 2 (-2k +k+(2k-12)a+2kc)(2k+l+a+c) + (8k-4)(4a+k) with respect to the variable c. a~ ((-2k 2+k+(2k-12)a+2kc)(2k+l+a+c) + (8k-4)(4a+k)) 2 = (-2k +k+(2k-12)a+2kc) + 2k(2k+l+a+c) 2 = 2k + 3k+ (4k-12)a+ 4kc ? 0 for k ~ 3. For k = 2 , a = 0 or 1, and 2 2k + 3k + (4k-12)a + 4kc ~ 10 + 8c >0 . 25 2 2 Since 2a+b+c ~ k -k and kc ~ b, it follows that c ~ k 2 2 stituting b = 0 and c = k a into (4) gives k.!f 2a . Sub- k~f W 2W 3 - W 22W 2 3 ;?,: 2 w2 ( 2 3w l (-2k +k+(2k-12)a+(2k-3)b+2kc)(2k+l+a+b+c) + (Bk-4) (4a+2b+k)) w2 2 2 2 t-2k + k+ (2k-12 )a+2k k ~ 3W:1 2 Ji:12a) ( 2k+ l+a+ k k:12a ) + (8k-4)(4a+k)) w22 = - -.....- 2 3(k+l) W l LJ( (-2k2+k+(2k-12)a)(k+l) 2 3 + (2k -2k -4ka~ ((2k+l+a)(k+l) 2 2 + (k -k-2a)) + (8k-4)(4a+k)(k+1) ] = w2 2 2 3(k+l) W l = w2 2 2 3(k+l) W l 2 2 2 (((2k -14k-12)a-3k +k)( (k-l)a+3k +2k+l) 2 2 + ( (32k-16)a+8k -4k)(k +2k+l~ 2 2 2 4 3 3 ((2k -16k +2k+12)a +(6k -9k -10k -39k-28)a 4 3 2 + (-k +9k -k -3k)) . 3 2 4 3 2 Smee 2k - 16k + 2k + 12 < 0 and -k + 9k - 9k - 3k > 0 for 2 ~ k ~ 5, this function of a is a parabola opening downward which is positive at a = 0. Now we choose maximal values of a such that this quadratic is 26 positive. Then it will be positive for all smaller positive values of a. For k = 5, let a = 10. Then w2 2 2 w2 w 3 -w 2 w3 "' ( +l)~(w ) ((2 -125-16. 25+ 2. 5+ 12) .100 3 5 1 +(6·625-9·125-10·25-39·5-28)·10 + (-62 5+9 • 12 5-25-3 • 5)) w2 2 = l08(W1) (7180) > 0 For k = 4, let a = 6. w2 3~ 3(4+1)~ (W ) ((2 • 54-16 • 16+2 •4+ 12) • 36 w3 -w 22w 2 w2 Then 1 +(6·256-9·64-10·16-39·4-28) ·6 +(-256+9·64-16-3·4~ w2 2 = 7o(W1) (100) > o For k = 3, let a = 1. Then 2 W 2W - W22W 3 3 2 W2 ( (2 • 27- 16 • 9 + 2. 3 + 12) ~ 2 3(3+1) (W 1 ) +(6·81-9·27-10-9-39·3-28)+(-81+9·27-9-3·3~ w2 2 = 48(W1) (80) > 0. There are still three cases remaining: k = 3, a = 3; k = 3, a = 2; and k = 2, a = 1. For k = 3 and a = 3, t ~ 7. By (2) 27 ~ w; (-6+1-6+b+2c + ~1~6~3:~/) w2 2 2 2 = 3(lO+b+c) (10+37b+27c+3b +9bc+6c ) >0 . Fork= 3, a= 2, by (4) w 2,2w 3- w 22w 3' ~ w2 2 3W21 ( (-2k +k+(2k-12)a+ (2k-3)b+ 2kc) (2k+l+a+b+c) + (8k-4)(4a+2b+k)) w2 2 = 3W ( (-18+3-12+3b+6c) (9+b+c) + (20)(11+2b)) 1 w2 2 2 2 = 3W (-23+40b+27c+3b +9bc+6c) 1 > 0 since c ~ 1 . For k = 2, a = 1, by (4) 2 w2 ( 2 (-2k +k+(2k-12)a + (2k-3)b + 2kc) (2k+l+a+b+c) 3w l + (8k-4)( 4a+2b+k)) w2 = 3~l ((-8+2-8+b+4c)(6+b+c) + (12)(6+2b)) > 0 if b ~ 1 or c ~ 1 . 28 The case k = 2, a = 1, b = 0, c = 0 is V v*1~V2 v'~ Figure 8 Here W2 = 11, W3 = 7, W 2= 7, W3= 1, so This completes the proof of Theorem 1. 7. 29 CHAPTER II CUT-CONTRACTIONS The previous chapter gave a characterization of the closed sets of H' in terms of closed sets in H. The effect was that of deleting certain elements from L(H) to produce L(H'). In this chapter it will be shown that a generalization of this procedure can be carried out for arbitrary geometric lattices, and that any geometric lattice can be constructed from a Boolean algebra in this way. Some preliminary definitions and a lemma will be needed. Definition: Let x, y be elements of a geometric lattice. Then (x, y) is a modular pair if r(x) + r(y) = r(x v y) + r(x /\ y) [8]. Definition: A modular cut Q of a geometric lattice L is a subset of L such that (i) if x E Q and y ~ x, then y E Q and (ii) if x, y E Q and x >- x A y, then x A y E Q [2]. Lemma 2. 1: If (x, y) is a modular pair in a modular cut Q of a geometric lattice L, then x A y E Q. Proof: Letx AY =:xo-c:: x 1 -< ... -< ~ =x, and let yi =~ v y. By semimodularity, y =Yo-< y 1 ~ ... ~ Yn =xv y, but since n = r(x) - r(x /\ y) = r(x v y) - r(y), we must have y = Yo-< y 1 -< ... -< Yn =xv y. From xi ~ ~+l A yi and Hence r(yj) - r(yi) = j - i = r(xj) - r(~). 30 r(~+l /\ yi) ~ r(xi+l) + r(yi) - r(~+l v yi) = r(xi+l) + r(yi) - r(yi+l) + (r(yi+l) - r(yn)) - (r(xi+l) - r(~)) = r(yi) - r(yn) + r(~) it follows that ~ = xi+l /\ yi for all i. xj i Q. Let xj be maximal such that Then j -:1- n, and xj+l E Q. Since Q is a modular cut, yj E Q and xj = xj+l /\ yj E Q which is a contradiction. Thus~ E Q for all i, and in particular, x /\ y = Xo E Q. Theorem 2. 2: Let L be a geometric lattice, let Q be a modular cut of L and let T = {x E L : x i Q, 3 q E Q 3 x -< q} . Then L - T is a geometric lattice. Before proving the theorem, we shall show that this construction is indeed a generalization of the basic reduction process used in Chapter I for geometric lattices associated with a graph. Let the graph H' be derived from the graph H by identifying two vertices v* and v in H. Let Q = {s E L(H) : 3 a path Pin H from v* to v, Pc;_ s}. Clearly if s1 , s2 E L(H) are such that s1 E Q and s1 ~ s2 , then s2 E Q. Now let s1 , s2 E Q be such that s1 > s1 /\ s2 in L(H). Then s1 /\ s2 E L(H') since s1 , s2 E Q ~ L(H'). But then by Lemma 1. 9, s1 /\ s2 must contain a path in H from v* to v, i.e., s1 A s2 E Q. Thus Q is a modular cut. By Lemma 1. 9 again, the set T corresponding to Q is exactly the collection of closed sets of H which are not closed in H'. Hence L(H) - T is isomorphic to L(H') . 31 The following three lemmas will be useful in proving the theorem. Lemma 2. 3: If x E T and y ~ x, then y e: T U Q . Let q e: Q be such that q > x. If y ~ q, then y e: Q. If y --f- q, then y I\ q = x <: q, and y v q · >y. But y v q e: Q since y v q ~ q. Hence if y i Q, then y E T. Lemma 2. 4: Let x > y > z in L with x E Q, z E L - Q - T. Then y E T, and hence x > z in L - T. Since x > y in L and x E Q, either y E Q or y E T. If y E Q, then z e: Q or z ET. That contradicts z EL - Q - T, soy ET. Since y i L - T for all y such that x > y > z in L, it follows that x >- z in L - T . Lemma 2. 5: If x > z in L - T, then either x > z in L, or there exists y E T such that x >Y > z in L. Let x > z in L - T. If x 'i- z in L, then there exists y E T such that x > y > z in L. Since y € T, x E (L - T) 0 (Q U T) = Q. If y 'i- z in L, then there exists t E T such that x > y >- t > z in L. Let q E Q be such such that q > t. Now q le x since otherwise x > q > z in L - T. Hence t = x /\ q <: q, and t E Q which is impossible. Thus y >- z in L. The proof of Theorem 2. 2 has three steps. It must be shown that L - Tis a lattice, that it is a point lattice, and that it is semimodular. Proof: In order to show that L - T is a lattice, we show that L - T is closed with respect to meet. Let x, y E L - T, and assume that 32 x/\yET. ByLemma2.3, x,yET UQ. Butx,yEL-T, sox,yEQ. Let q E Q be such that x /\ y -< q; such a q exists since x /\ y E T. Either x -:;/ q or y -:;/ q, so without loss of generality, it may be assumed that x /-- q. Then x /\ q = x /\ y <: q. Since Q is a modular cut, x /\ q E Q, and so x /\ y E Q. This contradicts x /\ y E T. An immediate consequence of L - T being closed with respect to meet is that for t E T, there is a unique q E Q such that q >- t. For assume this is not so, and let t ET and q 1 , q 2 E Q be such that q 1 =1= q2 , q >- t and q 2 >- t in L. Then t = q1 /\ q2 <: q 1 ; so t E Q, a contradiction. 1 Since L - T contains the unit element of L and is closed with respect to meet, it follows that L - T is a lattice. join operation in L - T. Let v' denote the Let x, y E L - T. If x v y E L - T, then it is clear that x v y = x v y. If x v y i L - T, i.e. , x v y E T, then there exists a unique q E Q such that x v y <:: q in L. Let z E L - T be such that z >-: x, y. Then q >-: q /\ z >-: x V y. Since q /\ z E L - T and xv y E T, it follows that q = q v z ~ z. Thus q = x v' y. In order to show that L - T is a point lattice, let x E L - T, and let P = { p E L: x >-: p >- O}. Then VP = x since L is a point lattice. There are two cases to consider. First, if O E T, let q E Q be such that q > 0. Then q is the O element of L - T. Since q v x EQ, q v x > x and xi T, it follows that x E Q. But now x >-: q or else 0 = x /\ q <: q E Q and O E Q, a contradiction. Thus x = q v VP =V{p v q: p E P} =V'{p v q :p E P} which is a representation of x as a join of points in L - T. If O E L - T, let P' = {p' E L - T : x >-: p' >- 0 in L - T} . For p E P, if p EL - T, then p E P' and VP'>-: p. If p ET, then there exists 33 q E Q such that q > p in L. By Lemma 2. 4, q > 0 in L - T. By the argument of the preceding paragraph, x? q. Hence q E P' and VP' ? q > p. Since VP' ? p for all p E P, it follows that Vp' ? VP. Thus V"'P' ? VP' ? VP = X? V'P' and hence x =V' P' . Finally it must be shown that L - T is semimodular. Let x ► x I\ y in L - T. Then x > x /\ y in L or there exists t E T such that x ► t ► x I\ y in L by Lemma 2. 5. If x ► x /\ y in L, then x v y > y in L. If in addition xv y E L - T, then xv' y =xv y ► y. Thus we may assume that x v y E T. Then x v' y E Q, and x v' y ► x v y. Since y must be in L - Q - T, Lemma 2. 4 implies that x v' y > y in L - T. On the other hand, if there exists t E T such that x > t > xv yin L, then x E Q, x /\ y f/ Q, xv y E Q and xv' y =xv y. Clearly if x v y ► yin L, then x v' y = x v y > y in L - T. Otherwise, if xv y i- y in L, then there exists z such that x v y > z > y in L, and (x, y) is a modular pair. Since x E Q and x /\ y ¢ Q, it follows that y ¢ Q, i.e., y E L - Q - T. Then by Lemma 2. 4, x v' y > y in L - T. This completes the proof of Theorem 2. 2. Since L - T is a geometric lattice, it has a well defined rank function r'. The following lemma will be useful in characterizing r' in terms of the rank function r on L. Lemma 2.6: Let x,y EL - T be such that x? y. If x,y E Q or x, y E L - Q - T, then x ? z ? y implies z i T. 34 Proof: Assume that there exists z E T such that x ~ z ~ y. Then x > z > y since x,y EL - T. By Lemma 2.3, x E Q and y E L - Q - T. Thus the contrapositive of Lemma 2 . 6 is established. Theorem 2. 7: For x EL - T, r' (x) r(x) if X f- Q { r(x) - 1 if XE Q = Proof: If x f. Q, i. e . , x E L - Q - T, then O E L - Q - T and z EL - T for all z EL such that z ~ x by Lemma 2. 6. Hence any maximal chain in L - T from O to x is a maximal chain in L from O to x. Thus r' (x) = r(x). If x E Q, then let O = x 0 , x 1 , ... , xk = x be a maximal chain in L - T from O to x such that x 0 , ... , xi-l E L - Q - T, and ~' ... ,xk E Q. By Lemma 2.6, x 0 , ... ,xi-land xi' ... ,xk are maximal chains in L. Since x.1 E Q and x.1- 1 ¢ T, there must exist t E T such that~> t > xi-l in L. Lemma 2 . 5 then implies that~> t > xi-l in L. Hence O = Xo, ... ,xi-l' t,~, ... ,xk = x is a maximal chain in L from O to x, and r' (x) = r(x) - 1. The geometric lattice L - T will be called the cut-contraction of L with respect to Q. A cut-contraction L - T of L will be called a trivial cut-contraction of L if T is empty; this occurs if and only if Q is empty or Q = L. The next corollary is an immediate consequence of Theorem 2. 7. 35 Corollary 2. 8: If L' is a nontrivial cut-contraction of L, then dim (L') = dim (L) - 1. Thus by forming cut-contractions, we can produce new, smaller geometric lattices from other geometric lattices. In fact, it will be shown that any geometric lattice can be obtained by means of a sequence of cut-contractions, starting from a suitable Boolean algebra. Every geometric lattice L has a canonical representation in terms of closed subsets of the set of points of L. In this representation, each element x E L is associated with the closed set Sx = {p EL: x ~ p >- O}. The element x /\ y is associated with SXAY = Sx n SY, and the element x v y is associated with Sxv Y = n{sz : Sz ::: Sx and Sz .:?8) . The next theorem will be formulated in terms of this canonical representation. Theorem 2. 9: Let Land L' be geometric lattices. If there exists a one-to-one map from the points of L' onto the points of L such that closed sets in L' correspond to closed sets in L, then L' can be obtained from L by a sequence of k = dim (L) - dim (L') cutcontractions. The hypothesis of Theorem 2. 9 is equivalent to the assumption that there exists a meet preserving embedding of L' into L which maps the points of L' onto the points of L. Proof: First note that for any pair x, y E L' with y ~ x that r(y) - r(x) ~ r' (y) - r' (x). For let x = Xo -< x 1 -< ... -< xm = y be a maximal chain in L'. Then each ~ is closed in L, and they are distinct. Hence x = x 0 < x 1 < ... < xm =yin L, and r(y) - r(x) ~ m = r'(y) - r'(x). 36 Let Q = {x E L' :dim (L) - r(x) = dim(L') - r' (x)}. It will be shown that Q is a modular cut of Land that L' is contained in the cutcontraction of L with respect to Q. In order to show that Q is a modular cut of L, let x E Q, and let y E L be minimal such that y > x and y </ Q. If y E L', then dim(L) - r(y) ~ dim(L') - r' (y) = (dim(L') - r' (x)) - (r' (y) - r' (x)) ~ (dim(L) - r(x)) - (r(y) - r(x)) = dim(L) - r(y). If y i L', then let Hence dim(L) - r(y) = dim(L') - r' (y), and y E Q. y >- z ~ x in L. By the minimality of y, z E Q. (and in L') such that y = z v p. Let p be a point in L Butz v' pis a closed set in L', and hence z v' p is closed in L such that z v' p ~ z v p = y. By semi- modularity in L', r' (z v' p) = r' (z) + 1. Then r(z v' p) = dim(L) - dim(L') + r'(z v' p) = dim(L) - (dim(L') - r'(z)) + 1 = dim(L) - (dim(L) - r(z)) + 1 = r(z) + 1 = r(y) Hence y = z v' p, and y E L', a contradiction. Thus x E Q, y E L and y ~ X imply y E Q. Since x /\ y corresponds to the intersection of the sets oJ points contained in x and y, x /\ y = X/\ 1 y. Let x,y E Q be such that 37 x >- x /\yin L. Then since 1 = r(x) - r(x /\ y) ? r'(x) - r'(x /\ y) ? 1, it follows that r(x) - r(x /\ y) = r'(x) - r' (x /\ y) and dim(L) - r(x /\ y) = (dim(L) - r(x) ) + (r(x) - r(x /\ y)) = (dim(L') - r'(x)) + (r'(x) - r'(x /\ y)) = dim(L') - r' (x /\ y) Hence x /\ y E Q, and Q is a modular cut. If dim(L) = dim(L'), then O E Q, and L - T is a trivial cut- contraction of L. All closed sets of L are in Q, and hence they are closed in L'. Thus L and L' have the same closed sets. Since L and L' have the same order relation, they are isomorphic. If dim(L) > dim(L'), then O i Q. However, the unit element of L is in Q, so L - T is a nontrivial cut-contraction of L. Then by Corollary 2. 8, dim(L) = dim(L - T) + 1. Let L 1 = L - T denote the cut-contraction of L with respect to Q. By Theorem 2. 2, L 1 is a geometric lattice. There is an induced map of points of L to the points of L 1 . In order to see that all closed sets in L' are closed in L 1 , let t E L, q E Q be such that t i. Q and t -< q in L. If t were closed in L', then t -< q in L' and dim(L) - r(t) = dim(L) - r(q) - 1 = dim(L') - r'(q) - 1 = dim(L') - r'(t). Hence t E Q, a contradiction. Thus closed sets in L' are closed in L 1 ; in particular, each point in L' is a point in L 1 . To see that the induced map from the points of L' to the points of L 1 is onto, let q be a point of L which does not correspond to a 38 point in L'. Then q does not correspond to a point in L. By Lemma 2. 5, with x = q and z = 0, there exists an element y E T such that q > y > 0 in L. But y is a point in L, and hence is a point in L 1 . This contradicts y E T. Thus all points in L 1 correspond to points in L', i.e. , the induced map from points of L' to points of L 1 is onto. The previous paragraph showed that it is one-to-one. Hence L 1 and L' satisfy the conditions of the theorem. Repeating this construction k times, where k = dim(L) - dim(L'), gives the sequence of cut-contractions As shown above, the lattices Lk and L' satisfy the conditions of the theorem, and dim(Lk) = dim(L) - k = dim(L'). It follows that Lk and L' are isomorphic. This completes the proof of Theorem 2. 9. If L' is an arbitrary geometric lattice, let L be the Boolean algebra of all subsets of the set of points of L'. Then L and L' satisfy the conditions of Theorem 2. 9. Thus we get the following corollary. Corollary 2.10: Let L be a geometric lattice with w1 points, and let B be the Boolean algebra having W1 points. Then L can be obtained from B by a sequence of k = w1 - dim(L) cut-contractions. 39 APPENDIX Theorem A. l: metric lattices. Let L 1 and L 2 be logarithmically concave geo- Then L = L 1 x L 2 is logarithmically concave also. Proof : Let Ui, Vi and Wi be the Whitney numbers of L 1 , L 2 and L, respectively. Then i w.1 = l u.v . . J 1-J j =() and 2 W.1 -W.1- 1w.1+ l i i i-1 i+l = \"' \"' U.J ukv.1- J. V.1- k - \"' \"' U.J ukv 1. l - J.V.1+ l - k Li L, L, Li j =0 k =O j =0 k =0 i = i-1 i "Li u.ukv •• v.1- k 1 J 1-J 0 v.1- k + "L, "L u.ukv k=O j=O k=O i-1 i-1 i - "L u.u. v. .v - "Li "Li u.ukv . .v. k J 1+ 1 1- 1 -J 0 J 1- 1 -J 1+ 1 j=O j=O k=O i i-1 = u.1 UoVoV·1 + \' u 1. UkVoV·1- k + \' U-UoV· .v. L, L· J 1-J 1 k=l j =O 40 i-1 + i-1 j I uj uj+l v i-j vi-j-1 + I I uj ukvi-j vi-k j =O j =1 k=l + i-2 i ~ I: j =0 k =j+2 i-1 u.ukv . . v.1- k J 1-J i-1 - 'Li°' u.u. 1V- l -J-Vo - 'Li °' U-UoVl -J.v. l ] ] 1+ j=O 1- 1- 1+ j=O i-1 - '°' U.U. v. l .v . . J J+ 1 1- - J 1- J L1 j=O i-1 j i-2 i - "L, "Li u J. ukv.1- 1-J•V.1+ 1 - k - "L , "L u.Jukv.1- 1 -J.V.1+ 1 - k j =1 k=l j =0 k =j+2 i-1 i-1 ) + "L u.u . . v.1 - "L u.u J 0 v 1-J J 0 v.1- 1 -J.v.1+ 1 ( j=O j =O ·-1 + ( -~ i-1 ) u .u . v . . v. . u .u. v. .v . . J J+l 1-J 1-J-l j~O J J+l 1-l-J 1-J . 41 i = L (ukuCuk-lui+l)vOvi-k k=l i-1 + '\'. u U.(V . . V.-V . . v. ) + 0 0 J 1-J 1 1-J- 1 l+ 1 l., j=O i-1 j + \' '\' U.Uk(V . . V. k-V . . v. k ) Li Li J 1-J 11-J- 1 1- + 1 j=l k=l i-2 + i-1 ~ i I: \' . . v.1- k-v 1-J. . 1V-1- k + 1) L u J.uk(V1-J j =O k=j+2 i-1 \ \' U U (V. V. -V. v. 1) lJ Li n m 1-n 1-m 1-n- 1 1-m+ m=l n=m i-1 i-1 + '\', '\' U u (V. v. - V. V. ) D Li m- 1 n+ 1 1-m+ 1 1-n- 1 1-m 1-n m=l n=m i-1 = i-1 L; L (Um Un-Um-1 un+l)(Vi-n Vi-m-Vi-n-1 Vi-m+l) m=l n=m since ukuj - uk-l uj+l ~ k ~ j. o fork ~ j,and vk vj - vk-l vj+l ~ o for 42 REFERENCES 1. Birkhoff , Garrett, Lattice Theory, 3rd ed., Amer . Math. Soc. Colloq. Publ., XXV, Amer. Math. Soc., Providence, Rhode Island , 1967. 2. Crapo, H. H., and Rota, G.-C., On the Foundations of Combinatorial Theory: Combinatorial Geometries (preliminary edition), M.I.T. Press, Cambridge, Massachusetts , 1970. 3. Dowling , T . A., and Wilson, R. M., A Whitney number inequality for geometric lattices, to appear. 4. Greene, C., A rank inequality for finite geometric lattices, J. Combinatorial Theory, 9 (1970), 357-364 . 5. Harper, L. H., The morphology of geometric lattices, unpublished. 6. Leib, E. H., Concavity properties and a generating function for Stirling numbers, J. Combinatorial Theory, 5 (1968), 203-207. 7. Rota, G.-C., and Harper, L. H., Matching theory, an introduction, Advances in Probability, 1, Marcel Dekker, Inc., New York, New York, 1971 , 169-215. 8. Wilcox, L. R . , Modularity in the theory of lattices, Annals of Math., 40 (1939), 490-505 .