All Questions
Tagged with co.combinatorics convex-polytopes
244 questions
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 ...
- 3,079
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
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
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 $...
- 13.6k
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
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
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 ...
- 10.5k
6
votes
1
answer
133
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-...
- 13.6k
4
votes
0
answers
210
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 ...
- 10.5k
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
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
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
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 ...
- 7,149
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$....
- 159
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
142
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
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?
...
- 13.9k
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
4
votes
1
answer
189
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:
...
- 14.3k
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 ...
- 2,585
4
votes
0
answers
221
views
Extending a Theorem of Brualdi to Matrices with Infinitely Many Rows
This question is about extending a result on transportation polytopes from Brualdi regarding $m\times n$ matrices to the case when $m=\infty$.
Notation: Denote an $m\times n$ matrix by $A=[a_{i,j}]$, ...
- 329
6
votes
1
answer
254
views
Extend space to make polyhedra convex hulls of finite sets
A (convex) polytope is the convex hull of a finite number of points in Euclidean space (this is the so-called "vertex description"). Alternatively, it can defined to be a bounded polyhedron (this is ...
- 24.2k
5
votes
2
answers
294
views
Convex caps with prescribed edges
Let $P$ be a convex polygon in the plane $R^2=R^2\times \{0\}$, and $E$ be the edge graph of some subdivision of $P$ into convex polygons, which is $3$-connected. Does there exist a convex polyhedral ...
- 7,149
2
votes
0
answers
545
views
On Kalai's $3^{d}$ conjecture
I just learned the existence of Gil Kalai's $3^{d}$ conjecture, which according to Wikipedia, is proven for $d$ at most $4$. It states that every $d$ dimensional polytope with central symmetry has at ...
- 6,984
4
votes
2
answers
675
views
How to know if convex-hull of a set contains zero?
Let $(\lambda_1 , \cdots , \lambda_d) \vdash k$ be a partition of $k$ of length $d$. Is there any way to decide if $0 \in \text{Conv}\{(\underbrace{\alpha_1, \cdots, \alpha_1}_{\lambda_1}, \cdots , \...
- 500
7
votes
1
answer
295
views
Section of an $n$-dimensional convex polytope by $2$-dimensional plane
Consider an $n$-dimensional convex polytope with $k$ vertices. In the worst case the number of faces is exponential in $n$ and $k$. Consider a $2$-dimensional plane which intersects this polytope, i....
- 415
3
votes
2
answers
302
views
Narayana polynomials as numerators of Ehrhart series rational functions?
The Narayana polynomials (OEIS A001263) are the h-polynomials of the associahedra (the Stasheff polytopes) and their dual simplicial polytopes (cf. the Fomin and Reading ref in the OEIS entry).
Are ...
- 10.5k
8
votes
1
answer
498
views
Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)
From "The multiple facets of the associahedra" by Loday:
Let us consider the formal power series
$$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$
and let
$$ g(x) = x+b_1 x^2 + ...
- 10.5k
4
votes
0
answers
181
views
Keep doing it: generalized Catalan
One more time, let us see how else the Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ can be generalized. First recall the generating function
$$C(x):=\frac{1-\sqrt{1-4x}}x=\sum_{n\geq0}C_n\,x^n.$$
...
- 43.2k
4
votes
1
answer
172
views
The number of simplicial and general $d$-polytopes with $d+3$ labelled vertices
Micha Perles used Gale diagrams to compute the number of simplicial $d$-polytopes with $d+3$ vertices and of general $d$-polytopes with $d+3$ vertices. The computation can be found in Chapter 6.3 of ...
- 24.7k
2
votes
0
answers
62
views
on vectors for which the intersection of their convex hull and the nonegative orthant is the unit simplex
Consider the vectors $r^1 = (0,2,-1)$, $r^2 = (-1,0,2)$, and $r^3 = (2,-1,0)$. Two properties of these vectors that interest us here are:
1) The $i$'th coordinate of $r^i$ is 0, and
2) The ...
- 745
3
votes
1
answer
158
views
Cyclic polytopes whose boundary is a flag complex
A cyclic polytope $C(n, d)$ is defined as the convex hull of $n$ distinct points on the moment curve in $\mathbb{R}^d$ (here $n>d$). This is a simplicial polytope so its boundary $\partial C(n, d)$ ...
- 1,017
0
votes
1
answer
28
views
Finding a point at which only certain linear functionals are integral
Let $C$ be a full-dimensional rational polyhedral cone in $\Bbb R^d$ with facets $G_1,\ldots,G_n$ . For each $i$, let $h_i$ be an integer-valued linear functional on $\Bbb R^d$ whose kernel is the ...
- 3,079
1
vote
0
answers
385
views
About hyperplanes cutting the discrete hypercube
Given $\{-1,1\}^n$ we randomly choose a hyperplane in $\mathbb{R}^n$. Now given an integer $p \in [1,n]$ and a number $\epsilon \in [0,1]$, I want to ask, "How likely is it that at least one of the $p-...
- 2,246
0
votes
1
answer
81
views
Can convex combinations of indicator functions for pairwise non-disjoint sets unordered by inclusion dominate one another?
Let $N$ be a finite subset of the naturals. Let $P$ be a set of subsets of $N$ such that:
1) $P\neq \varnothing$,
2) $\forall x\in P, |x| >1$,
3) $\forall x,y\in P,$ if $x\neq y$, then $x\not\...
- 3
2
votes
0
answers
165
views
Link of a power series by the Bernoullis for a Riccati equation to zonotopes?
On pg. 85 of The Rise and Development of Theory of Series up to the Early 1820s by Ferraro is a series soln. of
$$ d^2z/z = -x^2dx^2 $$
related to the reputed first appearance of a Riccati-type eqn.,...
- 10.5k
16
votes
3
answers
1k
views
Can a convex polytope with $f$ facets have more than $f$ facets when projected into $\mathbb{R}^2$?
Let $P$ be a convex polytope in $\mathbb{R}^d$ with $n$ vertices and $f$ facets.
Let $\text{Proj}(P)$ denote the projection of $P$ into $\mathbb{R}^2$.
Can $\text{Proj}(P)$ have more than $f$ facets?
...
- 163
1
vote
1
answer
413
views
estimating binomial coefficients
There is a beautiful paper on the arXiv by Andrew Suk containing an asymptotic result about the Erdös-Szekeres convex polygon problem. I am struggling with one of the estimates he makes on page 4. He ...
- 7,637
5
votes
0
answers
474
views
Convex polytopes as "products" of lower dimensional polytopes of the same family
This MO-Q details the sense in which an associahedron is a product of lower dimensional associahedra, and this MSE-Q indicates the same is true for permutohedra.
Is there a reference which classifies ...
- 10.5k
2
votes
0
answers
75
views
Terminology and technique for repeated pairwise removal of elements of posets: "Collapsibility" of a "face poset"
Let $P$ be a poset, or partially ordered set. Let $\le$ denote the reflexive order on $P$, and $<$ the corresponding irreflexive order. Let the phrase "a maximal pair" in $P$ refer to an
ordered ...
- 366
2
votes
1
answer
404
views
Relating face polytopes of permutohedra to integer partitions
The OEIS entries A019538, A049019, and A133314, relate a refinement of the face polynomials of the permutohedra (A049019) to partition polynomials (A133314) defined by multiplicative inversion of an ...
- 10.5k
3
votes
0
answers
219
views
First to note/document the relation between permutohedra and multiplicative inversion
The relation between the refined face numbers of the permutohedra and the formal series expansion of the reciprocal of a function (exponential generating function, formal Taylor series) is given in ...
- 10.5k
1
vote
1
answer
153
views
Counting faces on multipermutahedra/multipermutohedra
A multipermutahedron is the convex hull of all permutations of a list of numbers. For example, $\Pi(0,1,2)$ generates a regular hexagon, and $\Pi(0,1,1,2)$ generates a cuboctahedron.
In general, ...
- 363
3
votes
0
answers
387
views
regular triangulations of the product of two simplices
Is description of all regular triangluations of $\Delta^n\times \Delta^k$ known? (Regular triangulations are those which correspond to vertices of Gelfand--Kapranov--Zelevinsky secondary polytope, or, ...
- 109k
1
vote
1
answer
256
views
Quick way to compute Ehrhart polynomial of Young diagram posets?
Using the hook formula, it is easy to compute the volume of order polytopes obtained from posets with partition shape, since this is the same as the number of linear extensions.
To my knowledge, ...
- 15.8k
4
votes
1
answer
388
views
What are the 4 convex simplicial 4-polytopes that have 6 vertices?
In Convex polytopes and related complexes by Klee and Kleinschmidt they state the number of $d$-polytopes with $d+2$ vertices is $\lfloor \frac{d^2}{4}\rfloor$.
I was wondering what the four $4$-...
- 43
9
votes
0
answers
204
views
Positivity of coefficients of Ehrhart polynomial of n-Tetrahedron
A set of positive integers $d_1, \dots, d_n$ describe two n-dimensional closed lattice tetrahedron:
$$ T = \left\{ (x_1, \dots, x_n) \in \mathbb{R}^n: \sum_{i=1}^n \frac{x_i}{d_i} \leq 1 \textrm{ and ...
- 909
1
vote
0
answers
57
views
Is the complement of a vertex figure in an (abstract) polytope connected?
I consider an (abstract) regular polytope $P$, and $H$ a vertex figure of $P$. Is the complement $P \setminus H$ connected (as a poset, in the sense that its Hasse diagram, ignoring the improper faces,...
- 31