View source for Combinatorial geometry(2)

<!--
c0232701.png
$#A+1 = 43 n = 0
$#C+1 = 43 : ~/encyclopedia/old_files/data/C023/C.0203270 Combinatorial geometry
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A finite set  $  S $
together with a closure relation

$$ 
A  \rightarrow  \overline{A}\; ,
$$

defined for all subsets  $  A $
of  $  S $(
that is,  $  A \subseteq \overline{A}\; $, 
$  A \subseteq B $
implies  $  \overline{A}\; \subseteq \overline{B}\; $
and  $  \overline{ {\overline{A}\; }}\; = \overline{A}\; $, 
but not necessarily  $  \overline{ {A \cup B }}\; = \overline{A}\; \cup \overline{B}\; $), 
and satisfying the conditions: 1) for the empty set  $  \overline \emptyset \; = \emptyset $; 
2)  $  \overline{p}\; = p $
for each element  $  p \in S $; 
and 3) if  $  p, q \in S $
and  $  A \subseteq S $
and if  $  q \in \overline{ {A \cup p }}\; $
but  $  q \notin \overline{A}\; $, 
then  $  p \in \overline{ {A \cup q }}\; $(
the  "exchange"  property). The closed sets, or subspaces,  $  ( \overline{A}\; = A) $
form a [[geometric lattice]] (cf. [[Semi-Dedekind lattice|Semi-Dedekind lattice]]). A subset  $  I \subseteq S $
is independent if  $  p \notin \overline{ {I \setminus  p }}\; $
for all  $  p \in I $; 
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  $  A $
are defined in the usual way. The cardinality of the bases of the restriction of a combinatorial geometry to  $  A $
is called the rank  $  r ( A) $
of  $  A $. 
The rank function satisfies the condition

$$ 
r ( A \cup B) +
r ( A \cap B)  \leq  \ 
r ( A) + r ( B).
$$

A subset  $  A \subseteq S $
for which  $  r ( A) < | A | $
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  $  S $
of a vector space  $  V $
with the relation

$$ 
A  \rightarrow  \overline{A}\;  = \ 
 \mathop{\rm sp} ( A) \cap S,
$$

defined for all  $  A \subseteq S $, 
where  $   \mathop{\rm sp} ( A) $
is the linear subspace in  $  V $
spanned by  $  A $.

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  $  S $
in an  $  n $-
dimensional projective space over a Galois field, this problem consists in the determination of the smallest positive integer  $  k $(
the critical exponent) for which there exists a family of hyperplanes  $  H _ {1} \dots H _ {k} $
distinguishing  $  S $. 
(A family of hyperplanes distinguishes a set  $  S $
if for every  $  t \in S $
there is at least one hyperplane not containing  $  t $.)

====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>