View source for Combinatorial geometry(2)

A finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232701.png" /> together with a closure relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232702.png" /></td> </tr></table>

defined for all subsets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232703.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232704.png" /> (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232705.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232706.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232707.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232708.png" />, but not necessarily <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232709.png" />), and satisfying the conditions: 1) for the empty set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327010.png" />; 2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327011.png" /> for each element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327012.png" />; and 3) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327014.png" /> and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327015.png" /> but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327016.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327017.png" /> (the  "exchange"  property). The closed sets, or subspaces, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327018.png" /> form a [[geometric lattice]] (cf. [[Semi-Dedekind lattice|Semi-Dedekind lattice]]). A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327019.png" /> is independent if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327020.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327021.png" />; all maximal independent sets, or bases, have the same cardinality. The direct sum of combinatorial geometries and the restriction of a combinatorial geometry to a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327022.png" /> are defined in the usual way. The cardinality of the bases of the restriction of a combinatorial geometry to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327023.png" /> is called the rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327024.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327025.png" />. The rank function satisfies the condition

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327026.png" /></td> </tr></table>

A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327027.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327028.png" /> is said to be dependent; the minimal dependent sets of a combinatorial geometry are called circuits. By dropping conditions 1) and 2) in the definition of a combinatorial geometry one obtains the definition of a pre-geometry or [[Matroid|matroid]]. Infinite combinatorial geometries are also considered, but here it is required that the bases be finite.

Example of a combinatorial geometry. A subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327029.png" /> of a vector space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327030.png" /> with the relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327031.png" /></td> </tr></table>

defined for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327033.png" /> is the linear subspace in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327034.png" /> spanned by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327035.png" />.

One of the fundamental problems in the theory of combinatorial geometries is the so-called critical problem. For the combinatorial geometry defined by a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327036.png" /> in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327037.png" />-dimensional projective space over a Galois field, this problem consists in the determination of the smallest positive integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327038.png" /> (the critical exponent) for which there exists a family of hyperplanes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327039.png" /> distinguishing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327040.png" />. (A family of hyperplanes distinguishes a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327041.png" /> if for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327042.png" /> there is at least one hyperplane not containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c02327043.png" />.)

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  H. Whitney,   "On the abstract properties of linear dependence"  ''Amer. J. Math.'' , '''57'''  (1935)  pp. 509–533</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  H.H. Crapo,   G.C. Rota,   "On the foundations of combinatorial theory: combinatorial geometries" , M.I.T.  (1970)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  W.T. Tutte,   "Introduction to the theory of matroids" , American Elsevier  (1971)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  R.J. Wilson,   "Introduction to graph theory" , Oliver &amp; Boyd  (1972)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  K.A. Rybnikov,   "Introduction to combinatorial analysis" , Moscow  (1972)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  D.J.A. Welsh,   "Matroid theory" , Acad. Press  (1976)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  R. von Randow,   "Introduction to the theory of matroids" , Springer  (1975)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  N. White (ed.) , ''Theory of matroids'' , Cambridge Univ. Press  (1986)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  K.A. Rybnikov (ed.) , ''Combinatorial analysis: exercises and problems'' , Moscow  (1982)  (In Russian)</TD></TR></table>