In mathematics, an incidence poset or incidence order is a type of
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...
that represents the
incidence relation
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...
between vertices and edges of an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
. The incidence poset of a graph ''G'' has an element for each vertex or edge in ''G''; in this poset, there is an order relation ''x'' ≤ ''y'' if and only if either ''x'' = ''y'' or ''x'' is a vertex, ''y'' is an edge, and ''x'' is an endpoint of ''y''.
Example
As an example, a
zigzag poset
In mathematics, a fence, also called a zigzag poset, is a partially ordered set (poset) in which the order relations form a path with alternating orientations:
:acehbdfi \cdots
A fence may be finite, or it may be formed by an infinite alternatin ...
or ''fence'' with an odd number of elements, with alternating order relations ''a'' < ''b'' > ''c'' < ''d''... is an incidence poset of a
path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
.
Properties
Every incidence poset of a non-empty graph has
height
Height is measure of vertical distance, either vertical extent (how "tall" something or someone is) or vertical position (how "high" a point is).
For example, "The height of that building is 50 m" or "The height of an airplane in-flight is abou ...
two. Its width equals the number of edges plus the number of acyclic connected components.
Incidence posets have been particularly studied with respect to their
order dimension
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order.
This concept is also sometimes called the order dimension or the Dushnik–Miller d ...
, and its relation to the properties of the underlying graph. The incidence poset of a connected graph ''G'' has order dimension at most two if and only if ''G'' is a path graph, and has order dimension at most three if and only if ''G'' is at most planar (
Schnyder's theorem
In graph theory, Schnyder's theorem is a characterization of planar graphs in terms
of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in 1989.
The incidence poset of an undirected graph ...
). However, graphs whose incidence posets have order dimension 4 may be
dense
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
and may have unbounded
chromatic number
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 o ...
. Every complete graph on ''n'' vertices, and by extension every graph on ''n'' vertices, has an incidence poset with order dimension ''O''(log log ''n''). If an incidence poset has high dimension then it must contain copies of the incidence posets of all small trees either as sub-orders or as the duals of sub-orders.
[.]
References
{{reflist
Graph theory
Order theory