Incidence system

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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


[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


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.


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