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>



Square submatrix
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](http://en.wikipedia.org/wiki/Zarankiewicz_problem). The answer to this special case was shown [here](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.4995) as $4n^2 -3n$.


