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
918
questions
16
votes
3
answers
701
views
Can we realize a graph as the skeleton of a polytope that has the same symmetries?
Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton.
A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
2
votes
0
answers
48
views
2-dimensional smooth lattice polytopes with minimal edge lengths
For each integer $k \geq 3$, does there exist a full-dimensional, $2$-dimensional, smooth lattice polytope $P$ with $k$ edges, such that each edge contains only two lattice points (i.e. only its ...
1
vote
0
answers
90
views
Simple polytope with smooth facets
Let $P$ be a simple $3$-dimensional (and full-dimensional) lattice polytope such that every facet $F$ is a smooth polytope. Is then $P$ itself smooth?
EDIT: A full-dimensional lattice polytope $P$ is ...
1
vote
0
answers
68
views
Can sufficiently symmetric polytopes be uniquely reconstructed from their 1-skeleton?
General convex polytopes can not be uniquely reconstructed from their 1-skeleton1, as explained here. Not even the dimension is known from the skeleton, as e.g. the complete graph $K_n,n\ge 5$ is the ...
4
votes
1
answer
439
views
Is the preimage of a face under an affine map a face?
Let $X\subseteq\mathbb{R}^n$ be a convex set. Let $\pi{:}\ X\to\mathbb{R}^m$ be a linear map, with $m<n$ (for example, a projection). Let $\pi^{-1}(y)=\{x\in X\mid\pi(x)=y\}$ denote the inverse of $...
8
votes
1
answer
491
views
Higher dimensional scutoids?
The recent discovery of scutoids in biological structures is fascinating. Two scutoids are depicted below (from Scientists Have Discovered an Entirely New Shape, And It Was Hiding in Your Cells), each ...
6
votes
1
answer
125
views
How rich is the class of vertex- and edge-transitive polytopes?
There are only a few regular polytopes (five in 3D, six in 4D, three in any dimension above). In contrast, the class of uniform polytopes becomes very rich with higher dimensions.
The class of vertex-...
4
votes
2
answers
466
views
Complexity of 2D-Minkowski sum of non-convex polygons
I have read that the complexity of computing the Minkowski-Sum of $2$ non-convex polygons (through convex decomposition) is $O(m^2 n^2)$, where $m$ and $n$ is the number of vertices of each polygon. ...
4
votes
1
answer
136
views
Continuity of the combinatorial structure of a polytope with respect to face variables
Suppose we are given a convex polytope in terms of the face variables.
That is, let $Y = (1,x_1,\dots,x_n)$ and suppose we have vectors $W_a$ in $\mathbb{R}^{n+1}$ such that the locus $W_a \cdot Y \...
8
votes
0
answers
270
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 ...
4
votes
0
answers
207
views
Conjecture on tilting modules for an Auslander algebra
On page 13 of "Tilting modules for the Auslander algebra of $K(x)/x^n$" the author, Geuenich, suggests that the number ($p_{n,i}$) of isomorphism
classes of modules, occurring as the $i$-th summand of ...
6
votes
1
answer
263
views
Example of convex n-gon that cannot be decomposed into k congruent convex polygons
I asked a related question here on MO without any answers yet.
The question is in the title - give an example of a convex $n$-gon that cannot be subdivided into $k>1$ congruent convex polygons.
...
0
votes
0
answers
163
views
Probability that the perturbed convex hull is larger than the original one
I am wondering if any convex geometers/probabilists have looked at the following question:
Given $n$ randomly distributed (not sure what assumption to put there) points in $\mathbb{R}^d$, for each ...
-1
votes
2
answers
112
views
On OR condition in Linear Programming with exponentially many constraints [closed]
Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
9
votes
3
answers
448
views
Minimal combinatorial data needed to define a polytope [duplicate]
Suppose I give a list of vertices $(v_1, v_2, ..., v_n)$, and a list of "adjacencies", i.e. pairs of vertices $(v_i,v_j)$. Does it exists a unique polytope that has this vertices and realises the ...
1
vote
0
answers
47
views
What separates a cyclic polytope from a projective polytope?
I am having trouble understanding the difference between a cyclic polytope and a convex projective polytope as positive geometries.
The link https://arxiv.org/pdf/1703.04541.pdf is the source of ...
6
votes
1
answer
285
views
Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?
In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...
3
votes
0
answers
173
views
Refined f- and h-partition polynomials of the associahedra
The f-polynomials, $F_n(x)$ (cf. OEIS A126216, A033282, and A086810), and the h-polynomials, $H_n(x)$ (cf. A001263, the Narayana polynomials), of the family of simple convex polytopes the associahedra ...
2
votes
0
answers
40
views
Efficient $H$ representation of matrices with distinct cyclic shift permuted entries
Given points $v_1,\dots,v_n\in\mathbb Z^n$ in codimesion $1$ hyperplane $x_1+\dots+x_n=t$ with $0\leq x_{i}$ and a cyclic shift permutation $\sigma$ where
$v_1,\dots,v_n$ when written as columns of ...
7
votes
2
answers
254
views
How different can the constituents of an Ehrhart quasi-polynomial be?
Consider a $d$-dimensional convex rational polytope $P\subset\mathbb{Q}^d\subset\mathbb{R}^d$. Then, it's a standard fact that in general the function counting the number of lattice points inside the ...
1
vote
0
answers
193
views
Relative interior of a normal cone at a face of a convex polytope?
Suppose $A$ is a nonempty convex polytope in $\mathbb{R}^n$. Suppose $F$ is a face of $A$.
Consider the normal cone of $A$ at $F$:
$C_A(F)=\{v\in\mathbb{R}^n:v\cdot x\geq v\cdot y\ \forall\ x\in ...
3
votes
1
answer
260
views
Size of a minimal non-negative conic basis
Suppose $v_1,\dots,v_n \in \mathbb{R}^k$ are entry-wise non-negative (column) vectors with $k<n$. Let $r \leq k$ be the non-negative rank of the matrix $V = [v_1 v_2 \cdots v_n]$ (i.e., the ...
9
votes
2
answers
724
views
Parallelepiped is defined by the volumes of its faces
Let $v_1,...,v_n\in \mathbb{R}^n$ be linearly independent. The parallelepiped defined by these vectors is $P(v_1,...,v_n)=\{\sum_{i=1}^{n}\alpha_i v_i|~0\le\alpha_i\le 1\}$. Observe that while the ...
6
votes
1
answer
246
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 ...
10
votes
1
answer
456
views
Odds on rolling a rhombicosidodecahedron
This is more of a curiosity to me, but I'm sure I don't have the mathematical skills to answer it. That said... I took a look at several other posts with questions that relate to this one, but I ...
2
votes
1
answer
344
views
Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?
Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
0
votes
0
answers
337
views
Finding a point in the relative interior of the convex hull of a set of integer-valued vectors
Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
1
vote
0
answers
51
views
Projecting two convex polyhedra onto their intersection
Suppose we are given two convex polyhedra $\mathcal{C}_1, \mathcal{C}_2 \subset \mathbb{R}^n$ with non-empty intersection $\mathcal{C}_1 \cap \mathcal{C}_2 \neq \emptyset$.
For the orthogonal ...
1
vote
0
answers
55
views
geometry of intersection of 2 polytope in higher dimension [closed]
Suppose $P_{1}$ is a $\frac{n}{2}$-dimension polytope in $ R^{n}$ with barycenter $c$, and $P_{2}$ is a $(n-1)$-simplex in $R^{n}$ with the same barycenter as $P_{1}$, i.e $c$ . And also suppose they ...
4
votes
0
answers
88
views
Maximum number of integer points in a polytope
What is the maximum number of integer points $\#M$ in a dimension $n$ closed bounded convex polytope $M$ given by $Ax\leq b$ with number $m$ of constraints and $O(d)$ bits in any entry of $A\in\Bbb Z^{...
3
votes
0
answers
161
views
What is a natural way to extend a function from a subset of vertices to faces?
Let $n$ be a positive integer, and suppose $f$ is a probability distribution on the $2^n$ subsets of $[\![n]\!] := \{1,\ldots,n\}$. What is a "natural" way to extend $f$ to a distribution $\bar{f}$ on ...
4
votes
0
answers
139
views
Reciprocity for multi-parameter Ehrhart polynomials
In McMullen's 1977 paper "Valuations and Euler-type relations on certain classes of convex polytopes" (https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s3-35.1.113), he shows that for $...
9
votes
2
answers
467
views
The "Johnson polychora"
Firstly, a definition:
A convex polyhedron, whose faces are regular polygons (2D polytopes).
This includes the 92 Johnson solids, 13 Archimedean solids, 5 Platonic solids and two infinite ...
0
votes
0
answers
194
views
Generalizations of 'Injectivity on one line'
The main result of J. Gwozdziewicz in this paper says the following:
"Let $k$ be an algebraically closed field of characteristic zero, and let $f:k[x,y] \to k[x,y]$, $(x,y) \mapsto (p,q)$, be a $k$-...
1
vote
0
answers
115
views
Radial similarity of Newton polytopes
Let $k$ be a field of characteristic zero, and assume that $p,q \in k[x,y]$ is a Jacobian pair, namely, $p_xq_y-p_yq_x \in k^*$
(= the determinant of the Jacobi matrix $\in k^*$).
It is known that ...
2
votes
1
answer
319
views
Bit complexity of Barvinok's algorithm
I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension.
What exactly is this arithmetic complexity?
...
13
votes
1
answer
527
views
Minuscule weights of parabolic sub-root systems are not far from dominant
Let $\Phi$ be a crystallographic root system in an $n$-dimensional Euclidean vector space $(V,\langle\cdot,\cdot\rangle)$. For a root $\alpha\in \Phi$ we use $\alpha^\vee := \frac{2}{\langle \alpha,\...
1
vote
0
answers
42
views
Quantitative error control in Minkowski-Stein formula
Let $K\subseteq\mathbb R^d$ be a compact convex body with non-empty interior, and $E$ be a $(d-1)$-dimensional linear subspace of $\mathbb R^d$. Let $\theta\in\mathbb R^d$ be the unit vector such that ...
1
vote
0
answers
43
views
In convex optimization we know that the optimum solution is on which hyper plane
We have a standard linear program, I mean a set of inequalities $c_i^Tx\leq b_i$ where $i\in \{1,\ldots ,k\}$ and we want to find $max\{c^Ty| y\in \{\cap \{x|c_i^Tx\leq b_i\}\}$. I put some condition ...
3
votes
0
answers
294
views
Factorization of tropical polynomials
I am referring to the definition of a tropical polynomial given on page 8 (top of section 3) here in this review, https://arxiv.org/pdf/math/0306366.pdf. I understand that here a tropical polynomial ...
4
votes
1
answer
180
views
2-faces of reflexive Delzant polytopes
Question 1. Can a reflexive Delzant polytope of some dimension contain a $2$-face with more than $11$ edges?
Motivation. I would like more generally to get an answer to the following question:
...
17
votes
2
answers
2k
views
Who first used the word "Simplex"?
Who first used the word "Simplex" to describe the considered geometric figure?
1
vote
1
answer
616
views
Product of two matrices of convex combinations [closed]
How to show that product of two matrices $\mathbf{A}$ and $\mathbf{B}$ of convex combinations as $\mathbf{C=A*B}$ is also a matrix of convex combinations.
Convex combinations: entries of each column ...
0
votes
0
answers
38
views
Influence of Vertex Weights on Performance of Polyhedral TSP Algorithms
It is well known, that the optimal tours are invariant under the addition of vertex weights; it is also known, that minimum spanning trees provide an upper bound on the length of the shortest Hamilton ...
15
votes
4
answers
810
views
Convex bodies have more volume on the outside near the boundary
I am looking for a reference for a result from convex geometry that I suspect has already been proven. The result seems geometrically obvious, but I couldn't find a similar result in Peter Gruber's ...
6
votes
2
answers
150
views
Inequality on permutation polytope
Let $a = (a_1, \cdots, a_n), b = (b_1, \cdots, b_n), c = (c_1, \cdots, c_n) \in \mathbb{R}^n$ with $a_1 \geq \cdots \geq a_n, b_1 \geq \cdots \geq b_n, 0 < c_1 \leq \cdots \leq c_n$.
In addition, ...
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 ...
1
vote
0
answers
254
views
Prove that the following set of triples forms a convex polytope
Take $a,\,b,\,c,\,d \in \mathbb R_+$ such that $a+b+c+d=1$. Define:
\begin{equation}
x_1 = \min(a+b,\,c+d)\,,\qquad x_2 = \min(a+c,\,b+d)\,,\qquad x_3 = \min(a+d,\,b+c)\;.
\end{equation}
I would like ...
2
votes
1
answer
156
views
Counting lattice points can some give all?
Given convex polytope $\mathcal P\subseteq\Bbb R^n$ with $\mathcal P_\Bbb Z\leq2^n$ integer points and given locations of $O(\log \mathcal P_\Bbb Z)$ integer points in some positions can we obtain $\...
8
votes
0
answers
194
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 :
...