Namespaces
Variants
Actions

Difference between revisions of "Incidence system"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: expand bibliodata)
 
(4 intermediate revisions by the same user not shown)
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.
+
{{MSC|05B}}
  
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" />.
+
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.
  
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
+
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: for example, [[balanced incomplete 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$.
  
<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>
+
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 <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.
+
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====
 
====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) {{ZBL|0159.50001}}, repr. (1997) ISBN 3-540-61786-8  {{ZBL|0865.51004}}</TD></TR>
 +
</table>
  
 
====Comments====
 
====Comments====
 
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}}

Latest revision as of 10:38, 27 March 2018

2010 Mathematics Subject Classification: Primary: 05B [MSN][ZBL]

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: for example, balanced incomplete 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) Zbl 0159.50001, repr. (1997) ISBN 3-540-61786-8 Zbl 0865.51004

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=19258
This article was adapted from an original article by V.E. Tarakanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article