All Questions
Tagged with co.combinatorics convex-polytopes
244 questions
6
votes
1
answer
237
views
Some polytopes in $\mathbb R^n$ whose vertices have coordinates 1, -1 or 0
Let $n$ and $k$ be positive integers with $k\leq n$.
Let $P(n,k)$ be the convex hull in $\mathbb R^n$ of the $2^k {n \choose k}$ vectors whose exactly $k$ coordinates belong to $\{\pm 1\}$ all the ...
- 838
4
votes
2
answers
437
views
Unimodular triangulation and Ehrhart polynomials
Let $P$ be a convex lattice polytope. Then it has a polynomial Ehrhart function.
I am interested in what can be said about the Ehrhart polynomial when
$P$ has any of the properties
is integrally ...
- 15.8k
2
votes
1
answer
165
views
Integrally closed polytopes from 01-matrices
Let $A$ be a matrix with entries either 0 or 1, where each column contains at least one 1, to remove trivial degenerations.
Let $P$ be the convex hull of all integer vectors $x$ that satisfy $Ax \leq ...
- 156k
3
votes
1
answer
409
views
Looking for a canonical (matroid polytope) subdivision of the hypersimplex
A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are ...
- 902
7
votes
1
answer
756
views
Generalized permutahedron and random polytopes
The Birkhoff polytope $B_n$ is defined as the convex hull of the set of permutation matrices, which gives us the set of doubly stochastic matrices. A concept which is intimately related is that of the ...
- 1,846
4
votes
1
answer
271
views
On a conjecture by Hibi regarding h-vectors
For integral polytopes, it is conjectured (T. Hibi), that if the $h^*$-vector is symmetric, then it is also unimodal (increasing, then non-decreasing).
A non-integral polytope do not, in general, ...
- 1,046
1
vote
0
answers
107
views
Stronger condition than being a normal polytope?
A polytope $P$ with integer vertices is called normal if
for every $p = \sum_j a_j p_j $ such that $a_j \geq 0$, $\sum_j a_j = k \in \mathbb{N}$,
$p_j$ are vertices of $P$ and $p$ is an integer ...
- 15.8k
2
votes
1
answer
79
views
The minimal number of halfspaces to represent a convex but non strongly convex cone
We say a cone at the origin in $R^n$ means that it is an intersection of finitely many halfspaces, i.e.
$$C=\bigcap_{i\in I}H_i,\text{ where }|I|<\infty.$$
A cone is strongly convex if $C\cap -C=\...
- 7,722
6
votes
1
answer
395
views
Normal polytopes - counterexample?
An integral polytope $P$ is normal if all lattice points inside the integer dilation $kP$ can be expressed as $p_1+p_2+\dots+p_k$, where $p_i \in P$ are lattice points.
I am looking for an example $P$...
CommunityBot
- 1
4
votes
5
answers
728
views
Lattice points in dilated polytopes and sumsets
Let $P$ be an integral polytope, that is, the convex hull of some points in $\mathbb{N}^d$.
Let $p_1,\dots,p_m$ be all lattice points in $P$.
Question: What is the condition on $P$ that guarantees ...
- 15.8k
5
votes
2
answers
879
views
Intersection homology for toric varieties
is there any algorithm known for computing (middle perversity)intersection homology of complex toric varieties based on their combinatorial data? I'm not looking for a computer program.
Regards,
...
- 6,162
6
votes
1
answer
185
views
Maximizing ratio volume/diameter^n by an affinity
Suppose we have a convex compact body $D\subset \mathbb R^n$. We can try to apply affine transformation keeping the volume and decreasing the diameter of $D$.
It is clear that there is a constant $\...
- 7,276
3
votes
1
answer
271
views
The facial structure of the convex hull of a family of characteristic functions
Let $S$ be a finite set and let $\mathcal{A} \subset\mathcal{P}(S)$ be a family of subsets of $S$. Consider the convex polytope spanned by the characteristic functions of members of $\mathcal{A}$ :
$$...
CommunityBot
- 1
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 ...
CommunityBot
- 1
1
vote
1
answer
152
views
Submodular measures on the hypercube
By the hypercube I mean the lattice formed by all n-bit strings ordered by pointwise inequality. For example, $000 \leq 110$, $010 \leq 110$, $110$ and $001$ are not comparable. Further we have the ...
- 655
1
vote
0
answers
193
views
Lattice-point enumeration question involving linear combinations of matrices
I would like to know some references to learn more about an answer to this question, if there are any references:
Let $A_1, \dots , A_m$ and $B$ be $n\times n$ symmetric matrices. Let $$S = \{(x_1, \...
- 170
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( ...
- 24.7k
5
votes
0
answers
324
views
Lattice points inside a (n-dimensional) tetrahedron
Hi, overflowers.
I was interested in a sharp lower bound for the number of lattice points (say, integral lattice points) inside the tetrahedron defined by the coordinate hyperplanes and $x_1/a_1+...+...
- 306
3
votes
2
answers
270
views
Formalization (and background) of a formula, concering the integral points of a polygon.
I have recently become aware of the following neat statement.
Consider a convex polygon $P$ in the real plane with integral vertices. If we associate with every integral point $(a,b)$ the monomial $x^...
- 3,513
3
votes
1
answer
258
views
Classification of lattice polytopes with small number of lattice points in the facets
Suppose $P$ is a convex lattice polytope in $Z^3$ without interior lattice points, and we require the interior lattice points of each facet(i.e. dimensional 2 faces) are neither too much nor too few, ...
- 170
4
votes
1
answer
510
views
moduli space of polytopes
When considering classification problems about polytopes, I sometimes has the feeling that one need to talk about certain parametrized families, i.e. moduli space of such polytopes. But neither do I ...
- 27.8k
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 ...
CommunityBot
- 1
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\...
- 10.5k
1
vote
1
answer
288
views
Realizing not-quite-barycentric subdivision of a polytope
Given a poset $S$, one can form a new poset $I(S)$ whose elements are intervals in $S$ (i.e. either $\emptyset$ or $[a,b]$ for some $a\leq b\in S$) with ordering by (set) inclusion. If $S$ is ranked, ...
- 3,532
4
votes
1
answer
1k
views
Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)
Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i).
I guess complexity of its volume calculate is higher than linear in "N", am I right ?
(Is the complexity ...
CommunityBot
- 1
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$,
...
CommunityBot
- 1
7
votes
3
answers
866
views
Not quite regular polyhedra
Take a naive interpretation of regular polyhedra:
All vertices (including epsilon ball) congruent
All edges congruent
All faces congruent
We can now find interesting families by removing one ...
- 3,532
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, ...
- 13.1k
2
votes
1
answer
303
views
Max/min problems related to associahedra or their duals (ions on balls revisited)
Original motivation: This is a follow-up question to and generalization of MO Q78877 on equilibrium configurations of ions on n-Dim balls. Henry Cohn gave an excellent answer dispelling my naive ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
5
votes
0
answers
503
views
Reference for this polyhedral lemma
Recall the definition of a fan: Let $U$ be a finite dimensional real vector space. Then a fan is a collection $\mathcal{F}$ of cones in $U$ such that
(1) If $\sigma \in \mathcal{F}$ and $\tau$ is a ...
- 156k
3
votes
3
answers
390
views
Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?
I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...
- 17.9k
8
votes
2
answers
217
views
Flipping Hilbert series of semigroup rings
I'll first give intuition, and then give a precise statement.
For $|z|<1$, we have $\sum_{i \geq 0} z^i = 1/(1-z)$. For $|z|>1$, we have $\sum_{i<0} (-1) z^i=1/(1-z)$. Thus, the two ...
- 156k
8
votes
1
answer
1k
views
When is a complete fan a normal fan?
Is there a characterization for when a complete fan in $\mathbf{R}^n$ is the normal fan of a polytope? Thanks!
- 28.9k
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 ...
- 2,372
9
votes
0
answers
738
views
Counting Lattice Points in Real Polytopes
Suppose one did have an exact formula for the number of $\mathbb{Z}^n$-lattice points intersecting an arbitrary dilate of a (not necessarily rational) finite, closed and convex $n$-polytope. As a ...
CommunityBot
- 1
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
3
votes
0
answers
234
views
Maximum of a function on $d-$dimensional convex compact sets
Let $\mathcal C_d$ denote the set of all $d-$dimensional convex compact subsets with
barycenter at the origin of the $d$-dimensional Euclidean space $\mathbb E^d$. Given an
element $C\in\mathcal C_d$ ...
CommunityBot
- 1
8
votes
2
answers
383
views
Do singular values of a point set determine its shape?
Suppose I have $k$ points in $d$ dimensions. Let A be a $k\times d$ matrix with $i$th row giving the coordinates of $i$th point. Do singular values of this matrix have an interpretation as some kind ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
6
votes
2
answers
2k
views
Birkhoff's theorem about doubly stochastic matrices
Birkhoff's theorem states:
The set of $n \times n$ doubly stochastic matrices is a convex set whose extreme points are the permutation matrices
This theorem seems to be commonly attributed to ...
- 56.6k
0
votes
2
answers
611
views
6
votes
2
answers
659
views
How many vertices of a polytope can be chopped off to produce a k-vertex facet?
Let P be a simple n-facet d-polytope with facet F, and let F have k vertices. Let H be a halfspace and Q be a simple (n-1)-facet polytope such that H ∩ Q = P.
In terms of k, what is an upper ...
- 6,523
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 $\...
- 28.9k