A combinatorics question on a $n \times n$ grid

Question

In the book 'Foundations of Data Science' by Hopcroft and Kannan, they have the following exercise (Ex. 5.46):

Let G be a $n \times n$ lattice and let $S$ be a subset of $G$ with cardinality at most $\frac{n^2}2$. Define $$N = \{(i,j) \in S \,\, | \text{all elements in row $i$ and all elements in column $j$ belong to $S$}\}$$Show that $$\displaystyle |N| \leq \dfrac{|S|}2$$

My failed attempt:

I tried to fix $k$ elements in $N$ and calculate the minimum number of elements that should be added to $S$ so that the membership criteria of $N$ is satisfied. I added an element, one at a time to $N$, and kept track of how $|S|$ increases. The first element in $N$, immediately adds $2n-1$ elements to $S$. The second element adds at least $n-1$ elements and the third element adds at least $n-2$ elements. Sadly, I ran into a problem. As an example consider, adding row 1 and column 1 to $S$, that is, adding $(1,1)$ to $N$. Now subsequently add $(1,2)$ and $(2,1)$ to $N$ and therefore add $n-1 + n-2$ more elements in $S$. But observe how $(2,2)$ can now be freely added to $N$ without adding any elements in $S$. This shows that picking elements for $S$ affects the choice of elements for $N$ and it is hard to keep track. :(

Is there a simple solution to this problem? Or is there a work around for my failed attempt?

Thanks

Answer 1

I'm not sure how to make your idea work, but it could still be possible. Consider the following however.

First note that $|S|\le n^2/2$ implies $|S|/n^2 \le 1/2$.

I'll write $S$ covers a row or column to mean all elements of that row/column are in $S$. Given $|S|$ we want to know how many whole rows or columns we could cover with $S$ of that size, as each row/column has $n$ entries we could cover at most $|S|/n$ rows or $|S|/n$ columns.

(You could stop reading here and maybe try and finish it off with this idea in mind :))

Now a pair $(i,j)\in N$ if and only if both its row and its column are covered by $S$. So as we have at most $|S|/n$ rows and $|S|/n$ columns covered by elements of $S$ there can be at most $(|S|/n)^2$ elements of $N$. So $$|N| \le \frac{|S|^2}{n^2} = |S| \frac{|S|}{n^2} \le \frac{|S|}{2}.$$

Answer 2

Here's an entirely different approach (although somewhat related to Alex' solution) that can give a much stronger bound $$ \sqrt{|N|}+\sqrt{n^2-|S|}\le n $$ from which the result follows.

If $S$ contains $p$ full rows and $q$ full columns, then $|N=pq|$. However, with $p$ rows and $q$ columns full, if $k$ of the remaining $(n-p)(n-q)$ grid points (from the rows and columns other than these $p$ and $q$ full ones) are in $S$, that makes $$ |S|=n^2-(n-p)(n-q)+k\ge np+nq-pq. $$

Now, we may use $\frac{x+y}{2}\ge\sqrt{xy}$ for any $x,y\ge0$ to get $$ n^2-|S|\le(n-p)(n-q)\le\left(n-\frac{p+q}{2}\right)^2. $$ On the other hand, $$ |N|=pq\le\left(\frac{p+q}{2}\right)^2. $$ Taking square roots and adding these two inequalities, we get $$ \sqrt{|N|}+\sqrt{n^2-|S|}\le n, $$ which, entering $s=|S|/n^2$, makes $$ \frac{|N|}{n^2}\le \left(1-\sqrt{1-s}\right)^2 =\left(\frac{s}{1+\sqrt{1-s}}\right)^2 $$ which is $\le s/2$ whenever $s\le8/9$. If $s\le 1/2$, then $|N|/|S|\le3-2\sqrt{2}=0.17157\ldots$ follows.