Combinatorial geometry(2)

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). 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. 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

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