Incidence structure

In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects.

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

[1] 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.

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.

[2] 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).

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.

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: If the first axiom above is replaced by the stronger: the incidence structure is called a linear space.

Incidence structures use a geometric terminology, but in graph theoretic terms they are called hypergraphs and in design theoretic terms they are called block designs.

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 "∈".

Normally a block design is required to satisfy numerical regularity conditions.

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.

If the sets P and L are finite these representations can compactly encode all the relevant information concerning the structure.

The incidence matrix of a (finite) incidence structure is a (0,1) matrix that has its rows indexed by the points {pi} and columns indexed by the lines {lj} where the ij-th entry is a 1 if pi I lj and 0 otherwise.

[a] An incidence matrix is not uniquely determined since it depends upon the arbitrary ordering of the points and the lines.

[6] The non-uniform incidence structure pictured above (example number 2) is given by:

An incidence structure is self-dual if there exists an ordering of the points and lines so that the incidence matrix constructed with that ordering is a symmetric matrix.

Since this is a symmetric matrix, the Fano plane is a self-dual incidence structure.

An incidence figure (that is, a depiction of an incidence structure), is constructed by representing the points by dots in a plane and having some visual means of joining the dots to correspond to lines.

Some incidence structures admit representation by points and (straight) lines.

If no ambient space is mentioned then the Euclidean plane is assumed.

[7] On the other hand, examples 2 and 5 above are realizable and the incidence figures given there demonstrate this.

As any bipartite graph is two-colorable, the Levi graph can be given a black and white vertex coloring, where black vertices correspond to points and white vertices correspond to lines of C. The edges of this graph correspond to the flags (incident point/line pairs) of the incidence structure.

Since the Heawood graph is connected and vertex-transitive, there exists an automorphism (such as the one defined by a reflection about the vertical axis in the figure of the Heawood graph) interchanging black and white vertices.

The specific representation, on the left, of the Levi graph of the Möbius–Kantor configuration (example 4 above) illustrates that a rotation of π/4 about the center (either clockwise or counterclockwise) of the diagram interchanges the blue and red vertices and maps edges to edges.

It is possible to generalize the notion of an incidence structure to include more than two types of objects.

[12] Formally these are defined as k + 1 tuples S = (P1, P2, ..., Pk, I) with Pi ∩ Pj = ∅ and