Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
29 views

Integral hull of a polyhedron Q is polyhedron

Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
1 vote
0 answers
124 views

Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)

Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
56 votes
1 answer
3k views

Intersecting family of triangulations

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
9 votes
0 answers
144 views

Which polytopes have compact realization spaces?

Let $P\subset\Bbb R^d$ be a convex polytope. Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations. I am interested in polytopes for ...
0 votes
0 answers
44 views

Lattice points in the boundary of a Minkowski sum of two convex lattice polygons

Let $P$ and $Q$ be two convex lattice polygons in $\mathbb{R}_+^2$ and let $P+Q$ be their Minkowski sum. Given a set $S \subset \mathbb{R}^2$, we let $L(S) =\#( S \bigcap \mathbb{Z}^2)$. The equality $...
6 votes
2 answers
2k views

Extreme points of transportation polytope

I'm interested in $n \times m$ joint probability tables with prescribed row and column marginals. Such tables form a convex set known as the transportation polytope. What are the extreme points of ...
2 votes
2 answers
196 views

Estimates on the number of vertices of reflexive polytopes

Suppose $M \cong \mathbb{Z}^n$ is a rank $n$ lattice, with dual lattice $N$. Suppose $\Delta$ is a full dimensional lattice polytope (i.e. convex hull of finite lattice points) in $M$. Then $\Delta$ ...
0 votes
0 answers
81 views

A generalized permutohedron as the sum of the dilatations of the faces of the standard simplex

I am trying to understand the proof of the statement, specifically it refers to a theorem stated by Postnikov in his text on permutohedra. So, this sentence claims the following: If $\{Y_I \}$ is a ...
1 vote
1 answer
200 views

Description of the generalized permutahedron

According to Postnikov, we know that the generalized permutahedron are describe as "polytopes obtained by moving vertices of the usual permutohedron so that directions of all edges are preserved&...
15 votes
3 answers
1k views

Classification of Platonic solids

My question is very basic: where can I find a complete (and hopefully self-contained) proof of the classification of Platonic solids? In all the references that I found, they use Euler's formula $v-e+...
2 votes
0 answers
318 views

What's the number of facets of a $d$-dimensional cyclic polytope?

A face of a convex polytope $P$ is defined as $P$ itself, or a subset of $P$ of the form $P\cap h$, where $h$ is a hyperplane such that $P$ is fully contained in one of the closed half-spaces ...
9 votes
1 answer
889 views

Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory

In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
4 votes
3 answers
347 views

Minimal data required to determine a convex polytope

Let $P\subset \Bbb R^d$ be a convex polytope. Suppose that I know its combinatorial type (aka. the face-lattice), the length $\ell_i$ of each edge, and the distance $r_i$ of each vertex from the ...
4 votes
0 answers
46 views

Implementation of Friedman's algorithm of reconstructing simple polytopes

In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
16 votes
0 answers
298 views

Realization spaces of 3-dimensional polytopes with fixed face areas

It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible. A proof of this theorem can be found for instance in ...
2 votes
0 answers
64 views

Eulerian polynomial from Bruhat interval - h* of something?

Let $\sigma \in S_n$ be a fixed permutation. Consider the polynomial $$ P_{\sigma}(t) = \sum_{\substack{\pi \in S_n \\ \pi \leq \sigma}} t^{\textrm{des}(\pi)} $$ where $\leq$ denotes Bruhat order, and ...
4 votes
1 answer
181 views

Denominators of rational polytopes in terms of hyperplane coefficients

Let $\mathcal{P}$ be a convex polytope in $\mathbb{R}^n$ given in the form $\mathcal{P} = \{ x \in \mathbb{R}^n\colon A x\leq b \}$. Suppose that the entries of $A$ and $b$ are integers. Then it is ...
3 votes
0 answers
124 views

Does this construct Platonic solids?

Consider $\mathrm{O}(3)\curvearrowright\mathbb{R}^3$. Let $\Gamma\subseteq\mathrm{O}(3)$ be a finite group. Let $x\in \mathbb{R}^3\setminus\{0\}$ be a point such that $\mathrm{Stab}_\Gamma(x)$ has ...
4 votes
1 answer
298 views

Does Kalai's $3^d$ conjecture hold for simplicial spheres?

Kalai's $3^d$ conjecture asserts that every centrally symmetric $d$-polytope has at least $3^d$ non-empty faces. This is open in general, but has been proven for simplicial polytopes. Question: Does ...
6 votes
2 answers
291 views

"Minimal" connected matroids

I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...
0 votes
0 answers
90 views

Which polytopes can be folded to an edge?

While playing with bar-and-joint linkages, I noticed that the skeleton of a regular 3-dimensional cube can be folded to a single edge (this can be achieved by first flexing the cube to bring it to a ...
3 votes
1 answer
111 views

Does a matroid base polytope contain its circumcenter?

Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...
8 votes
2 answers
417 views

Permutohedron and triangulation of cube via Eulerian numbers

The $h$-vector of the (simplicial complex given by the boundary of the polytope dual to the) permutohedron is the sequence of Eulerian numbers $A(n,k)=\#\{w\in S_n\colon \mathrm{des}(w)=k\}$. Example: ...
34 votes
16 answers
7k views

Generalizations of the Birkhoff-von Neumann Theorem

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices. The question is to point out different ...
9 votes
1 answer
327 views

The convex hull of Schur polynomial evaluations

Let $r\leq n$ and $d$ be positive integers. A probability vector is a vector of non-negative entries that sum to 1. For each probability vector $\lambda$ of length $n$, let $$s(\lambda)=(\dim[\pi] \...
2 votes
0 answers
68 views

Sampling theorems for partition polynomials (associahedra, noncrossing partitions / parking functions)

Define the associahedra partition polynomial $$ \begin{split} A(x) &= 1 + A_1(u_1) z + A_2(u_1,u_2) z^2 + A_3(u_1,u_2,u_3) z^3 + \cdots\\ & \qquad\qquad = 1 + \sum_{n \geq 1} A_n(u_1,...,u_n) ...
2 votes
2 answers
2k views

Mathematical tools appropriate to analyse convex polyhedra

What mathematical tools (means: set of areas of mathematical knowledge) are appropriate to begin with to analyse (to enumerate face vectors associated with polyhedron, to calculate the combinatorial ...
4 votes
0 answers
287 views

How can we prove this combinatorial identity?

This is a follow up on my earlier MO post. Let's recall the sets $$\mathbf{K}_n=\{\mathbf{k}\in\mathbb{Z}^n: k_i\geq0, k_1+\cdots+ k_n=n, k_1+\cdots k_i\leq i, \text{for all $1\leq i\leq n$}\}$$ and $\...
5 votes
1 answer
398 views

Catalan sequences vs composition sequences

In the paper, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Pitman and Stanley studied the $n$-dimensional polytope $$\Pi_n(\mathbf x)=\{y\in\...
8 votes
1 answer
447 views

Do this polyhedron and other set have names?

Updated: My first post had a mistake because I confused in my mind two different but related sets. Hopefully the description below is correct now. Let $\Lambda$ be a finite set. Let $\Lambda^{(2)}$ be ...
2 votes
0 answers
200 views

Toric decomposition of multipartitions

Fix $k \in \mathbb Z_{>0}$. By a $k$-multipartition $\lambda=(\lambda_1,\dots,\lambda_k)$ of $N$, I mean that each $\lambda_i$ is a partition of some $N_i$ and $\sum N_i = N$. Let's call $\lambda$ ...
1 vote
1 answer
1k views

The stock market polytope: explanation?

Ovidiu Racorean. "Crossing stocks and the positive Grassmannian I: The Geometry behind Stock Market." (arXiv Abstract link) Anyone care to offer a summary of what's going on here? (The ...
10 votes
3 answers
322 views

Integer decomposition property with a partial order

Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...
3 votes
0 answers
187 views

Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets

Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
7 votes
0 answers
162 views

Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets

We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
10 votes
2 answers
676 views

Status of Barany's conjecture?

One of Barany's most intriguing conjectures is about the $f$-vectors of convex polytopes. It asks: Let $P$ be a convex $d$-polytope. Is it always true that $f_k \geq \min(f_0, f_{d-1})$? A convex $...
4 votes
1 answer
189 views

2-faces of reflexive Delzant polytopes

Question 1. Can a reflexive Delzant polytope of some dimension contain a $2$-face with more than $11$ edges? Motivation. I would like more generally to get an answer to the following question: ...
19 votes
2 answers
1k views

About a Delzant polytope. (In particular dodecahedron)

Hi. I have a question. Definition. Delzant polytope $P$ is a rational convex simple polytope with the smooth condition. Here, "smooth" means that for each vertex $v$, the $n$ edges containing $v$ ...
4 votes
2 answers
266 views

A rational polytope that is not a 01-polytope?

A 01-polytope is the convex hull of some points $S\subseteq\{0,1\}^n$. I wonder, which polytopes can be represented (combinatorially) as 01-polytopes? There are polytopes that cannot have rational ...
2 votes
1 answer
137 views

Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$

Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
3 votes
1 answer
218 views

Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions

We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (I guess nothing changes for any other fixed ...
8 votes
1 answer
361 views

Inscribed $n$-polytope with $2^n$ vertices of maximal volume

The question is in the title: Question: Which inscribed $n$-dimensional polytope (inscribed in the unit sphere) with $2^n$ vertices has the largest possible volume? Is it the $n$-dimensional cube? ...
4 votes
1 answer
149 views

A combinatorial characterization of the central inversion of a polytope?

Given a convex full-dimensional polytope $P\subset\Bbb R^d$ (convex hull of finitely many points and not contained in any proper affine subspace) and a symmetry thereof (a linear map $\smash{T\in\...
3 votes
2 answers
438 views

If a polytope is centrally symmetric and combinatorially equivalent to a zonotope, is it a zonotope?

A zonotope is a polytope whose 2-faces are centrally symmetric. Question: If a polytope $P$ is centrally symmetric and combinatorially equivalent to a zonotope, is it itself a zonotope?
19 votes
3 answers
2k views

Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?

Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the ...
3 votes
0 answers
151 views

Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?

Given the formal Taylor series, or e.g.f., $f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$, the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via $ \sum_{n \geq 1} ...
15 votes
2 answers
481 views

Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?

For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices $$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\ \pi_{2,1} & \ddots & \...
1 vote
0 answers
154 views

Volume of a polytope as its degenerates to be lower dimensional

Consider a polytope $P$ defined by the usual inequalities $A\mathbf{x}\leq \mathbf{b}$; let me assume that $P$ is not contained in a proper subspace. A result which I believe to true, but am not ...
6 votes
1 answer
133 views

How rich is the class of vertex- and edge-transitive polytopes?

There are only a few regular polytopes (five in 3D, six in 4D, three in any dimension above). In contrast, the class of uniform polytopes becomes very rich with higher dimensions. The class of vertex-...
1 vote
1 answer
92 views

How to compute external angles of a hypersimplex?

Recently, I concern with the volume of the outer parallel body of a hypersimplex that is defined as follows $$ \mathcal{H}_s(n,k)=\left\{ (x_1,\cdots,x_n):\sum_{i=1}^n x_i=k,x_i\in[0,1] \right\}, $$ ...

1
2 3 4 5