In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the points and lines of the Euclidean plane as the two types of objects and ignore all the properties of this geometry except for the relation of which points are incident on which lines for all points and lines. What is left is the incidence structure of the Euclidean plane. Incidence structures are most often considered in the geometrical context where they are abstracted from, and hence generalize, planes (such as affine, projective, and Möbius planes), but the concept is very broad and not limited to geometric settings. Even in a geometric setting, incidence structures are not limited to just points and lines; higher-dimensional objects (planes, solids, n-spaces, conics, etc.) can be used. The study of finite structures is sometimes called finite geometry.
Formal definition and terminology An incidence structure is a triple (P, L, I) where P is a set whose elements are called points, L is a distinct set whose elements are called lines and I ⊆ P × L is the incidence relation. The elements of I are called flags. If (p, l) is in I then one may say that point p "lies on" line l or that the line l "passes through" point p. A more "symmetric" terminology, to reflect the symmetric nature of this relation, is that "p is incident with l" or that "l is incident with p" and uses the notation p I l synonymously with (p, l) ∈ I. In some common situations L may be a set of subsets of P in which case incidence I will be containment (p I l if and only if p is a member of l). Incidence structures of this type are called set-theoretic. This is not always the case, for example, if P is a set of vectors and L a set of square matrices, we may define
I = { ( v , M ) : v → is an eigenvector of matrix M } . {\displaystyle I=\{(v,M):{\vec {v}}{\text{ is an eigenvector of matrix }}M\}.}
This example also shows that while the geometric language of points and lines is used, the object types need not be these geometric objects.
Examples
An incidence structure is uniform if each line is incident with the same number of points. Each of these examples, except the second, is uniform with three points per line.
Graphs
Any graph (which need not be simple; loops and multiple edges are allowed) is a uniform incidence structure with two points per line. For these examples, the vertices of the graph form the point set, the edges of the graph form the line set, and incidence means that a vertex is an endpoint of an edge.
Linear spaces Incidence structures are seldom studied in their full generality; it is typical to study incidence structures that satisfy some additional axioms. For instance, a partial linear space is an incidence structure that satisfies:
Any two distinct points are incident with at most one common line, and Every line is incident with at least two points. If the first axiom above is replaced by the stronger:
Any two distinct points are incident with exactly one common line, the incidence structure is called a linear space.
Nets A more specialized example is a k-net. This is an incidence structure in which the lines fall into k parallel classes, so that two lines in the same parallel class have no common points, but two lines in different classes have exactly one common point, and each point belongs to exactly one line from each parallel class. An example of a k-net is the set of points of an affine plane together with k parallel classes of affine lines.
Dual structure If we interchange the role of "points" and "lines" in
C = ( P , L , I ) {\displaystyle C=(P,L,I)}
we obtain the dual structure,
C ∗ = ( L , P , I ∗ ) {\displaystyle C^{*}=(L,P,I^{*})}
where I∗ is the converse relation of I. It follows immediately from the definition that:
C ∗ ∗ = C {\displaystyle C^{**}=C}
This is an abstract version of projective duality. A structure C that is isomorphic to its dual C∗ is called self-dual. The Fano plane above is a self-dual incidence structure.
Other terminology The concept of an incidence structure is very simple and has arisen in several disciplines, each introducing its own vocabulary and specifying the types of questions that are typically asked about these structures. Incidence structures use geometric terminology, but in graph theory they are hypergraphs and in combinatorial design theory they are block designs. They are also known as a set system or family of sets in a general context.
Hypergraphs
Each hypergraph or set system can be regarded as an incidence structure in which the universal set plays the role of "points", the corresponding family of subsets plays the role of "lines" and the incidence relation is set membership "∈". Conversely, every incidence structure can be viewed as a hypergraph by identifying the lines with the sets of points that are incident with them.
Block designs
A (general) block design is a set X together with a family F of subsets of X (repeated subsets are allowed). Normally a block design is required to satisfy numerical regularity conditions. As an incidence structure, X is the set of points and F is the set of lines, usually called blocks in this context (repeated blocks must have distinct names, so F is actually a set and not a multiset). If all the subsets in F have the same size, the block design is called uniform. If each element of X appears in the same number of subsets, the block design is said to be regular. The dual of a uniform design is a regular design and vice versa.
Example: Fano plane Consider the block design/hypergraph given by:
… excerpt ends here. Continue reading the full article.
