Incidence geometry

(Redirected from Incidence system)

An incidence geometry or Buekenhout geometry is a type of combinatorial structure comprising a typed set of elements with an incidence relation describing how they are connected. Incidence geometries are highly general and encompass abstract polytopes, configurations, hypertopes, generalized polygons, and many other concepts.

Definition

Incidence system

An incidence system is a tuple ${\displaystyle (X,*,t,I)}$ where

• X  is a set whose members are called elements.
• I  is a finite set whose members are called types. (Types generalize the notion of rank in polytopes, or the distinction between nodes and edges in a graph.)
• ${\displaystyle t:X\rightarrow I}$ is a type function, mapping each element to a type.
• *  is a binary relation on X  called incidence. If ${\displaystyle x*y}$ is true, we say that x  and y  are incident. The relation must obey three properties:
• ${\displaystyle \forall x.x*x}$ (reflexivity)
• ${\displaystyle \forall x,y.x*y\iff y*x}$ (symmetry)
• ${\displaystyle \forall x,y.x*y\land t(x)=t(y)\implies x=y}$. This states that two distinct elements of the same type cannot be incident (for example, in a graph, two vertices are not considered incident).

In the context of incidence system a flag is a set of elements, F , such that any two elements in F  are incident. This is a distinct notion from the flag of a polytope. It follows from the final condition on the incidence relation that all the types of elements in a flag must be distinct.

A chamber is a flag, F , such that ${\displaystyle t(F)=I}$ (using the image). In a chamber, every type is represented exactly once.

Incidence geometry

An incidence geometry is an incidence system such that every flag is a subset of some chamber. In other words, every maximal clique in the incidence graph has type ${\displaystyle I}$. A necessary but not sufficient condition is that every element must be incident on elements of every other type.

Incidence structure

A incidence system with two types is called an incidence structure. Incidence structures in general are too broad of a category to make them interesting objects of study on their own, but several subclasses of incidence structures have interesting behavior:

If every element in an incidence structure is incident on at least one other distinct element, then it is also an incidence geometry. For example, a graph is an incidence geometry iff every vertex has a degree of at least 1.

An incidence structure may be defined more simply as a triple ${\displaystyle \left(P,L,I\right)}$ where P  is a set of vertices, L  is a set of edges and I  is an incidence relation. Some authors require that I  is symmetric, however this is only required of you do not require I  to be typed.

Examples

Abstract polytopes

Every abstract polytope is an incidence geometry.

• The element set are the elements of the abstract polytope.
• The incidence relation is incidence.
• The type function is the rank of each element.
• The chambers are flags of the abstract polytope.