Incidence system
A family 
of two sets 
and 
with an incidence relation 
between their elements, which is written as 
for 
, 
. In this case one says that the element 
is incident with 
, or that 
is incident with 
. 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 
and 
are called, respectively, points and lines, and 
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), which are obtained by requiring that 1) each 
is incident with precisely 
elements of 
; 2) each 
is incident with precisely 
elements of 
; and 3) each pair of distinct elements of 
is incident with precisely 
elements of 
. Often a set of subsets of 
is taken for 
; then 
is simply 
.
Two incidence systems 
and 
are called isomorphic if there are one-to-one correspondences 
and 
such that
 |
If 
and 
are finite sets, then the properties of the incidence system 
can be conveniently described by the incidence matrix 
, where 
if 
, and 
otherwise. The matrix 
determines 
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 
and 
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) |
Incidence system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Incidence_system&oldid=37004