This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ minor. The problem asks for the maximum possible number of entries equal to $1$. When $n=q^2+q+1$, one may take the incidence matrix of (points vs. lines in) the finite projective plane of order $q$, giving the answer $(q^2+q+1)(q+1)$. Moreover one can prove that this answer is optimal, when a projective plane of the right order exists. Since there is no finite projective plane of order $6$ one may ask
What is the maximum possible number of entries equal to $1$ in such a $43\times 43$ matrix?
The upper bound of $(6^2+6+1)(6+1)=301$ can not be achieved, but is the answer close to it?
The motivation here, is to understand if projective planes are "badly approximable" when they do not exist for a given order. One may speculate that the answer to the question above is given by cutting off from a projective plane of order $7$ a carefully chosen set of $13$ points and lines, but I'm not sure.
Best Answer
I tried this years ago (mid 1990's) and with much slower computers could never get over 290. Here's one example with 290.
0000000010000000010110000000000010011000000 0000001010010000000000000010000001000001001 1000000001000100000000001000010000000101000 0100000101000000000000010100000000010000001 0010000000000101100000000001000000010000000 1000100110000000101000000000000000100000000 1000011000000001000101010000000000000000000 1001000000000000000010000111000100000000000 0010100000000000000001000100000000001001000 0000000000100000000010010000100000100001000 1010000000001000010000000000101000000000001 0000000001100000100000100010001000001000000 1000000000010010000000100000000000010010000 0000000010100011000000001100000000000000010 0101010010000100000000100000100000000000000 0000000100010001000000000000100100001100000 0000000010000000000000010001001000000100100 0000100000000001000010100000010000000000101 0000000000000000100100000100110001000010000 0000000000100100001100000000000100000000001 0000001000000000000000000000011100110000010 0001000000000000100001000000000010000100011 0001000001000001010000000000000001100000000 0000000000000000001001001010100000010000100 0000010000000000000000001001000000101010001 0000100000000100010000010010000000000010010 0000000011001000000001000000000100000010000 0000101001000010000000000001100010000000000 0100000000000001001000000000001010000011000 0011001100100000000000000000000000000010100 0000000100000110000011000000001001000000000 0100001000001000100010001000000000000000000 0100000000110000010001000001010000000000000 0000000000011100000000000100000010100000100 0000000100001000000100100001000000000001010 0001000000001010001000010000010000001000000 0000110000101000000000000000000001010100000 0110000000000010000100000010000000100100000 0000010000000010110000000000000100000001100 0010000000000000000000111000000111000000000 1100000000000000000000000000000001001000110 0000001000000000011000100100000000000100000 0010010001010000001010000000000000000000010