Combinatorial Properties of Finite Geometric Lattices Citation Greene, Curtis (1969) Combinatorial Properties of Finite Geometric Lattices. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/0VKW-5375. https://resolver.caltech.edu/CaltechTHESIS:02222016-103219152 Abstract Let L be a finite geometric lattice of dimension n, and let w(k) denote the number of elements in L of rank k. Two theorems about the numbers w(k) are proved: first, w(k) ≥ w(1) for k = 2, 3, ..., n-1. Second, w(k) = w(1) if and only if k = n-1 and L is modular. Several corollaries concerning the "matching" of points and dual points are derived from these theorems. Both theorems can be regarded as a generalization of a theorem of de Bruijn and Erdös concerning ʎ= 1 designs. The second can also be considered as the converse to a special case of Dilworth's theorem on finite modular lattices. These results are related to two conjectures due to G. -C. Rota. The "unimodality" conjecture states that the w(k)'s form a unimodal sequence. The "Sperner" conjecture states that a set of non-comparable elements in L has cardinality at most max/k {w(k)}. In this thesis, a counterexample to the Sperner conjecture is exhibited. 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: 7 April 1969 Funders: Funding Agency Grant Number NSF UNSPECIFIED Caltech UNSPECIFIED Record Number: CaltechTHESIS:02222016-103219152 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:02222016-103219152 DOI: 10.7907/0VKW-5375 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 9572 Collection: CaltechTHESIS Deposited By: INVALID USER Deposited On: 22 Feb 2016 21:55 Last Modified: 29 Apr 2024 21:11 Thesis Files Preview PDF - Final Version See Usage Policy. 734kB Repository Staff Only: item control page

COMBINATORIAL PROPER TIES OF FINITE GEOMETRIC LA TT ICES Thesis by Curtis Greene In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1969 (Submitted April 7, 1969) (ii) ACKNOWLEDGEMENTS I am greatly indebted to Professor R. P. Dilworth, whose advice and assistance have been invaluable. His patience and interest in my work have meant a great deal to me. I wish also to express my thanks to the National Science Foundation for its support of my graduate career, and to the California Institute of Technology for providing me with a teaching assistantship for the past two years. To my wife, Betsy, I am eternally grapefruit. (iii) ABSTRACT Let L be a finite geometric lattice of dimension n, and let w(k) denote the number of elements in L of rank k. Two theorems about the numbers w(k) are proved: first, w(k) "2'.: w( 1) for k = 2, 3, ... ,n-1. Second, w(k) = w( 1) if and only if k = n-1 and L is modular. Several corollaries concerning the "matching" of points and dual points are derived from these theorems. Both theorems can be regarded as a generalization of a theorem of de Bruijn and Erdtls concerning >-. = 1 designs. The second can also be considered as the converse to a special case of Dilworth' s theorem on finite modular lattices. These results are related to two conjectures due to G. -C. Rota. The 11 unimodality" conjecture states that the w(k)'s form a unimodal sequence. The "Sperner" conjecture states that a set of non-com- parable elements in L has cardinality at most max ( w(k)} • k this thesis, a counterexample to the Sperner conjecture is exhibited. In (iv) TABLE OF CONTENTS I INTRODUCTION ................... o • • • • • • • • • • • • • • • o • • • 1 II DEFINITIONS AND PRELIMINARIES •••••.••••••••••••• 5 III COUNTEREXAMPLE TO THE SPERNER CONJECTURE. o .9 IV A RANK INEQUALITY, AND APPLICATIONS ..•.••.••••. 12 V EQUALITY . . . . . . . . . . . . . . . . . o • • • • • • • • • • • • • • o • • • • • • • • • 19 VI GEOMETRIC LATTICES OF DIMENSION 3 .••••••••••••• 24 REFERENCES . . o • o • o . o • • • • • • • o • • • • • • • • • o • • • • • • • • • • • • • 26 ( 1) I. INTRODUCTION Many combinatorial problems find a natural setting in the theory of finite geometric lattices. By specializing in various direc- tions, one can apply the theory to such diverse subjects as graph coloring, network flows, partitions, finite geometries, matching theory, and Boolean algebras (see [ 5], [ 17] ). Recently, there has been considerable interest in combinatorial problems involving finite geometric lattices as a general class. This thesis is devoted to several of these problems. The principal motivation for this work has come from two conjectures which apparently were first made by G. -C. Rota. The "Unimodality-Conjecture": Let L be a finite geometric lattice, and let w(k) denote the number of elements in L of rank k. The conjecture asserts that w(k) > {w( i), w(j)} for any i and j such that i ~ k < j. In other words, there exists an integer m such that the first m values of w(k) are nondecreasing and the succeeding values are nonincreasing. The "Sperner" Conjecture: Let L be a finite geometric lattice, and let SC L be a set of pairwise non-comparable elements. Then the conjecture asserts that ISi < max Cw(k)}. k (This conjecture derives from a theorem of E. Sperner [ 20] which states the same result for Boolean algebras.) The unimodality conjecture can be immediately verified for projective geometries and Boolean algebras by means of explicit formulas for w(k). It can also be shown that unimodality is preserved (2) under direct products, and the unimodal property thus holds for all finite, complemented, modular lattices, by the Birkhoff - Menger decomposition theorem [ 2, Ch. 4]. In the case of partition lattices, where the w(k}'s are Stirling numbers of the second kind, the unimodal property has been verified by L. H. Harper [ 11]. The Sperner conjecture is known to be valid for several classes of geometric lattices in addition to Boolean algebras. Recent work by L. H. Harper [ 12] shows that geometric lattices having a "normalized matching property" 1 also have both the Sperner property and. the unimodal property. A theorem of Harper arid R. L. Graham [ 8] shows that this category includes projective and affine geometries and, more generally, any geometric lattice which can be represented as a direct product of lattices which are "regular" (i.e., elements of the same rank cover and are covered by the same number of elements}. By extending a proof of Sperner's Theorem due to Lubell [ 13], K. Baker has shown that 11 regularity 11 alone is sufficient even if the structure is not a lattice: any finite, 11 regular, 11 graded partially ordered set satisfies the conclusion of Sperner's Theorem [ l]. Unfortunately, an example constructed by R. P. Dilworth shows 1. This property_.,is the following: if S C L consists of elements of rank k, and s··- denotes the set of elements of rank k+ 1 covering some element of S, then IS I < w(k) w(k+ 1) (3) that not every geometric lattice has Harper's "normalized matching property, 11 and, hence, that this approach cannot be used to resolve either conjecture in its full generality. This thesis cons is ts· of several results of a general nature which relate to.both of the conjectures discussed above. In Chapter 3, we show that the Sperner conjecture is, in general, false. In Chapter 4, we prove the following theorem: Theorem 1: Let L be a finite geometric lattice of dimension n> 1. Then w( 1) < w{k) fork= 2, 3, ... , n-1. This theorem trivially verifies the unimodality conjecture for geometric lattices of dimension 4, and, by specialization to various sublattices, provides a large number of inequalities which must hold in any geometric lattice. We also obtain several matching theorems which are, in turn, closely related to the Sperner property. In Chapter 5, we prove Theorem 2: Let L be a finite geometric lattice of dimension n > 1. Then w( 1) = w(k) if and only if k = n-1 and L is modular. The "if" part of this theorem is a special case of a theorem of Dilworth [ 6]: in any finite, modular lattice, the number of elements covering precisely k elements is equal to the number of elements cove:t-ed by precisely k elements. In particular (k = 1 ), the .number of join-irreducibles is equal to the number of meet-irreducibles. Our Theorem 2 can be regarded as a converse to this theorem in the geometric case. In Chapter 6, we discuss briefly the connection between Theorems 1 and 2 and the well-known theorem of de Bruijn and Erd8s [ 4] which (4) classifies all.\= 1 designs (c.£. Ryser [19]). Our results are in fact precisely equivalent to the de Bruijn - Erd8s theorem if one takes L to be a geometric lattice of dimension 3. (5) II. DEFINITIONS AND PRELIMINARIES In all that follows, we will concern ours elves only with finite lattices. If x and y are elements of a lattice, with x > y, and x > z > y implies x = z, we say that x covers y and write xr y. Elements which cover 0 (the null element) are called points, and elements covered by 1 (the unit element) are called dual points. A lattice in which every element is the join of the points it contains is called a point lattice . A lattice whose dual is a point lattice is called a dual point lattice. A lattice is semimodular if x v y covers x whenever y covers x /\. y. Equivalently, a lattice is semi- modular if x v y covers x and y whenever x and y cover x /\. y. A lattice Lis modular if and only if both Land its dual are semimodular. A geometric lattice is a s emimodular point lattice. If L is geometric, then there exists a unique rank function r on L with the property that r(O) = 0, r(x) = r(y) + 1 if x >- y, and r(x v y) < r(x) + r(y) - r(x /\. y) for all x, yin L. The dimension of L is defined to be the rank of the unit element 1. Every geometric lattice is both a point and a dual point lattice. If L is geometric, then so is every interval sublattice x/y in L. For a general discussion of these and other properties, see [2, Ch. 4]. We will make use of the following notation: PL =the set of points of L D L = the set of dual points in L r( L) = the dim ens ion of L w(k) = the number of elements of rank k in L ( 6) a(x) = the number of elements covered by x f3(x) = the number of elements covering x a*(x) = the number of points contained in x f3':'(x) = the number of dual points containing x. There are many different axiom schemes which are equivalent to the above definition of a geometric lattice. These can be expressed in terms of either lattices or abstract 11 geometric" structures. One of the simplest and most useful is based on the idea of a closure operator with the exchange property. A closure operator on a set S C(X} ~ X, (ii} X ~ Y ==:::> 8 8 is a map C: 2 - - 2 satisfying (i} C(X} ~ C(Y}, and (iii} CC(X) is closed if C(X} = X. We say that Chas the exchange property if, = C(X), for all X, Y C S. A subset X whenever X is a closed subset of S and p and q are elements of S, we have p € C(X U (q}} and p ¢ X =:::;> q € C(X U (p}). It can be shown (see [ 14], [3]} that the closed sets of any closure operator with the exchange property form a geometric lattice. Conversely, any geometric lattice yields such a closure operator on its set of points if one defines C(X} = { p I p < V X} • One of the simplest examples of a class of geometric lattices which is, in general, non-modular is given by the following: Lemma 2.1 (Whitney [21]-Birkhoff [3]}: Let G = (V,E} be a finite, non-oriented graph with vertex set V and edge set,E. Define a closure operator on E as follows: if X C E, then C(X) consists of all edges whose endpoints are vertices connected by a sequence of (7) edges in X. Then Chas the exchange property, and the C-closed subsets of E form a geometric lattice. This lattice is sometimes called the bond-lattice of G. The rank function is given by the formula r(X) =("vi - TJ (X), where ry(X) is the number of components of the subgraph of G determined by the edges in X. When G is the complete graph on its vertices (i.e. , E consists of all pairs of vertices in V), the bond-lattice of G is isomorphic to the lattice of partitions of V. In general, the bond-lattice of a graph can be regarded as the lattice of "admissible" partitions of its vertices - - those partitions whose blocks determine connected subgraphs of G. We will return to this example in Chapter 3. We continue now with a number of elementary lemmas. The first three are standard and well-known (see [ 2, Ch. 4] ). Lemma 2. 2: Let L be a finite geometric lattice, and let SC PL. Let L>:<(S) denote the set of all joins of subsets of S. Then L>:<(S) is a geometric lattice. Proof: Since L>:'(S) is closed under joins, it is a lattice, and every element is clearly the join of the points it contains. Semimodularity follows from the fact that coverings in L':'(S) are coverings in L. Lemma 2. 3: Let L be a finite geometric lattice of dimension n, and let k :S n. Denote by Lk the result of identifying all elements in L of rank > k. Then Lk is a geometric lattice. Proof: All properties follow immediately from the conditions on L. ( 8) Lemma 2;. 4: Let L be a finite s emimodular lattice. Let p £ PL and d £ DL with p </. d. Then the map x -+- x v p is an injection from d/O ~ 1 /p which takes points of d/O to points of 1 /p and dual points '!.!:.._d/O to dual points of 1 /p. Proof: Let x, y £ d/O, and suppose xv p = y v p = z. Then r(x) = r(y) = r(z) - 1, and xv y < z. If x :f. y, it follows that xv y = z, which implies that z £ d/O. But then d > z > p, a contradiction. Hence x = y, and the map is injective. A rank argument shows that the map preserves points and dual points. Lemma 2. 5: Let L be a finite s emimodular lattice. Let p E PL and d E DL with p 1.. d. Then a(d) < j3':<(p) and a':<(d} < /3(p). Proof: The inequalities follow immediately from Lemma 2. 4. Lemma 2. 6: Let L be a finite dual point lattice, and let x be an element of L with r(x) > 0. For any set S of elements covered by x, let S':< be the set of dual points which contain some element of S. Then Is I< Js':<J - w::(x) < !DL I - j3':<(x). In particular, we have a(x} < lDd - /3':<(x}. Proof: For each y ES, pick dy E DL such that y = x /\ dy" (This can be done since every element is the meet of the dual points which contain it.) The dy' s must be distinct elements of S':<. Since none contains x, the inequalities follow. (9) III. COUNTEREXAMPLE TO THE SPERNER CONJECTURE In this chapter, we describe an infinite class of geometric lattices which do not have the Sperner property. These lattices were originally constructed, in a different form, by R. P. Dilworth in order to illustrate another property. 1 We describe them below as bond-lattices of a class of graphs. The smallest counterexample which we exhibit contains 60, 073 elements. Consider the following graph G : n a b Let L(Gn) denote the bond-lattice of Gn· By the remarks in Chapter 2, L(Gn) is a geometric lattice of dimension n+ 1. If e 0 denotes the edge with vertices a and b, and X is a closed set of edges containing e , then r(X) 0 <::(==::::::)} (a, i) € X Hence the interval 1 /e 0 = <!XI + 1) /2 and we have (b, i) € X. in L(Gn) is isomorphic to the Boolean algebra of subsets of [l, 2, ..• , n} . If k < n+ 1, then the number of elements in L(Gn) of rank k containing e 0 is precisely (k~ ). 1 If X is a closed subs et of edges not containing e , then r(X) = IXI 0 and we have (a, i) € X ~ (b, i) d X 1 and (b, i) € X =::) (a, i) fl X. • They can be used to construct examples of nonisomorphic pairs of geometric lattices having the same structure above rank 1. { 1 O) Thus sets of this type having rank k are determined by k-subsets of the vertices [l, 2, ••• , n} together with a function which assigns either a or b to each vertex. Hence the number of elements in L{G ) n of rank k which do not contain e 0 is 2k(~), and we have the formula n ) + 2 k(nk). w (k) = ( k-1 Let L be any geometric lattice, and suppose that w(k m ) =max w(k). k If p € PL' let wp(i) denote the number of elements in L of rank i which contain p, and suppose that Then the Sperner property cannot hold in L. For, if R(i) denotes the set of elements in L of rank i, and S(i) denotes the set of elements of rank i containing p, then S(k -1) U (R(k ) - S(k ) ) is a nonm m m comparable set, and I S(km -1) U I (R(~) - S(km)) = w p(km -1) + w(km) - w p(km) which is strictly greater than w(~). We now observe that, for sufficiently large values of n, this situation occurs in the bondlattices L(Gn). From the formula for w(k) we obtain the relation (>!•) w(k) -w(k-1) = n~ (k-l)!(n-k+l)! [ 2 k-1 (2n-3k+ 2) k + (n-2k+ 3) · (n - k + 2) J• One can see intuitively from this expression that the w(k)'s increase until k is approximately 2n/3. On the other hand, we have which decreases strictly for k> n/2 + 1. To make this argument ( 11) precise, it suffices to show that w(k) > w(k-1) for k < k k 0 = n/2 + 2 if n is even and k follow that k 0 0 , where = (n+ 1) /2 + 2 if :n is odd. It will then > k 0 , and hence w eo(km -1) > w eo(km). m- Analysis of formula (>:<) shows that this is true provided that n > 10 if n is even and n > 13 if n is odd. {The argument fails for n< 10 and n = 11.) Hence the analog of Sperner's Theorem fails for the lattices L(G ) n when n = 10 and for all n > 12. For L{G 10 ) we have the following table: k w(k) 0 1 1 21 2 190 3 1005 4 3480 5 8274 6 13692 7 15570 8 11640 9 5165 10 1034 11 1 For this example we have IS{km-1) U (R(~)-S{km))f = 15570 - 210 + 252 = 15612 > 15570. ( 12} IV. A RANK INEQUALITY, AND APPLICATIONS It follows from Lemma 2. 3 that any theorem about points and elements of a fixed rank> 0 in a geometric lattice can be reduced to a statement about points and dual points. Such is the case with the main theorem of this chapter: Theorem 1: Let L be a finite geometric lattice of dimension n> 1. Thenw(l}<w(k}fork=2, 3, ... ,n-1. Proof: By Lemma 2. 3, it suffices to prove the single inequality w( 1) < w(n-1 ). The main tool is the P. Hall Theorem on distinct representatives of sets, and the proof is by induction on the dimen.sion of L. The theorem holds trivially for all lattices L with r{L) < 2. We now suppose that Lis a geometric lattice of dimension n, and that the theorem holds for all lattices of smaller dimension. The inductive assumption implies that Theorem 1 is true for all proper quotients of L. In particular, we have a( d) >a':'( d) for all de DL' and J3':'(p) > J3(p) for all p e PL. Furthermore, a>:'(d} <a(d) <J3':'(p) whenever p $ d, by Lemma 2. 5. Let S be any subset of PL with JsJ <(nLI. We show that there exists an injection f: S--+DL with the property that f(p) ~ p for all p e S. For each p e S, let T(p} = [de DL j d ~ p} , and let p , p , •.. , pk be k points in S. If U is the union of the sets T(pi)' 1 2 i=l, 2, ... ,k, thenitisevidentthatU=[deDL1d~u}, where u = p1 v p 2 v ... v pk. element of L, then Thus fu I = (nL J - J3>:'(u). If u = 1 , the unit ju I = JnLI > fsr > k. If u < 1, then juf = JnLJ - J3 >:'(u) > a(u) by Lemma. 2. 6, and a{u) > a>:'(u) by the ( 13) inductive assumption. Thus inu. Hence Ju) > c/:<(u) > k, since each pi is contained fu( >kin any case, andthe sets T(p), p€ S, have a system of distinct representatives. This gives the desired function f. Suppose now that IPL( >(DLI. JS f = Let S be any subset of PL with In LI, and let f: S - DL be a bijection with f(p) ";t. p for all p € S. Since a>:<(f(p)) < /3':<(p) , we have Since there are points in PL which are not in S, it follows that which is impossible, since both sums give the total number of "lines" in the partially ordered set of points and dual points. Thus IPL'< lnLj and the theorem follows by induction. We remark at this point that Theorem 1 is related to a settheoretic result of T. Motzkin ( [ 16], p. 463, Lemma 4. 5): if k subsets of an n-element set have the property that for every set S and point p IS, p is contained in at least }s) other sets, then (except for certain trivial cases) k > n. We could use this result to prove Theorem 1 immediately after establishing the relation a>!<(d} < f3>!<(p) for p 1. d. However, the method used above illustrates techniques which will be used to obtain many of the results which follow. The author is indebted to H. J. Ryser for clarifying certain aspects of (14) the Motzkin result. The following "matching" theorem is an immediate corollary to the above proof. Corollary 4. 1: Let L be a finite geometric lattice. Then there exists an injection f: PL-+ DL with the property that f(p) '-::/ p for all p €PL. The next result also follows from Theorem 1: Corollary 4. 2: Let L be a finite geometric lattice. Then there exists an injection g: PL-+ DL with the property that g(p) > p for Proof: We proceed by induction on the size of L, and show that the sets S(p) = [dEDLl d> p}, for p€PL' have a system of distinct representatives. Let p , p , ••• , pk be k points of L, and 1 2 let U be the set of dual points containing some p.. l U If k = w( 1), then = DL and (u I > jPLI > k by Theorem 1. If k < w( 1), let p 0 be any point not equal to p , p , 1 2 ... ' pk' and let L.,.·'· be the geometric lattice obtained by taking the joins of all subsets of points other than p 0 (see Lemma 2. 2). If r(L':<) = r(L}, then it is clear that ju!> jun L':<j > k, by the inductive assumption. If r(L':<) < r(L), it can easily be shown that L is the direct product of L':< and a two-element chain. In this case, the inductive assumption shows that p 1 , Pz, ••. , pk are contained in at least k dual points of L >!<, which are mapped into dis tin ct dual points of L under the map x-+ x v p • 0 Thus !uj > kin any case, and the funct~on g is given by a system of distinct representatives for the sets S(p}, p € PL. ( 15} By modifying the argument used in Theorem 1, and by applying Corollary 4. 2, we obtain the following stronger version of Corollary 4. I. Corollary 4. 3: Let L be a finite geometric lattice, and let s c PL with Is I> 1. Let s':< c DL denote the set of dual points which contain some point in S. Then there exists an injection f: S with the property that f(p) i s':< p for all p € S. Proof: As in the proof of Theorem 1, we show that the sets T(p) = (d € s':< Id -:f p} ' p E S, have a system of distinct representatives. Let p , p , ... , pk be k points in S, let u = p v 1 2 1 ... v pk' and let Ube the union of the sets T(p.}. As before, if u = 1, then l u = s':< and we have fu then lul I Js':'I > k' applying Corollary 4. 2. = = js':'j - /3':'(u), since every dual point > u If u < 1, is contained ins>:•. Suppose that r(u} > I. If R denotes the set of elements covered by u which dominate an element of S, then Lemma 2. 6 shows that jR I < f8':'1 - /3':'(u}. But k < JR j, by Corollary 4. 2. Hence k < js':•j - /3':'(u) lu I . = To satisfy the conditions for an SDR, it remains to show that when k = 1 - - that is, if IT(p)j juf > k I IT(p) > 1 for every p € S. This can fail only = 0, which says that 8':< = (d € DL j d-> p} . But S must contain another point q f: p, by hypothesis, and hence which implies that q > p, since L is a dual point lattice. This contradiction completes the proof. ( 16} Matching properties such as the one given by Corollary 4. 2 are closely related to the Sperner property, as the following result shows. Corollary 4. 4: that X (x C Let L be a finite geometric lattice, and suppose PL U DL is a set of non-comparable elements. Then I< IDLI . In particular, the Sperner property holds for geometric lattices of dimension 3. Proof: It is a standard result in the theory of bipartite graphs that such a property holds whenever a "matching" exists. The argument is as follows: let XD = X n DL' and Xp = X n PL. Then txp1 < jnL - XDr, by Corollary 4. 2, since the set of dual points which contain an element of Xp is disjoint from XD. Hence jx I = lxnl + jxpl < In the case when r(L} = 3, jxnl + PL - xnl = jnL I· Theorem 1 shows that jnLj =max (w(k}}, k and the Sperner property follows. Thus the Sperner conjecture is true if we restrict our attention to points and dual points. The next corollary shows that noncomparable sets of maximum size ( jnLj} are essentially unique. Corollary 4. 5: Let L be a finite geometric lattice, and let X c PL U DL be a non-comparable set with jx I = lnLj. Then x = DL ~(if jPLI = jnLI > x = PL. Proof: The result is trivial if r(L} < 2, so we may assume that r(L} > 2. Let xp = x we have n PL' and XD = x n DL. Since 1x1 = IDLI , jx~ = jnL - XDJ , from the proof of Corollary 4. 4. Denote by X~ the set of dual points containing elements of Xp. Since ( 17) 1x;1 ~ fxp( (by Corollary 4. 2), and since x ; n XD is empty, we must have x ; = DL - XD, and thus 1x;1 = lDL - Xnl = (xp(· We cannot have (xpj = 1 , since then l Ix~ = 1, contrary to the fact that every point is contained in at least two dual points. we are done, since then X = XD = DL. If lxp (= 0, Thus it remains to show that jxpl > 1 implies X =PL. In this case, we can apply Corollary 4. 3 and obtain an injection f: Xp--+ DL - XD such that f(p) =f=. p for all pin xp. Since jxp( = IDL - xn1' f must be surjective. We also have a>:'(f(p)) :::; W:<cp) for all p in XP' as in the proof of Theorem 1, so that On the other hand, _,_ since d E Xp whenever d > p and p EXP. Hence This relation states that every point less than an element of x ; is its elf in Xp. Now let q € PL. Since 1xp1 f. 0, by hypothesis, there exists a point q 3, there exists ad E DL 1 € Xp. Also, since r(L) > such that d ~ q V ql. But then d € x ; and hence q E Xp. Thus (18) Xp = PL, which implies X~ = DL. X = Xp = PL. Hence XD is empty and we have ( 19) V. EQUALITY The inequalities given by Theorem 1 can be regarded as essentially independent statements about the bipartite graphs consisting of points and e.lements of a fixed rank, On the other hand, the main theorem of this chapter shows that the corresponding equalities have implications throughout the lattice. Theorem 2: Let L be a finite geometric lattice. of dimension n > 1. Then w(l) = w(k) if and only if k = n-1 and Lis modular. Proof: As remarked in Chapter 1, it follows from a well-known theorem of R. P. Dilworth that w( 1) = w(n-1) for any finite, modular geometric lattice of dimension n. To prove the converse as stated above, it is first necessary to reduce the equality w( 1) = w(k} to the case where k = n-1. We isolate this result as a special lemma: Lemma 5. 1: Let L be a finite geometric lattice of dimension n, and let Lk be the geometric lattice obtained by identifying all ele- me.vts in L of rank> k. If Lk is modular, then k = 0, 1, 2, or n. (In other words, Lk is modular only in trivial cases.) Proof: Assume that k f. n. Since Lk is modular, the interval sublattices x/O are modular for each x in L of rank k. This implies that a(x} = a::«x} whenever r{x} = k. If we denote by /3:(p) the number of elements in L of rank k containing p, we have /3(p) < /3~(p) for all p E PL' by Theorem 1. (Note that this assumes k '/: n.) Thus 2:: r(x) = k a(x) = > 2:: p E PL /3(p) (20) Since Lk is modular, we have w( l) = w(k-1). By Corollary 4. 2, there is a bijection g which maps PL onto the elements of rank k-1 and has the property that g(p) > p for all p e PL" Furthermore, we have /3(p) > {:3(g(p)) if k-1? 1, since /3 is a strictly decreasing function on L. Hence L a( x) r(x)=k L = /3( y) r(y)=k-1 = -L /3(g(p)} < p e PL L /3(p) p ePL in conflict with the previous inequality. Hence k-1 < 1 and the lemma follows. Theorem 2 now depends only on showing that L is modular when w(l) = w(n-1). For it follows from this that L. i+ 1 is modular whenever w(l) = w(i). If 1 < i < n, Lemma 5.1 implies that i = n-1. The main part of the proof now proceeds by induction on the dimension of L. The theorem is trivial when r(L) < 2, so we assume that L has dimension n > 2, and that the result holds for all lattices of smaller dimension. From Theorem 1 and Lemma 2. 5 we have the inequalities a* (d) < a(d) :.S j3':«p) and a':«d) < /3(p) < j3':~(p), holding for all p e PL' d e DL' with p ~ d. Let f: PL~ DL be a bijection with f(p) ?t- p for all p e PL. (This is guaranteed by Corollary 4. 1). Then Since the sums on the right and left are equal, it follows that (21) a*(f(p)) = f3~~(p) for all p € PL. Hence a*{£(p)) = ~(f(p)) and .a~~(p) = f3(p) for all p € PL' by the above inequalities. Hence, by hypothesis, the intervals 1 /p and d/O are modular for all p e PL andd eDL. Suppose x and y are covered by xv y. 1£ xv y f. 1, then x and y cover x /\ y by the modularity of xv y /O. If x /\ y f. 0, the same result follows from the modularity of 1 /x /\ y. Thus, to show that L is modular, it suffices to show that x /\ y f. 0 for all x, y € DL. But this will follow if we can show that c/:«d} = f3':'(p) whenever p e PL, d e DL' and p $ d. For, suppose that x and y are distinct dual points of L, and let p be a point such that p < x, p$.y. Then, since a( y) = a':~( y) = j3':<cp), the map z---.. z v p takes the set [a onto the set (b e DLj b > p} , by Lemma 2. 4. must be an a-<y such that x =av p. I a-< y} Since x > p, there It then follows that xi\ y =a >O, since r(L) > 2. Thus, in order to complete the proof of Theorem 2, we need only show that if 1 >-d 0 ?f::. p 'r 0, the mapping f of Corollary 4. 1 can 0 be chosen so that £(p ) = d . 0 0 0 0 For then we have a~'(d ) = a~~(£(p )) = /3*(p ) as was shown earlier. 0 If p e PL - (Po} , let S(p) = ( d e DLl d ?f::. p} , and let (d € DL -(dJI d ?f::. p} • T(p) = We wish to find distinct representatives for the sets T(p), p e PL-[p }. 0 Let p , p , •.. , pk be k points in 1 2 PL-(Po} , and let and (22) Since the S(p)'s have an SDR, we have If ju 1j > k, so that ju 2 j > k-1. IU 2 1 = k-1, then d 0 U1 and (u 1j = k. We show that this leads € either to a conflict or to the desired result. Suppose that [u 2 d 0 I = k.-1, and let u = p 1 v p 2 v ... v pk. Note that ?t u, for otherwise d 0 ff. U 1 and 1u 2 j = ju 1j > k. if u =I, then U 1 = DL and to assumption. is modular. a>:<(u) Also u f:. I, since 1u 2t = 1u 1 j - I= IPLI - I > k, contrary Hence u/O is contained in a proper interval of L, and Thus a>:<(u) = a(u). In fact, a>!<(u) = a{u) = k, for if > k we have LJ S(q) I 1u I = i =k < a,:'{u) q<u and the SDR condition for the S(q)'s is violated. lnLI - w:«u), the map (d € DLI d ?t u} • Since a(u) = k = y~dy of Lemma 2. 6 maps (YI y.-<u} Thus d /\ u-< u for all d ?t u, and d 1 onto f:. d 2 implies that d /\ u f:. d /\ u for all d , d ?t u. The proof now splits into 1 1 2 2 several cases. Case 1. If r(u) > 2, then for any pair of distinct dual points d and d , 2 d /\ u and d /\ u are covered by or equal to u, and hence 1 2 r(d /\ d ) > 1 2 r((d /\ u) /\ (d /\ u)} > 1 by the modularity of u/O. Hence 1 2 1 d /\ d > 0 and the theorem follows. 1 2 C.ase 2. If r(u) = 1, we have k =I, u = p , and f3>:'{p ) = jnLj - 1. 1 1 We are assuming that 1u 2 1= IT(p 1 )j = k-1 = 0, so that p 1 ~ d 0 and js(p 1 >I = 1. Thus the function f of Corollary 4. I must map p 1 onto d • 0 Hence a>:'{d ) = /3,:'{p ) = jnLI- I= jPLj- 1. Since p ~ d andp f:.p , 1 1 1 0 0 0 it follows that d 0 > p , which contradicts the original assumption. 0 (23) Case 3. If r(u) = 2, we show again that d 0 > p • The function f 0 given by Corollary 4. 1 must map the points less than u onto the dual I points ";/::. u, since a(u) = k = DL(- J3>:'(u). be a point q -< u with f( q) ;::: d • 0 q = d /\ u. 1 Let d 1 Since d 0 ";/::. u, there must be a dual point such that jnLI - k + 1, since Then J3':'(q) = J3':'(d /\ u) > 1 J3':'(u) = jnLj - k. If J3':'(d /\ u) > (nLI - k + 1, there exists a dual 1 point d 2 distinct from d 1 such that d 2 > d /\ u and d ";/::. u. But 1 2 then d /\ u = d /\ u, which we have shown cannot hold. Hence 1 2 . w:'(q) = a':'(f(q)) =a':'( do) = Now d 0 I nL[ - k + 1 = IPLI- k + I. contains at most one of the points less than u, since, if it contained two, it would contain their join, which is u. Thus d 0 must contain all of the IPLj - k points not less than u. These include p , so that d > 0 0 p , contrary to assumption. 0 We may now conclude that the sets T(p), p :F p , have a 0 system of distinct representatives. Thus there exists a function g: PL---+- DL with the property that g(p ) = d and g(p) ";/::. p for 0 0 all p € PL~ As shown above, this completes the proof of Theorem 2. (24) VI GEOMETRIC LATTICES OF DIMENSION 3. Let L be a geometric lattice of dimension 3. with each dual point d of L the set Sd = the following properties h?ld: contained in exactly one Sd' points, and (iii) fp e PL I p ~ d }, then (i) every pair of points in PL are (ii) each Sd contains at least two no Sd contains all the points. collection of subsets If we associate Conversely, any s 1 , ... , Sm of a set T satisfying (i) - (iii) determines a geometric lattice of dimension 3. Condition (i) insures that the system (with a 1 and 0 adjoined) represents a lattice, and also that the lattice is semimodular. Condition (ii) insures that every element of rank 2 is a join of points, and condition (iii) insures that the unit element is a join of points. A theorem of deBruijn and Erd!:ls [4] makes the following assertions about configurations s , 1 ditions (i) - (iii): (1) m s 2 , ... , Sm' T satisfying con- > jTI , and (2) if m = IT j , then the configuration is either a projective plane or one of the degenerate planes represented by sl = ( 2, 3, ... ' m} ' Assertion ( 1) is equivalent to our Theorem 1 for geometric lattices of dimension 3. Assertion ( 2) follows from Theorem 2 by means of the Birkhoff-Menger decomposition theorem for complemented, modular lattices [2; Ch. 4, § 7]. This theorem states that a finite- dimensional, complemented, modular lattice can be expressed as a direct product of simple lattices which are either two-element chains or projective geometries (possibly degenerate). Thus a finite, modular geometric lattice of dimension 3 must be either a (25) projective plane or the product of a 2 -element chain with a lattice of the following type: The latter possibility corresponds to the degenerate case of the deBruijn - Erdes theorem. (26) References Baker, Kirby A., A Generalization of Sperner's Lemma, J. Combinatorial Theory 6 (T969), 224. Birkhoff, Garrett,· Lattice Theory, 3d edition, Amer. Math. Society Colloquium Publications, vol..25 (1967). [ 3 ] Linear Dependence and Lattices, Amer. ----..,J., Abstract Math. 57 (1935), 800-804. [4 ] de Bruijn, N. G., and Erdtls, P., On a Combinatorial Problem, Indigationes Math.10-(1948), 421-423. [5 ] Crapo, H. H., and Rota, G. -C., On the Foundations of Combinatorial Theory: Coffib:lllatorial Geometries, (preprint). [6 ] Dilworth, R. P., Proof of a Conjecture on Finite Modular Lattices, Ann. oTMath. 60 ( 1954), 359-364. [7 ] , and Greene, Curtis, A Counterexample to the ----Generalization~ Sperner 's Theorem,( to appear). [8 ] Graham, R. L., and Harper, L. H., Some Results on Matching in Bipartite Graphs,{tOappear). [9 ] Greene, Curtis, A Rank Inequality for Finite Geometric Lattices, (to appear). -- [10] Hall, M. Jr., Combinatorial Theory, Blaisdell, Waltham, Mass., 1967 . [11] Harper, L. H., Stirling Behavior is Asymptotically Normal, Ann. Math. Statistics 38 (1967), 410-414. [12] _ _ _, The Morphology ~ Geometric Lattices, (to appear). [13] Lubell, D., A Short Proof of Sperner 1 s Lemma, J. Combinatorial Theory l ( 1962), 299. [14] MacLane, S., A Lattice Formulation of Transcendence · Degrees-and p-Bases, Duke J. 4 ( 19 38), 455-468. [15] Menger, K., Alt, F., and Schreiber, 0., New Foundations of Projective and Affine Geometry, Ann. of Math. 37 (1936), 456-482. (27) fl6] Motzkin, T., The Lines and Planes Connecting the Points of a Fiill:te Set, Trans. Amer. Math. SoC:- 70 (l951), 45r-464. (17] Rota, G. -C. , On the Foundations of Combinatorial Theory I. Theory of MBbius Functions, Zeit. £Ur Wahrscheinlichkeitstheorie 2 (1964), 340-368. [18] Ryser, H. J., Combinatorial Mathematics, Carus Monograph Series No. 14, Math. Assoc. of Amer., Wiley, New York, 1963. [19] , An Extension of a Theorem of de Bruijn and Erdes on CombinatorTalDesigns, j:- Algebra 10(1968), 246-61. [20] Sperner, E., Ein Satz Uber Untermengen einer endlichen Menge, Math Z. (1928). 544-548. [21] Whitney, H. , The Abstract Properties ~ Linear Dependence, Amer.~ 57 (1935), 507-533.