Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

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$.

share|improve this answer
    
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. –  user27805 Mar 11 '13 at 18:41
2  
$$\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. –  Gerry Myerson Mar 11 '13 at 22:58
    
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 –  user27805 Mar 12 '13 at 6:12
add comment

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

share|improve this answer
    
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 –  Gerhard Paseman Mar 11 '13 at 19:13
    
$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$. –  user27805 Mar 11 '13 at 20:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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