Consider the finite collection $M(N,n)$ of all $N \times N$ matrices with exactly $n$ entries per row equal to $1$ and all other entries equal to zero $0$.

By an $a \times b$ submatrix of $M$ we mean a matrix obtained from $M$ by crossing out all but $a$ rows and all but $b$ columns.

I am interested in the proportion of $M(N)$ that that have no wide submatrix of all zeroes. By that I mean an $a \times b$ submatrix with $a > b$ and $a+b > N$.

For example we forbid any row of all zeroes (but this cannot happen by definition). We also also forbid all the zero matrices with one corner in the top-left and another on the diagonal. We also forbid everything in between up to permuting rows and columns.

The naieve approach is to divide up the collection of possible submatrices with $a+b = N+1$ according to the value of $a$. By symmetry the chance of any two elements of the same class being all zeroes depends only on the class. Compute the probability on a class-by-class-basis, then sum over each classes, then sum all the classes. This gives a crude upper bound to the question.

I'm wondering is a more sophisticated upper bound known?

I'm currently looking in the combinatorics literature to see if this problem has been considered before. But not being familiar with the various sub-areas I don't know what to look for. I've found a lot of papers on forbidden submatrices but none where the ambient space of matrices is formed as with $M(N,n)$. Usually the ambient space is just the space of all $(0,1)$ submatrices. I also know the problem is equivalent to one in bipartite graphs (each matrix is the adjacency matrix of a unique bipartite graph) but I don't even know what to call a bipartite graph $G = L \cup R$ were each node in $L$ has degree $n$. There are so-called biregular graphs where the degree over $L$ is constant and the degree over $R$ is some other constant (possibly the same). But I'm only interested in fixing the degree over one half, not both.

I'd appreciate if anyone could point me in the right direction to where similar problems have been considered before.

  • $\begingroup$ If $1<<n<<N$, the probability that the first column is empty is $e^{-n^2/2(1+o(1))}$. $\endgroup$ – Ilya Bogdanov Oct 31 '18 at 8:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.