# Questions tagged [convex-polytopes]

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

247
questions with no upvoted or accepted answers

**32**

votes

**0**answers

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$,
...

**24**

votes

**0**answers

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 ...

**19**

votes

**0**answers

486 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 ...

**15**

votes

**0**answers

242 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 ...

**14**

votes

**0**answers

191 views

### Have there been further developments on this scheme for polytope approximations to the unit ball of $\ell_p^n$?

A long time ago I happened to look at, and save (on a floppy disk!) for future reading, a copy of the following article:
W. T. Gowers, Polytope approximations of the unit ball of $l^n_p$.
In Convex ...

**14**

votes

**1**answer

523 views

### Inequalities for marginals of distribution on hyperplane

Let $H = \{ (a,b,c) \in \mathbb{Z}_{\geq 0}^3 : a+b+c=n \}$. If we have a probability distribution on $H$, we can take its marginals onto the $a$, $b$ and $c$ variables and obtain three probability ...

**14**

votes

**0**answers

242 views

### Is combinatorial automorphism of symmetric convex polytope always antipodal?

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 ...

**14**

votes

**0**answers

240 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 ...

**14**

votes

**0**answers

468 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 ...

**13**

votes

**0**answers

240 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 ...

**12**

votes

**0**answers

506 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 ...

**12**

votes

**0**answers

1k 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 ...

**11**

votes

**0**answers

307 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 exist ...

**11**

votes

**0**answers

353 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 B_{i}}{x_j}\quad\text{...

**10**

votes

**0**answers

294 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 ...

**9**

votes

**0**answers

145 views

### How to correctly state Cauchy's rigidity theorem?

Cauchy's rigidity theorem is usually cites briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...

**9**

votes

**0**answers

183 views

### Positivity of coefficients of Ehrhart polynomial of n-Tetrahedron

A set of positive integers $d_1, \dots, d_n$ describe two n-dimensional closed lattice tetrahedron:
$$ T = \left\{ (x_1, \dots, x_n) \in \mathbb{R}^n: \sum_{i=1}^n \frac{x_i}{d_i} \leq 1 \textrm{ and ...

**9**

votes

**0**answers

158 views

### Is every planar point set the projection 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)$ that are vertices of a neighborly polytope.
This problem comes from a simple ...

**9**

votes

**0**answers

262 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 ...

**9**

votes

**0**answers

722 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 ...

**8**

votes

**0**answers

191 views

### intriguing Polytope

Define $E_{i,j} \in \mathbb{R}^{n \times n}$ to be the canonical basis (that is all elements set to zero except the entry $i,j$ )
let the bloc matrix $M \in \mathbb{R}^{n^2 \times n^2}$ defined by :
...

**8**

votes

**0**answers

155 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 ...

**8**

votes

**0**answers

133 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$, ...

**8**

votes

**0**answers

135 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

**0**answers

75 views

### Can solutions to Thomson's problem have pentagons?

Thomson's problem asks for the minimum energy configuration for $N$ electrons on a sphere (refs: https://en.wikipedia.org/wiki/Thomson_problem, https://sites.google.com/site/adilmmughal/...

**7**

votes

**0**answers

116 views

### Probability of landing inside the convex hull of previously sampled points

Let $\{X_i\}_{0\leq i\leq\infty}$ be i.i.d. random vectors in $\mathbb{R^d}$.
I would like to show that the probability of one point being in the convex hull of the others goes to one with the number ...

**7**

votes

**0**answers

234 views

### Integral representations of finite groups and lattice point geometry

This contains both a reference request, and a specific problem.
Let $K$ be a finite group, and let $\theta: K \to {\rm GL}(d,{\bf Z})$ be a (faithful) group representation over the integers. Consider ...

**7**

votes

**0**answers

850 views

### Maximum volume cross-section of a hypercube

This is surely well known, but:
Q1. What is the $(d{-}1)$-dimensional polytope
that realizes the maximum volume cross-section of a unit hypercube
by a $(d{-}1)$-dimensional hyperplane?
...

**7**

votes

**0**answers

487 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
...

**7**

votes

**0**answers

4k 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?

**7**

votes

**0**answers

331 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 $...

**7**

votes

**0**answers

593 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 ...

**6**

votes

**0**answers

134 views

### An inequality related to the numbers of faces of polytopes with d+2 facets

I would like to prove an inequality related to the number of $k$-faces of two $d$-polytopes with $d+2$ facets; see (1) below.
Let $r>0$, $s>0$, $t\ge 0$, and $d\ge 2$ be such that $d=r+s+t$. We ...

**6**

votes

**0**answers

202 views

### Complexity of scissors congruence?

Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...

**6**

votes

**0**answers

88 views

### Tiling with Horn's polytopes

Let $n\ge2$ be an integer. Consider the hyperplane $H_n$ of ${\mathbb R}^n$ defined by the equation $x_1+\cdots+x_n=0$ and then the sector $P_n\subset H_n$ defined by the inequalities $x_1\le\cdots\le ...

**6**

votes

**0**answers

145 views

### Cut locus on a hypercube

Inspired by the question, "Shortest path connecting two opposite points on a cube":
Q. What does the cut locus with respect to one corner of a hypercube
in $\mathbb{R}^d$ look like?
"The cut ...

**6**

votes

**0**answers

98 views

### Rational $d$-simplices

Define a rational $d$-simplex as a simplex in $\mathbb{R}^d$
such that the measure of all its $k$-dimensional faces, $k \ge 1$, is rational.
So a rational triangle has rational edge lengths and ...

**6**

votes

**0**answers

105 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 ...

**6**

votes

**0**answers

171 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

**0**answers

214 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

**0**answers

448 views

### Minimum solid angle and aspect ratio of an $n$-simplex

In computational geometry and other fields, it is of interest to have degeneracy measures for shapes of simplices, which quantitatively seperate the regular simplex from degenerate simplices.
In two ...

**6**

votes

**1**answer

195 views

### Triangulations of convex surfaces

Let $M$ be a smooth closed positively curved surface in Euclidean 3-space, $T$ be a geodesic triangulation of $M$, and $E$ be the edge graph of the convex hull of vertices of $T$.
It is easy to see ...

**5**

votes

**0**answers

59 views

### Which polytopes can be deformed while keeping their edge-lengths?

Let $P\subset\Bbb R^d$ be a convex polytope (a convex hull of finitely many points). Lets call it flexible, if it can be continuously deformed while
keeping its combinatorial type, and
keeping its ...

**5**

votes

**0**answers

109 views

### How does a map from permutahedra to associahedra factor through multiplihedra?

Let $P_i$ denote permutahedra, $K_i$ associahedra and $J_i$ multiplihedra. In their famous paper on operadic diagonals, Saneblidze and Umble use a projection $p_i: P_i \to K_{i+1}$ which factors as $...

**5**

votes

**0**answers

99 views

### Laplace Beltrami eigenvalues on surface of polytopes

The recently posted arxiv paper Spectrum of the Laplacian on Regular Polyhedra
by Evan Greif, Daniel Kaplan, Robert S. Strichartz, and Samuel C. Wiese, collects numerical evidence for conjectured ...

**5**

votes

**0**answers

164 views

### Is there a well-established terminology for polyhedra/polytopes?

I got confused lately. It seems like in the metric context a polyhedron tends to mean an intersection of a finite number of half-spaces, while a polytope is a convex hull of a finite set of points. At ...

**5**

votes

**0**answers

101 views

### Lattice paths in polytopes

Let $P$ be a polytope in $\mathbb{R}^n$. Let $A_ix = b_i$ be the defining equations of its codimension $1$ faces. Is there an algorithm or some kind of criterion to decide if the lattice points inside ...

**5**

votes

**0**answers

126 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 $p_1<\ldots<...

**5**

votes

**0**answers

291 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

**0**answers

226 views

### Biggest (or large) rectangle in a polytope

I need an efficient method to construct a (hyper)rectangle inside a polytope with a lot of dimensions (say $100 < d < 1000$). Ideally I'd want the biggest possible rectangle, but as I don't ...