Incidence structure

[[File:Inzidenz-struktur.svg|thumb|Examples of incidence structures:

Example 1: points and lines of the Euclidean plane (top)

Example 2: points and circles (middle),

Example 3: finite incidence structure defined by an incidence matrix (bottom)]]

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, -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 () where is a set whose elements are called points, is a distinct set whose elements are called lines and is the incidence relation. The elements of are called flags. If () is in then one may say that point "lies on" line or that the line "passes through" point . A more "symmetric" terminology, to reflect the symmetric nature of this relation, is that " is incident with " or that " is incident with " and uses the notation synonymously with .

In some common situations may be a set of subsets of in which case incidence will be containment ( if and only if is a member of ). Incidence structures of this type are called set-theoretic. This is not always the case, for example, if is a set of vectors and a set of square matrices, we may define

<math display=block>I = \{(v, M) : \vec v \text{ is an eigenvector of matrix } M \}.</math>

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:

<li value="3"> Any two distinct points are incident with exactly one common line,</li>

the incidence structure is called a linear space.

Nets

A more specialized example is a -net. This is an incidence structure in which the lines fall into 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 -net is the set of points of an affine plane together with parallel classes of affine lines.

Dual structure

If we interchange the role of "points" and "lines" in

we obtain the dual structure,

where is the converse relation of . It follows immediately from the definition that:

This is an abstract version of projective duality.

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

<math display=block>\begin{align}

P &= \{ A, B, C, D, E, P \} \\[2pt]

L &= \left\{ \begin{array}{ll}

l = \{C, P, E \}, & m = \{ P \}, \\

n = \{ P, D \}, & o = \{ P, A \}, \\

p = \{ A, B \}, & q = \{ P, B \} \end{array} \right\}

\end{align}</math>

An incidence matrix for this structure is:

<math display="block"> \begin{pmatrix}

0 & 0 & 0 & 1 & 1 & 0 \\

0 & 0 & 0 & 0 & 1 & 1 \\

1 & 0 & 0 & 0 & 0 & 0 \\

0 & 0 & 1 & 0 & 0 & 0 \\

1 & 0 & 0 & 0 & 0 & 0 \\

1 & 1 & 1 & 1 & 0 & 1

\end{pmatrix} </math>

which corresponds to the incidence table:

{| class="wikitable" style="text-align:center; width=200px; height=200px;"

! !! !! !! !! !! !!

| 0 || 0 || 0 || 1 || 1 || 0

| 0 || 0 || 0 || 0 || 1 || 1

| 1 || 0 || 0 || 0 || 0 || 0

| 0 || 0 || 1 || 0 || 0 || 0

| 1 || 0 || 0 || 0 || 0 || 0

| 1 || 1 || 1 || 1 || 0 || 1

If an incidence structure has an incidence matrix , then the dual structure has the transpose matrix T as its incidence matrix (and is defined by that matrix).

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.

With the labels as given in example number 1 above and with points ordered and lines ordered , the Fano plane has the incidence matrix:

<math display="block"> \begin{pmatrix}

1 & 1 & 1 & 0 & 0 & 0 & 0\\

1 & 0 & 0 & 1 & 1 & 0 & 0 \\

1 & 0 & 0 & 0 & 0 & 1 & 1 \\

0 & 1 & 0 & 1 & 0 & 1 & 0 \\

0 & 1 & 0 & 0 & 1 & 0 & 1 \\

0 & 0 & 1 & 1 & 0 & 0 & 1 \\

0 & 0 & 1 & 0 & 1 & 1 & 0

\end{pmatrix} . </math>

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

Pictorial representations

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. On the other hand, examples 2 and 5 above are realizable and the incidence figures given there demonstrate this. Steinitz (1894) has shown that (incidence structures with points and lines, three points per line and three lines through each point) are either realizable or require the use of only one curved line in their representations. The Fano plane is the unique () and the Möbius–Kantor configuration is the unique ().

Incidence graph (Levi graph)

thumb|[[Heawood graph with labeling]]

Each incidence structure corresponds to a bipartite graph called the Levi graph or incidence graph of the structure. 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 . The edges of this graph correspond to the flags (incident point/line pairs) of the incidence structure. The original Levi graph was the incidence graph of the generalized quadrangle of order two (example 3 above), but the term has been extended by H.S.M. Coxeter to refer to an incidence graph of any incidence structure.

left|thumb|Levi graph of the Möbius–Kantor configuration (#4)

Levi graph examples

The Levi graph of the Fano plane is the Heawood graph. 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. This, in turn, implies that the Fano plane is self-dual.

The specific representation, on the left, of the Levi graph of the Möbius–Kantor configuration (example 4 above) illustrates that a rotation of about the center (either clockwise or counterclockwise) of the diagram interchanges the blue and red vertices and maps edges to edges. That is to say that there exists a color interchanging automorphism of this graph. Consequently, the incidence structure known as the Möbius–Kantor configuration is self-dual.

Generalization

It is possible to generalize the notion of an incidence structure to include more than two types of objects. A structure with types of objects is called an incidence structure of rank or a rank geometry.