# 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

885
questions

9
votes

0
answers

190
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] \...

0
votes

0
answers

20
views

### Reference on high dimensional polytopes with E8 symmetry

I'm starting to work with high dimensional polytopes. I am interested in uniform polytopes of 16-dimension and of 8-dimension (especially Elte and Gosset polytopes that have E8 symmetry).
...

2
votes

0
answers

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

4
votes

0
answers

165
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

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

0
votes

0
answers

17
views

### Approximation of connected set by triangluation / covering by simplices

Good afternoon. I have two distinct questions:
If I have connected compact in $\mathbb{R}^n$, how much $(n+1)$-simplices are needed to fill its interior such that diameter of maximal uncovered part ...

4
votes

0
answers

29
views

### Quantifying error in the reconstruction of convex polytopes from moments

The problem of reconstructing a geometric object from its moments is of interest in a variety of fields. In the paper The Inverse Moment Problem for Convex Polytopes, the authors show that a convex ...

4
votes

1
answer

104
views

### Approximation of convex bodies by polytopes corresponding to smooth toric varieties

Let $P\subset \mathbb{R}^n$ be an $n$-dimensional polytope with rational vertices. There is a well known construction which produces an $n$-dimensional algebraic variety $X_P$ called toric variety. In ...

8
votes

1
answer

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

1
vote

0
answers

30
views

### Fitting a convex polytope with 𝑛 facets between two nested spheres

This is related to a research problem that is interested in approximation of spheres by convex polytopes.
Let $C_r$ and $C_R$ be two spheres in $\mathbb R^d$ of radius $r$ and $R$, respectively, where ...

1
vote

0
answers

35
views

### About the number of faces of the conification of a polytope

Let $P\subset\mathbb{R}^n$ be a polytope of dimension $(n-1)$ such that the origin $\vec{0}\not\in\text{Aff}(P)$, where $\text{Aff}(P)$ denotes the affine hull of $P$ in $\mathbb{R}^n$. Now, we ...

2
votes

1
answer

44
views

### Example of worst case distributions for 4D convex hull

My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf
This same source writes
In 4D, there are ...

0
votes

1
answer

108
views

### How can I find the hyperplane passing through a 600-cell

I have a 600-cell, whose coordinates are given by
$$\begin{array}{ccc}
\text{8 vertices} & \left(0,0,0,\pm1\right) & \text{all permutations,}\\
\text{16 vertices} & \frac{1}{2}\left(\pm1,\...

1
vote

0
answers

21
views

### Does Hoffman constant keep the same after a very tiny perturbation on the polyhedron such that the bases are even unchanegd?

Suppose that $P$ is a polyhedron represented by
$$P:=\{x \in \mathbb{R}^n: A x \le b \} \text{ for }A \in \mathbb{R}^{m\times n},\ b \in \mathbb{R}^m,$$
and $P$ contains interior points. Moreover, the ...

1
vote

0
answers

49
views

### Polytope of a projected toric variety

I was looking for such a result in the book by Cox, Little and Schenck but I'm not able to find a proper reference.
All of the following requirements are tacitly assumed to be in the projective ...

3
votes

0
answers

42
views

### maximizing number of lattice points with bounded diameter

Suppose I have a lattice $L$ that's just $\mathbb{Z}^k$ but scaled in every coordinate by some (potentially different) real numbers. Now I want to construct a finite set of lattice points $S \subset L$...

0
votes

1
answer

73
views

### Maximum number of vectors with bounds on inner products (follow up question)

This is a follow-up question from my previous question.
Suppose there are (2n+1) vectors $\{m_1,m_2,...,m_n\}$, $\{p_1,p_2,...,p_n\}$ and $p^*$ in $R^{k+1}$. $m_i$ are weakly positive vectors. $p_i$ ...

4
votes

2
answers

219
views

### Does the edge-graph of a centrally symmetric polytope determine which vertices are antipodal?

Given two origin symmetric convex polytopes $P_1$ and $P_2$ (that is $P_i=-P_i$) with the same edge-graph, but potentially of different dimensions and combinatorial types.
Let $\phi: G_{P_1}\to G_{P_2}...

2
votes

0
answers

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

3
votes

0
answers

125
views

### Can a polytopal graph be "centrally symmetric" in more than one way?

Let $P,Q$ be two centrally symmetric convex polytopes, potentially of different dimensions and combinatorial type, but with the same edge-graph $G$.
The central symmetry of $P$ induces an involutory ...

1
vote

1
answer

159
views

### Maximum number of vectors with bounds on inner products

Suppose there are 2n vectors $\{m_1,m_2,...,m_n\}$ and $\{\mu_1,\mu_2,...,\mu_n\}$. All vectors are in k-dimensional Euclid space $R^k$. The vectors satisfy:
$$m_i \mu_j \leq 0, \quad \forall i\neq j $...

2
votes

0
answers

69
views

### Is it possible to deduce Poincaré duality from duality of polytopes?

I'm having trouble understanding Poincaré duality, as it seems unmotivated. Here for instance:
https://math.stackexchange.com/a/14469/454016
Poincaré duality is explained through a duality of ...

1
vote

0
answers

110
views

### Which vector configurations generate as zonotope the regular $2n$-gon?

For $X=(x_1,\dots,x_n) \in (\mathbb{R}^2)^n$, the generated zonotope (zonogon in 2D) is defined by
$ Z(X) := \{\sum_{k=1}^n \sigma_k x_k
: \sigma_1,\dots,\sigma_n \in [0,1] \}. $
Which $X$ ...

5
votes

1
answer

183
views

### Proof of Lemma 37.5 in Pak's Lectures on Discrete and Polyhedral Geometry

I am staring at the proof of Lemma 37.5 in Lectures on Discrete and Polyhedral Geometry, see page 331.
I cannot understand why the required triangulation exists.
In the first paragraph it says "...

5
votes

2
answers

184
views

### Topology of a union of facets of a convex polytope

The following question arose from a survey paper I am writing on
combinatorial reciprocity. Let $\mathcal{P}$ be a $d$-dimensional
convex polytope. Let $\mathcal{Q}$ be a union of facets (codimension
...

1
vote

1
answer

45
views

### Fixed points of rational continuous piecewise affine maps

Say that a compact convex polytope is rational if is the intersection of half-spaces whose bounding hyperplanes are the zero-sets of affine functions of the coordinates with rational coefficients. Say ...

16
votes

0
answers

324
views

### Is the dodecahedron flexible (as a polytope with fixed edge-lengths)?

Consider the (regular) dodecahedron $D\subset\Bbb R^3$. I want to continuously deform it so that throughout the deformation
it stays a convex polytope,
it stays a combinatorial dodecahedron (i.e. its ...

3
votes

0
answers

182
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

1
answer

176
views

### In a set of n points on $R^d$, each point can be "well separated" from the rest by a linear functional. Is the dimension necessarily $\Omega(n)$?

For $x\in\mathbb{R}^d$ and $A\subset\mathbb{R}^d$, we say that $x$ is well separated from $A$ if there is a linear functional $f:\mathbb{R}^d\rightarrow\mathbb{R}$ such that $f(A)\subseteq [0,1]$ and $...

7
votes

0
answers

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

0
votes

0
answers

81
views

### Upper bound on the diameter of a convex lattice n-gon with a given area

Given the area $A$ of a strictly convex polygon with $n$ vertices with integer Cartesian coordinates, there are usually several non-equivalent polygons. The relationship between the area, the number ...

1
vote

0
answers

77
views

### All 3-dimensional symmetric reflexive polytopes

$\DeclareMathOperator\Conv{Conv}$I am finding all 3-dimensional symmetric reflexive polytopes. To do so, first, we know that all 2 dim symmetric reflexive polytopes are $X_3=\Conv((-1,-1),(1,0),(0,1))$...

4
votes

0
answers

186
views

### Characterization of curves contained in the boundary of convex bodies

Given a continuous closed curve $\gamma$ in $\mathbb R^n$ does there exist a convex body $K$ (convex set with non-empty interior) such that $\gamma\subset \partial K$?
I am looking for a reference to ...

9
votes

1
answer

601
views

### Determining whether a lattice is the face lattice of a polytope - NP hard or undecidable?

According to this source (p. 10), determining whether a simplicial complex is a simplicial sphere (the sphere recognition problem) is undecidable.
According to this source, determining whether a ...

1
vote

0
answers

35
views

### Barnes-Wall lattices’ contact polytopes

The contact polytopes of the Barnes-Wall lattices in 1, 2, 4, and 8 dimensions are all uniform polytopes. Is this true in any higher number of dimensions?

4
votes

2
answers

244
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

249
views

### Intersection of the simplex with a linear subspace of codimension $2$

The sets are defined in $\mathbb{R}_+^n$ $(n\geq 1)$. The relative interior of a convex set $C$ is denoted $\mathring C$.
Let $S$ be the $n$-simplex:
$$S=\left\{x\in\mathbb{R}_+^n,\,\sum_{i=1}^n x_i=1\...

3
votes

1
answer

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

18
votes

1
answer

520
views

### Known configurations maximizing the volume of the convex hull of n points on the unit sphere

For $n\geq 4$, let $V_n$ be the maximum volume of the convex hull of $n$ points on the unit sphere (in $\mathbb{R}^3$, although information on higher dimensions is welcome as well). I'm sure the ...

23
votes

1
answer

573
views

### Covering the unit sphere in $\mathbf{R}^n$ with $2n$ congruent disks

Let $v_i$ be $2n$ points in $\mathbf{R}^n$, with equal distance $|v_i|$ from the origin. Suppose that the convex hull of these points contains the unit ball. Is it known that $|v_i|\geq\sqrt{n}$? ...

0
votes

0
answers

45
views

### Intersection of the simplex with a space vector

The sets are defined in $\mathbb{R}_+^n$ $(n\geq 1)$. The relative interior of a convex set $C$ will be denoted $\mathring C$. The codimension of a submanifold $M$ of a manifold $N$ will be denoted ...

15
votes

1
answer

667
views

### Information inequalities

What are the feasible $2^n$-tuples of entropies $h(S) := H(X_{i_1},\dots,X_{i_{|S|}})$ where $X_1,\dots,X_n$ are discrete random variables with some (unknown) joint probability distribution as $S=\{...

11
votes

0
answers

242
views

### How many ways to flatten a Tesseract onto a table?

A cube can be cut and flattened out onto a table in a way that the faces stay connected and none of them overlap. There are $384$ ways to make the cuts and $11$ distinct meshes emerge (see here). And ...

2
votes

0
answers

46
views

### Endpoints of intrinsic diameter of a convex polyhedron

Let $P$ be a convex polyhedron in $\mathbb{R}^3$, and $d(P)$ its intrinsic diameter,
i.e., the longest shortest surface path between two points. Say that $P$ is of
class
$D_0$ if neither endpoint of $...

24
votes

1
answer

636
views

### Given a group action on a simplex, can I always find a fundamental region that is a simplex?

Let $\Delta\subset\Bbb R^n$ be a simplex with $n+1$ vertices. Let $G\subset\mathrm{GL}(\Bbb R^n)$ be a finite group of linear symmetries of $\Delta$, i.e. linear transformations that fix the simplex ...

1
vote

1
answer

190
views

### Algorithm to find a facet of a polyhedron given the vertices?

I have a set of points $X=\{x_1,\ldots,x_N\}$ on the unit sphere in $\mathbb{R}^d$ ($N>d\ge 3$). What is an algorithm to find any facet of the polyhedron whose vertices are $X$?
The set $X$ has ...

1
vote

1
answer

60
views

### Volume ratio of polytopes with few vertices

The volume ratio of a convex body $K\subset \mathbb{R}^{n}$ is $v_r(K) = \inf_{\mathcal{E}\subset K} \left(\frac{Vol(K)}{Vol(\mathcal{E})}\right)^{1/n}$ where the infimum run over ellipsoids included ...

3
votes

0
answers

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

4
votes

1
answer

104
views

### Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?

Suppose that $P\subset\Bbb R^n, n\ge 3$ is a (full-dimensional) convex polytope with a bipartite edge-graph $G=(V_1\cup V_2,E)$ (for example, a zonotope). Suppose further that there are concentric ...

3
votes

0
answers

76
views

### Simplex cover of an n-cube with non-congruent simplexes

I am curious about simplex coverings of the unit n-dimensional hypercube (or n-cube) with the following properties:
The simplexes do not need to be regular
The simplexes can be non-congruent (i.e. of ...