MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

9 added 7 characters in body

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$?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$eachH_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.) 8 added 389 characters in body 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$eachN_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$anyn\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$? 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$eachH_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.) 7 deleted 177 characters in body 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$eachN_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$anyn\times n$matrix, except only the all-1 and all-0 matrices. 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$eachH_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$. H_i$. But it seems nicer to state the graph-theoretic problem this way, and I think it is interesting enough.)

Edit: Actually, for the graph-theoretic problem to be interesting, we either have to require that every non-edge in $G$ has to be covered as well, or require that $G$ must be nonempty.

6 added 188 characters in body