Timeline for $0,1$-matrices with $1$ in every row/column vs. all $0,1$-matrices
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7, 2021 at 3:12 | comment | added | Sam Hopkins | I see! Thanks very much for these explanations. | |
| Oct 7, 2021 at 3:10 | comment | added | Ira Gessel | You have to delete a 2-dimensional slice. That's what corresponds to a vertex. So the analogous statement for $n$-dimensional arrays will be about arrays in which every $n-1$-dimensional slice has at least one 1. | |
| Oct 7, 2021 at 3:09 | comment | added | Ira Gessel | By the same reasoning the exponential generating function for (labeled) graphs without isolated vertices is $e^{-x}\sum_{n=0}^\infty 2^{\binom n2} x^n/n!$; these correspond to symmetric 0-1 matrices with 0s on the diagonal and a 1 in every row. (oeis.org/A006129) | |
| Oct 7, 2021 at 3:05 | comment | added | Sam Hopkins | But I can't really delete a row/column(/pillar) of a 3D array and be left with a 3D array, the way I can in 2D... | |
| Oct 7, 2021 at 3:04 | comment | added | Ira Gessel | No, there's nothing special about two dimensions. The analogous statement will be true for 3D arrays. Think of a 3D 0-1 arrays as tricolored 3-regular hypergraph: you have three vertex sets each a different color, corresponding to the three coordinates, and each 1 of the array corresponds to a triple of vertices, one of each color. Each such hypergraph will be a set of isolated vertices together with a hypergraph without isolated vertices. | |
| Oct 7, 2021 at 3:00 | vote | accept | Sam Hopkins | ||
| Oct 7, 2021 at 2:47 | comment | added | Sam Hopkins | Ah, okay. Is it something special about two dimensions? For example the analogous statement is not true of $3D$-arrays, right? | |
| Oct 7, 2021 at 2:43 | history | answered | Ira Gessel | CC BY-SA 4.0 |