All Questions
Tagged with convex-polytopes enumerative-combinatorics
10 questions
4
votes
0
answers
287
views
How can we prove this combinatorial identity?
This is a follow up on my earlier MO post. Let's recall the sets
$$\mathbf{K}_n=\{\mathbf{k}\in\mathbb{Z}^n: k_i\geq0, k_1+\cdots+ k_n=n, k_1+\cdots k_i\leq i, \text{for all $1\leq i\leq n$}\}$$
and $\...
- 43.1k
5
votes
1
answer
398
views
Catalan sequences vs composition sequences
In the paper, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Pitman and Stanley studied the $n$-dimensional polytope
$$\Pi_n(\mathbf x)=\{y\in\...
- 43.1k
1
vote
0
answers
63
views
Counting $\bmod 2$ number of vertices of sparsely represented polyhedra
Given a polyhedron
$$Ax\geq b$$
is there an $NC^1$ or an $NC^2$ algorithm to count the number of vertices $\bmod2$?
Assume $A\in\{0,1\}^{m\times n}$ and $b\in\mathbb Z^{m}$ ($m=O(n)$) and assume rows ...
- 13.9k
3
votes
0
answers
152
views
Ehrhart-Macdonald reciprocity with multiplicities
Let $P$ be a convex lattice polytope in $\mathbb{R}^n$. The function $L(t, P) = |\mathbb{Z}^n \cap t\cdot P|$ is a polynomial, and we have an equality
$$L(-t, P) = (-1)^nL(t, P^{int}),$$
where $P^{int}...
- 645
3
votes
0
answers
70
views
On the proportion of simplicial $d$-polytopes on $n$-vertices
I have a question regarding estimates for the proportion of simplicial $d$-polytopes on $n$-vertices.
Let $c_s(n,d)$ denote the number of combinatorial types of simplicial $d$-polytopes on $n$ ...
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^{...
- 13.9k
2
votes
1
answer
339
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
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
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 ...
- 902
3
votes
3
answers
311
views
Are there infinite sets of stellations of polyhedra?
Lists of stellations of polyhedrons are given particular rules like in the book The Fifty Nine Icosahedra which follows "Miller's Rules".
There seems to be no "correct" ruleset to use, so more ...
- 2,615