Saturday, March 12, 2016

Incidence order of graphs

The incidence order of a graph is a type of partial order that forbids three different partial orders [1 1 1], [2 2], and [3 1]. If these three partial orders are forbidden as suborders then the partial order may be embedded in the incidence order of a graph. This defines the suborder closure of the class of incidence orders of graphs. In order for a partial order to be an incidence order of a graph all of its non-minimal elements must also have exactly two parts.

If this final condition is met then the join representations of the partial order correspond to a dependency family. There is a complementary condition produced by the transposition of the incidence order of a graph. Only those graphs which have locally at most two elements meet this suborder condition in their transposition. All graphs can be produced from the join representations of a partial order that meets these conditions.