This page is an entry in an

Encyclopedia of Combinatorial Polytope Sequences



Back to big table.

Acyclic subgraph polytope

(No 3d term.)
[polymake for n=3]

• Acyclic subgraph polytopes P_AC [ULB] (S. Fiorini)
[springer] (M. Grötschel, M. Jünger, G. Reinelt),
[MIT] (M. Goemans, L. Hall)
• convex_hull({char_vector_AC | AC an acyclic subgraph of complete digraph on n nodes})
• Dicycle covering polytope P_DC [ULB] (S. Fiorini)
• convex_hull({<1,...,1> - char_vector_AC | AC an acyclic subgraph of complete digraph on n nodes})
• Dimensions:
0, 2, 6, 12, ... n(n-1)
• Numbers of vertices in nth polytope:
1, 3, 25, 543, 29281, ... [ OEIS A003024]
• Facets:
0, 3, 11 ... OPEN [ OEIS ?]
• f-vectors:
1, 3, 3, 1, 25, 93, 142, 111, 48, 11, 1, ... [ OEIS ?]
top    index