let $A$ be an $m\times n$ binary matrix with $pmn$ ones and $(1-p)mn$ zeros. we want a submatrix $B$ of $A$ all of whose entries are ones that is as large as possible. (namely to pick a collection of rows and columns of $A$ all of whose intersections are ones)
how large can we guarantee $B$ to be as a function of $p$ ?
trivial thought : by picking the row with the most ones, we can have $B$ be $1\times \lceil pn\rceil$.
any idea is welcome :)
I have spent a considerable amount of time trying to find the answer, so by Murphy's law, it must have been that this is an actual open problem in mathematics.
Consider a bipartite graph with two classes $X$, $Y$, where $X$ contains vertices corresponding to the rows of $A$ and $Y$ contains the vertices corresponding to the columns of $A$. Now, we could do the following: for each $1$ in the matrix $A$ at position $i, j$ add an edge from the vertex $i$ in $X$ to the vertex $j$ in $Y$. Then, your problem may be stated as follows:
As we ask for the lower bound on the size of the biclique, we may equivalently ask for the upper bound on the number of edges, i.e.:
This is a slight generalisation of the problem in question, as the author counts the number of ones, i.e., is interested in a number of edges such that $G$ is free from $K_{s, t}$ for a fixed product $s \cdot t$. However, certainly, the maximal possible number of edges is then bounded from the above by the minimal upper bound over all complete subgraphs with this value of the product.
Now, to answer the question - this is an open problem, known as the Zarankiewicz problem. The link to the Wikipedia page contains a number of results and bounds, with the Kővári–Sós–Turán theorem being a somewhat noticeable result.