# Difference between revisions of "Incidence system"

m (link) |
(link) |
||

Line 1: | Line 1: | ||

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. | 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 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$. | + | 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 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 | 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 |

## Revision as of 22:03, 4 January 2016

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

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