3
$\begingroup$

We have $2n\times 2n$ binary matrix with $k$ of its elements are $1$. We are searching for an $n\times n$ submatrix full of $1$s.

What is the least $k$ such that we can always find one?

What is the least $k$ for $n=10$?

Definition of submatrix: http://en.wikipedia.org/wiki/Submatrix

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

We can represent this matrix as a bipartite graph, with rows as left vertices and columns as right vertices. This problem is then a special case of extremal problems with forbidden graphs, in particular, special case of Zarankiewicz problem. The answer to this special case was shown here as $4n^2 -3n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Suppose $n=2$, your answer says that it is necessary to set $16-6 = 10$ elements to $1$ to find a $2\times 2$ submatrix. But my trials on $4\times 4$ matrix claims $k=9$ is necessary to find a submatrix. My conjecture for the least $k$ is $4n^2 - 4n + 1$. I haven't proved it yet. $\endgroup$
    – user27805
    Commented Mar 11, 2013 at 18:41
  • 2
    $\begingroup$ $$\pmatrix{1&1&1&0\cr1&0&0&1\cr0&1&0&1\cr0&0&1&1\cr}$$ has $n=2$, $k=9$, and no $2\times2$ submatrix of ones. $\endgroup$
    – Gerry Myerson
    Commented Mar 11, 2013 at 22:58
  • $\begingroup$ Thanks for your answers. I asked this question also on MathLinks. This is the given answer: artofproblemsolving.com/Forum/viewtopic.php?f=41&t=524322 $\endgroup$
    – user27805
    Commented Mar 12, 2013 at 6:12
-1
$\begingroup$

Here is a cheap lower bound. Let the first column, first row, and diagonal of a 2n by 2n matrix have zeros. Any nxn submatrix must intersect one of these lines, quickly giving $4n^2 - 6n + 2 \lt k$. This likely can be tweaked to close to $(2n-1)^2 \leq k$.

Gerhard "Ask Me About Binary Matrices" Paseman, 2013.03.11

Improve this answer
$\endgroup$
2
  • $\begingroup$ In fact, the diagonal, plus n elements in a row and n corresponding elements in a corresponding column also seems to work. Maybe further tweaking will easily take the number of zeros needed from $4n$ down to $3n$? Gerhard "Ask Me About System Design" Paseman, 2013.03.11 $\endgroup$
    – Gerhard Paseman
    Commented Mar 11, 2013 at 19:13
  • $\begingroup$ $a_{1(n-1)} = a_{1n} = 0$ $a_{2n} = a_{21} = 0$ $\dots$ $a_{n(n-2)} = a_{n(n-1)} = 0$ So there are $4n^2 - 4n$ $1$s; $4n$ $0$s. Let $x_1,\dots, x_n$ be the row #s of square submatrix. Let $y_1,\dots, y_n$ be the column #s of square submatrix. If we have $x_1, y_1$, then we should remove $2$ of columns that doesn't contain $x_1$. For $x_2, y_1$, then we should remove at least $1$ more columns, \dots After $x_10, y_1$, we should remove at least $11$ columns at total. So for that distribution of $1$s, one can never find a $10\times10$ submatrix. So I think $k>4n^2-4n$. $\endgroup$
    – user27805
    Commented Mar 11, 2013 at 20:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .