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
4
votes
1answer
108 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 $...
0
votes
0answers
27 views
Interpretation of this sum for concave bodies
For some polyhedron, $P$, define
$$H(P)=\sum_{e\in E} L_e(\pi - \delta_e)/(4\pi)$$
Where $E$ is the set of all edges of the polyhedron, $L_e$ is the length of edge $e$ and $\delta_e$ is the interior ...
7
votes
1answer
256 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 ...
3
votes
0answers
49 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-...
2
votes
2answers
32 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
1answer
100 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 \...
7
votes
0answers
154 views
Integral representations of finite groups and lattice point geometry
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 representation over the integers. Consider ...
3
votes
0answers
78 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
1answer
115 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
0answers
29 views
Realisation of a Polytope as a convex set [duplicate]
Suppose I have ALL the combinatorial data of an abstract Polytope: a list of all facets and incidence relations.
Is there a way to produce linear functions, in a suitable $R^d$, so that the region ...
0
votes
0answers
123 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 ...
0
votes
2answers
80 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
3answers
326 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
0answers
22 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 ...
4
votes
1answer
85 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
0answers
113 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
0answers
36 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
2answers
136 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
0answers
35 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
1answer
98 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
2answers
452 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
1answer
153 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
1answer
273 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
1answer
151 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
0answers
31 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
0answers
37 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
0answers
28 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
0answers
72 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
0answers
151 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
0answers
94 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 $...
6
votes
1answer
132 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
0answers
166 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
0answers
72 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 ...
1
vote
1answer
155 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?
...
12
votes
1answer
401 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
0answers
35 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
0answers
39 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
0answers
93 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 ...
3
votes
1answer
83 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:
...
16
votes
2answers
2k views
Who first used the word “Simplex”?
Who first used the word "Simplex" to describe the considered geometric figure?
0
votes
1answer
102 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
0answers
23 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
4answers
591 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
2answers
138 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, ...
39
votes
3answers
2k 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
0answers
170 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
1answer
140 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
0answers
183 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 :
...
0
votes
0answers
92 views
On necessary condition for polytopes with constant number or polynomial number of integer points?
If we fix $m>0$ (for example say $m=2$ or $m=4$) then for a convex polytope $\mathcal K$ in $\Bbb R^n$ presented by $O(n^c)$ linear inequalities is it true that for $|\mathcal K\cap \Bbb Z^n|=m$ it ...
4
votes
1answer
128 views
On necessary condition for no integer points in polytope
For a convex polytope $\mathcal K$ in $\Bbb R^n$ presented by $O(n^c)$ linear inequalities is it true that for $|\mathcal K\cap \Bbb Z^n|=0$ it is necessary that at least one axis of John's ellipsoid ...
