Incidence structure
From Wikipedia, the free encyclopedia
In combinatorial mathematics, an incidence structure is a triple
where P is a set of "points", L is a set of "lines" and 
is the incidence relation. The elements of I are called flags. If
we say that point p "lies on" line ℓ.
Contents |
[edit] Comparison with other structures
A figure may look like a graph, but in a graph an edge has just two ends (beyond a vertex a new edge starts), while a line in an incidence structure can be incident to more points.
An incidence structure has no concept of a point being in between two other points; the order of points on a line is undefined.
[edit] Dual structure
If we interchange the role of "points" and "lines" in
the dual structure
is obtained, where I* is the inverse relation of I. Clearly
A structure C that is isomorphic to its dual C* is called self-dual.
[edit] Correspondence with hypergraphs
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.
[edit] Example: Fano plane
In particular, let
- P = {1, 2, 3, 4, 5, 6, 7},
- L = { {1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1}, {6,7,2}, {7,1,3} }.
The corresponding incidence structure is called the Fano plane.
[edit] 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.
[edit] Levi graph of an incidence structure
Each incidence structure C corresponds to a bipartite graph called Levi graph or incidence graph with a given black and white vertex coloring where black vertices correspond to points and white vertices correspond to lines of C and the edges correspond to flags.
[edit] Example: Heawood graph
For instance, 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 above figure) interchanging black and white vertices. This, in turn, implies that the Fano plane is self-dual.
[edit] See also
- Binary relation
- Incidence matrix
- Incidence (geometry)
- Projective configuration
- Pappus configuration
- Hypergraph
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (December 2007) |
