I would like to get an upper bound $b(n,m)=b(m,n)$ for the number of $2 \times 2$ submatrices with one element equal to $1$ an the other three equal to $0$, over all possible $n \times m$ binary matrices.
I have computed with brute force the very maximum $M(n,m) \le b(n,m)$ for the following cases: $M(n,2)=1,2,4,6,9,12,16,20,25,30$ for $n=2$ to $11$ and it seems that $M(n,2)=\lfloor n^2/4 \rfloor$ (conjecture); $M(n,3)=2,6,12,18,26,36$ for $n=2$ to $7$, $M(n,4)=4,12,24,36$ for $n=2$ to $5$.
Any suggestion?