Encyclopedia of Combinatorial Polytope Sequences...
...but it has a ways to go. Send entry suggestions to:
Entry Editor
(4, 0, 0, 0) |
Simplices Δ [wiki] Order polytope O(P) for P the linear order on {1,...,n}. [citeseer](R.Stanley) Chain polytope C(P) for P the linear order on {1,...,n}. [citeseer](R.Stanley) Poset associahedra for antichain [arxiv] Vertex cover polytope of the complete graph VC(K_n) [wiki] edgeless-graph-associahedra [arxiv] (S. Devadoss) (n+1)-cycle-graph graphic matroid polytopes [wiki] Uniform matroid U^n_(n+1) polytope [wiki] |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 3, 4, 5, ... n+1 [ OEIS A000027 ] Numbers of facets in dimension n (starting at n=0): 0, 2, 3, 4, 5, ... n+1 [ OEIS A000027 ] f-vectors: 1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 10, 5, 1, ... [ OEIS A135278] |
(4, 0, 0, 0) |
Demihypercubes; [wiki] n-demicubes, n-hemicubes convex_hull({alternating vertices of n-cube}) |
Dimensions: 1, 3, 4, ... n Number of Vertices in nth polytope: 2, 4, 8, 16 ... 2^n [ OEIS A000079] Numbers of facets in dimension n 2, 4, 16, 26, 44, 78,... 2^(n-1)+2n [ OEIS ?] f-vectors: 1, 2, 1, 4, 6, 4, 1, 8, 24, 32, 16, 1, 16, 80,... [ OEIS ?] |
(4, 0, 0, 0) [polymake for n=4] |
Cut Polytopes of complete graph CUT(n)= P_C(K_n) [Springer] (Barahona, Mahjoub)[SMAPO library] Correlation Polytopes COR(n) convex_hull({incidence_vector_F | F a cut of the complete graph on n nodes}) |
Dimensions: 1, 3, 6, 10, 15,... (n choose 2) [ OEIS A000217] Number of Vertices in nth polytope: 2, 4, 8, 16, 32 ... 2^(n-1) [ OEIS A000079] Number of Facets: 2, 4, 16, 56, 368, 116764, ... OPEN [ OEIS A235459] f-vectors: 1, 2, 1, 4, 6, 4, 1, 8, 28, 56, 68, 48, 16, 1... [ OEIS ?] |
(4, 0, 0, 0) [polymake for n=5,6] |
Flow Polytopes of complete graph FLOW(n)= F(K_n) [arxiv] (Mιszαros, Morales, Striker) Chan-Robbins-Yuen Polytopes CRY(n-1) convex_hull({incidence_vector_F | F a unit flow of the complete graph on n nodes}) Volume equals product of the first n - 2 Catalan numbers |
Dimensions: 1, 3, 6, 10, 15,... (n-1 choose 2) [ OEIS A000217] Number of Vertices in nth polytope: 2, 4, 8, 16, 32 ... 2^(n-2) [ OEIS A000079] Number of Facets: 2, 4, 8, 13 ... OPEN [ OEIS ?] f-vectors: 1, 2, 1, 4, 6, 4, 1, 8, 26, 45, 45, 26, 8, 1, 16, 98, 327, 681, 944, 897, 588, 262, 76, 13... [ OEIS ?] |
(4, 0, 0, 0) [polymake for n=4] |
Matching Polytopes of complete graph MATCH(n)= M(K_n) [wiki] convex_hull({incidence_vector_M | M a general matching of the complete graph on n nodes}) [imsc](M. Mahajan) |
Dimensions: 0, 1, 3, 6, 10, 15,... (n choose 2) [ OEIS A000217] Number of Vertices in nth polytope: 1, 2, 4, 10, 26, 76, 232, 764... Sum_{k=0..[ n/2 ]} n!/((n-2*k)!*2^k*k!) [ OEIS A000085] Number of Facets: 2, 4, 14... OPEN [ OEIS ?] f-vectors: 1, 2, 1, 4, 6, 4, 1, 10, 39, 78, 86, 51, 14,... [ OEIS ?] |
(0, 6, 0, 0) |
Cubes C [wiki] Order polytope O(P) for P the poset with no relations on n elements (antichain with n elements). [citeseer](R.Stanley) Chain polytope C(P) for P the poset with no relations on n elements (antichain with n elements). [citeseer](R.Stanley) Lipschitz polytope L(P) for P an antichain.[Sanyal and Stump] Lipschitz polytope L(P) for P a chain. Stanley-Pitman polytopes [arxiv] (Postnikov, Reiner, Williams) Acyclotopes, or graphical zonotopes, for graphs that are forests. [ Zaslavsky],[Postnikov] Voronoi cells of cographical lattice for tree graphs (primary parallelohedra, primary parallelotopes) [F. Vallentin] Brillouin zone (Wigner-Seitz cell of reciprocal space) for Simple Cubic lattice in 3d [wiki] Poset associahedra for cross-stack posets [arxiv] |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 4, 8, 16, ... 2^n [ OEIS A000079 ] Number of Facets (start at n=0): 0, 2, 4, 6, 8 ... 2*n [ OEIS A004277] f-vectors: 1, 2, 1, 4, 4, 1, 8, 12, 6, 1, 16, ... [ OEIS A038207] |
(4, 3, 0, 0) |
Uniform matroid U^(n-1)_n independent set polytope [arxiv] (Ardila, Benedetti, Doker) n-cycle-graph graphic matroid independent set polytopes [wiki] |
Dimensions: 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 3, 7, 15, ... 2^n - 1 [ OEIS A000225] Number of Facets (start at n=0): 0, 0, 3, 7, ... |
(4, 3, 0, 0) |
Bipartite Subgraph Polytopes of the complete graph P_B(K_n) = BS(n) [jstor](F. Barahona, M. Grφtschel, A. Mahjoub) [SMAPO library(large subgraphs only)] |
Dimensions: 0, 1, 3, 6, 10 ... (n choose 2) Number of Vertices in nth polytope: 1, 2, 7, 41, 376, ... [ OEIS A047864] Number of Facets (start at n=1): 0, 2, 7, ... |
(1, 3, 3, 0) |
Edgeless-graph cubeahedra [arxiv] (Devadoss, Heath, Vipismakul) Range quotient of edgeless-graph multiplihedron JGr [arxiv] (Devadoss, Forcey) |
Dimensions: 1, 2, 3, ... n Number of Vertices in nth polytope: 2, 5, 10, ... 2^n + n-1 [ OEIS A052944 ] Number of Facets (start at n=0): 0, 2, 5, 7, 9, ... 2*n + 1 [ OEIS A130773 ] |
(8, 0, 0, 0) |
Linear ordering polytopes P_LO [zib.de] (M. Grφtschel, M. Jόnger, G. Reinelt), [citeseer] (T. Christof, G. Reinelt), [arxiv] (Katthδn), [SMAPO library] Binary choice polytopes convex_hull({char_vector_LO | LO a linear order with n elements}) |
Dimensions: 0, 1, 3, 6, 10, ... (n choose 2) Number of Vertices in nth polytope: 1, 2, 6, 24, ... n! [ OEIS A000142][see: i, ii, iii] Number of Facets: 0, 2, 8, 20, 40, 910, 87472 ... OPEN [ OEIS ?] f-vectors: 1, 2, 1, 6, 12, 8, 1, 24, ... [ OEIS ?] |
[polymake for n=4] |
Huffmanhedra, Huffman polytopes HP(n) [ResearchGate] (J. Maurras, T. Nguyen, V. Nguyen)DOI: 10.1016/j.dam.2012.05.004) convex_hull({char_vector_t | t a Huffman tree with n leaves}) |
Dimensions: 0, 2, 4, 5, 6, ... n Number of Vertices in nth polytope: 1, 1, 3, 13, 75, ... OPEN [ OEIS ?] Number of Facets: 0, 3, 9, ... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 13, 30, 26, 9, 1, ... [ OEIS ?] |
(0, 4, 4, 0) |
Freehedra F [arxiv] (Saneblidze) Hochschild polytope. |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 2, 5, 12, 28, 64, 144, 320, 704...(n+3)*2^(n-2) [Conj. OEIS A045623] (F. Chapoton) Number of Facets: 0, 2, 5, 8, 11 ... 3*n - 1 [ OEIS A016789] |
( 0, 3, 6, 0) |
Associahedra K, Y [claymath] (J.L. Loday) Stasheff polytopes Type A associahedra [arxiv] (Fomin, Reading) Secondary polytope of the set of vertices of a polygon [maa review] (Gelfand, Kapranov, Zelevinsky) Newton polytope of the discriminant polynomial of the (integer coordinate) vertices of a polygon. Fiber polytope of the simplex over a polygon. [jstor] (Billera, Sturmfels) Path graph associahedra [arxiv] (Carr, Devadoss) Path graph cubeahedra [arxiv] (Devadoss, Heath, Vipismakul) Zig-zag poset associahedra [arxiv] (Devadoss et.al.) (1,n) biassociahedra KK(n,1), KK(1,n) [arxiv] (Saneblidze, Umble) alt. notation B^n_1, B^1_n [arxiv] (Markl) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 5, 14, 42, ... Catalan numbers [ OEIS A000108] Number of Facets: 0, 2, 5, 9, 14, ... Triangular numbers minus one [ OEIS A000096 ] f-vectors: 1, 2, 1, 5, 5, 1, 14, 21, 9, 1, 42, 84, 56, 14, 1, ... [ OEIS A033282] h-vectors: 1, 3, 1, 1, 6, 6, 1, 1, 10, 20, 10, 1, 1, 15, 50, 50, 15, 1... [ OEIS A001263] |
( 0, 3, 6, 0) |
Type D associahedra [arxiv] (Fomin, Reading) [arxiv] (Ceballos, Pilaud) |
Dimensions: 2, 3, ... n Number of Vertices in nth polytope: 4, 14, 50, 182 ... (3n-2)*C(n-1), where C is Catalan numbers [ OEIS A051924] Number of Facets: 4, 9, 16, 25 ... conjecture n^2 [ OEIS A000290] f-vectors: 1, 4, 4, 1, 14, 21, 9, 1, 50, 100, 66, 16, 1, ... [ OEIS A080721] |
(0, 4, 6, 0) |
Composihedra CK [arxiv] (Forcey) Path-graph composihedra [arxiv] (Devadoss, Forcey) (in low dimensions) pasting diagrams of pseudomonoids in monoidal 2-categories [TAC] (P. McCrudden) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 5, 15, 51, ... binomial transform of Catalan numbers [ OEIS A007317] Number of Facets: 0, 2, 5, 10, 19 ... 2^n+n-1 [ OEIS A052944] |
(0, 3, 6, 1) |
Halohedra H [arxiv] (Devadoss, Heath, Vipismakul) Cycle-cubeahedra [arxiv] (Devadoss, Forcey) |
Dimensions: 1, 2, 3, ... n Number of Vertices in nth polytope: 2, 5, 16, ... OPEN [ OEIS ?] Number of Facets: 0, 2, 5, 10, 17, ... n^2+1 [ OEIS A002522] |
(0, 3, 6, 1)** |
Cycle-composihedra JGd [arxiv] (Devadoss, Forcey) |
Dimensions: 1, 2, 3, ... n Number of Vertices in nth polytope: 2, 5, 16, ... OPEN [ OEIS ?] Number of Facets: 0, 2, 5, 10, ... OPEN [ OEIS ?] |
(0, 3, 6, 1) |
Stellohedra S [arxiv] (Postnikov, Reiner, Williams) Secondary polytopes of pairs of nested concentric n-dimensional simplices. [arxiv] (V. Pilaud, T. Manneville) Star-graph associahedra [arxiv] (Carr, Devadoss) complete-graph-cubeahedra [arxiv] (Devadoss, Heath, Vipismakul) complete-graph-composihedra JGd [arxiv] (Devadoss, Forcey) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 5, 16, 65, ... Sum_{k=0..n} n!/k! [ OEIS A000522][see: i] Number of Facets: 0, 2, 5, 10, 19, 36, ... 2^n + n - 1 [ OEIS A052944 ] (Thanks to P. Showers) f-vectors: 1, 2, 1, 5, 5, 1, 16, 24, 10, 1, 65, 130, ... [ OEIS A248727] (Thanks to Tom Copeland) h-vectors: 1, 3, 1, 1, 7, 7, 1, 1, 15, 33, 15, 1, 1, 31, 131, 131, 31, 1, ...[ OEIS A046802] (Thanks to Tom Copeland) |
(1, 6, 3, 0) |
Edgeless-graph-composihedra JGd [arxiv] (Devadoss, Forcey) |
Dimensions: 1, 2, 3, ... n Number of Vertices in nth polytope: 2, 5, 13, ... OPEN [ OEIS ?] Number of Facets: 0, 2, 5, 10, ... OPEN [ OEIS ?] |
(2, 6, 0, 3) |
Edgeless-graph-multiplihedra JG [arxiv] (Devadoss, Forcey) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 15, 36, ... n*2^(n-1) + n [ OEIS A215149] Number of Facets: 0, 2, 6, 11, 20, ... 2^n + n [ OEIS ?] |
(0, 4, 4, 4) |
Cyclohedra W [arxiv] (M. Markl) Bott-Taubes polytopes Type B,C associahedra [arxiv] (S. Fomin, N. Reading)(R. Simion) cycle-graph-associahedra [arxiv] (S. Devadoss) (in low dimensions) hexagonator equations (pasting diagrams) in braided monoidal categories [arxiv] (M. Stay) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 20, 70, ... central binomial coefficients [ OEIS A000984] Number of Facets: 0, 2, 6, 12, 20, ... n^2+n [ OEIS A002378] f-vectors: 1, 2, 1, 6, 6, 1, 12, 30, 20, 1, 20, 90, 140, ... [ OEIS A063007] |
(0, 14, 0, 0) |
Acyclotopes for cycle graph A(G) [ Zaslavsky] Graphical zonotopes for cycle graph Z(G) [Postnikov] Voronoi cells of cographical lattice for cycle graphs (primary parallelohedra, primary parallelotopes) [F. Vallentin] Brillouin zone (Wigner-Seitz cell of reciprocal space) for Body Centered Cubic lattice in 3d [wiki] |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 14, 30, ... acyclic orientations of (n+1)-cycle = 2^(n+1) - 2 [ OEIS A000918] Number of Facets: 0, 2, 6, 12, 20, ... directed edge cuts of the (n+1)-cycle = n^2+n [ OEIS A002378] |
(0, 6, 2, 5) |
Multiplihedra J, M [arxiv] (Forcey) Step 1 Biassociahedra K^2_n [arxiv](M. Markl) (in low dimensions) trihomomorphism axioms (pasting diagrams) in tricategories [books] (Gordon, Power, Street) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 21, 80, ... Catalan transform of Catalan numbers [ OEIS A121988] Number of Facets: 0, 2, 6, 13, 25, 46, ... n(n + 1)/2+ 2^n - 1. [ OEIS ?][see: i] |
(0, 5, 2, 6)** |
(2,n)-Brick Polytopes B^2(n) [arxiv](V. Pilaud) convex hulls of the brick vectors of all (2, n)-twists Brick Polytopes of the 2-kernels of (size n) bubble sort networks Omega(B^2_(n+4)) [arxiv](V. Pilaud, F. Santos) |
Dimensions: 0, 1, 2, 3, ... n-1 Number of Vertices in nth polytope: 1, 2, 6, 22, 92, 420, 2042, ... [ OEIS conjecture A264868] Number of Facets: 0, 2, 6, 13, 25, 45, 78, 132, ... [ OEIS A065220] f-vectors: 1, 2, 1, 6, 6, 1, 22, 33, 13, 1, 92, 185, 118, 25, 1, 420, 1062, 945, 346, 45, ... [ OEIS ?] |
(0, 5, 2, 6) |
Pterahedra P_t [L. Berry] fan-graph-associahedra [arxiv] (S. Devadoss) |
Dimensions: 0, 1, 2, 3, ... n-1 Number of Vertices in nth polytope: 1, 2, 6, 22, 94, 464, ... Catalan transform of the factorials [ OEIS ?] Number of Facets: 0, 2, 6, 13, 25, 46, ... n(n + 1)/2+ 2^n - 1. [ OEIS ?][see: i] f-vectors: 1, 2, 1, 6, 6, 1, 22, 33, 13, 1, 94, ... [ OEIS ?] |
(0, 6, 0, 8) |
(Type A) Permutohedra/ permutahedra P, S [wiki] Secondary polytopes of the prisms of simplices. [e-book] (Gelfand, Kapranov, Zelevinsky) complete-graph-associahedra [arxiv] (S. Devadoss) complete-graph-multiplihedra [arxiv] (Devadoss, Forcey) Step 1 Bipermutohedra P^n_m [arxiv](M. Markl)[arxiv](S.Saneblidze, R. Umble) Step 1 Biassociahedra K(n,m) = K^n_m [arxiv](M. Markl)[arxiv](S.Saneblidze, R. Umble) Acyclotopes for complete graphs A(K_n) [ Zaslavsky] Graphical zonotopes for complete graphs Z(K_n) [Postnikov] Zonotopes polar to the braid arrangements. Fiber polytopes of unit cubes over line segments. Voronoi cells of cographical lattice for complete graphs (primary parallelohedra, primary parallelotopes) [F. Vallentin] Brillouin zone (Wigner-Seitz cell of reciprocal space) for Face Centered Cubic lattice in 3d [wiki] Poset-associahedra for antichain with minimal element adjoined [arxiv] 1-skeleton is Cayley graph for symmetric group, using transpositions.[wiki] |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 24, 120, ... n! [ OEIS A000142][see: i, ii, iii] Number of Facets: 0, 2, 6, 14, 30 ... 2^(n+1) -2 [ OEIS A000918] f-vectors: 1, 2, 1, 6, 6, 1, 24, 36, 14, 1, ... [ OEIS A019538] h-vectors: 1, 4, 1, 1, 11, 11, 1, 1, 26, 66, 26, 1, ... [ OEIS A008292] |
(0, 6, 0, 8) |
Type D permutohedra PD [zib.de] (Reiner, Ziegler) |
Dimensions: 2, 3, ... n Number of Vertices in nth polytope: 4, 24, 192, ... 2^(n-1)*n! [ OEIS A002866] Number of Facets: 4, 14, 48, ... 3^n - n*2^(n-1) - 1 [ OEIS ?] (Thanks N. Reading) f-vectors: 1, 4, 4, 1, 24, 36, 14, 1, 192, 384, 240, 48, 1,... [ OEIS A145902] |
(0, 6, 0, 8)** |
Cycle-multiplihedra JG [arxiv] (Devadoss, Forcey) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 24, 104, ... OPEN [ OEIS ?] Number of Facets: 0, 2, 6, 14, 28, ... OPEN [ OEIS ?] |
(0, 6, 0, 8)** |
(3,n)-Brick Polytopes B^3(n) [arxiv](V. Pilaud) convex hulls of the brick vectors of all (3, n)-twists Brick Polytopes of the 3-kernels of (size n) bubble sort networks Omega(B^3_n) [arxiv](V. Pilaud, F. Santos) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 24, 114, 612, 3600, ... OPEN [ OEIS ?] Number of Facets: 0, 2, 6, 14, 29, 57, 109, ... OPEN [ OEIS ?] |
(0, 6, 4, 4) |
Diagonal rectangulation polytopes [arxiv] (Law, Reading) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 6, 22, 92, ... Baxter permutations [ OEIS A001181] Number of Facets: 0, 2, 6, 14, 30 ... 2^(n+1) -2 [ OEIS A000918] |
(0, 12, 0, 8, 0, 6) |
Type B permutohedra PB [arxiv] (Fomin, Reading) Conjectured: Acyclotopes of signed complete graphs [Zaslavsky] |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 8, 48, 384, ... 2^n*n! = (2n)!! [ OEIS A000165][see: i] Number of Facets: 0, 2, 8, 26, 80, ... 3^n-1 [ OEIS A024023] (Thanks to N. Reading) f-vectors: 1, 2, 1, 8, 8, 1, 48, 72, 26, 1, ... [ OEIS A145901 (dual)] |
(0, 36, 0, 0, 0, 6, 0, 0, 0, 8) |
Type B Coxeter-associahedra KPB [zib.de] (Reiner, Ziegler) |
Dimensions: 1, 2, 3, ... n Number of Vertices in nth polytope: 2, 8, 96, ... 2^n*n!*(Catalan number) [ OEIS conjecture] Number of Facets: 2, 8, 50, ... OPEN [ OEIS ?] |
(0, 42, 24, 0, 0, 0, 0, 0, 0, 8) |
Type A Coxeter-associahedra KPA [zib.de] (Reiner, Ziegler) Permutoassociahedra, Permuto-associahedra KP [M. Batanin, via R. Street] |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 12, 120, 1680... n!*(Catalan number) [ OEIS ] Number of Facets: 0, 2, 12, 74, ... Ordered Bell numbers -1 [ OEIS A000670][ OEIS A052875] f-vectors: 1, 2, 1, 12, 12, 1, 120, 192, 74, 1, ... [ OEIS ?] |
(0, 18, 0, 4, 0, 0, 0, 0, 0, 4) |
Type D Coxeter-associahedra KPD [zib.de] (Reiner, Ziegler) |
Dimensions: 0, 1, 2, 3, ... n Number of Vertices in nth polytope: 1, 2, 4, 48, ... [ OEIS ? ] Number of Facets: 0, 2, 4, 26, ... [ OEIS ?] f-vectors: 1, 2, 1, 4, 4, 1, 48, 72, 26, 1, ... |
(No 3d term) [polymake for n=4,5] |
s-t Path Polytopes of complete graph Path(n)= Path(K_n), n>1 [Springer] (A. Schrijver) convex_hull({incidence_vector_F | F a path from node s to node t of the complete graph on n nodes}) |
Dimensions: 0, 1, 4, 8,... conject. (n choose 2)-2 [ OEIS A034856] Number of Vertices in nth polytope: 1, 2, 5, 16, 65, ... Sum_{k=0..(n-2)} (n-2)!/k! [ OEIS A000522][see: i] Number of Facets: 2, 5, 25, ... OPEN [ OEIS ?] f-vectors: 1, 2, 1, 5, 10, 10, 5, 1, 16, 102, 334, 622, 685, 442, 156, 25, 1... [ OEIS ?] |
(No 3d term.) [polymake for n=3] |
Birkhoff polytopes B [wiki] assignment polytope Transportation polytope Trans_n(1, 1, . . . , 1) [arxiv] (Mιszαros, Morales, Rhoades) perfect matching polytope of complete bipartite graph set of doubly stochastic matrices convex_hull({M | M an nxn permutation matrix}) |
Dimensions: 0, 1, 4, 9, 16 ... (n-1)^2 Number of Vertices in nth polytope: 1, 2, 6, 24, ... n! [ OEIS A000142][see: i, ii, iii] Number of Facets: 0, 2, 9, 16,... n^2 [ OEIS A000290] f-vectors: 1, 2, 1, 6, 15, 18, 9, 1 ... [ OEIS ?] |
(No 3d term.) [polymake for n=3] |
Alternating Sign Matrix polytopes ASM(n) [arXiv] (J. Striker) convex_hull({char_vector_ASM | ASM an nxn alternating sign matrix }) |
Dimensions: 0, 1, 4, 9, 16, ... (n-1)^2 Number of Vertices in nth polytope: 1, 2, 7, 42, 429, 7436,... Product[j=0..n-1](3j+1)!/(n+j)! [ OEIS A005130] Number of Facets: 0, 2, 4, 8, 20, 40, 68, 104,...,4[(n-2)^2 +1][ OEIS A128445] f-vectors: 1, 2, 1, 7, 17, 18, 8, 1, 42, ... [ OEIS ?] |
(No 3d term) [polymake for n=2] |
Linear signed ordering polytopes Q [science direct] (S. Fiorini, P. Fishburn) convex_hull({char_vector_SLO | SLO a signed linear order with 2n elements}) |
Dimensions: 0, 1, 4, 9, 16, ... n^2 Number of Vertices in nth polytope: 1, 2, 8, 48, 384 ... 2^n*n!=(2n)!! [ OEIS A000165][see: i] Number of Facets: 0, 2, 16, 82, 8480, ... OPEN [ OEIS ?] f-vectors: 1, 2, 1, 8, 24, 32, 16, 1 ... [ OEIS ?] |
(No 3d term.) [polymake for 2n=6] |
Perfect Matching polytope of complete graph on 2n nodes PM(n) = PM(K_2n) [wiki] convex_hull({incidence_vector_PM | PM a perfect matching of the complete graph on 2n nodes}) [PNAS](P.Diaconis, S. Holmes) |
Dimensions: 0, 2, 9, ... Number of Vertices in nth polytope: 1, 3, 15, 105, ... (2n-1)!! [ OEIS A001147][see: i] Number of Facets: 0, 3, 25, ... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 15, 105, 435, 1095, 1657, 1470, 735, 195, 25, 1, ... [ OEIS ?] |
(No 3d term.) |
Interval order polytopes P_IO [citeseer] (R. Muller, A. Schulz) [wiki] Interval order polytopes P_IO(D_n) of the complete digraph. convex_hull({char_vector_IO | IO an interval order with n elements}) |
Dimensions: 0, 2, 6, ... Number of Vertices in nth polytope: 1, 3, 19, 207, 3451, ... [ OEIS ] Number of Facets: 0, 3, 17, ... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 19, 96, 193, 183, 84, 17, 1, 207, ... [ OEIS ?] |
(No 3d term.) |
Partial order polytopes P_PO [science direct] (S. Fiorini) convex_hull({char_vector_PO | PO a partial order with n elements}) |
Dimensions: 0, 2, 6, 12, ... n(n-1) Number of Vertices in nth polytope: 1, 3, 19, 219, ... OPEN [ OEIS ?] Number of Facets: 0, 3, 17, 128 ... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 19, 96, 193, 183, 84, 17, 1, 219, 5791 ... [ OEIS ?] |
(No 3d term.) |
Symmetric Traveling Salesman polytopes STSP [zib.de] (M. Grφtschel, M. Padberg), [SMAPO library] convex_hull({char_vector_HC | HC a Hamiltonian cycle of the complete graph on n nodes}) |
Dimensions: 0, 2, 5, 9, 14 ... n(n-3)/2 Number of Vertices in nth polytope: 1, 3, 12, 60, ... (n-1)!/2[ OEIS A001710] Number of Facets: 0, 3, 20 ,100, 3437, 194187, 42104442,... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 12, 60, 120, 90, 20, 1 ... [ OEIS ?] |
(No 2d,3d,4d terms.) |
Asymmetric Traveling salesman polytopes ATSP(n) [cornell] (L. Billera, A. Sarangarajan) [science direct] (R. Euler,H. Le Verge) convex_hull({char_vector_HC | HC a Hamiltonian cycle of the complete digraph on n nodes}) |
Dimensions: 1, 5, 11, 19 ... n(n-3)+1; n>2 Number of Vertices in polytope for n nodes: 2, 6, 24, 120, ... (n-1)![ OEIS A000142][see: i, ii, iii] Number of Facets: 2, 6, 390, 319015,... OPEN [ OEIS ?] f-vectors: 1, 2, 1, 6, 15, 20, 15, 6, 1, 24, ... [ OEIS ?] |
(No 3d term.) [polymake for n=5,6] [MatLab code for running PolySplit] [also need matrix generator] [and branch and bound algorithm] [and distance algorithm] [and RF-metric algorithm] |
Splitohedra Sp_n [arxiv] (S. Forcey, L. Keefe, W. Sands) relaxation of the Balanced Minimal Evolution Polytope BME(n). intersection of half-spaces{split-facets, intersecting cherry faces, caterpillar facets and the cherry clade-faces} from BME(n) and also obeying the {Kraft equalities}. |
Dimensions (start n =3): 0, 2, 5, 9, 14 ... (n choose 2)-n Number of Vertices in nth polytope: 1, 3, 27, 2335, ... OPEN [ OEIS ?] Number of Facets: 0, 3, 40, 85, 161 ... (2^n+n^3-3n^2-2)/2 [ OEIS ?] f-vectors: 1, 3, 3, 1, 27, 165, 310, 210, 40, 1, 2335, ... [ OEIS ?] |
(No 3d term.) [polymake for n=5,6] [faces and facets](2 page pdf.) |
BME polytopes P_n = BME(n) [arxiv] (D. Haws, T. Hodge, R. Yoshida) [almob](Eickmeyer et. al.)[blog resources][conference slides](R. Yoshida)[facets:preprint] convex_hull({dist_vector_T | T a binary tree with n labeled leaves}) |
Dimensions (start n =3): 0, 2, 5, 9, 14 ... (n choose 2)-n Number of Vertices in nth polytope: 1, 3, 15, 105, ... (2n-5)!! [ OEIS A001147][see: i] Number of Facets: 0, 3, 52, 90262... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 15, 105, 250, 210, 52, 1, 105, 5460... [ OEIS ?] |
(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) Number of Vertices in nth polytope: 1, 3, 25, 543, 29281, ... [ OEIS A003024] Number of Facets: 0, 3, 11 ... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 25, 93, 142, 111, 48, 11, 1, ... [ OEIS ?] |
(No 3d term.) |
Weak order polytopes P_WO [science direct] (S. Fiorini, P. Fishburn) convex_hull({char_vector_WO | WO a weak order with n elements}) |
Dimensions: 0, 2, 6, 12, ... n(n-1) Number of Vertices in nth polytope: 1, 3, 13, 75, ... sum{k=0..inf} (k^n)/(2^(k-1))[ OEIS A000670] Number of Facets: 0, 3, 15, 106 ... OPEN [ OEIS ?] f-vectors: 1, 3, 3, 1, 13, ... [ OEIS ?] |
(0, 22, 0, 0, 8) |
Cyclic polytopes C(n,m) Pairahedra Ph(n,m) Finite product lattice polytopes P_(l,m,...,k) Resultohedra (indexed by trees) (Step 2) Biassociahedra KK(n,m) = B^n_m (Step 2) Biassociahedra KK(n,m) = B^n_m (Step 2) Biassociahedra KK(n,m) = B^n_m Bimultiplihedra JJ(n,m) (Step 2) Bipermutahedra PP(n,m) |
[ wiki] (0, 4, 4, 3) I(2,1)= I(1,2) [T. Tradler],[ T. Tradler] (0, 4, 4, 3) P_(1,2) [J. Bloom] (0,4,4,4); (0, 7, 6, 6) [M. Batanin, via R. Street] [arxiv](Batanin) KK(2,3) = KK(3,2)= heptagon [arxiv](M. Markl) [arxiv](S.Saneblidze, R. Umble) KK(2,4) = KK(4,2) = (0, 13, 3, 0, 5), 32 vert. 21 facets [arxiv](M. Markl) KK(3,3) = (0, 22, 0, 0, 8), 44 vert. 30 facets [arxiv](M. Markl) JJ(2,2) = octagon ; JJ(2,3) =(0, 19, 0, 3, 4, 0, 0, 2) 46 vert. 28 facets [arxiv] (S.Saneblidze, R. Umble) PP(1,2) = heptagon; PP(2,2) = KK(3,3) = (0, 22, 0, 0, 8), 44 vert. 30 facets; [arxiv](S.Saneblidze, R. Umble) |
Revision Date: