All Questions
1,021 questions
11
votes
1
answer
591
views
The lattice handshake number ("nearly kissing" number)?
Update: I'm happy to say that this question has been made essentially obsolete by the breakthrough result of Serge Vlăduţ, who showed that the kissing number is exponentially large: https://arxiv.org/...
- 1,016
17
votes
3
answers
2k
views
The minimum of a sum of absolute values of inner products in $\mathbb{R}^d$
Consider a collection of unit vectors $v_1, \ldots, v_n$ in $\mathbb{R}^d$ (we think of $n$ being much larger than $d$). I would like to minimize the sum:
$$\sum_{i\neq j}|\langle v_i,v_j\rangle|.$$
...
- 2,288
7
votes
0
answers
410
views
Can generalization of a generalization Pascal theorem, Pappus theorem to Higher Dimensions? [closed]
Please see a chain of six circles associated with a conic. This is a generalization of Pascal theorem, Pappus theorem. I reformulate as following:
Let $1, 2, 3, 4, 5, 6$ be six arbitrary points in a ...
- 477
10
votes
0
answers
722
views
Fractional Matching version of Hall's Marriage theorem
Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:
1) there exist a perfect matching in $G$;
2) there exist non-negative weights on edges such that the sum of ...
- 109k
2
votes
0
answers
344
views
Linear programming with an infinite matrix
I would like to solve the following infinite linear system subject to $x_i \ge 0$ that minimizes $x_3$.
The third column contains no additional nonzero values beyond what is shown. Though the first ...
- 283
15
votes
1
answer
8k
views
On the determinant of a class symmetric matrices
Consider the matrix $2\times2$ symmetric matrix:
$$
A_2=\begin{pmatrix} 1 & a_1 \\ a_1 & 1\end{pmatrix}.
$$
It's clear that the restriction $|a_1|<1$ implies that $\det(A_2)>0$. Moreover,...
- 563
1
vote
1
answer
305
views
Name of area between two parallel lines [closed]
Assume that there are two distinct parallel lines on a Euclidean plane. Is there a name for the zone between these two lines?
- 121
1
vote
2
answers
83
views
Algorithm for a linear optimization problem
For the vectors $X=(x_1,\cdots, x_n),~ Y=(y_1,\cdots, y_n)$ and $\alpha=(\alpha_1,\cdots,\alpha_n),~ \beta=(\beta_1,\cdots, \beta_n)\in\mathbb R^n_+$ s.t. $\sum_{k=1}^n\alpha_k~~=~~\sum_{k=1}^n\beta_k~...
- 131
8
votes
1
answer
629
views
Bi-Lipschitz version of Kirszbraun's extension theorem
Kirszbraun's theorem for $\mathbb{R}^2$ states the following:
Given any set $S\subset \mathbb{R}^2$ and any Lipschitz function $f:S\rightarrow \mathbb{R}^2$ with Lipschitz constant $k$, $0< k<...
user99087
1
vote
0
answers
78
views
Family of functions which satisfies $f(\boldsymbol{x}) = 0$ if $\nabla f(\boldsymbol{x})=0$? [closed]
I have a Lagrangian of which I want to find the supremum in the primal variable $\boldsymbol{x}$:
$\mathscr{L}(\boldsymbol{x},\boldsymbol{\lambda})=f(\boldsymbol{x})^T\boldsymbol{a} + \boldsymbol{\...
7
votes
1
answer
683
views
Proof of the stable homeomorphism conjecture
I would like to get a demonstration of the stable homeomorphism conjecture (SHC$_n$), stating that any orientation-preserving homeomorphism $\mathbb{R}^n \rightarrow \mathbb{R}^n$ is stable in ...
- 73
2
votes
2
answers
187
views
Crossing number of some Sphere of Influence Graphs and relation to their coloring number
My motivation is to apply some graph theoretic methods in real analysis (like in a simple proof that every open real set $ A $ is coutable union of disjoint graph - take the connected component of the ...
1
vote
0
answers
47
views
Linear programs [closed]
Can the optimal value of the primal problem of a linear program ever be less then zero?
An example is: minimize $C=2x_1 +3x_2$ Subject to: $3x_1+4x_2 \leq 5$. Obviously, $x_1$ and $x_2$ are free ...
- 11
6
votes
2
answers
289
views
Problem on distances in a polygon
In $\mathbb{R}^2$ consider a square (call it $S$) and three triangles (one acute $T_2$ and two obtuse $T_1$ and $T_3$) such that each triangle shares one different side with the square and the ...
- 113
1
vote
0
answers
93
views
quick hull algorithm detail
When using quick hull algorithm to find the polytope for half space intersection, we are required to provide an interior point to the solver qhalf.
In other words, providing
$$Ax \le b$$
is not ...
- 867
2
votes
0
answers
62
views
Number of Nearest-Neighbors in high dimensions [closed]
Consider $n$ adversarially chosen points in $\mathbb{R}^{d}$ where $n \gg d$. Let $\mathbf{a}$ be one of the $n$ points. Is there an upper bound on the number of points among the remaining $n-1$ ...
- 275
1
vote
0
answers
43
views
a question about probabilities on spaces of digraphs
Let $G$ be a directed graph with fixed nodes $s$ and $t$. Assume that each edge $e$ in the graph comes with a number $n(e)\in[0,1]$.
We consider probability spaces $S$ whose points are directed ...
- 61
3
votes
2
answers
1k
views
Equality constraints in mixed-integer optimization
Suppose I have a linear mixed-integer optimization problem of the form
$$MIP: min_{(x,y) \in \mathbb{R}^n \times \mathbb{Z}^m} c^\top x + d^\top y \hspace{0.2cm} \text{s.t.} \hspace{0.1cm} Ax+By \leq ...
5
votes
1
answer
208
views
Possible generalization to Kirszbraun's theorem for $\mathbb{R}^2$
A key lemma to Kirszbraun's theorem for $\mathbb{R}^2$ states the following:
Given any two finite collections of points $x_1,\dots,x_n$ and $x_1',\dots,x_n'$ in $\mathbb{R}^2$ such that $|x_i'x_j'|\...
- 153
0
votes
1
answer
79
views
algorithms and tools available for a particular polytope computation
Let me define each half space i as:
$${H_i}:{c_i}{\bf{x}} \le {b_i}$$
The intersection of all such ${H_i}$ gives a polyhedron (bounded or not). Suppose I am interested in if ${H_i}$ is active (...
- 867
6
votes
1
answer
494
views
Algorithm to decide whether two constructible numbers are equal?
The set of constructible numbers
https://en.wikipedia.org/wiki/Constructible_number
is the smallest field extension of $\mathbb{Q}$ that is closed under square root and complex conjugation. I am ...
- 1,282
8
votes
0
answers
161
views
What is a geometric construction corresponding to elliptic curve addition for Sharygin-isosceles triangles?
NB: this is a cross-posting from from MSE after two months with no progress (despite a bounty). It's totally elementary but I think it's cute.
Consider the elliptic curve defined by the cubic:
$$
a^...
- 1,444
7
votes
2
answers
805
views
Continuing generalization of the Simson line
In 2014, I found a nice result in plane geometry, the result is a generalization of the Simson line theorem, and there are nine proofs for this result were published in [1]-[7]. Continuing, I find a ...
- 1,044
6
votes
0
answers
113
views
Area of generalized ellipse
An ellipse $E$ can be defined by two foci, $p,q\in\mathbb{R}^2$, and a length parameter $\ell$ as follows:
$$ E = \{x\in\mathbb{R}^2 : ||p-x||+||q-x||\le\ell
\}.$$
The area of $E$ is uniquely ...
- 6,541
1
vote
1
answer
73
views
minimize number of unique elements in a vector
I was wondering if there is a simple or known way to minimize the number of unique elements in a decision variable (vector). Note that I'm not asking for minimization of nonzero elements (rank ...
- 13
3
votes
1
answer
368
views
Lot sizing problem: how to add these cuts efficiently
Consider the set of constraints of the uncapacitated lot sizing problem:
$$
\{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
- 225
6
votes
4
answers
708
views
Surface dissection of regular tetrahedron to cube
Does anyone know what is the fewest-piece
dissection
of the surface of
a regular tetrahedron to the surface of a cube (of the same area)?
It is well-known that the volume of a regular ...
- 151k
2
votes
2
answers
403
views
Is this a linear optimization problem? $Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative
$Ax=0$, $A$ has $m$ rows and $n$ columns, $m \le n$, all entries of $x$ are non-negative.
What should $A$ satisfy to guarantee the equation set have only zero solution?
- 23
2
votes
1
answer
148
views
Fast algorithm for large-scale, asymmetric transportation linear program
I have a large-ish instance of a transportation problem that is very asymmetric, say of dimensions $100\times10000$. I am currently solving it with a stock LP solver, but obviously something like the ...
- 4,049
1
vote
0
answers
180
views
Cocompact (finite covolume) lattices in euclidean groups
1) Is there a classification of cocompact ( or finite co-volume) lattices in Euclidean groups E(n)( motions of Euclidean space) ( especially in dimensions 2,3,4)?
2) Also what is (if any) the ...
- 11
16
votes
2
answers
814
views
What are Sylvester-Gallai configurations in the complex projective plane?
A Sylvester-Gallai configuration in the the complex projective plane is a finite number of $n\ge 2$ points in the complex projective plane such that there is no line through exactly two of them. ...
- 7,722
11
votes
0
answers
239
views
Euclidean realizations of a configuration of $27$ points and $45$ lines
Let $GQ(2,4)$ denote the abstract configuration (=incidence structure) consisting of $27$ points and $45$ lines, with $3$ points on leach line and $5$ lines through each point, which can be described ...
- 32.5k
1
vote
1
answer
206
views
Show $0-1$ Knapsack is polynomially reducible to this problem
I have already posted this question here but have not received an answer so I am cross-posting with hope to reach a larger amount of mathematicians:
Let $T=\{1,\cdots,n\}$ and consider the ...
- 225
11
votes
1
answer
2k
views
What is needed to prove the consistency of Tarski's Euclidean geometry?
This question might be too elementary for MO, in which case I would gladly move it to math.stackexchange.com
Consider Tarski's axiomatization of Euclidean Geometry. It is stated in the wikipedia ...
- 26k
6
votes
2
answers
1k
views
Linear programming is continuous
Consider an arbitrary linear program:
$$\max \vec c \cdot \vec x$$
subject to:
$$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$
Assume that this program is feasible and bounded. ...
- 884
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
0
votes
0
answers
68
views
A seemingly easy integer programming question
Let $k, m \in \mathbb{Z}_{ > 1}$. Let $a \in \mathbb{Z}_{> 0}^m$ and $t \in \mathbb{Z}^k$. Let $\varepsilon = (\varepsilon_{i,j})_{1 \leq i \leq m \\1 \leq j \leq k}$ be a matrix with entries in ...
- 501
1
vote
1
answer
113
views
Are convex combinations of 0-1 Pareto efficient vectors efficient?
Let $Y$ be any subset of $\{0,1\}^n$ for $n\geq3$. A vector $\alpha\in$ $Y$ is Pareto efficient if there is no $\beta\in$ $Y$ such that $\beta_i$ $\geq$ $\alpha_i$ for each $i\in\{1,...,n\}$ and $\...
- 11
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
54
votes
5
answers
2k
views
Unusual symmetries of the Cayley-Menger determinant for the volume of tetrahedra
Suppose you have a tetrahedron $T$ in Euclidean space with edge lengths $\ell_{01}$, $\ell_{02}$, $\ell_{03}$, $\ell_{12}$, $\ell_{13}$, and $\ell_{23}$. Now consider the tetrahedron $T'$ with edge ...
- 10.1k
3
votes
0
answers
63
views
Exact Value of a Constant Related to the Quickhull Algorithm
What is the exact value of the infinite sum
$$ \sum_{n=1}^{\infty}n2^n\sin\left(\frac{\pi}{2^n}\right)\left(1-\cos\left(\frac{\pi}{2^n}\right)\right)$$
That constant is related to the Quickhull ...
- 13.2k
2
votes
1
answer
509
views
Under what condition does Courant–Fischer–Weyl min-max principle hold in general?
From Wikipedia:
Let $A$ be an $n \times n$ Hermitian matrix. As with many other variational results on eigenvalues, one considers the Rayleigh–Ritz quotient $R_A :
\mathbf C^n \setminus \{0\} \to \...
- 155
12
votes
1
answer
3k
views
Intuition behind the Dehn Invariant
EDIT: as pointed-out below, this has been posted on math.stackexchange. I'll leave it up to the community whether or not to delete this question, but I do think there is room for a more technical ...
- 2,218
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
16
votes
2
answers
528
views
Lipschitz constant for map between triangles
Let $T_1$ and $T_2$ be any two euclidean triangles with labeled sides. The sides are labeled respectively $e_1^1,e_2^1,e_3^1$ and $e_1^2,e_2^2,e_3^2$. Call $A:T_1\rightarrow T_2$ the affine map which ...
user99087
2
votes
1
answer
742
views
Inspired from British Flag theorem
I get this from inspired from British Flag theorem
British Flag theorem: Let $P$ be a point in the plane, let $ABCD$ be a rectangle in the plane then:
$$PA^2+PC^2=PB^2+PD^2$$
The theorem holds if P ...
- 1,044
2
votes
2
answers
3k
views
Linear programming with infinitely many constraints
I wish to study the following linear program
$$\begin{array}{ll} \text{minimize} & \mathrm c^{\top} \mathrm x\\ \text{subject to} & \mathrm A \mathrm x = \mathrm b\\ & \mathrm x \geq 0\...
- 283
0
votes
2
answers
120
views
Reference request: dependence on linear constraints
Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem:
$$P(...
- 1,835
3
votes
0
answers
71
views
Dependence of optimization problem on the linear constraints
Let $I=\{x_1,\cdots, x_n\}\subset \mathbb R$ be fixed. Given two probability distributions $\alpha=(\alpha_i)_{1\le i\le n}$ and $\beta=(\beta_i)_{1\le i\le n}$ on $I$, and a matrix $c=(c_{i,j})_{1\le ...
- 1,835
2
votes
1
answer
1k
views
Complementary slackness for approximately optimal Dual solution
Given a Primal LP (P) and it Dual LP (D) we know that the optimal solutions to P ($x_{opt}$) and D $(y_{opt})$ satisfy complementary slackness condition, i.e. under optimal solutions either a ...
- 133