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
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] \...
Ben's user avatar
  • 988
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). ...
Dac0's user avatar
  • 295
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) ...
Tom Copeland's user avatar
  • 9,197
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 $\...
T. Amdeberhan's user avatar
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\...
T. Amdeberhan's user avatar
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 ...
Dmitry Vilensky's user avatar
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 ...
Lucas Blakeslee's user avatar
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 ...
asv's user avatar
  • 20.3k
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 ...
Abdelmalek Abdesselam's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 ...
ElliptCg's user avatar
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 ...
Alec Jacobson's user avatar
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,\...
Dac0's user avatar
  • 295
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 ...
ZZZZZZ's user avatar
  • 11
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 ...
gigi's user avatar
  • 1,303
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$...
Yan X Zhang's user avatar
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$ ...
TanG's user avatar
  • 23
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}...
M. Winter's user avatar
  • 11.4k
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$ ...
user147163's user avatar
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 ...
M. Winter's user avatar
  • 11.4k
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 $...
TanG's user avatar
  • 23
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 ...
Alexander Praehauser's user avatar
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$ ...
BerndM's user avatar
  • 91
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 "...
aglearner's user avatar
  • 13.8k
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 ...
Richard Stanley's user avatar
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 ...
James Propp's user avatar
  • 18.8k
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 ...
M. Winter's user avatar
  • 11.4k
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 ...
Penelope Benenati's user avatar
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 $...
Faidh's user avatar
  • 71
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 \...
Penelope Benenati's user avatar
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 ...
Hugo Pfoertner's user avatar
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))$...
King 's user avatar
  • 21
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 ...
Vadim Semenov's user avatar
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 ...
M. Winter's user avatar
  • 11.4k
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?
Daniel Sebald's user avatar
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 ...
M. Winter's user avatar
  • 11.4k
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\...
G. Panel's user avatar
  • 513
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 ...
Penelope Benenati's user avatar
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 ...
Gro-Tsen's user avatar
  • 26.5k
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}$? ...
Mohammad Ghomi's user avatar
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 ...
G. Panel's user avatar
  • 513
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=\{...
James Propp's user avatar
  • 18.8k
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 ...
ryu576's user avatar
  • 171
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 $...
Joseph O'Rourke's user avatar
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 ...
M. Winter's user avatar
  • 11.4k
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 ...
Ryan Bennink's user avatar
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 ...
Gericault's user avatar
  • 235
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} ...
Tom Copeland's user avatar
  • 9,197
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 ...
M. Winter's user avatar
  • 11.4k
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 ...
Sirplentifus's user avatar

1
2 3 4 5
18