I uniformly mark $n^2$ points in $[0,1]^2$. Then I want to draw $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point. Surely, for a given constant c it is not always possible.


But it seems that for $c=100$ when n tends to infinity, the probability that such a cut exists should tend to one, as a variation of the law of the large numbers.
Do you have any idea how to prove this rigorously?



A variation of the law of large numbers for random points in a square
Given $n^2$ i.i.d. uniform points in $[0,1]^2$, the goal is to draw a configuration of $cn$ vertical lines and $cn$ horizontal lines such that in each small rectangle there is at most one marked point. 


We show below that $c$ must satisfy $c=\Omega(n^{1/3})$ for this to be typically possible:


In fact, $\Theta(n^{4/3})$ lines are necessary and sufficient for such a configuration to exist with substantial probability.


More precisely, denote by $p\_n(k)$ the probability that a configuration of $k$ vertical lines and $k$ horizontal lines separate $n^2$ i.i.d. uniform points $\{x\_j\}\_{j=1}^{n^2}$ in $[0,1]^2$.


Claim: For suitable constants $0<c\_1<c\_2<\infty$, we have (omitting integer part symbols):


(a) $\; p\_n(c\_1 n^{4/3}) \to 0$ as $n \to \infty$, and 


(b) $\; p\_n(c\_2 n^{4/3}) \to 1$ as $n \to \infty$.


This is proved below with $c\_1=1/20$ and $c\_2=3/2$; no attempt has been made to optimize these constants.


Proof: Consider an auxiliary grid of $L:=n^{4/3}$ uniformly spaced vertical lines and 
$L$ uniformly spaced horizontal lines in the unit square. This grid defines $L^2$ grid squares of side length $1/L$. 


(a) Call a grid square $Q$ nice if it contains exactly two of the $n^2$ given points $\{x\_j\}$. Observe that for two distinct grid squares, the events that they are nice are negatively correlated. Call a nice grid square $Q$ good if there is at most one other nice square in its row and at most one other nice square in its column. The probability that a specific grid square $Q$ is nice is
 $${n^2 \choose 2}L^{-4}(1-L^{-2})^{n^2-2}=(1/2+o(1))L^{-1}.$$  

Given that $Q$ is nice, The conditional expectation of the number of nice squares (other than $Q$) in the row of $Q$ is $1/2+o(1)$ Thus, given that $Q$ is nice, Markov's inequality implies that the conditional probability that there are two or more additional nice squares in the row of $Q$ (besides $Q$ itself) is at most $1/4+o(1)$.
The same applies to the column of $Q$, and we deduce that
 $$P(Q \; {\rm is \; good}\; | Q \; {\rm is \; nice}) \ge 1/2+o(1) \, ,$$ so 
 $$P(Q \; {\rm is \; good} ) \ge (1/4+o(1))L^{-1} \, .$$
Let $G$ denote the number of good grid squares. Then the mean satisfies
$$E(G) \ge (1/4+o(1))L \,.$$
Observe that if we replace one point $x\_i$ by $x\_i'$ then $G$ will change by at most 5, so Mcdiarmid's inequality, see [1, Theorem 3.1] or [2], implies that for $n$ large enough,
 $$P(G \le L/5) \le \exp(-\frac{(L/21)^2}{25n^2}) \to 0 \,. {\rm as} \; n \to \infty \,.$$
(Alternatively, one could invoke the Efron-Stein inequality or estimate the variance directly to verify this.)
Now suppose that $S$ is a set of vertical and horizontal lines that separate the points
$\{x\_j\}\_{j=1}^{n^2}$.
For each good grid square $Q$, a line of $S$ is required to separate the two points $x\_i, x\_j$ in the square, and each such line can be used for at most two good squares. Thus $|S| \ge G/2$ so
$$p\_n(L/20) \le P(\exists \; {\rm separating } \; S \; {\rm with } \; |S| \le L/10) \le P(G \le L/5) \to 0
$$.


(b) Denote by $M$ the number of pairs $(i,j)$ such that $1 \le i<j \le n^2$ and $x\_i,x\_j$ fall in the same grid square. Then 
$E(M) = {n^2 \choose 2}L^{-2} \le L/2$, and another application of McDirarmid's inequality implies that $P(M \ge L) \to 0$ as $n \to \infty$. 


Finally, construct a separating set of lines $S$ by combining the $2L$ lines of the auxiliary grid with one separating line for each pair $(i,j)$ counted in $M$
(we can take half of these lines vertical and half horizontal). Then $P(|S| \ge 3L) \to 1$
as $n \to \infty$ and $p\_n(3L/2) \to 1$ as well.


[1] McDiarmid, Colin. "Concentration." In Probabilistic methods for algorithmic discrete mathematics, pp. 195-248. Springer, Berlin, Heidelberg, 1998.<http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8B1FFFE4553B63543AFEA0706E686E65?doi=10.1.1.168.5794&rep=rep1&type=pdf>


[2] McDiarmid, C. (1989). "On the method of bounded differences". Surveys in Combinatorics. London Math. Soc. Lectures Notes 141. Cambridge: Cambridge Univ. Press. pp. 148–188. MR 1036755


