4
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Is there any context for this? $\endgroup$
    – Igor Rivin
    Dec 20, 2011 at 13:17
  • 1
    $\begingroup$ And do you know any result in one dimension? $\endgroup$
    – Igor Rivin
    Dec 20, 2011 at 13:20
  • 1
    $\begingroup$ Actually, that's not true. If $N$ is an array of all zeros, then this does not work... $\endgroup$
    – Igor Rivin
    Dec 20, 2011 at 14:05
  • 1
    $\begingroup$ Could you please add the graph-theoretical statement? That might get more responses. $\endgroup$
    – Igor Rivin
    Dec 20, 2011 at 16:13
  • 1
    $\begingroup$ 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? $\endgroup$ Dec 21, 2011 at 12:06

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.