All Questions
Tagged with co.combinatorics convex-polytopes
244 questions
56
votes
1
answer
3k
views
Intersecting family of triangulations
Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...
- 24.7k
34
votes
16
answers
7k
views
Generalizations of the Birkhoff-von Neumann Theorem
The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.
The question is to point out different ...
- 24.7k
32
votes
0
answers
2k
views
A Combinatorial Abstraction for The "Polynomial Hirsch Conjecture"
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$,
...
- 24.7k
31
votes
7
answers
3k
views
Why are we interested in permutahedra, associahedra, cyclohedra, ...?
The following families of polytopes have received a lot of attention:
permutahedra,
associahedra,
cyclohedra,
...
My question is simple: Why?
As I understand, at least the latter two were ...
- 13.6k
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, ...
- 37.7k
29
votes
0
answers
3k
views
Why do polytopes pop up in Lagrange inversion?
I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
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
25
votes
2
answers
692
views
Convex hull of total orders
Let $n$ be a positive integer and $\prec$ an arbitray total order on $\{1,\dots,n\}$. I associate to this order a vector $v$ with one coordinate for every pair $(i,j)$ s.t. $1\leq i\neq j \leq n$, by ...
- 4,484
24
votes
1
answer
622
views
Polytope where each vertex belongs to all but two facets
Let $P$ be a (convex, bounded) polytope with the following property: for every vertex $v$, there are exactly two facets which do not contain $v$. Does it follow that $P$ is (combinatorially) a ...
- 4,653
23
votes
3
answers
3k
views
How many different numbers can be obtained as product of first $n$ natural numbers?
Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...
- 323
22
votes
4
answers
3k
views
Can you determine whether a graph is the 1-skeleton of a polytope?
How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?
- 9,720
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) ...
- 28.6k
20
votes
5
answers
1k
views
From convex polytopes to toric varieties: the constructions of Davis and Januszkiewicz
One of the most useful tools in the study of convex polytopes is to move from polytopes (through their fans) to toric varieties and see how properties of the associated toric variety reflects back on ...
- 24.7k
19
votes
3
answers
2k
views
Cutting convex sets
Any bounded convex set of the Euclidean plane can be cut into two convex pieces of equal area and circumference.
Can one cut every bounded convex set of the Euclidean plane into an arbitrary number $...
- 17.9k
19
votes
3
answers
2k
views
Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?
Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the ...
- 10.5k
19
votes
2
answers
1k
views
About a Delzant polytope. (In particular dodecahedron)
Hi. I have a question.
Definition. Delzant polytope $P$ is a rational convex simple polytope with the smooth condition. Here, "smooth" means that for each vertex $v$, the $n$ edges containing $v$ ...
- 1,037
18
votes
1
answer
641
views
Can all convex polytopes be realized with vertices on surface of convex body?
The following question was asked by me on Mathematics.SE. Unfortunately, no one answered it so I thought I might give it a try one level higher. Below the line you can find the slightly edited ...
- 907
17
votes
4
answers
1k
views
Can I build infinitely many polytopes from only finitely many prescribed facets?
Given a finite set of convex $d$-dimensional polytopes $\mathcal P$, for some $d\ge 2$.
Question: Is it true that there are only finitely many different convex $(d+1)$-dimensional polytopes whose ...
- 13.6k
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
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$...
- 17.9k
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
16
votes
0
answers
298
views
Realization spaces of 3-dimensional polytopes with fixed face areas
It is a well-know result (Steinitz, 1922) that the realization space of 3-dimensional convex polytopes with fixed combinatorics is contractible.
A proof of this theorem can be found for instance in ...
- 31.2k
15
votes
3
answers
1k
views
Classification of Platonic solids
My question is very basic: where can I find a complete (and hopefully self-contained) proof of the classification of Platonic solids? In all the references that I found, they use Euler's formula $v-e+...
- 955
15
votes
2
answers
481
views
Ehrhart period collapse for $123\ldots k$-avoiding Birkhoff polytope?
For $1 \leq r \leq n$, let $\mathcal{B}^n_r$ denote the polytope of all real matrices
$$ \pi = \begin{pmatrix} \pi_{1,1} & \pi_{1,2} & \cdots & \pi_{1,n} \\
\pi_{2,1} & \ddots & \...
- 24.2k
14
votes
0
answers
254
views
Is combinatorial automorphism of symmetric convex polytope always antipodal?
The question is formulated in the title. More precisely, if $P$ is an origin-symmetric convex polytope in $\mathbb{R}^d$, and $f$ is a bijective transform of the set of the vertices of $P$, which ...
- 109k
14
votes
0
answers
262
views
Polytopes with few vertices and few facets
I recently realized that, for fixed $\alpha$ and $\beta$, the number of (combinatorial types of) $d$-polytopes with $\leq d+1+\alpha$ vertices and $\leq d+1+\beta$ facets is bounded by a constant that ...
- 278
13
votes
2
answers
2k
views
Combinatorics of the Stasheff polytopes
First a little background for those unaware. The Stasheff polytopes (or associahedra) are certain convex polytopes that arise in the theory of $A_\infty$-algebras. There is one polytope for each $n\...
- 3,423
13
votes
3
answers
1k
views
Triangulations of polyhedra
A topologist came to me with this question, but everything I think should work doesn't.
How many triangulations are there of a polyhedron with n vertices?
By a "triangulation" of a polyhedron P we ...
- 1,975
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
12
votes
2
answers
665
views
Detecting tilings by toric geometry
This is probably a silly question, but I figured that if there is a good answer, this would be a good place to ask.
Ever since I got my hands on the book "Toric Varieties" by Cox, Little and Schenck, ...
- 85.6k
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 ...
- 50.8k
12
votes
1
answer
651
views
Does a triangulation without fixed simplex property always exist?
Suppose we are given a triangulable topological space $X$. If $X$ has the fixed point property (FPP), then obviously for every triangulation $K$ of $X$ and every simplicial map $f:K\to K$ a simplex $\...
- 2,104
12
votes
4
answers
2k
views
What is the number of equitriangulations of the n-cube?
I wonder if this question has been considered before and if anything is known. My search attempts have failed so far.
Let's consider the n-dimesnional cube, $[0,1]^n$, and let's call a simplex with ...
- 85.6k
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 ...
- 263
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 ...
- 13.6k
11
votes
0
answers
352
views
Right-angled polytopes
%This question is motivated by the little discussion here at the bottom.
The following thing are known about hyperbolic right-angled polytopes:
Compact hyperbolic right-angled polytopes do not exist ...
- 1,268
11
votes
0
answers
366
views
Lower Bound on the Volume of Certain Polytopes
Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks
$$
\rho=\{B_1,B_2,\ldots,B_{k}\}
$$
we can define the set of equations
$$
E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in B_{i}}{x_j}\quad\text{...
- 3,626
10
votes
3
answers
1k
views
Polytopes with few vertices.
Suppose I have a convex polytope in $\mathbb{R}^d$ which I know has few vertices (in the case which prompted this question, I seem to have a polytope in $\mathbb{R}^9$ which has sixteen vertices). Is ...
- 96.4k
10
votes
2
answers
676
views
Status of Barany's conjecture?
One of Barany's most intriguing conjectures is about the $f$-vectors of convex polytopes. It asks:
Let $P$ be a convex $d$-polytope. Is it always true that $f_k \geq \min(f_0, f_{d-1})$?
A convex $...
- 1,312
10
votes
3
answers
322
views
Integer decomposition property with a partial order
Let $\mathcal{P}$ be a convex lattice polytope in $\mathbb{R}^n$. We say that $\mathcal{P}$ has the integer decomposition property (or "is IDP") if for all $k\in \mathbb{N}$ and $\alpha \in ...
- 24.2k
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
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 ...
- 15.8k
9
votes
1
answer
261
views
Do there exist "expanding" $1$-skeletons of simple $4$-polytopes?
Let $\{ G_n \}_{n \ge 1}$ be a sequence of graphs such that the number of vertices of $G_n$ tends to $\infty$ as $n \to \infty$. We say that $\{ G_n \}_{n \ge 1}$ is an expander family if
$\lambda_2( ...
- 7,857
9
votes
1
answer
665
views
Question about tetrahedron decomposition
Are there tetrahedra which can be subdivided into three non-overlapping parts similar to the original? I believe this would require splitting one face into three parts. I know some types of tetrahedra ...
- 93
9
votes
1
answer
523
views
The volume of the “unit ball” in $\mathbb{R}^{m\times n}$ with respect to the cut norm
This question is inspired by the question “ε-nets with respect to the cut norm” by the user Aaron, which had been reposted to cstheory.stackexchange.com.
The cut norm ||A||C of a matrix A=(aij)∈ℝm×n ...
- 1,959
9
votes
1
answer
327
views
The convex hull of Schur polynomial evaluations
Let $r\leq n$ and $d$ be positive integers. A probability vector is a vector of non-negative entries that sum to 1. For each probability vector $\lambda$ of length $n$, let
$$s(\lambda)=(\dim[\pi] \...
- 980
9
votes
1
answer
1k
views
Finding the vertices of a polyhedral complex coming from a GIT wall and chamber decomposition
I am interested in a polyhedral/combinatorics problem that arises in algebraic geometry in the context of geometric invariant theory (GIT).
Algebro-geometric background: Consider the natural ...
- 1,871
9
votes
1
answer
889
views
Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory
In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
- 10.5k
9
votes
0
answers
144
views
Which polytopes have compact realization spaces?
Let $P\subset\Bbb R^d$ be a convex polytope.
Its reduced realization space is the space of all combinatorially equivalent polytopes modulo projective transformations.
I am interested in polytopes for ...
- 13.6k
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