Editing Incidence structure (section)

==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]].

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]], 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]].<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|issue=1–3 |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]] with labeling]]
Each incidence structure {{mvar|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 [[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]] of order two (example 3 above),<ref>{{citation  | last = Levi | first = F. W. | author-link = Friedrich Wilhelm Levi  | 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|issue=5 |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 graph|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 {{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.