Adjacency of vertices of the complete pre-order polytope

AbstractA complete pre-order (c.p.o.) on a finite set V is a relation on V that is transitive and total. We define the c.p.o. polytope Pn as the convex hull of the incidence vectors of all c.p.o.'s on a set with n elements. We study the adjacency relation of the vertices of the c.p.o. polytope Pn, n ⩾ 3. The main results are: (1) if A, B are c.p.o.ś with vbAΔBvb = 2, then xA and xB are adjacent in Pn if and only if the digraph induced by AΔB is connected; (2) if A ⊆ B are c.p.o.'s then xA and xB are adjacent in Pn if and only if the digraph induced by B 0–2 is connected; (3) the diameter of the c.p.o. polytope is equal to 2