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
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 $...
M. Winter's user avatar
  • 12.5k
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 ...
Mellon's user avatar
  • 197
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 ...
Mellon's user avatar
  • 197
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 ...
M. Winter's user avatar
  • 12.5k
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 $...
Tom Werner's user avatar
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 ...
Tom Copeland's user avatar
  • 9,937
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-...
M. Winter's user avatar
  • 12.5k
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. ...
Teodor Chiaburu's user avatar
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 \...
giulio bullsaver's user avatar
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 ...
David Handelman's user avatar
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 ...
Tom Copeland's user avatar
  • 9,937
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. ...
Per Alexandersson's user avatar
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 ...
user3799934's user avatar
-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 ...
Turbo's user avatar
  • 13.7k
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 ...
giulio bullsaver's user avatar
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 ...
Alexander's user avatar
  • 151
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 ...
Mario Krenn's user avatar
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 ...
Tom Copeland's user avatar
  • 9,937
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 ...
Turbo's user avatar
  • 13.7k
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 ...
user347489's user avatar
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 ...
Yi-Hsuan Lin's user avatar
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 ...
Rajesh Jayaram's user avatar
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 ...
erz's user avatar
  • 5,385
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 ...
Mohammad Ghomi's user avatar
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 ...
TwoScoopsOfHot's user avatar
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$....
Yi-Hsuan Lin's user avatar
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 \...
rasul's user avatar
  • 136
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 ...
madison54's user avatar
  • 337
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 ...
shere's user avatar
  • 111
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^{...
Turbo's user avatar
  • 13.7k
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 ...
dohmatob's user avatar
  • 6,716
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 $...
Sam Hopkins's user avatar
  • 22.7k
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 ...
FusRoDah's user avatar
  • 3,680
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$-...
user237522's user avatar
  • 2,783
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 ...
user237522's user avatar
  • 2,783
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? ...
Turbo's user avatar
  • 13.7k
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,\...
Sam Hopkins's user avatar
  • 22.7k
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 ...
Yining Wang's user avatar
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 ...
Nothing's user avatar
  • 19
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 ...
gradstudent's user avatar
  • 2,136
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: ...
aglearner's user avatar
  • 14k
17 votes
2 answers
2k views

Who first used the word "Simplex"?

Who first used the word "Simplex" to describe the considered geometric figure?
Gérard Lang's user avatar
  • 2,617
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 ...
Astro's user avatar
  • 185
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Harry Crimmins's user avatar
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, ...
C.M.'s user avatar
  • 61
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 ...
John Baez's user avatar
  • 21.3k
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 ...
jvn99's user avatar
  • 31
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 $\...
Turbo's user avatar
  • 13.7k
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 : ...
Rémy Martin's user avatar

1
6 7
8
9 10
19