Incidence structure

In mathematics, an incidence structure is a triple

C=(P,L,I).\,

where P is a set of "points", L is a set of "lines" and $I \subseteq P \times L$ is the incidence relation. The elements of $I$ are called flags. If

(p,l) \in I,

we say that point p "lies on" line $l$ . One may concretely have L be a set of subsets of P, and have incidence I be containment ( $(p,l) \in I$ if and only if $p \in l$ ), but one may also work more abstractly.

Incidence structures generalize planes (such as affine, projective, and Möbius planes) as can be seen from their axiomatic definitions. Incidence structures also generalize the higher-dimensional analogs and the finite structures are sometimes called finite geometries.

Comparison with other structures

An incidence figure (that is, a depiction of an incidence structure), may look like a graph, but in a graph an edge has just two endpoints (beyond a vertex a new edge starts), while a line in an incidence structure can be incident to more than two points. In fact, incidence structures are hypergraphs.

In an incidence structure there is no concept of a point being between two other points; the order of points on a line is undefined. Compare this with ordered geometry, which does have a notion of betweenness.

Dual structure

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

C = (P,L,I)

the dual structure

C* = (L,P,I*)

is obtained, where I* is the inverse relation of I. Clearly

C** = C.

This is an abstract version of projective duality.

A structure C that is isomorphic to its dual C* is called self-dual.

Correspondence with hypergraphs

Seven points are elements of seven lines in the Fano plane

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 sets plays the role of "lines" and the incidence relation is set membership "∈". Conversely, every incidence structure can be viewed as a hypergraph.

Example: Fano plane

In particular, let

P=\left\{1,2,3,4,5,6,7\right\}

L = \left\{\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}\right\}

The corresponding incidence structure is called the Fano plane.

The lines are precisely the subsets of the points that consist of three points whose labels add up to zero using nim addition.

Geometric representation

Incidence structures can be modelled by points and curves in the Euclidean plane with usual geometric incidence. Some incidence structures admit representation by points and lines. The Fano plane is not one of them since it needs at least one curve.

Levi graph of an incidence structure

Heawood graph with labeling

Each incidence structure C 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 C. The edges of this graph correspond to the flags (incident point/line pairs) of the incidence structure.

Example: Heawood graph

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.

References

CRC Press (2000). Handbook of discrete and combinatorial mathematics, (Chapter 12.2), ISBN 0-8493-0149-1
Mauro Biliotti, Vikram Jha, Norman L. Johnson (2001) Foundations of Translation Planes, Appendix V: Incidence Structures and Parallelisms, pp 507–12, Marcel Dekker ISBN 0-8247-0609-9 .