Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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 ...