Namespaces
Variants
Actions

Difference between revisions of "Combinatorial geometry(2)"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
 
Line 1: Line 1:
A finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c023/c023270/c0232701.png" /> together with a closure relation
+
<!--
 +
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.
 +
-->
  
<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>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
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
+
A finite set  $ S $
 +
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/c02327026.png" /></td> </tr></table>
+
$$
 +
A  \rightarrow  \overline{A}\; ,
 +
$$
  
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.
+
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
  
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
+
$$
 +
r ( A \cup B) +
 +
r ( A \cap B)  \leq  \
 +
r ( A) + r ( B).
 +
$$
  
<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>
+
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.
  
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" />.
+
Example of a combinatorial geometry. A subset  $  S $
 +
of a vector space  $  V $
 +
with the relation
  
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" />.)
+
$$
 +
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====
 
====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>
 
<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>

Latest revision as of 17:45, 4 June 2020


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)
How to Cite This Entry:
Combinatorial geometry(2). Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Combinatorial_geometry(2)&oldid=46401
This article was adapted from an original article by A.M. Revyakin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article