View source for Incidence structure

{{short description|Abstract mathematical system of two types of objects and a relation between them}}
[[File:Inzidenz-struktur.svg|thumb|Examples of incidence structures:<br />
Example 1: points and lines of the Euclidean plane (top)<br />
Example 2: points and circles (middle),<br />
Example 3: finite incidence structure defined by an [[Incidence matrix|incidence matrix]] (bottom)]]

In [[Mathematics|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 [[Point (geometry)|point]]s and [[Line (geometry)|line]]s of the [[Euclidean plane]] as the two types of objects and ignore all the properties of this geometry except for the [[Heterogeneous relation|relation]] of which points are 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 plane (incidence geometry)|affine]], [[Projective plane|projective]], and [[Möbius plane]]s), 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 ([[Plane (mathematics)|plane]]s, [[Solid geometry|solid]]s, {{mvar|n}}-spaces, [[Conical surface|conics]], etc.) can be used. The study of finite structures is sometimes called [[Finite geometry|finite geometry]].<ref>{{harvnb|Colbourn|Dinitz|2007|page=702}}</ref>

==Formal definition and terminology==
An '''incidence structure''' is a triple ({{math|''P'', ''L'', ''I''}}) where {{mvar|P}} is a set whose elements are called ''points'', {{mvar|L}} is a distinct set whose elements are called ''lines'' and {{math|''I'' ⊆ ''P'' × ''L''}} is the [[Incidence (geometry)|incidence]] [[Heterogeneous relation|relation]]. The elements of {{mvar|I}} are called '''flags.''' If ({{math|''p'', ''l''}}) is in {{mvar|I}} then one may say that point {{mvar|p}} "lies on" line {{mvar|l}} or that the line {{mvar|l}} "passes through" point {{mvar|p}}. A more "symmetric" terminology, to reflect the symmetric nature of this relation, is that "{{mvar|p}} is ''incident'' with {{mvar|l}}" or that "{{mvar|l}} is incident with {{mvar|p}}" and uses the notation {{math|''p'' I ''l''}} synonymously with {{math|(''p'', ''l'') ∈ ''I''}}.<ref name=Demb1>{{harvnb|Dembowski|1968|pages=1–2}}</ref>

In some common situations {{mvar|L}} may be a set of subsets of {{mvar|P}} in which case incidence {{mvar|I}} will be containment ({{math|''p'' I ''l''}} if and only if {{mvar|p}} is a member of {{mvar|l}}). Incidence structures of this type are called ''set-theoretic''.<ref>{{harvnb|Biliotti|Jha|Johnson|2001|page=508}}</ref> This is not always the case, for example, if {{mvar|P}} is a set of vectors and {{mvar|L}} a set of [[Square matrix|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==
{{main|Incidence geometry}}

{{Gallery|title=Some examples of incidence structures|width=180|height=170|align=center|
File:Fano plane.svg|alt1=Fano plane|1. [[Fano plane]]|
File:Incidencestructure.svg|alt2=A non-uniform incidence structure|2. Non-uniform structure|
File:GQ(2,2), the Doily.svg|alt3=Generalized Quadrangle called the Doily|3. [[Generalized quadrangle]]|
File:Möbius–Kantor configuration.svg|alt4=8 point and 8 line configuration|4. [[Möbius–Kantor configuration]]|
File:Pappusconfig.svg|alt5=Configuration of Pappus theorem|5. [[Pappus configuration]] }}

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 (discrete mathematics)|graph]] (which need not be simple; [[Loop (graph theory)|loops]] and [[Multiple edges|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|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 (geometry)|linear space]]''.<ref>The term ''linear space'' is also used to refer to vector spaces, but this will rarely cause confusion.</ref><ref>{{harvnb|Moorhouse|2014|page=5}}</ref>

===Nets===
A more specialized example is a {{mvar|k}}'''-net'''.  This is an incidence structure in which the lines fall into {{mvar|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 {{mvar|k}}-net is the set of points of an [[Affine plane|affine plane]] together with {{mvar|k}} parallel classes of affine lines.

==Dual structure==

If we interchange the role of "points" and "lines" in
<math display="block">C = (P, L, I)</math>
we obtain the ''dual structure'',
<math display="block">C^* = (L, P, I^*)</math>
where {{math|''I''<sup>∗</sup>}} is the [[Converse relation|converse relation]] of {{mvar|I}}. It follows immediately from the definition that:
<math display="block">C^{**} = C</math>

This is an abstract version of [[Duality (projective geometry)|projective duality]].<ref name=Demb1 />

A structure {{mvar|C}} that is isomorphic to its dual {{math|''C''<sup>∗</sup>}} 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 a geometric terminology, but in [[Graph theory|graph theoretic]] terms they are called [[Hypergraph|hypergraph]]s and in design theoretic terms they are called [[Block design|block design]]s. They are also known as a ''set system'' or [[Family of sets|family of sets]] in a general context.

===Hypergraphs===
{{main|Hypergraph}}
[[File:Fano plane with nimber labels.svg|thumb|right|Seven points are elements of seven lines in the [[Fano plane|Fano plane]]]]
Each [[Hypergraph|hypergraph]] or set system can be regarded as an incidence
structure in which the [[Universal set|universal set]] plays the role of "points", the corresponding [[Family of sets|family of sets]] plays the role of "lines" and the incidence relation is [[Element (mathematics)|set membership]] "{{math|∈}}".  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===
{{main|Block design}}
A (general) block design is a set {{mvar|X}} together with a [[Family of sets|family {{mvar|F}} of subsets]] of {{mvar|X}} (repeated subsets are allowed). Normally a block design is required to satisfy numerical regularity conditions. As an incidence structure, {{mvar|X}} is the set of points and {{mvar|F}} is the set of lines, usually called ''blocks'' in this context (repeated blocks must have distinct names, so {{mvar|F}} is actually a set and not a multiset). If all the subsets in {{mvar|F}} have the same size, the block design is called ''uniform''. If each element of {{mvar|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:
<math display="block">\begin{align}
P &= \{1,2,3,4,5,6,7\}, \\[2pt]
L &= \left\{ \begin{array}{ll}
  \{1,2,3\}, & \{1,4,5\}, \\
  \{1,6,7\}, & \{2,4,6\}, \\
  \{2,5,7\}, & \{3,4,7\}, \\
  \{3,5,6\} \end{array} \right\}.
\end{align}</math>

This incidence structure is called the [[Fano 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 using nim addition. Alternatively, each number, when written in [[Binary number|binary]], can be identified with a non-zero vector of length three over the [[GF(2)|binary field]]. Three vectors that generate a [[Linear subspace|subspace]] form a line; in this case, that is equivalent to their vector sum being the zero vector.

==Representations==

Incidence structures may be represented in many ways. If the sets {{mvar|P}} and {{mvar|L}} are finite these representations can compactly encode all the relevant information concerning the structure.

===Incidence matrix===
{{main|Incidence matrix}}

The '''incidence matrix''' of a (finite) incidence structure is a (0,1) matrix that has its rows indexed by the points {{mvar|{p<sub>i</sub>} }} and columns indexed by the lines {{math|{''l<sub>j</sub>''} }} where the {{mvar|ij}}-th entry is a 1 if {{math|''p<sub>i</sub>'' I ''l<sub>j</sub>''}} and 0 otherwise.{{efn|The other convention of indexing the rows by lines and the columns by points is also widely used.}} An incidence matrix is not uniquely determined since it depends upon the arbitrary ordering of the points and the lines.<ref name=Beth17>{{harvnb|Beth|Jungnickel|Lenz|1986|page=17}}</ref>

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;"
|-
! {{math|I}} !! {{mvar|l}} !! {{mvar|m}} !! {{mvar|n}} !! {{mvar|o}} !! {{mvar|p}} !! {{mvar|q}}
|-
! {{mvar|A}}
| 0 || 0 || 0 || 1 || 1 || 0 
|-
! {{mvar|B}}
| 0 || 0 || 0 || 0 || 1 || 1 
|-
! {{mvar|C}}
| 1 || 0 || 0 || 0 || 0 || 0
|-
! {{mvar|D}}
| 0 || 0 || 1 || 0 || 0 || 0 
|-
! {{mvar|E}}
| 1 || 0 || 0 || 0 || 0 || 0 
|-
! {{mvar|P}}
| 1 || 1 || 1 || 1 || 0 || 1 
|}

If an incidence structure {{mvar|C}} has an incidence matrix {{mvar|M}}, then the dual structure {{math|''C''<sup>∗</sup>}} has the transpose matrix {{mvar|M}}<sup>T</sup> 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|symmetric matrix]].

With the labels as given in example number 1 above and with points ordered {{math|''A'', ''B'', ''C'', ''D'', ''G'', ''F'', ''E''}} and lines ordered {{math|''l'', ''p'', ''n'', ''s'', ''r'', ''m'', ''q''}}, 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.<ref name=Beth17 /> 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 with [[Ordered geometry|ordered 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 of [[Graph (discrete mathematics)|graphs]], 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.

====Realizability====
Incidence structures can be modelled by points and curves in the [[Euclidean plane]] with the usual geometric meaning of incidence. Some incidence structures admit representation by points and (straight) lines. Structures that can be are called ''realizable''. 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 the [[Complex plane|complex plane]].<ref>{{harvnb|Pisanski|Servatius|2013|page=222}}</ref> On the other hand, examples 2 and 5 above are realizable and the incidence figures given there demonstrate this. Steinitz (1894)<ref>E. Steinitz (1894), ''Über die Construction der Configurationen'' {{math|''n''<sub>3</sub>}}, Dissertation, Breslau</ref> has shown that {{nowrap|{{math|''n''<sub>3</sub>}}-configurations}} (incidence structures with {{mvar|n}} points and {{mvar|n}} 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.<ref>{{citation|first=Harald|last=Gropp|title=Configurations and their realizations|journal=Discrete Mathematics|year=1997|volume=174|pages=137–151|doi=10.1016/s0012-365x(96)00327-5|doi-access=free}}</ref> The Fano plane is the unique ({{math|7<sub>3</sub>}}) and the Möbius–Kantor configuration is the unique ({{math|8<sub>3</sub>}}).

=== Incidence graph (Levi graph) ===
[[Image:Fano plane-Levi graph.svg|thumb|[[Heawood graph|Heawood graph]] with labeling]]
Each incidence structure {{mvar|C}} corresponds to a [[Bipartite graph|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 [[Graph coloring|vertex coloring]], where black vertices correspond to points and white vertices correspond to lines of {{mvar|C}}. 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|generalized quadrangle]] of order two (example 3 above),<ref>{{citation  | last = Levi | first = F. W. |  location = Calcutta  | mr = 0006834  | publisher = University of Calcutta  | title = Finite Geometrical Systems  | year = 1942}}</ref> but the term has been extended by H.S.M. Coxeter<ref>{{citation|first=H.S.M.|last=Coxeter|author-link=H.S.M. Coxeter|title=Self-dual configurations and regular graphs|journal=Bulletin of the American Mathematical Society|volume=56|year=1950|pages=413–455|doi=10.1090/s0002-9904-1950-09407-5|doi-access=free}}</ref> to refer to an incidence graph of any incidence structure.<ref name=Pisanski158>{{harvnb|Pisanski|Servatius|2013|page=158}}</ref>
[[File:Möbius–Kantor unit distance.svg|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|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 {{math|{{pi}}/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.

==Generalization==
It is possible to generalize the notion of an incidence structure to include more than two types of objects. A structure with {{mvar|k}} types of objects is called an ''incidence structure of rank'' {{mvar|k}} or a ''rank'' {{mvar|k}} ''geometry''.<ref name=Pisanski158 /> Formally these are defined as {{math|''k'' + 1}} tuples {{math|1= ''S'' = (''P''<sub>1</sub>, ''P''<sub>2</sub>, ..., ''P''<sub>k</sub>, ''I'')}} with {{math|1=''P''<sub>''i''</sub> ∩ ''P''<sub>''j''</sub> = ∅}} and
<math display="block">I \subseteq \bigcup_{i < j} P_i \times P_j.</math>

The Levi graph for these structures is defined as a [[Multipartite graph|multipartite graph]] with vertices corresponding to each type being colored the same.

==See also==

*[[Incidence (geometry)]]
*[[Incidence geometry]]
*Projective configuration
*[[Abstract polytope]]

==Notes==
{{reflist|group=lower-alpha}}

==References==
{{reflist}}

==Bibliography==
* {{citation|first1=Thomas|last1=Beth|first2=Dieter|last2=Jungnickel|first3=Hanfried|last3=Lenz|title=Design Theory|year=1986|publisher=Cambridge University Press|isbn=3-411-01675-2|url-access=registration|url=https://archive.org/details/designtheory0000beth}}
* {{citation|first1=Mauro|last1=Biliotti|first2=Vikram|last2=Jha|first3=Norman L.|last3=Johnson|year=2001|title=Foundations of Translation Planes|publisher= Marcel Dekker|isbn=0-8247-0609-9}}
* {{citation|last1=Colbourn|first1=Charles J.|last2=Dinitz|first2=Jeffrey H.|title=Handbook of Combinatorial Designs|year=2007|publisher=Chapman & Hall/ CRC|location=Boca Raton|isbn=1-58488-506-8|edition=2nd|url-access=registration|url=https://archive.org/details/handbookofcombin0000unse}}
* {{Citation | last1=Dembowski | first1=Peter | title=Finite geometries | publisher=[[Physics:Springer-Verlag|Springer-Verlag]] | location=Berlin, New York | series=Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44 | mr=0233275 | year=1968 | isbn=3-540-61786-8 | url-access=registration | url=https://archive.org/details/finitegeometries0000demb }}
* {{cite web |first=G. Eric |last=Moorhouse |date=2014 |title=Incidence Geometry |url=http://math.ucr.edu/home/baez/qg-fall2016/incidence_geometry.pdf |via=John Baez at [[Organization:University of California, Riverside|University of California, Riverside]]}}
* {{citation|first1=Tomaž|last1=Pisanski|first2=Brigitte|last2=Servatius|title=Configurations from a Graphical Viewpoint|year=2013|publisher=Springer|isbn=978-0-8176-8363-4|doi=10.1007/978-0-8176-8364-1}}

==Further reading==
* 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


[[Category:Combinatorics]]
[[Category:Finite geometry]]
[[Category:Incidence geometry]]

{{Sourceattribution|Incidence structure}}