All Questions
18 questions
52
votes
2
answers
3k
views
vector balancing problem
I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.
This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...
- 42.8k
15
votes
3
answers
1k
views
Representation of vectors in $\mathbb{R}^2$ via differences of small vectors.
Is the following fact true?
Let $v_1,\ldots, v_k \in \mathbb{R}^2$, $\|v_i\|\leq 1$, be vectors that add up to zero. Does there exist a permutation $\sigma\in S_k$ and vectors $w_1,\ldots, w_k \...
- 1,284
11
votes
2
answers
797
views
Three half circles on the plane may not meet nicely
Let $H$ denote the union of the northern hemisphere of the unit circle $S^{1}$ with the interval $[-1,1]$ on the $x$-axis. That is, $H=\{(x,\sqrt{1-x^{2}}):-1\le x\le 1\}\cup\{(x,0):-1\le x\le 1\}$
...
- 2,136
8
votes
2
answers
528
views
Number of matrices with unit determinant and fixed sum of elements
Question. Let $\mathcal{M}_3$ be the set of $3\times 3$ matrices with non-negative integer entries and unit determinant. What is the number of $M\in \mathcal{M}_3$ with fixed sum of entries? What is ...
- 577
7
votes
1
answer
299
views
Lipschitz-continuity of convex polytopes under the Hausdorff metric
Recently, I proved the following Lipschitz-continuity like result for convex polytopes:
Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,:\,Ax\leq 0\}=\{0\}$ (which ...
7
votes
0
answers
254
views
Set of unit vectors such that among any three there is an orthogonal pair
I was fascinated by the solutions of Problem 8 of the IMC 2021 contest, which can be summarized as:
Theorem 1. Let $v_1,\dotsc,v_N$ be distinct unit vectors in $\mathbb{R}^n$ such that among any three ...
- 105k
6
votes
2
answers
1k
views
Division of space by hyper-planes
It is a well known and lovely result that the maximum number of regions that $\mathbb R^{k}$ (with $k$ positive) can be divided into by $n$ hyperplanes is given by
$$1+n+\binom{n}{2}+\cdots+\binom{n}{...
- 30.1k
5
votes
1
answer
394
views
Disjoint union of affine subspaces contains a larger affine subspace
I'd like to say that a large structured subset of the $n$-dimensional Boolean cube $\{0,1\}^n$ contains a non-trivial affine subspace. To be more specific, I want to prove/disprove that for some ...
- 211
4
votes
1
answer
492
views
Generalization of the "double cap conjecture" to a vector space with complex field
The conjecture that I proposed in
Maximal set on hypersphere that does not contain pairs of orthogonal vectors
is in fact known as the "double cap conjecture", as noted by Guillaume Aubrun.
See for ...
- 1,207
4
votes
0
answers
189
views
Slices of Simplices that are Simplices, Reference?
I am trying to find a reference for the following fact. It is elementary and not hard to prove, but I haven't been able to find the question treated anywhere.
Let $A$ be an $l\times n$ matrix with ...
- 41
3
votes
1
answer
525
views
VC dimension of vector spaces
Does the collection of all subspaces of a fixed finite-dimensional vector space have bounded VC dimension?
Could someone please provide references for this question?
- 397
2
votes
2
answers
505
views
Maximal number of intersecting subspaces of a finite dimensional vector space
For a given $k,n$ such that $0<k \leq n/2$, is there a number $N_{n,k}$, such that if one has $N$ different $k$-dimensional subspaces $V_1, V_2,...,V_N$ in $\mathbb{R}^n$ satisfying:
1) $\bigcap_{...
- 1,101
2
votes
1
answer
150
views
Intersection of a lower dimensional space and a discrete set
Let $H\subset \mathbb{R}^n$ with dimension ${\rm dim}(H)=\ell<n$; let $S$ be a finite subset of reals.
My question is the following. Is it correct to say,
$$
{\rm card}(H \cap V)\leqslant |S|^\...
- 1,096
2
votes
0
answers
81
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
- 153
1
vote
0
answers
69
views
Convolutions of (m)-associahedra and (m)-noncrossing partition polynomials--combinatorial proofs?
I'm looking for combinatorial proofs of the convolutional identity COP below and its specializations I) and II).
(Edit 6/2/2023: A combinatorial proof is sketched in a blog post by Mike Spivey of a ...
- 10.5k
1
vote
0
answers
54
views
Lattice-isotopic essentialization of arrangements
I'm working on a problem related to
$\textbf{Randell's isotopy theorem}$ for complex hyperplane arrangements. I have a question which seems quite obvious. However, I haven't found a rigorous proof ...
- 741
0
votes
1
answer
340
views
[Matrices over Z] - An algorithm for calculating the diagonal with elementary operations
Dear mathoverflow,
Let
$
\left(
\begin{array}{cc}
a & b \newline
c & d
\end{array}
\right)
$
be a matrix with $a, b, c, d \in \mathbb{Z}$, $\gcd(a,b,c,d) = 1$ and $ad - bc = \pm N$, with $N &...
- 11
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