All Questions
Tagged with co.combinatorics convex-polytopes
244 questions
4
votes
2
answers
173
views
4-polytopes with only one kind of regular facet
Is there a neat way to show (or a reference that already proves) that
the 4-cube is the only convex 4-polytope in which all facets are regular 3-cubes?
the 24-cell is the only convex 4-polytope in ...
1
vote
1
answer
112
views
Regions of hyperplane arrangements and their faces
Consider a finite hyperplane arrangement $\mathcal{A}$ over $\mathbb{R}^n$. Let the regions given by $\mathcal{A}$ be $\mathcal{R}(\mathcal{A})=\{A_1,\dots A_m\}$ for some $m$.
For any index set $I\...
- 109k
2
votes
0
answers
94
views
Anything similar to cone product formula (for convex polytopes)?
The convex polytope flag vector ring $\mathcal{R}$ satisfies the cone product formula
$$
C(U) C(V) = C(J(U, V)) + DUV
$$
where
$$
J(U, V) = U C(V) + C(U) V - e_1 UV
$$
is the join formula.
Note: ...
- 459
6
votes
1
answer
539
views
Proofs of Euler's characteristic formula for n-Dim polytopes
Twenty proofs of Euler's formula V - E + F - 1 = 1, which applies to convex polyhedrons, i.e., 3-dimensional polytopes, are presented at the Geometry Junkyard.
I'm interested in proofs of the more ...
- 10.5k
4
votes
3
answers
617
views
An example of a "simple poset" which does not belong to a convex polytope
Are there examples of d-regular graphs (i.e. graphs where every node has exactly d adjacent nodes) which are not the 1-skeleton of a simple convex polytope?
UPDATE:
New version of the question: is ...
- 1,435
3
votes
1
answer
152
views
Are there any more polytopes whose 2-faces are identical 4-gons?
What are examples for convex polytope $P\subset \Bbb R^d,d\ge 3$ for which holds
$P$ is 2-face transitive (that is, all 2-faces are equivalent under the symmetries of $P$), and
all 2-faces of $P$ are ...
- 13.6k
5
votes
1
answer
417
views
Iterated derivative and rectangular standard Young tableaux
We first make a few definitions, seemingly out of the blue (they are introduced/defined in this paper).
Let $F^0_{a}(z) = (1-z)^{-1}$ and define recursively
$$
F^{k+1}_{a}(z) = z^{a-1} \frac{d^a}{dz^...
- 446
1
vote
1
answer
103
views
A source for $01$-polytopes
Can you recommend any books or survey articles on $01$-polytopes, thats is, polytopes with vertices in $\{0,1\}^n$?
I am less interested in random $01$-polytopes, but more in the combinatorial ...
- 4,589
1
vote
0
answers
49
views
Realizing 0/1-polytopes with shortest possible edge lengths
Has there been something written about the following question?
Question: Given a 0/1-polytope, what is the shortest edge lengths with which this polytope can be realized as a 0/1-polytope.
The ...
- 13.6k
2
votes
1
answer
85
views
The number of Hamiltonian circuits on a convex polytope embedded in $\mathbb{R}^N$
Recently I wondered whether there might be a natural topological complexity measure for convex polytopes embedded in $\mathbb{R}^N$. After some reflection it occurred to me that the number of distinct ...
- 3,486
22
votes
3
answers
2k
views
Sampling from the Birkhoff polytope
The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope
Recently someone asked me if I knew
How to sample (in polynomial time) ...
- 32.1k
3
votes
1
answer
94
views
Regular triangulations of star-convex polyhedra with given boundary
Given an $n$-dimensional star-convex polyhedron $P\subset \mathbb{R}^n$ with simplicial facets, is it always possible to construct a regular triangulation $K$ of $P$ which does not subdivide the ...
- 6,337
5
votes
1
answer
322
views
Sufficient criterion for a simplicial sphere to be polytopal
Are there any purely combinatorial criteria which allow you to deduce that a spherical simplicial complex is polytopal (i.e., there exists a simplicial polytope whose boundary is isomorphic to it)?
...
- 10.7k
11
votes
1
answer
228
views
Geometric realization of combinatorial self-duality in polytopes
Let's say I have a combinatorially self-dual polytope $P\subseteq\Bbb R^d$, i.e., its face lattice is isomorphic to its dual (you reverse the direction of the lattice order).
Question: Is it always ...
- 10.7k
1
vote
1
answer
111
views
Given $H_{N}=\{\vec{x} \in [-1,1]^N:\sum_{i=1}^N x_i = 0\}$, what is the smallest subset $S \subset H_{2N}$ such that $\mathrm{conv}(S)=H_{2N}$
Motivation:
This is related to a different question I asked in April. It occurred to me while thinking about the sums of uniform random variables and it stuck in my mind because it's the special case ...
CommunityBot
- 1
2
votes
0
answers
252
views
Understanding the geometry of $H_{n}=\{\vec{x} \in [-N,N]^n:\sum_{i=1}^n x_i = 0\}$
I am not an expert in convex geometry but if we define $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{R}$ and $S_n = \sum_{i=1}^n a_i$ I suspect that for arbitrary $N \in [1, \infty) $:
...
- 3,871
16
votes
5
answers
1k
views
Name of a polytope
What is the name of the polytope $\Sigma\cap (-\Sigma)$ for $\Sigma$ a $d-$simplex with barycenter at the origin?
In dimension $2$, one gets a hexagon, in dimension $3$ an octahedron (given by the $6$...
- 13.6k
1
vote
1
answer
125
views
Projections of particular simplex yielding boundary of a regular polygon?
What is the maximum $m$ such that there is a simplex with $n$ vertex points in $n-1$ dimensions whose projection yields boundary of a regular $m$-gon on $2D$ plane?
- 548
5
votes
0
answers
140
views
$q$-Kostant partition function and flow polytopes?
The Kostant partition function is known to be related to volumes and Ehrhart polynomials of flow polytopes of graphs (see e.g. https://link.springer.com/article/10.1007/s00031-008-9019-8 or https://...
- 24.2k
12
votes
2
answers
510
views
Positivity of the coefficients of the Ehrhart polynomial of a cross-polytope
Question 35996 asks about the Ehrhart polynomial $i_d(n)$ of the
standard regular cross-polytope. It can be defined equivalently by
$$ \sum_{n\geq 0}i_d(n)x^n = \frac{(1+x)^d}{(1-x)^{d+1}}. $$
It ...
- 43.2k
1
vote
0
answers
79
views
What is known about the combinatorics of the hyperplane arrangement spanned by cyclic polytopes?
Let $1\leq d$ be an integer.
Consider the $d$-dimensional moment curve $\mu\colon \mathbb R\to \mathbb R^d$ given by $t\mapsto (t,t^2,\dots, t^d)$. Given a finite subset $S\subset \mathbb R$ of ...
- 725
3
votes
2
answers
344
views
Is a vertex- and edge-transitive polytope already a uniform polytope?
I want to consider (convex) polytopes $P=\mathrm{conv}\{p_1,...,p_n\}\subset\Bbb R^d$ which are both, vertex- and edge-transitive (or maybe stronger: 1-flag-transitive).
Question: Is every such ...
- 13.6k
5
votes
2
answers
345
views
Finding the Boundary Faces of the Zonohedron
A zonotope is a linear combination of m vectors with coefficients in [0,1]: $Z = \{ \sum \lambda_i v_i : 0 \leq \lambda _i \leq 1 \}$. The fancy way is to say it's the Minkowski sum of line segments ...
- 2,821
8
votes
2
answers
497
views
Integer decomposition of dilated integral polytopes
For $n > 0$, let $P$ be an integral polytope, that is, the convex hull in $\mathbb{R}^n$ of points in $\mathbb{Z}^n$. Suppose that $\dim(P) = n$.
Question: Given $d > n + 2$ is it true that
$$ ...
- 4,679
8
votes
1
answer
725
views
Number of simplicial polytopes with a given f-vector
Plenty of very nice literature is available on the characterization of f-vectors of simplicial complexes of diverse sorts (results by Billera, Bjoerner, Kalai, Stanley, among others). I mention, as an ...
2
votes
0
answers
87
views
Existence of a "generic enough" lattice point interior to a lattice triangle
Let $T$ be a lattice triangle in $\Bbb R^2$ (i.e. the convex hull of three noncolinear points in $\Bbb Z^2$), and assume it has at least one interior lattice point. Is it always possible to find a ...
- 3,079
11
votes
3
answers
847
views
"Database" of simplicial polytopes/spheres
Reading through various papers on polytopes I have come across really interesting examples of simplical polytopes and non-shellable (or non-PL) simplicial spheres but sometimes it is hard to keep ...
- 3,407
5
votes
1
answer
349
views
What is the lower bound for the number of facets that a general convex $d$-polytope with $n$ vertices can have?
I am familiar with Barnette's Lower Bound Theorem on the number of facets a $d$-dimensional simplicial convex polytope with $n$ vertices can have. Is there a similar result for a general (i.e. not ...
- 6,337
0
votes
0
answers
42
views
When is the set of faces of a convex polytope algebraically independent?
This is related to another question of mine
Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in ...
- 3,079
3
votes
0
answers
102
views
The ring generated by a convex polytope and its faces
Let $V=\Bbb R^n$. Morelli defined the (commutative unital) ring $L(V)$ to be the additive group generated by the indicator functions of convex polytopes in $V$ with multiplication induced by Minkowski ...
- 3,079
1
vote
1
answer
106
views
Linear relations between volume of a polytope and its faces
Let $P$ be a polytope. Is anything known about the set of linear relations that hold between the volumes of the (not-necessarily proper) faces of $P$ as $P$ “varies slightly”? By varies slightly I ...
- 6,337
10
votes
2
answers
224
views
The set of polytopes with given $f$-vector
Let $f=(f_0,\ldots f_n)$ be a vector in $\Bbb N^{n+1}$. Let $X$ be the set of all (ordered) $f_0$-tuples in $\Bbb R^n$ whose convex hull has $f$ as its $f$-vector. Assume that $X$ is non-empty. Is ...
- 3,079
2
votes
1
answer
349
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$....
CommunityBot
- 1
1
vote
0
answers
41
views
Possible volumes of lattice polytopes
All polytopes here are assumed to be convex lattice polytopes.
Given a polytope $P$, set $$v(P):= (\operatorname{vol}(F))_{F\text{ a face of }P},$$ where the volume of a $d$-dimensional polytope $P\...
- 3,079
3
votes
0
answers
84
views
condition on rational polyhedral cone to guarantee dual cone is homogeneous
Let $\sigma\subseteq \Bbb R^d$ be a full-dimensional rational polyhedral cone which is strongly convex (i.e. $\sigma\cap-\sigma=0$).
Definition. The cone $\sigma$ is homogeneous if there are ...
- 3,079
16
votes
3
answers
720
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 $...
- 156k
1
vote
0
answers
92
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 ...
- 197
2
votes
0
answers
51
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 ...
- 197
8
votes
1
answer
497
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 ...
- 984
13
votes
1
answer
538
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,\...
- 24.2k
2
votes
0
answers
41
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 ...
- 13.9k
3
votes
0
answers
181
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 ...
- 10.5k
7
votes
2
answers
268
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 ...
- 650
2
votes
1
answer
340
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?
...
- 17k
6
votes
1
answer
254
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 ...
3
votes
0
answers
163
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 ...
- 6,853
4
votes
0
answers
143
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 $...
- 24.2k
31
votes
4
answers
2k
views
Probability of zero in a random matrix
Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...
- 13.4k
28
votes
1
answer
1k
views
Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)
This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original ...
- 156k
9
votes
4
answers
1k
views
Positivity of Ehrhart polynomial coefficients
Are there any results stating that a given family of convex polytopes have Ehrhart polynomials with non-negative coefficients?
What methods are available for proving such a property for some family ...
- 24.2k