Convex polytopes are the convex hulls of a finite set of points in Euclidean spaces. They have rich combinatorial, arithmetic, and metrical theory, and are related to toric varieties and to linear programming

learn more… | top users | synonyms

42
votes
0answers
1k 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 ...
29
votes
0answers
2k views

A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ . Suppose that (*) For every $i \lt j \lt k$ and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...
18
votes
0answers
2k views

Why do polytopes pop up in Lagrange inversion?

I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
17
votes
0answers
303 views

“Japanese Theorem” on cyclic polygons: Higher-dimensional generalizations?

A beautiful theorem known as the Japanese Theorem (Wikipedia, MathWorld) says that, no matter how one triangulates a cyclic (inscribed in a circle) polygon, the sum of the radii of the incircles is ...
12
votes
0answers
174 views

Polytopes with few vertices and few facets

I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...
12
votes
0answers
153 views

realization spaces of 3-dimensional polytopes

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 ...
12
votes
0answers
402 views

Reciprocity (Ehrhart-style) for real polytopes?

Is there some sense in which the well-known Ehrhart reciprocity law for rational, convex, polytopes can be extended to any convex polytope with arbitrary real vertices? In other words, given any ...
11
votes
0answers
152 views

Is combinatorial automorphism of symmetric convex polytope always odd?

The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
11
votes
0answers
326 views

Lower Bound on the Volume of Certain Polytopes

Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks $$ \rho=\{B_1,B_2,\ldots,B_{k}\} $$ we can define the set of equations $$ E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in ...
11
votes
0answers
796 views

Constructive aspects of Caratheodory's theorem in convex analysis

Let me paraphrase Caratheodory's theorem in a probabilistic setup: Let $X$ be a real-valued random variable. For $k = 1, \ldots, m$, let $f_k: \mathbb{R} \to \mathbb{R}$ be a continuous function such ...
10
votes
0answers
224 views

Right-angled polytopes

%This question is motivated by the little discussion here at the bottom. The following thing are known about hyperbolic right-angled polytopes: Compact hyperbolic right-angled polytopes do not ...
9
votes
0answers
189 views

Does there always exist a self dual polytope that contains a given polytope contained in its dual?

Suppose a polytope $P$ is contained in its dual polytope $\tilde{P}$. Does there always exist a polytope $Q$ that contains $P$ and is self dual $Q=\tilde{Q}$? Is there any bound on the minimal number ...
8
votes
0answers
162 views

An affine invariant of convex bodies

The following invariants of "pointed" convex bodies (i.e., pairs consisting of a convex body and a distinguished point in its interior) roughly measure how many of its linear images fit between the ...
8
votes
0answers
230 views

Bi-spherical polyhedra

Bicentric polygons have been studied: a polygon all of whose vertices lie on its circumcirle, and whose incircle is tangent to every edge:   I have not been able to find a comparable literature ...
8
votes
0answers
587 views

Counting Lattice Points in Real Polytopes

Suppose one did have an exact formula for the number of $\mathbb{Z}^n$-lattice points intersecting an arbitrary dilate of a (not necessarily rational) finite, closed and convex $n$-polytope. As a ...
7
votes
0answers
93 views

What does this number tell me about a convex lattice polygon?

EDIT: I realized I'd tricked myself by working with a too special case of $f$, the question is now updated (boundary lattice points replaced vertices). Suppose I have a convex lattice polygon $P$, ...
7
votes
0answers
116 views

How many facets can $\{\|D^T x\|_1\leq 1\}$ have?

$\newcommand{\RR}{\mathbb{R}}$Consider $x\in\RR^n$ and $D\in \RR^{n\times p}$ with $p\geq n$ and full rank. My question is: How many facets can the polytope $ \{x\in\RR^n\ :\ \|D^T x\|_1\leq 1\}$ ...
7
votes
0answers
284 views

A question about a blue fan and a red fan and their common refinement

Is the following conjecture true? Conjecture: Let $M_1$ be a red map and let $M_2$ be a blue map drawn in general position on $S^n$, and let $M$ be their common refinement. There is a vertex $w$ of ...
6
votes
0answers
145 views

Looking for the correct version of a wrong statement from Barvinok's book on convex polyhedra

The book I'm concerned with is "Integer Points in Polyhedra" by A. Barvinok, which, I must say, is turning out to be highly fascinating. A real finite-dimensional vector space $V$ defines the ...
6
votes
0answers
147 views

Sampling from a Convex Body with Many Extremal Points

Let $p_{1}, \ldots, p_{N}$ be a collection of points in $\mathbb{R}^{n}$. I would like to sample uniformly from the convex hull of these $N$ points in an `efficienct' way. In my setting, I have $n$ ...
6
votes
0answers
135 views

Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between edges are rational multiples of $\pi$?

After reading these very interesting questions, I came up with another one: Does every convex polyhedron have a combinatorially isomorphic counterpart whose angles between all pairs of edges meeting ...
5
votes
0answers
50 views

Convex hull of the orbit of a matrix under permutations

Let $P$ be a generic permutation matrix on $\mathbb{R}^n$. For any vector $x \in \mathbb{R}^n$, the convex hull of the set $\{ Px : \; \text{$P$ is a permutation matrix}\}$ is the set of vectors ...
5
votes
0answers
69 views

Algorithm to express a point from a H-polyhedron as convex combination of extreme points

Let $P\subset\mathbb{R}^n$ be a convex polyhedron described as an intersection of hyperspaces, that is, $$P:=\{\boldsymbol{x}: A\boldsymbol{x} \leq \boldsymbol{b}\}$$ Let $\boldsymbol{x} \in P$. We ...
5
votes
0answers
58 views

Measure-minimizing simplex with fixed inradius

Let $\Delta^n$ be an $n$-simplex in $\mathbb{R}^n$. Let $V$ be the volume and $r$ the inradius (radius of the inscribed sphere) of $\Delta^n$. There is a well-known result that $$ V \geq ...
5
votes
0answers
137 views

Geometry of the metric cone

Let us say that two metrics $d$ and $d_0$ on a set $X$ are related if there exist positive constants $0 < \alpha \leq \beta$ such that $$ \alpha \,\left(d_0(x,y) + d_0(y,z) - d_0(x,z)\right) \leq ...
5
votes
0answers
182 views

4D polytope analogues of the icosahedron/Rogers-Ramanujan continued fraction relationship?

The formula for the j-function which employs polynomial invariants of the icosahedron, $$j(\tau)=-\frac{(r^{20} - 228r^{15} + 494r^{10} + 228r^5 + 1)^3}{r^5(r^{10} + 11r^5 - 1)^5}$$ where, ...
5
votes
0answers
226 views

Lattice points inside a (n-dimensional) tetrahedron

Hi, overflowers. I was interested in a sharp lower bound for the number of lattice points (say, integral lattice points) inside the tetrahedron defined by the coordinate hyperplanes and ...
5
votes
0answers
95 views

Regularity of simplices, part deux

This question is directly inspired by Pietro Majer's question and my answer to it. One can define a simplex, and the dihedral angles thereof in an infinite dimensional Hilbert space (one has to take ...
5
votes
0answers
184 views

A polytope associated with the Hadamard Transform

In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in ...
5
votes
0answers
401 views

Reference for this polyhedral lemma

Recall the definition of a fan: Let $U$ be a finite dimensional real vector space. Then a fan is a collection $\mathcal{F}$ of cones in $U$ such that (1) If $\sigma \in \mathcal{F}$ and $\tau$ is a ...
5
votes
0answers
479 views

When should a moment polytope have “smooth” faces?

A codimension $d$ face of a polytope is called rationally smooth if it lies on only $d$ facets, because this is exactly the condition for the corresponding toric variety to have only orbifold ...
4
votes
0answers
109 views

Reference for the notion of polyhedra “degenerations”

Let $P$ be a convex polyhedron and let $P(t)$ be a continuous deformation thereof, such that: a) $P(0)=P$; b) for all $t\in[0;1)$ the polyhedron $P(t)$ is strongly combinatorially equivalent to $P$ ...
4
votes
0answers
75 views

Face structures of chain polytopes

For a finite poset $P$ the chain polytope $\mathscr C(P)\subset\mathbb{R}^P$ consists of such $g$ that $g(p)\ge 0$ for all $p\in P$ and $$g(p_1)+\ldots+g(p_n)\le 1$$ for any chain ...
4
votes
0answers
93 views

Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim: Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...
4
votes
0answers
76 views

Can the GUE be thought of as a uniform point in a high-dimensional polytope

I have thought about this question for a long time and could only find partial answers. The Gaussian Unitary Ensemble (or GUE) is the eigenvalues of a random Hermitian matrix with complex Gaussian ...
4
votes
0answers
65 views

Is every planar point set be projections of vertices of a neighborly 4-polytope?

More exactly, written in coordinates, I'm curious to know if for every point set $(x_i,y_i)$ there are $(x_i,y_i,z_i,w_i)$ be vertices of a neighborly polytope. This problem comes from a simple ...
4
votes
0answers
242 views

Regular cross-sections of a dodecahedron; analogous sections of 4-polytopes

One can intersect a dodecahedron with a plane and obtain an equilateral triangle, a square, a regular pentagon, a regular hexagon, and a regular decagon:             ...
4
votes
0answers
161 views

Tetrahedra passing through a hole

Assume a plane $P\subset\mathbb R^3$ has a hole $H$, and that the hole is topologically a compact disc. Being so, $P\setminus H$ does not separate the space. A regular tetrahedron $\sigma^3$ (of ...
4
votes
0answers
202 views

What's the best way to test if a sphere is a polytope? (algorithms for the Simplicial Steinitz Problem)

The problem of recognizing whether a simplicial face lattice is polytopal is sometimes called the Steinitz problem. Sturmfels and Bokowski advanced a set of methods in the late 80s to test whether ...
3
votes
0answers
44 views

Delzant polytopes and combinatorial types

At first, let us see the following matheoverflow question, About a Delzant polytope. (In particular dodecahedron) The question is whether (combinatorial) regular dodecahedron can be realized as a ...
3
votes
0answers
35 views

Is every 1-skeleton of a 4-tope Steinitzian?

Call a graph "polyhedral" if it is simple, planar, and 3-connected. For example, the 1-dimensional skeleton of every 3-dimensional convex polytope, regarded as a graph, is polyhedral. By a theoreom ...
3
votes
0answers
36 views

“Spherelike” embedding for smooth Fano polytope

Let $\mathbb{R}^n$ be a vector space with Euclidean inner product and $\mathbb{Z}^n \subset \mathbb{R}^n$ be a lattice. Let $P$ be a full dimension convex lattice polytope in $\mathbb{R}^n$ containing ...
3
votes
0answers
95 views

Intersection numbers on blow ups of toric varieties

Suppose we have a smooth, complete toric varietiy $X_{\Sigma}$ of dimension $n$. Let $\sigma_k \in \Sigma(k)$ a smooth $k$-dimensional cone in $\Sigma$ and suppose we make the toric blow up at the ...
3
votes
0answers
83 views

Polytopes whose intersections have few vertices

This is related to one that I asked earlier: The intersection of two $l_1$ balls My question: are there any general classes of polytopes $P_1,P_2\subset\mathbb{R}^n$ such that $P_1$ has few ...
3
votes
0answers
78 views

Does a polytope have a self-indexing shelling?

If $X$ is a smooth projective toric variety and $P \subset \mathbf{R}^n$ is its moment polytope, then a generic linear function on $\mathbf{R}^n$ induces (1) a Morse function on $X$, and (2) a ...
3
votes
0answers
72 views

Which (polytopal) fans/polytopes are secondary?

Let $P$ be a (d-1)-dimensional polytope with $n$ vertices that sits in an affine hyperplane in $\mathbb{R}^d$. The secondary fan of $P$ is a polytopal fan in $\mathbb{R}^n$ with $d$-dimensional ...
3
votes
0answers
88 views

max volume of inscribed simplex in a ball

Let $B_n$ be the $n$-dimensional unit ball, and $B_n(\epsilon)$ be the spherical cap with height $\epsilon$ I am interested in the quantity $$\Gamma:=\sup_{\Delta:\textrm{ inscribed simplex in ...
3
votes
0answers
58 views

Polynomials connected with Gale's condition and cyclic polytopes

I was reading about cyclic polytopes and (I think naturally) became interested in polynomials $f(X) \in \mathbb{R}[X]$ which have a factorization of the form $f(X)=g(X)g(X+1)$ for some $g(X) \in ...
3
votes
0answers
53 views

Minimax-like theorems involving union and intersection of regions in $\mathbb R^d$

From Minimax theorems, we roughly know that if $f(x,y)$ is convex on $X$ and concave $Y$ for both compact $X,Y$, then: $$ \max_{x\in X}\min_{y\in Y} f(x,y)=\min_{y\in Y}\max_{x\in X} f(x,y). $$ We can ...
3
votes
0answers
1k views

Convex hulls of compact sets

Let $A$ be a compact set in a separable Hilbert space $H$, and let $\bar A$ denote its convex hull. Is $\bar A$ compact?