Incidence system

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.

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)