Timeline for Connected components $0-1$ matrices
Current License: CC BY-SA 3.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 22, 2014 at 1:41 | comment | added | fedja | First, you can enhance the probabilistic argument by tweaking the parameters. Let $p$ be the probability of $1$ in every cell. Then the probability of no isolated $1$ is $[(1-p(1-p)^8]^{n^2/9}$, which, for $p=1/9$ is less than $1/(n!)^2$ for $n\approx 3000$ already (not small yet, but somewhat better than $96462$). Second, you can change the way you place 1's from totally random to semi-deterministic, which, if executed intelligently, may shave off another factor of 10. At last, you can use computers to check sizes up to 8 or so (16 or so, if you spend some time on the algorithm design first). | |
| Dec 21, 2014 at 23:26 | comment | added | Turbo | @NathanielJohnston Like what other arguments could be useful there? I understand counting and probabilistic method fails there (so what other techniques are there?). | |
| Dec 21, 2014 at 23:24 | comment | added | Nathaniel Johnston | @Turbo - $96462$ is just the smallest value of $n$ for which $(2^9 - 1)^{n^2/9} \cdot (n!)^2$ (the upper bound derived in this answer to the number of matrices that can be brought to $1$-component form) is smaller than $2^{n^2}$ (the number of $(0,1)$-matrices). | |
| Dec 21, 2014 at 23:20 | comment | added | Turbo | @NathanielJohnston Could you plEase elaborate your comment as answer in the other post? Like how you got $96462$.\ | |
| Dec 21, 2014 at 23:15 | comment | added | Nathaniel Johnston | @Turbo - This sort of argument is very loose, so you likely won't get any sort of precise statement or "estimates" out of it. It only shows even that there are at least two components when $n \geq 96462$ (you could likely tweak the argument to lower that bound a bit, of course, but it will still be quite large). | |
| Dec 21, 2014 at 23:11 | comment | added | Włodzimierz Holsztyński | The Garden of Eden configurations were introduced by E.F. Moore (see my earlier comment). | |
| Dec 21, 2014 at 23:02 | comment | added | Włodzimierz Holsztyński | @Fedja's proof (Christian's presentation) can be applied to a weaker connectivity, where constant $1$ is replaced by $D$, so that $\ x\ y\in\mathbb Z^2\ $ are considered connected when $\ ||x-y||\le D$ (and the connectivity distributes over entire lattice). | |
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:54 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:53 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:54 | |||||
| Dec 21, 2014 at 22:50 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:53 | |||||
| Dec 21, 2014 at 22:50 | comment | added | Turbo | @ChristianRemling Do you think your idea can be refined to get an estimate for the maximum number of components a given $n\times n$ matrix has? | |
| Dec 21, 2014 at 22:44 | vote | accept | Turbo | ||
| Dec 21, 2014 at 22:45 | |||||
| Dec 21, 2014 at 22:15 | comment | added | Włodzimierz Holsztyński | THe 3x3 blocks block partition construction reminds me the Garden of Eden early cellurar automata theory invented by Stan Ulam--it was Ulam's reaction to the engineering electric-mechanical John von Neumann's idea of the self-reproducing automaton. The Garden of Eden was introduced by someone else, after Ulam. | |
| Dec 21, 2014 at 22:06 | history | edited | Christian Remling | CC BY-SA 3.0 |
added 3 characters in body
|
| Dec 21, 2014 at 21:36 | comment | added | Christian Remling | @Turbo: $2^{cn^2}\cdot 2^{dn\log n}$, and I called it $\lesssim 2^{c'n^2}$ for good measure; it's really $2^{(c+o(1))n^2}$. | |
| Dec 21, 2014 at 21:30 | comment | added | Turbo | How did you get $c'$? I mean can you explain So the number of matrices that can be brought to one component form is $≲2^{c′n^2}$ with $c′<1$? | |
| Dec 21, 2014 at 21:13 | history | edited | Christian Remling | CC BY-SA 3.0 |
deleted 21 characters in body
|
| S Dec 21, 2014 at 21:05 | history | answered | Christian Remling | CC BY-SA 3.0 | |
| S Dec 21, 2014 at 21:05 | history | made wiki | Post Made Community Wiki by Christian Remling |