# 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

251 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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$, ...
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 ...
487 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 ...
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 ...
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 ...
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 ...
243 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 ...
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 ...
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 ...
241 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 ...
507 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 ...
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 ...
309 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 ...
353 views

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 ...
266 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 ...
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 ...
84 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/...
253 views

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

See the edit at the bottom (April 2021) 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 ...
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 : ...
156 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 ...
135 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$, ...
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\}$ ...
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 ...
875 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? ...
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 ... 0answers 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? 0answers 334 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 ... 0answers 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 ... 0answers 135 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 ... 0answers 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 ... 0answers 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 ... 0answers 146 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 ... 0answers 99 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 ... 0answers 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 ... 0answers 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 ... 0answers 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 ... 0answers 449 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 ... 1answer 196 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 ... 0answers 60 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 ... 0answers 112 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 ... 0answers 101 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 ... 0answers 166 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 ... 0answers 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 ... 0answers 127 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<... 0answers 295 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 ...
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 ...