Skip to main content

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

Filter by
Sorted by
Tagged with
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\...
T. Amdeberhan's user avatar
15 votes
1 answer
703 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=\{...
James Propp's user avatar
  • 19.7k
24 votes
1 answer
770 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 ...
M. Winter's user avatar
  • 13.6k
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] \...
Ben's user avatar
  • 980
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 ...
Yikun Qiao's user avatar
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 ...
Abdelmalek Abdesselam's user avatar
3 votes
0 answers
69 views

Volume of all Voronoi cells in n-dimensional bounded space

How can one find the volume of all Voronoi cells (bounded and unbounded) in an $n$-dimensional bounded space? For instance, consider an $N$-dimensional space (hypercube) with bounds on each dimension ...
Maaz's user avatar
  • 131
11 votes
1 answer
712 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 ...
M. Winter's user avatar
  • 13.6k
23 votes
1 answer
714 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}$? ...
Mohammad Ghomi's user avatar
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 ...
Tom Copeland's user avatar
  • 10.5k
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 ...
M. Winter's user avatar
  • 13.6k
54 votes
5 answers
2k views

Unusual symmetries of the Cayley-Menger determinant for the volume of tetrahedra

Suppose you have a tetrahedron $T$ in Euclidean space with edge lengths $\ell_{01}$, $\ell_{02}$, $\ell_{03}$, $\ell_{12}$, $\ell_{13}$, and $\ell_{23}$. Now consider the tetrahedron $T'$ with edge ...
Dylan Thurston's user avatar
18 votes
1 answer
841 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 ...
Gro-Tsen's user avatar
  • 32.5k
2 votes
1 answer
241 views

Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?

According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard. However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
Makogan's user avatar
  • 123
1 vote
0 answers
163 views

Membership test of convex set

Let $K$ be a compact convex subset of $R^n$ which has some positive gaussian measure, say at least 1/2. For each nonzero vector $u \in R^n$, we define another compact convex set $K * u$ in the ...
Sandra's user avatar
  • 11
0 votes
1 answer
113 views

On the extreme points of two convex sets

Let $A$ and $B$ be two compact convex sets (which may be assumed to be polytopes) in $\mathbb R^n$ such that $A\cap B\ne\emptyset$. Is it then always true that either $A\cap\text{ext}B\ne\emptyset$ ...
Iosif Pinelis's user avatar
4 votes
2 answers
254 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}...
M. Winter's user avatar
  • 13.6k
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 ...
Pritam Majumder's user avatar
4 votes
1 answer
159 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 ...
asv's user avatar
  • 21.8k
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? ...
M. Rumpy's user avatar
  • 283
11 votes
1 answer
652 views

How to correctly state Cauchy's rigidity theorem?

Cauchy's rigidity theorem is often stated briefly as Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent. As a more formal generalization to general ...
M. Winter's user avatar
  • 13.6k
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 ...
M. Winter's user avatar
  • 13.6k
54 votes
3 answers
3k views

The view from inside of a mirrored tetrahedron

Suppose you were standing inside a regular tetrahedron $T$ whose internal face surfaces were perfect mirrors. Let's assume $T$'s height is $3{\times}$ yours, so that your eye is roughly at the ...
Joseph O'Rourke's user avatar
48 votes
4 answers
3k views

How many ways can you inscribe five 24-cells in a 600-cell, hitting all its vertices?

You can inscribe five tetrahedra in a dodecahedron so that each vertex of the dodecahedron is the vertex of just one tetrahedron, as drawn here by Greg Egan: Warmup question: How many ways can you do ...
John Baez's user avatar
  • 22.3k
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 $\...
T. Amdeberhan's user avatar
3 votes
1 answer
42 views

A converse question about the polyhedrality under linear mapping

It is quite well known that for any polyhedral set $K$ and any linear mapping $A$, the set $AK$ is polyhedral and hence closed. I am more curious about the converse problem, namely: Suppose $K$ is a ...
Wenqing Ouyang's user avatar
5 votes
1 answer
223 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 "...
aglearner's user avatar
  • 14.3k
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 ...
Gil Kalai's user avatar
  • 24.7k
44 votes
11 answers
26k views

Algorithm for finding the volume of a convex polytope

It's easy to find the area of a convex polygon by division into triangles, but what is the optimal way of finding the volume of higher-dimensional convex bodies? I tried a few methods for dividing ...
Xerxes's user avatar
  • 441
0 votes
1 answer
116 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,\...
Dac0's user avatar
  • 295
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 ...
M. Winter's user avatar
  • 13.6k
5 votes
2 answers
672 views

Secondary polytope

Given a polytope $P$, what do the points of the secondary polytope correspond to? I know that the vertices of the secondary polytope correspond to regular triangulations of $P$. But what do the ...
André Henriques's user avatar
1 vote
2 answers
539 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 ...
Ryan Bennink's user avatar
5 votes
2 answers
217 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 ...
Richard Stanley's user avatar
1 vote
0 answers
61 views

$\psi_2$ marginals of the permutahedron?

Let $K$ be a convex body. I in particular care about the permutahedron. I will view this as being the convex hull of all coordinate-wise permutations of the vector $$v = \frac{1}{2n+2}(-n, -n+2,\dots, ...
Mark Schultz-Wu's user avatar
2 votes
0 answers
51 views

Estimating the Hausdorff distance of parallel facets of convex polytopes

Background Let $\mathcal{K}_P^n$ denote the class of open, convex, $n$-dimensional polytopes in $\mathbb{R}^n$ containing the origin. For each $K\in \mathcal{K}_P^n$, its gauge function $f_*:\mathbb{R}...
kenvergence's user avatar
1 vote
1 answer
207 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 $...
TanG's user avatar
  • 23
7 votes
1 answer
184 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 $...
Faidh's user avatar
  • 71
1 vote
0 answers
91 views

Factorising a multivariate polynomial, in terms of products of linear polynomials, using blowups

I am considering multivariate polynomials of the form $$f(x,y)=x^a\,y^b\,p(x,y)^c$$ (and similarly for higher dimensions). I am trying to transform these polynomials into the generic form $$\widetilde{...
Giulio Crisanti's user avatar
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) ...
Tom Copeland's user avatar
  • 10.5k
2 votes
1 answer
85 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 ...
Alec Jacobson's user avatar
20 votes
0 answers
433 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 ...
M. Winter's user avatar
  • 13.6k
24 votes
1 answer
622 views

Polytope where each vertex belongs to all but two facets

Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
Guillaume Aubrun's user avatar
9 votes
2 answers
341 views

Are there centrally-symmetric self-dual polytopes in dimension $d> 4$?

A convex polytope $P\subset\Bbb R^d$ is centrally symmetric if $-P=P$. It is self-dual (or better, self-polar?) if its polar dual $P^\circ$ is congruent to $P$, that is, there is a map $X\in\mathrm O(\...
M. Winter's user avatar
  • 13.6k
16 votes
3 answers
1k views

Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?

Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets. Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$. Can $\text{Proj}(P)$ have more than $f$ facets? ...
Pedro Ruiz's user avatar
1 vote
0 answers
137 views

References/applications/context for certain polytopes

First, let's consider an almost trivial notion. With any subspace $V\subset \mathbb R^n$ we associate a convex polytope $P(V)\subset V^*$ as follows. Each of the $n$ coordinates in $\mathbb R^n$ is a ...
Igor Makhlin's user avatar
  • 3,513
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$ ...
user147163's user avatar
4 votes
0 answers
132 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 ...
M. Winter's user avatar
  • 13.6k
17 votes
4 answers
1k views

Can I build infinitely many polytopes from only finitely many prescribed facets?

Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$. Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...
M. Winter's user avatar
  • 13.6k
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 & \...
Sam Hopkins's user avatar
  • 24.2k

1
2
3 4 5
19