Incidence structure
Encyclopedia
In 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
. One may concretely have L be a set of subsets of P, and have incidence I be containment (
if and only if 
), but one may also work more abstractly.
Incidence structures generalize planes (such as affine
, projective
, and Möbius plane
s) in their axiomatic definitions, as the terminology indicates. The higher-dimensional analog is called an incidence geometry.
, 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. Compare with ordered geometry
, which does have a notion of betweenness.
the dual structure
is obtained, where I* is the inverse relation
of I. Clearly
This is an abstract version of projective duality
.
A structure C that is isomorphic to its dual
C* is called self-dual.
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.
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.
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.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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. Ifwe say that point p "lies on" line
. One may concretely have L be a set of subsets of P, and have incidence I be containment ( if and only if ), but one may also work more abstractly.Incidence structures generalize planes (such as affine
Affine plane (incidence geometry)
In incidence geometry, an affine plane is a system of points and lines that satisfy the following axioms :* Any two distinct points lie on a unique line.* Given a point and line there is a unique line which contains the point and is parallel to the line...
, projective
Projective
-About :Projective provides project management services for financial institutions. According to the firm's website, Projective currently has three branches . The headquarter is located in Kontich, Belgium...
, and Möbius plane
Möbius plane
A Möbius plane or inversive plane is a particular kind of plane geometry, built upon some affine planes by adding one point, called the ideal point or point at infinity. In a Möbius plane straight lines are a special case of circles; they are the circles that pass through the ideal point. Möbius...
s) in their axiomatic definitions, as the terminology indicates. The higher-dimensional analog is called an incidence geometry.
Comparison with other structures
A figure may look like a graphGraph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, 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. Compare with ordered geometry
Ordered geometry
Ordered geometry is a form of geometry featuring the concept of intermediacy but, like projective geometry, omitting the basic notion of measurement...
, 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
Inverse relation
In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...
of I. Clearly
- C**=C.
This is an abstract version of projective duality
Duality (projective geometry)
A striking feature of projective planes is the "symmetry" of the roles played by points and lines in the definitions and theorems, and duality is the formalization of this metamathematical concept. There are two approaches to the subject of duality, one through language and the other a more...
.
A structure C that is isomorphic to its dual
Dual
Dual may refer to:* Dual , a notion of paired concepts that mirror one another** Dual , a formalization of mathematical duality** . . ...
C* is called self-dual.
Correspondence with hypergraphs
Each hypergraphHypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
or set system can be regarded as an incidence
structure in which the universal set
Universal set
In set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, the conception of a set of all sets leads to a paradox...
plays the role of "points", the corresponding family of sets
Family of sets
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a 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 = {1, 2, 3, 4, 5, 6, 7},
- L = { {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6} }.
The corresponding incidence structure is called the Fano plane
Fano plane
In finite geometry, the Fano plane is the finite projective plane with the smallest possible number of points and lines: 7 each.-Homogeneous coordinates:...
.
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
Each incidence structure C corresponds to a bipartiteBipartite
Bipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:-Mathematics:* 2 * bipartite graph* bipartite cubic, a type of cubic function-Medicine:...
graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
called Levi graph
Levi graph
In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure. From a collection of points and lines in an incidence geometry or a projective configuration, we form a graph with one vertex per point, one vertex per line, and an edge for...
or incidence graph with a given black and white vertex coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
where black vertices correspond to points and white vertices correspond to lines of C and the edges correspond to flags.
Example: Heawood graph
For instance, the Levi graph of the Fano planeFano plane
In finite geometry, the Fano plane is the finite projective plane with the smallest possible number of points and lines: 7 each.-Homogeneous coordinates:...
is the Heawood graph
Heawood graph
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.-Combinatorial properties:...
. Since the Heawood graph is connected
Connected space
In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint nonempty open subsets. Connectedness is one of the principal topological properties that is used to distinguish topological spaces...
and vertex-transitive
Vertex-transitive
In geometry, a polytope is isogonal or vertex-transitive if, loosely speaking, all its vertices are the same...
, 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
Fano plane
In finite geometry, the Fano plane is the finite projective plane with the smallest possible number of points and lines: 7 each.-Homogeneous coordinates:...
is self-dual.
See also
- Binary relationBinary relationIn mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
- Incidence matrixIncidence matrixIn mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related ...
- Incidence (geometry)Incidence (geometry)In geometry, the relations of incidence are those such as 'lies on' between points and lines , and 'intersects' . That is, they are the binary relations describing how subsets meet...
- Projective configuration
- Pappus configuration
- HypergraphHypergraphIn mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...