All Questions
23 questions
24
votes
3
answers
4k
views
What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
- 4,922
17
votes
1
answer
622
views
Longest of random worm-like paths in $\mathbb{Z}^2$
Imagine at each lattice point of $\mathbb{Z}^2$ within $[1,3n]^2$,
with coordinates
$\equiv 2 \bmod 3$,
we place, with equal probability, one of these six patterns:
The result ...
- 151k
14
votes
1
answer
955
views
Partitioning the vertices of an n-cube with random hyperplane cuts
An evolutionary biologist asked me a question which boils down, at least in part, to what seems to me an interesting question of combinatorial/probabilistic geometry.
It is an old chestnut of a ...
- 19.2k
11
votes
1
answer
370
views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
- 6,917
9
votes
1
answer
640
views
Inner product over finite fields
Let $F$ be a finite field,
For every $c \in F$, let $X_1, X_2,..., X_9, Y_1,..., Y_9$ be independent non-zero random variables over $F$.
Denote $X=(X_1,...,X_9)$, $Y=(Y_1,...,Y_9)$, also let $\...
- 93
7
votes
1
answer
318
views
Finding a short path using $(0.99n)!$ permutations
Suppose I have $n$ points $x_1,\dots,x_n$ that are all independent uniform samples in the unit square, and I'd like to find a short path (in terms of Euclidean length) that touches all of them (a ...
- 4,049
7
votes
0
answers
162
views
Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets
We denote by $V(A)$ the $d$-volume of any convex set $A$. Furthermore, given any two convex sets $A,B\in\mathbb{R}^d$, we denote by $V_{A,B}$ the $d$-volume of the symmetric difference $V\left(A \...
- 1,677
7
votes
0
answers
122
views
Discrepancy of the finite approximation of the Lebesgue measure
Let $\mu$ be a probabilistic measure on the unit square $Q$ which is the average of $N$ delta-measures in some points in this square; let $\lambda$ denote the Lebesgue measure on $Q$. What is the rate ...
- 109k
5
votes
1
answer
241
views
Height growth for randomly falling Tetris like blocks ? What if Young diagrams are falling down?
Question: How the maximal height grows for random Tetris like blocks falling down ? Numeric simulation (see below)
shows leading term is linear with some constant
depending on shapes of blocks ...
- 24.9k
5
votes
1
answer
261
views
Do random triangulation edge-flips maintain randomness?
Let $S$ be a fixed set of $n$ points in the plane in general position.
Let $T$ be a triangulation
of $S$, (somehow) selected
uniformly at random from all triangulations of $S$.
(There are an ...
- 151k
4
votes
3
answers
269
views
Existence of (near) equidistant codewords
My question is originally related to coding theory, but fairly easy to state in pure combinatorial way.
Fix $k\in\mathbb{N}$, $\beta\in(0,1)$ and consider the binary cube $\Sigma_n = \{0,1\}^n$ ...
- 1,096
4
votes
1
answer
115
views
What is the probability of an empty convex $k$-gon among many given points?
Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points.
For a big number $n$ of randomly distributed ...
- 13.4k
4
votes
0
answers
144
views
Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$
We are given a convex shape $C$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume of $C$ be $\tfrac12$ (I guess nothing changes for any other fixed constant ...
- 1,677
4
votes
0
answers
141
views
Level sets of function of inner products of vectors on hypercube
Let $H = \{ 0, 1\}^d$ be the $d$-th Cartesian product of $\{0, 1\}$ in $\mathbb{R}^d$. Suppose $v_1, \ldots, v_k$ are $k$ vectors in $H$ in general position. We define function $F \colon H^{k}\...
- 1,127
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
3
votes
1
answer
228
views
Density of a somewhat random set
The density of a set
$X\subseteq\omega$ refers to:
$\limsup\limits_{n\rightarrow\infty}\dfrac{C\cap n}{n}$.
Given a set of positive integers
$F= \{m_0<\cdots<m_{k-1}\}$,
let $C\subseteq \omega$...
- 909
3
votes
1
answer
218
views
Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions
We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (I guess nothing changes for any other fixed ...
- 1,677
3
votes
0
answers
187
views
Approximating any $d$-dimensional convex shape that occupies a constant fraction of its bounding box with a polytope having $\mathrm{poly}(d)$ facets
Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric ...
- 1,677
3
votes
0
answers
151
views
Permutahedra Euler characteristic polynomials from cumulant-moment relation, a combinatorial proof?
Given the formal Taylor series, or e.g.f.,
$f(x) = 1 + \sum_{n \geq 1} m_n \; \frac{x^n}{n!}$,
the classical formal cumulants $c_n$ are generated from the formal moments $m_n$ via
$ \sum_{n \geq 1} ...
- 10.5k
2
votes
1
answer
151
views
Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance
We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...
- 1,677
2
votes
2
answers
279
views
Combinatorial optimization problem with interdependent constraints on points in $[0,1]$
We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
- 1,677
2
votes
1
answer
404
views
Euclidean distance bound with geometric constraints
Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$.
Let $s_n$ and $\ell_n$ be respectively defined as follows:
$$...
- 1,677
1
vote
1
answer
106
views
Almost-parallel corners of the hypercube in high dimensions
Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
- 435