This page is the beginnings of an

Encyclopedia of Combinatorial Polytope Sequences...
...but it has a ways to go. Send entry suggestions to: Entry Editor


Searching the table:
  • Ctrl-F, with sub-sequence using commas and spaces: 0, 3, 6
  • or use the index of named sequences
  • or enter below any keyword or sub-sequence: vertices, facets, polygon faces or f-vectors. Use quotes: "0, 3, 6, 0" to find named entry.
    
    


Each entry of this encyclopedia is a well defined sequence P_n , array or otherwise indexed family of polytopes with a combinatorial definition. Duals (polars) to the polytopes are considered to be the same entry--just reverse the f-vectors.

Pictured are the 3d terms of polytope sequences, which have at most one term in each dimension. Pictures are often links to individual pages.
Below each picture is a list giving the polygon score in the 3d term: (# triangles, # squares, # pentagons, # hexagons, ...)
Immediately to the right is a list of names for the sequence: many sequences have multiple interpretations.
The sequences of numbers of vertices and facets in each dimension n begins with n=0.
The sequence labeled f-vectors is the triangle of f-vectors read by rows: each row starts with vertices, and the occurrences of 1 are the top-dimension faces.
Links are to introductory literature, not necessarily primary sources.
SEQUENCES
Simplex

(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]
top    index

Demihypercube

(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 ?]
top    index

Cut Polytope

(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 ?]
top    index

Flow Polytope

(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 ?]
top    index

Matching Polytope of complete graph

(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 ?]
top    index

Hypercube

(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]
top    index

Independent set polytope of Uniform matroid

(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, ...
top    index

Bipartite Subgraph Polytope

(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, ...
top    index

Cubeahedron (edgeless graph)

(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 ]
top    index

Linear Ordering Polytope

(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 ?]
top    index

Huffman Polytope, Huffmanhedron

[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 ?]
top    index

Freehedron

(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]
top    index

Associahedron

( 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]
top    index

Type D Associahedron

( 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]
top    index

Composihedron

(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]
top    index

Halohedron

(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]
top    index

Graph composihedron (cycle graph)

(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 ?]
top    index

Stellohedron

(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)
top    index

Graph composihedron (edgeless graph)

(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 ?]
top    index

Graph multiplihedron (edgeless graph)

(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 ?]
top    index

Cyclohedron

(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]
top    index

Acyclotope (cycle graph)

(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]
top    index

Multiplihedron

(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]
top    index

(2,n)-Brick Polytope

(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 ?]
top    index

Pterahedron

(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 ?]
top    index

Permutohedron, permutahedron

(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]
top    index

Type D permutohedron

(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]
top    index

Graph multiplihedron (cycle graph)

(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 ?]
top    index

(3,n) Brick Polytope

(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, 205, ... OPEN [ OEIS ?]
top    index

2-associahedron for sequence (0,n,0)

(0, 6, 0, 8) conj. polytope

• (0,n,0) 2-associahedra W_0n0 [arxiv](N. Bottman)
• Faces are 2-tubings based on the sequence 0,n,0

• Dimensions:
0, 1, 2, 3, ... n
• Number of Vertices in nth polytope:
1, 2, 6, 24, 108, 520, 2620, 13648, 72956, ... OPEN [ OEIS ?]
• Number of Facets:
0, 2, 6, 14, 29, 57, 110, 212, ... OPEN [ OEIS ?]
top    index

Diagonal rectangulation polytope

(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]
top    index

Type B permutohedron

(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)]
top    index

Type B Coxeter-associahedron

(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 ?]
top    index

Type A Coxeter-associahedron (Permutoassociahedron)

(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 ?]
top    index

Type D Coxeter-associahedra

(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, ...
top    index

Symmetric Path Polytope

(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 ?]
top    index

Birkhoff polytope


(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 ?]
top    index

Alternating Sign Matrix Polytope

(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 ?]
top    index

Linear signed order polytope

(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 ?]
top    index

Perfect Matching polytope of complete graph

(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 ?]
top    index

Interval order polytope

(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 ?]
top    index

Partial order polytope

(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 ?]
top    index

Symmetric Traveling salesman polytope

(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 ?]
top    index

Asymmetric Traveling Salesman polytope
(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 ?]
top    index

Splitohedron

(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 Minimum 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 ?]
top    index

Balanced Minimum Evolution Polytope

(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 ?]
top    index

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)
• 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 ?]
top    index

Weak order polytope

(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 ?]
top    index


coming: Graphical Traveling salesman polytope GTSP(n) [SMAPO library]
** 3d term is simple but probably not later terms.
top    index

ARRAYS (two or more indices) (we are trying to decide how to organize these!)
Full entry coming soon:

(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)

top    index


INDEX
# | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | X | Y | Z |
2-associahedron for sequence (0,n,0)
Acyclic subgraph polytope
Acyclotopes: see Graphical Zonotopes
Acyclotope (cycle graph)
Alternating Sign Matrix Polytope
Asymmetric Traveling Salesman polytope
Associahedron
Balanced Minimum Evolution Polytope
Biassociahedra
Bimultiplihedra
Bipartite Subgraph polytope
Birkhoff polytope

Brick Polytopes Chain Polytopes Composihedron
Cube
Cubeahedron(edgeless graph)
Cut Polytope
Cyclic polytopes
Cyclohedron
Demihypercube
Diagonal rectangulation polytope
Edgeless-graph-associahedra
Finite product lattice polytopes
Flow polytopes
Freehedron

Graph Associahedra Graph Composihedra Graph Cubeahedra Graph Multiplihedra Graphical Traveling Salesman polytope

Graphical Zonotopes Graph composihedron (cycle graph)
Graph composihedron (edgeless graph)
Graph multiplihedron (cycle graph)
Graph multiplihedron (edgeless graph)
Halohedron
Huffman Polytope
Hypercube
Independent set polytope of Uniform matroid
Interval order polytope
Linear Ordering Polytope
Linear signed order polytope

Matching Polytopes Multiplihedron

Order Polytopes Pairahedra
Partial order polytope
Path polytope
Perfect Matching Polytopes: see Matching Polytopes.
Permutohedron/ permutahedron
Permutoassociahedron

Poset Associahedra Pterahedron
Resultohedra
Simplex

Secondary Polytopes Splitohedron
Stellohedron
Symmetric Traveling Salesman polytope
Type A Coxeter-associahedron (Permutoassociahedron)
Type B Coxeter-associahedron
Type B permutohedron
Type D Associahedron
Type D Coxeter-associahedra
Type D permutohedron
Vertex cover polytope: complete graph
Weak order polytope

top    index

Conjectured
simplicial complex of k-triangulations
Species compositions: permutohedra with associahedra
pseudograph-multiplihedra
 Back to research page. 

Revision Date: