Timeline for Covering the zeros of 0/1 matrix with submatrices
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2016 at 14:39 | answer | added | user85022 | timeline score: 2 | |
| Jan 8, 2016 at 10:17 | vote | accept | user85022 | ||
| Jan 8, 2016 at 2:08 | comment | added | Tony Huynh | Given $M_n$, you can define a bipartite graph $G_n$ with bipartition $A$ and $B$ where $a_i$ is adjacent to $b_j$ if $M_{i,j}=0$. Your question then becomes what is the minimum number of complete bipartite subgraphs needed to partition the edges of $G_n$. You can do this for any square $0$-$1$ matrix, so if you are interested in matrices besides $M_n$, then Googling biclique covering number will turn up a lot of useful links. | |
| Jan 8, 2016 at 0:52 | history | edited | user85022 | CC BY-SA 3.0 |
example with M_{15}
|
| Jan 7, 2016 at 23:49 | answer | added | Douglas Zare | timeline score: 10 | |
| Jan 7, 2016 at 23:33 | comment | added | user85022 | @DouglasZare That would be great to have such a divide-and-conquer method! I do have a lower bound, but I must admit it is quite bad. For $M_7$, if we look at the entries (1,2), (2,3), (4,7) and (7,1), none can be in the same submatrix of another, so we have at least 4 different submatrices. But even for greater $n$, I am not able to find more than 4 entries verifying this property. | |
| Jan 7, 2016 at 23:13 | comment | added | Douglas Zare | My guess is that some sort of divide-and-conquer gives a cover with $O(\log n)$ submatrices. What lower bounds do you have? | |
| S Jan 7, 2016 at 23:11 | history | suggested | user85022 | CC BY-SA 3.0 |
better example
|
| Jan 7, 2016 at 23:00 | review | Suggested edits | |||
| S Jan 7, 2016 at 23:11 | |||||
| Jan 7, 2016 at 21:46 | review | First posts | |||
| Jan 7, 2016 at 22:09 | |||||
| Jan 7, 2016 at 21:42 | history | asked | user85022 | CC BY-SA 3.0 |