All Questions
608 questions
2
votes
0
answers
45
views
Can every non-hemi uniform polytope tile hyperbolic space?
Can every uniform polytope which is not a hemipolytope tile hyperbolic space on its own?
- 2,773
4
votes
2
answers
315
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 5,429
1
vote
0
answers
61
views
Linear programming robustness to input perturbations
I'm running a linear program whose parametrization depends on the output of a neural network. I was wondering if there exist results on how robust linear programs are towards perturbations in their ...
- 11
1
vote
0
answers
58
views
Are cells of 4-polytopes a convex polyhedron by definition?
I'm going by the Wikipedia definition for a 4-polytope.
Do by definition, cells of 4-polytopes have to be a convex polyhedra?
If not, then are there polyhedra with non-convex faces?
If yes, is it the ...
- 11
2
votes
1
answer
644
views
How to maximise infinity norm of $x$ with constraint $Ax \le b$ using linear program? [closed]
I want to maximise the infinity norm of $x$, subject to constraint: $Ax \le b$. I think you can use a linear program to solve this, but how do you go about formulating it?
- 162
5
votes
1
answer
186
views
Looking for clarification of C-H Sah's definition of abstract scissors congruence
In C-H Sah's book Hilbert's third problem: scissors congruence, the author defines the data for abstract scissors congruence in order to prove Zylev's theorem by combinatorial means in great ...
- 1,025
0
votes
0
answers
115
views
Explicit equation for border of the Minkowski sum of sets
Assume we have sets of the form
$$
M_j = \{x\in\mathbb{R}^d : f_j(x) \le 0,x \ge 0\}
$$
where $x\ge 0$ means $x_i \ge 0 \quad \forall i=1,\dots, d$.
Goal
I am looking for an (explicit) representation ...
- 63.9k
6
votes
1
answer
277
views
Realizing spherical complexes as convex polytope
A spherical polytope is the intersection of some closed hemispheres which is non-empty and does not contain a pair of antipodal points. A spherical complex is a tiling of the whole (d−1)-dimensional ...
- 13.6k
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 63.9k
0
votes
0
answers
124
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 287
1
vote
0
answers
35
views
How to chose the start vector for the MTZ variables
In the context of LP-formulations for the Traveling Salesman Problem the MTZ constraints prevent subtours via $n$ (i.e. effectively $n-1$) additional variables $$u_1=1\\2\le u_2,\,\dots ,\,u_n\le n\\ ...
- 4,713
0
votes
0
answers
85
views
Realizability of abstract polytopes
What are the conditions that allow an abstract polytope to have a non-skew (but not necessarily convex) realization in Euclidean space?
- 2,773
2
votes
0
answers
35
views
Finding uniform polytopes in 3D versus in 4D
How was the exhaustive uniform polyhedron search (which found the great dirhombicosidodecahedron) conducted?
What’s so difficult about doing the same thing but in four dimensions?
- 2,773
1
vote
0
answers
200
views
Drawing a 3D object in a 3D environment, and converting to math [closed]
So I have been granted a free time and I want to work on a project but first I had to research.
As we know, lines have infinite points, and with lines, we can create infinite shapes. I want to let ...
- 11
0
votes
0
answers
109
views
How to find a set given its support function
Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
- 53
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
1
vote
1
answer
101
views
Graph diameter of the omnitruncated $E_8$ polytope
What is the graph diameter of the 1-skeleton of the omnitruncate of the $E_8$ family of uniform 8-polytopes?
CommunityBot
- 1
4
votes
1
answer
74
views
Simplicial polytope with regular cones
Let $P$ be a convex simplicial polytope in $\mathbb{R}^n$. Can we find a convex simplicial polytope $P_0$ in $\mathbb{R}^n$ combinatorially equivalent to $P$, satisfying the following condition: The ...
- 1,502
0
votes
0
answers
96
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
- 29
1
vote
1
answer
82
views
Do we really need degree constraints for ILP formulations of TSP problems
The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is
$$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...
- 5,429
2
votes
3
answers
2k
views
non-convex Polytope definition
I have a simple question. I read that given a vector space $N_{\mathbb{R}}$ over $\mathbb{R}$,
we can define a convex polytope in the following way:
$$P:= \Big\{ \sum_{u\in S} \mu_u u \,\Big| \, \...
- 2,773
0
votes
0
answers
97
views
Possible new convex uniform polytope
Does there exist a convex uniform 9-polytope obtained by diminishing the 9-hypercube, removing 480 of its 512 vertices and turning each 8-hypercube facet into an 8-orthoplex?
- 2,773
4
votes
1
answer
417
views
Triangulation of a simplex
I am looking for a triangulation of an $n$-dimensional simplex such that all sub-simplices are of comparable size, and are "as close as possible" to a regular simplex : the latter property ...
- 934
1
vote
0
answers
58
views
Second-order envelope theorem for linear programming
Consider parameterized linear programming $V(\theta) = \max_x \langle c(\theta),x\rangle$ s.t. $A(\theta)x\leq b(\theta)$, $x\geq 0$. Let's also assume $c,A,b$ are infinitely differentiable with ...
- 373
1
vote
1
answer
475
views
Sufficient conditions for a system of linear inequalities to admit a solution
I am looking for sufficient conditions such that a system of linear inequalities of the type $A x >0$ admits a non-negative solution $x \in \mathbb{R}^n_+$. I know a few properties of the $m \times ...
1
vote
0
answers
37
views
Sum of all integer binary solutions of a TUM linear system
I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...
- 11
2
votes
1
answer
96
views
A matrix that commutes with all symmetries of a vertex-transitive polytope
Let $P\subset\Bbb R^d$ be a vertex-transitive polytope aka. an orbit polytope.
Can there be a matrix $T\in\mathrm{SO}(\Bbb R^d)$ that commutes with all symmetries in $\mathrm{Aut}(P)\subset\mathrm O(\...
- 13.6k
4
votes
1
answer
866
views
When is a triangular matrix totally unimodular?
I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
- 32.1k
2
votes
2
answers
418
views
Lovasz theta function - uses
Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
- 32.1k
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?
...
- 32.1k
2
votes
0
answers
94
views
Dodecahedron deformation II
(Follow-up to this question)
Can a dodecahedron be deformed into a great stellated dodecahedron while maintaining the number of dimensions each element occupies?
- 2,773
6
votes
1
answer
264
views
Can a dodecahedron be deformed into a great stellated dodecahedron?
Can a convex regular dodecahedron be deformed into a great stellated dodecahedron while keeping all pentagons planar and all edges of nonzero length the whole time?
- 2,773
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
8
votes
3
answers
390
views
Is there any edge- but not vertex-transitive polytope in $d\ge 4$ dimensions?
I consider convex polytopes $P\subset\Bbb R^d$. The polytope is called vertex- resp. edge-transitive, if any vertex resp. edge can be mapped to any other by a symmetry of the polytope.
I am looking ...
- 13.6k
0
votes
0
answers
165
views
Minimum circumscribed ellipsoid of $\mathcal H$-polytope
Given matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^n$, consider the $\mathcal H$-polytope $P$ defined as follows
$$ P := \left\{ x \in \mathbb{R}^n : Ax \leq b \right\} $$
I ...
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 ...
3
votes
0
answers
121
views
Expanded 24-simplices in the Leech polytope
The vertex coordinate set for the contact polytope of the Leech lattice listed on Wikipedia contains all permutations of:
$\{4,-4,0^{22}\}$
$\{-3,1^{23}\}$
$\{3,-1^{23}\}$
The convex hull of these ...
- 2,773
0
votes
0
answers
137
views
Any technique for linearization, or linear approximation?
Consider the following Matrix constraint:
$$
\begin{bmatrix} -U+\psi\Sigma_b^{-1} & V \\ V^T & -V^TU^{-1}V+\tau_2 -\psi \end{bmatrix} \leq 0
$$
where $\Sigma_b$ is a known positive definite ...
3
votes
0
answers
243
views
Textbooks/References for Solid Angles? [closed]
Are there any good textbooks that consider the properties of solid angles for polytopes? Being not the most well-versed in geometry, I am unsure of where to start looking. Thank you very much!
- 4,713
1
vote
0
answers
48
views
Lattice deformations of regular polytopes
It is trivial to see that the 24-cell, all hypercubes, and all polytopes with simplicial facets, can be deformed into lattice polytopes, and this blog post implies the same is true for the ...
- 2,773
0
votes
1
answer
131
views
How hard is a linear programming with a bounded constraint?
Background: I am reading Greg Kuperberg's answer to the question Deciding membership in a convex hull. I am thinking about the complexity of ''Deciding membership in a convex hull''.
Restate the ...
- 63.9k
1
vote
0
answers
71
views
Diminishing of the $4_{21}$
One of the projections of the $4_{21}$ polytope (https://en.m.wikipedia.org/wiki/4_21_polytope) into four dimensions positions its vertices as those of two concentric 600-cells scaled by the golden ...
- 2,773
3
votes
0
answers
282
views
Continuum of Lagrange multipliers, duality gap, and minimax theorem
Suppose I have a linear optimization problem involving random variables on some (infinite) probability space $\Omega$. For example, need to maximize expectation $E[Q]$ of random variable $Q$ subject ...
- 781
0
votes
1
answer
214
views
How do you call a linear programming problem when the solution should be "constrained" to a norm?
(apologies for the n00b question)
Let's say we have a vector of length $n$, with to-be-determined values: $a_1, a_2, ...,a_n$.
And we have information that partial sums of these elements are equal to ...
- 1,714
0
votes
0
answers
72
views
Regiment map from Coxeter-Dynkin diagram
The following problem arises in the attempt to enumerate uniform polytopes:
Given a Wythoffian polytope, what are all other Wythoffian polytopes which use maximal subsets of its vertices and edges, ...
- 2,773
0
votes
1
answer
110
views
Detecting non-negativity of a single constraint by polyhedral constraints - $I$
We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\...
- 14k
1
vote
0
answers
162
views
Optimization problem on trace of complex matrix product
Given a complex rectangular matrix $A$ $(k \times n)$, I am interested in solving the following optimization problem over $(k\times n)$ complex matrices $x$:
$$
\mathrm{arg}\max_X \,\mathrm{trace}(X^...
- 377
1
vote
0
answers
43
views
Detecting non-negativity of a single constraint by polyhedral constraints - $II$
Let $$\langle a,x\rangle=b$$ be a linear constraint where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\...
- 13.9k
0
votes
1
answer
116
views
Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem
This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i,\mathbf{b}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the ...
- 5,429
2
votes
0
answers
54
views
Inverting "codimension matrix" for polytopes?
Let $P$ be an abstract polytope. Let's construct its square matrix $A$ as follows. Its lines and columns are labelled by all faces of $P$, of all dimensions. Put $A(F_1,F_2)=t^m$ if $F_1$ is a subface ...
- 765