Timeline for enumeration of connected blocks in finite size square
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 5, 2014 at 16:01 | vote | accept | user40780 | ||
| Oct 5, 2014 at 9:35 | answer | added | Joonas Ilmavirta | timeline score: 2 | |
| Oct 5, 2014 at 1:31 | comment | added | Joseph O'Rourke | Possibly related MO question: "Expected number of components with multiple cycles in a subgraph of a square lattice." | |
| Oct 5, 2014 at 0:53 | history | edited | user40780 | CC BY-SA 3.0 |
added 40 characters in body
|
| Oct 5, 2014 at 0:51 | comment | added | user40780 | @BrendanMcKay:yes, I confirm that it means adjacent square, thank you:) | |
| Oct 5, 2014 at 0:49 | comment | added | Brendan McKay | Oh, I see I misunderstood "connected". You mean only adjacent squares (please confirm), I was referring to being in the same row or column. In that case there are usually very many components. | |
| Oct 5, 2014 at 0:47 | comment | added | user40780 | @BrendanMcKay, and we are interested in few connected components, which is j=1,2,3 while n,m,k could be large.... | |
| Oct 5, 2014 at 0:46 | comment | added | user40780 | @BrendanMcKay, this gives a more interesting insight. Actually, there is <1 probability that it is connected. let nmk goes to infinity, choose a "1", if all its 6 surrounding neighbor is 0, then we have one isolation and thus there are more than 1 connected component, and the probability for this event is 1/2^6=1/64.... Keep looking for "1" sites that satisfy this property from the huge nmk, then there must be some "1" sites that has this property. Then there are actually 0 probability that all "1"s are connected... | |
| Oct 5, 2014 at 0:32 | comment | added | Brendan McKay | If you make the matrix at random (each entry independently 0 or 1 with equal probability), I'm pretty sure that the 1s will be connected with probability ${}\to 1$ as $nmk\to\infty$. So $2^{mnk}$ is close to the correct value. To get a more interesting situation, specify that the number of 1s must be small. | |
| Oct 4, 2014 at 21:28 | comment | added | user40780 | I am actually more interested in the tighter upper bound.... and I hope that given j, the upper bound could be polynomial (with smallest possible order) in terms of n,m,k :) thank you | |
| Oct 4, 2014 at 21:00 | comment | added | Joonas Ilmavirta | Do you want an exact solution or would some kind of estimates be enough? If the number of possible choices is $N(n,m,k;j)$, then naive arguments show that $\sum_{i=0}^j{nmk\choose i}\leq N(n,m,k;j)\leq2^{nmk}$ (this gives the exact amount when $j\geq nmk$). | |
| Oct 4, 2014 at 20:41 | history | asked | user40780 | CC BY-SA 3.0 |