Inmathematics, anincidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider thepoints andlines of theEuclidean plane as the two types of objects and ignore all the properties of this geometry except for therelation of which points areincident 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 asaffine,projective, andMö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 calledfinite geometry.^[1]

Anincidence structure is a triple (P,L,I) whereP is a set whose elements are calledpoints,L is a distinct set whose elements are calledlines andI ⊆P ×L is theincidencerelation. The elements ofI are calledflags. If (p,l) is inI then one may say that pointp "lies on" linel or that the linel "passes through" pointp. A more "symmetric" terminology, to reflect thesymmetric nature of this relation, is that "p isincident withl" or that "l is incident withp" and uses the notationp Il synonymously with(p,l) ∈I.^[2]

In some common situationsL may be a set of subsets ofP in which case incidenceI will be containment (p Il if and only ifp is a member ofl). Incidence structures of this type are calledset-theoretic.^[3] This is not always the case, for example, ifP is a set of vectors andL a set ofsquare matrices, we may define$${\displaystyle I=\{(v,M):\overrightarrow{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.

An incidence structure isuniform 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.

Anygraph (which need not besimple;loops andmultiple 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, apartial linear space is an incidence structure that satisfies:

1. Any two distinct points are incident with at most one common line, and
2. Every line is incident with at least two points.

If the first axiom above is replaced by the stronger:

3. Any two distinct points are incident with exactly one common line,

the incidence structure is called alinear space.^[4][5]

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

If we interchange the role of "points" and "lines" in$${\displaystyle C=(P,L,I)}$$we obtain thedual structure,$${\displaystyle C^{\ast }=(L,P,I^{\ast })}$$whereI^∗ is theconverse relation ofI. It follows immediately from the definition that:$${\displaystyle C^{\ast \ast }=C}$$

This is an abstract version ofprojective duality.^[2]

A structureC that isisomorphic to its dualC^∗ is calledself-dual. The Fano plane above is a self-dual incidence structure.

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 a geometric terminology, but ingraph theoretic terms they are calledhypergraphs and in design theoretic terms they are calledblock designs. They are also known as aset system orfamily of sets in a general context.

Eachhypergraph orset system can be regarded as an incidencestructure in which theuniversal set plays the role of "points", the correspondingfamily of subsets plays the role of "lines" and the incidence relation isset 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.

A (general) block design is a setX together with afamilyF of subsets ofX (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 andF is the set of lines, usually calledblocks in this context (repeated blocks must have distinct names, soF is actually a set and not a multiset). If all the subsets inF have the same size, the block design is calleduniform. If each element ofX appears in the same number of subsets, the block design is said to beregular. The dual of a uniform design is a regular design and vice versa.

Consider the block design/hypergraph given by:

This incidence structure is called theFano plane. As a block design it is both uniform and regular.

In the labeling given, the lines are precisely the subsets of the points that consist of three points whose labels add up to zero usingnim addition. Alternatively, each number, when written inbinary, can be identified with a non-zero vector of length three over thebinary field. Three vectors that generate asubspace form a line; in this case, that is equivalent to their vector sum being the zero vector.

Incidence structures may be represented in many ways. If the setsP andL are finite these representations can compactly encode all the relevant information concerning the structure.

Theincidence matrix of a (finite) incidence structure is a(0,1) matrix that has its rows indexed by the points{p_i} and columns indexed by the lines{l_j} where theij-th entry is a 1 ifp_i Il_j 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 matrix for this structure is:which corresponds to the incidence table:

If an incidence structureC has an incidence matrixM, then the dual structureC^∗ has thetranspose matrixM^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 asymmetric matrix.

With the labels as given in example number 1 above and with points orderedA,B,C,D,G,F,E and lines orderedl,p,n,s,r,m,q, the Fano plane has the incidence 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.^[6] The dots may be placed in any manner, there are no restrictions on distances between points or any relationships between points. 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 withordered geometry, which does have a notion of betweenness. The same statements can be made about the depictions of the lines. In particular, lines need not be depicted by "straight line segments" (see examples 1, 3 and 4 above). As with the pictorial representation ofgraphs, the crossing of two "lines" at any place other than a dot has no meaning in terms of the incidence structure; it is only an accident of the representation. These incidence figures may at times resemble graphs, but they aren't graphs unless the incidence structure is a graph.

Incidence structures can be modelled by points and curves in theEuclidean plane with the usual geometric meaning of incidence. Some incidence structures admit representation by points and (straight) lines. Structures that can be are calledrealizable. If no ambient space is mentioned then the Euclidean plane is assumed. The Fano plane (example 1 above) is not realizable since it needs at least one curve. The Möbius–Kantor configuration (example 4 above) is not realizable in the Euclidean plane, but it is realizable in thecomplex plane.^[7] On the other hand, examples 2 and 5 above are realizable and the incidence figures given there demonstrate this. Steinitz (1894)^[8] has shown thatn₃-configurations (incidence structures withn points andn 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.^[9] The Fano plane is the unique (7₃) and the Möbius–Kantor configuration is the unique (8₃).

Each incidence structureC corresponds to abipartite graph called theLevi graph or incidence graph of the structure. As any bipartite graph is two-colorable, the Levi graph can be given a black and whitevertex coloring, where black vertices correspond to points and white vertices correspond to lines ofC. 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 thegeneralized quadrangle of order two (example 3 above),^[10] but the term has been extended byH.S.M. Coxeter^[11] to refer to an incidence graph of any incidence structure.^[12]

The Levi graph of theFano plane is theHeawood graph. Since the Heawood graph isconnected andvertex-transitive, there exists anautomorphism (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π/4 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.

It is possible to generalize the notion of an incidence structure to include more than two types of objects. A structure withk types of objects is called anincidence structure of rankk or arankkgeometry.^[12] Formally these are defined ask + 1 tuplesS = (P₁,P₂, ...,P_k,I) withP_i ∩P_j = ∅ and

The Levi graph for these structures is defined as amultipartite graph with vertices corresponding to each type being colored the same.

• Incidence (geometry)
• Incidence geometry
• Projective configuration
• Abstract polytope

• Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986),Design Theory, Cambridge University Press,ISBN 3-411-01675-2
• Biliotti, Mauro; Jha, Vikram; Johnson, Norman L. (2001),Foundations of Translation Planes,Marcel Dekker,ISBN 0-8247-0609-9
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007),Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC,ISBN 978-1-58488-506-1
• Dembowski, Peter (1968),Finite geometries,Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44, Berlin, New York:Springer-Verlag,ISBN 3-540-61786-8,MR 0233275
• Moorhouse, G. Eric (2014)."Incidence Geometry"(PDF) – viaJohn Baez atUniversity of California, Riverside.
• Pisanski, Tomaž;Servatius, Brigitte (2013),Configurations from a Graphical Viewpoint, Springer,doi:10.1007/978-0-8176-8364-1,ISBN 978-0-8176-8363-4

• CRC Press (2000).Handbook of discrete and combinatorial mathematics, (Chapter 12.2),ISBN 0-8493-0149-1
• Harold L. Dorwart (1966)The Geometry of Incidence,Prentice Hall

• Families of sets
• Combinatorics
• Finite geometry
• Incidence geometry

• Articles with short description
• Short description is different from Wikidata