Namespaces
Variants
Actions

Difference between revisions of "Incidence system"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 1: Line 1:
A family <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504101.png" /> of two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504102.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504103.png" /> with an incidence relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504104.png" /> between their elements, which is written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504105.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504106.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504107.png" />. In this case one says that the element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504108.png" /> is incident with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i0504109.png" />, or that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041010.png" /> is incident with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041011.png" />. The concept of an incidence system is introduced with the purpose of using the language of geometry in the study of general combinatorial existence and construction problems; the incidence relation is ascribed certain properties that lead to some or other combinatorial configurations.
+
A family $S = (A,\mathfrak{B},I)$ of two sets $A$ and $\mathfrak{B}$ with an incidence relation $I$ between their elements, which is written as $a\,I\,B$ for $a \in A$, $B \in \mathfrak{B}$. In this case one says that the element $a$ is incident with $B$, or that $B$ is incident with $a$. The concept of an incidence system is introduced with the purpose of using the language of geometry in the study of general combinatorial existence and construction problems; the incidence relation is ascribed certain properties that lead to some or other combinatorial configurations.
  
An example of incidence systems used in combinatorics are (finite) geometries: the elements of the (finite) sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041013.png" /> are called, respectively, points and lines, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041014.png" /> is a relation with properties that are usual in the theory of projective or affine geometry. Another characteristic example of incidence systems is that of block designs (cf. [[Block design|Block design]]), which are obtained by requiring that 1) each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041015.png" /> is incident with precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041016.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041017.png" />; 2) each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041018.png" /> is incident with precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041019.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041020.png" />; and 3) each pair of distinct elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041021.png" /> is incident with precisely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041022.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041023.png" />. Often a set of subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041024.png" /> is taken for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041025.png" />; then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041026.png" /> is simply <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041027.png" />.
+
An example of incidence systems used in combinatorics are (finite) geometries: the elements of the (finite) sets $A$ and $\mathfrak{B}$ are called, respectively, points and lines, and $I$ is a relation with properties that are usual in the theory of projective or affine geometry. Another characteristic example of incidence systems is that of [[block design]]s, which are obtained by requiring that 1) each $a \in A$ is incident with precisely $r$ elements of $\mathfrak{B}$; 2) each $B \in \mathfrak{B}$ is incident with precisely $k$ elements of $A$; and 3) each pair of distinct elements of $A$ is incident with precisely $\lambda$ elements of $\mathfrak{B}$. Often a set of subsets of $A$ is taken for $\mathfrak{B}$; then $a\,I\,B$ is simply $a \in B$.
  
Two incidence systems <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041029.png" /> are called isomorphic if there are one-to-one correspondences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041030.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041031.png" /> such that
+
Two incidence systems $S = (A,\mathfrak{B},I)$ and $S' = (A',\mathfrak{B'},I')$ are called isomorphic if there are one-to-one correspondences $\alpha : A \leftrightarrow A'$ and $\beta : \mathfrak{B} \leftrightarrow \mathfrak{B'}$ such that
 +
$$
 +
a\,I\,B \Leftrightarrow \alpha(a)\,I'\,\beta(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/i/i050/i050410/i05041032.png" /></td> </tr></table>
+
If $A = \{a_1,\ldots,a_n\}$ and $\mathfrak{B} = \{B_1,\ldots,B_m\}$ are finite sets, then the properties of the incidence system $S$ can be conveniently described by the incidence matrix $\Sigma$, where $\Sigma_{ij} = 1$ if $a_i\,I\,B_j$, and $\Sigma_{ij} = 0$ otherwise. The matrix $\Sigma$ determines $S$ up to an isomorphism.
 
 
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041034.png" /> are finite sets, then the properties of the incidence system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041035.png" /> can be conveniently described by the incidence matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041036.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041037.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041038.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041039.png" /> otherwise. The matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041040.png" /> determines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041041.png" /> up to an isomorphism.
 
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  R. Dembowski,  "Finite geometries" , Springer  (1968)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  M. Hall,  "Combinatorial theory" , Blaisdell  (1967)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  R. Dembowski,  "Finite geometries" , Springer  (1968)</TD></TR>
 +
</table>
  
  
Line 17: Line 21:
 
Condition 1) for a block design follows from conditions 2) and 3).
 
Condition 1) for a block design follows from conditions 2) and 3).
  
A more general type of incidence system is a Buekenhout–Tits geometry, obtained when one considers not two sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050410/i05041043.png" /> but infinitely many types of objects.
+
A more general type of incidence system is a Buekenhout–Tits geometry, obtained when one considers not two sets $A$ and $\mathfrak{B}$ but infinitely many types of objects.
  
From the point of view of graph theory, an incidence system is a [[Hypergraph|hypergraph]].
+
From the point of view of graph theory, an incidence system is a [[hypergraph]].
  
 
An incidence system is also called an incidence structure.
 
An incidence system is also called an incidence structure.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , B.I. Wissenschaftsverlag Mannheim  (1985)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A. Beutelspacher,  "Einführung in die endliche Geometrie" , '''I-II''' , B.I. Wissenschaftsverlag Mannheim  (1982–1983)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  T. Beth,  D. Jungnickel,  H. Lenz,  "Design theory" , B.I. Wissenschaftsverlag Mannheim  (1985)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  A. Beutelspacher,  "Einführung in die endliche Geometrie" , '''I-II''' , B.I. Wissenschaftsverlag Mannheim  (1982–1983)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Revision as of 22:19, 19 December 2015

A family $S = (A,\mathfrak{B},I)$ of two sets $A$ and $\mathfrak{B}$ with an incidence relation $I$ between their elements, which is written as $a\,I\,B$ for $a \in A$, $B \in \mathfrak{B}$. In this case one says that the element $a$ is incident with $B$, or that $B$ is incident with $a$. The concept of an incidence system is introduced with the purpose of using the language of geometry in the study of general combinatorial existence and construction problems; the incidence relation is ascribed certain properties that lead to some or other combinatorial configurations.

An example of incidence systems used in combinatorics are (finite) geometries: the elements of the (finite) sets $A$ and $\mathfrak{B}$ are called, respectively, points and lines, and $I$ is a relation with properties that are usual in the theory of projective or affine geometry. Another characteristic example of incidence systems is that of block designs, which are obtained by requiring that 1) each $a \in A$ is incident with precisely $r$ elements of $\mathfrak{B}$; 2) each $B \in \mathfrak{B}$ is incident with precisely $k$ elements of $A$; and 3) each pair of distinct elements of $A$ is incident with precisely $\lambda$ elements of $\mathfrak{B}$. Often a set of subsets of $A$ is taken for $\mathfrak{B}$; then $a\,I\,B$ is simply $a \in B$.

Two incidence systems $S = (A,\mathfrak{B},I)$ and $S' = (A',\mathfrak{B'},I')$ are called isomorphic if there are one-to-one correspondences $\alpha : A \leftrightarrow A'$ and $\beta : \mathfrak{B} \leftrightarrow \mathfrak{B'}$ such that $$ a\,I\,B \Leftrightarrow \alpha(a)\,I'\,\beta(B) \ . $$

If $A = \{a_1,\ldots,a_n\}$ and $\mathfrak{B} = \{B_1,\ldots,B_m\}$ are finite sets, then the properties of the incidence system $S$ can be conveniently described by the incidence matrix $\Sigma$, where $\Sigma_{ij} = 1$ if $a_i\,I\,B_j$, and $\Sigma_{ij} = 0$ otherwise. The matrix $\Sigma$ determines $S$ up to an isomorphism.

References

[1] M. Hall, "Combinatorial theory" , Blaisdell (1967)
[2] R. Dembowski, "Finite geometries" , Springer (1968)


Comments

Condition 1) for a block design follows from conditions 2) and 3).

A more general type of incidence system is a Buekenhout–Tits geometry, obtained when one considers not two sets $A$ and $\mathfrak{B}$ but infinitely many types of objects.

From the point of view of graph theory, an incidence system is a hypergraph.

An incidence system is also called an incidence structure.

References

[a1] T. Beth, D. Jungnickel, H. Lenz, "Design theory" , B.I. Wissenschaftsverlag Mannheim (1985)
[a2] A. Beutelspacher, "Einführung in die endliche Geometrie" , I-II , B.I. Wissenschaftsverlag Mannheim (1982–1983)
How to Cite This Entry:
Incidence system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Incidence_system&oldid=37004
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article