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.)
