Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is the minimum of the extent of $PMQ$ taken over all permutation matrices $P$ and $Q$. Let $f(n,k)$ be the maximum of $q(M)$ over all matrices $M$ with $k$ ones. What bounds can we give on $f(n,k)$?

Specifically, I am interested in finding whether there are any matrices $M$ with $k=O(n)$, such that $q(M)\ge (1+\epsilon)n$ for some $\epsilon>0$, i.e. $f(n,k)\ge (1+\epsilon)n$.

Is it possible to achieve $f(n,k)\ge (1+\epsilon)n$ for $k=O(n)$?

Less formally, we have a grid that we can fill with a small number of dots, and the adversary is allowed to permute rows and columns in order to prevent the bottom corner from being filled. For example, I can have a matrix like

\begin{matrix} \bullet&\cdot&\cdot&\cdot&\bullet\\ \cdot&\bullet&\cdot&\cdot&\bullet\\ \cdot&\cdot&\bullet&\cdot&\bullet\\ \cdot&\cdot&\cdot&\bullet&\bullet\\ \bullet&\bullet&\bullet&\bullet&\cdot\\ \end{matrix}

and the adversary can permute this to \begin{matrix} \cdot&\bullet&\bullet&\bullet&\bullet\\ \bullet&\cdot&\cdot&\cdot&\bullet\\ \bullet&\cdot&\cdot&\bullet&\cdot\\ \bullet&\cdot&\bullet&\cdot&\cdot\\ \bullet&\bullet&\cdot&\cdot&\cdot\\ \end{matrix} so this matrix gets a quality of $6$. We want to distribute the dots so the quality is as large as possible.

Here are some observations:

  • $f(n,k)\le 2n$ trivially
  • $f(n,k)=2n$ only for $k=n^2$. This is because if $M$ has less than $n^2$ ones, then there is a spot containing a zero, which can be moved to the corner by a permutation.
  • $f(n,n)=n+1$. The identity matrix has $n$ ones, and all permutations of the identity matrix are permutation matrices. The best the adversary can do on a permutation matrix is put all the ones on the antidiagonal, which has $i+j=n+1$ for each of its ones.
  • $f(n,n+m^2-m)\ge n+m$: Similar to the above, where we use a $m\times m$ block of ones followed by ones on the diagonal. Permutations cannot break up the block, so the best option for the adversary is to put it on the antidiagonal, where it will extend out beyond the antidiagonal by $m$, like so: \begin{matrix} \cdot&\cdot&\cdot&\cdot&\bullet\\ \cdot&\cdot&\cdot&\bullet&\cdot\\ \bullet&\bullet&\bullet&\cdot&\cdot\\ \bullet&\bullet&\bullet&\cdot&\cdot\\ \bullet&\bullet&\bullet&\cdot&\cdot\\ \end{matrix}

The answer to the main question is yes, and the key to the construction is the notion of an expander graph.

A (bipartite $d$-left-regular) expander graph between vertices $\mathcal{I}$ and $\mathcal{O}$ (the bipartition), where $|\mathcal{I}|=|\mathcal{O}|=n$, with expansion factor $c>0$, is a graph which is $d$-left-regular, meaning that each $x\in \mathcal{I}$ has degree $d$, such that for all subsets $A\subseteq I$ such that $|A|\le n/2$, the set $B\subseteq\mathcal{O}$ of neighbors of elements of $A$ has $|B|\ge (1+c)|A|$.

There are many proofs of existence of expander graphs like this by the probabilistic method and some deterministic methods as well; for the present purpose we only need that expander graphs as defined above exist for some constant $c>0$ independent of $n$.

Given such a graph, we can construct a $n\times n$ matrix from the adjacency matrix of the graph, with $\mathcal{I}$ for the rows and $\mathcal{O}$ for the columns. This matrix has exactly $k=dn=O(n)$ ones, because of the $d$ left regular property, and the expander property is unaffected by any permutations performed by the adversary.

Now for $\alpha>0$, let $A$ be the last $\alpha n$ elements of $\mathcal{I}$ and let $C$ be the last $\alpha n$ elements of $\mathcal{O}$, after the adversary has chosen an ordering of the rows and columns. If there is no one in this square in the matrix, then there must correspondingly be no edge between $A$ and $C$, and hence the neighbors $B$ of elements of $A$ must satisfy $B\subseteq C^c$, so by the expander graph property this implies $$(1+c)|A|=(1+c)\alpha n\le |B|\le |C^c|=(1-\alpha)n\implies \alpha\le\frac{1}{2+c}.$$

Thus any empty bottom right square must be smaller than $n/(2+c)\times n/(2+c)$, so in the language of the OP, $$f(n,k)\ge 2n\left(1-\frac{1}{2+c}\right)=(1+\epsilon)n$$ where $\epsilon=\dfrac{c}{2+c}>0$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.