|
9
|
|
edited Dec 21 2011 at 13:26 |
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 $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.)
|
|
|
|
|
8
|
|
edited Dec 21 2011 at 10:05 |
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$?
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.)
|
|
|
|
|
7
|
|
edited Dec 21 2011 at 5:14 |
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.
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$. 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
|
|
edited Dec 20 2011 at 21:29 |
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.
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 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$. 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.
|
|
|
|
|
5
|
|
edited Dec 20 2011 at 18:13 |
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$ of $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.
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 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$. But it seems nicer to state the graph-theoretic problem this way, and I think it is interesting enough.)
|
|
|
|
|
4
|
|
edited Dec 20 2011 at 15:55 |
|
|
|
|
|
|
3
|
|
edited Dec 20 2011 at 13:59 |
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$ of $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.
|
|
|
|
|
2
|
|
edited Dec 20 2011 at 13:20 |
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$ of $N_i$?
I conjecture that if $s=\exp(n)$, then the size of $M$ must be $\exp(\Omega(n))$. Is this true? I even don't know the answer for $s=2$. I do have a solution of $M$ of size rougly $\exp(n)$ that can be covered by $any$ $n\times n$ matrix.
|
|
|
|
|
1
|
|
asked Dec 20 2011 at 13:09 |
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$ of $N_i$?
I conjecture that if $s=\exp(n)$, then the size of $M$ must be $\exp(\Omega(n))$. Is this true? I even don't know the answer for $s=2$. I do have a solution of $M$ of size rougly $\exp(n)$ that can be covered by $any$ $n\times n$ matrix.
|
|
|
