# Smallest matrix covered by many random n by n matrices

We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. Given $s$ random $n\times n$ $(0,1)$-matrices $N_1,\ldots,N_s$, what is the minimum size (rows times columns) of any matrix $M$ that can be covered by $each$ $N_i$?

I conjecture that if $s=\exp(n)$, then the size of $M$ must be $\exp(\Omega(n))$. Is this true? I do have a solution of $M$ of size rougly $\exp(n)$ that can be covered by $any$ $n\times n$ matrix, except only the all-1 and all-0 matrices.

REVISED QUESTIONS: Actually it can be shown by a simple counting argument that if $s\ge\exp(n)$, the size of $M$ must be $\exp(\Omega(n))$. However this argument doesn't work for small $s$, say $s=2$. So I revise my questions as follows: What is the asymptotic behavior of the minimum size of $M$ for small $s$? In particular, for $s=2$, must the size of $M$ be super-linear in $n\cdot n$?

Considering a matrix as a representation of a bipartite graph, the problem can be stated equivalently as a graph-theoretic problem as follows. We say that a bipartite graph $G$ can be covered by a bipartite graph $H$ if every edge in $G$ is contained in some induced subgraph of $G$ that is isomorphic to $H$. Given $s$ random bipartite graphs $H_1,\ldots,H_s$ on $n+n$ vertices (where each edge is present independently with probability 1/2), what is the minimum number of vertices of any nonempty graph $G$ that can be covered by $each$ $H_i$?

(To be exactly equivalent, we also need to require that every non-edge'' in $G$ has to be covered by a copy of $H_i$. But it seems nicer to state the graph-theoretic problem this way, and I think it is interesting enough.)

-
Is there any context for this? – Igor Rivin Dec 20 '11 at 13:17
And do you know any result in one dimension? – Igor Rivin Dec 20 '11 at 13:20
Actually, that's not true. If $N$ is an array of all zeros, then this does not work... – Igor Rivin Dec 20 '11 at 14:05
Could you please add the graph-theoretical statement? That might get more responses. – Igor Rivin Dec 20 '11 at 16:13
When you say “random matrix”, do you mean an “arbitrary matrix”, or do you want $M$ to be covered by $N_i$ only with high probability? – Emil Jeřábek Dec 21 '11 at 12:06