6
$\begingroup$

I hesitate to ask this question here, but since it remained unanswered after a bounty on MSE, I ask it here with some reservation.

Is the maximum bootstrap percolation time for $n$ points on an $n\times n$ grid $\big{|}\left \lceil{(n^2-3)/2}\right \rceil + n - 1 \big{|}$ for $1\leq n\leq 8$, and $n(n+3)/2-7$ for $n\geq 9$?

Below are some possible starting positions for $1\leq n\leq 12$:

enter image description here

and a possible construction method for $n\geq 10$ (based on the starting positions of $n-2$):

$\hspace{2em}$

In Mathematica, this might be constructed as follows:

aa = Uncompress@"1:eJzVlsEOgjAQRLuAgvyF/+PJT/BAwskD/n/UNhGG7mwpqNFLw8K8zuxaCcfL9dy1zrmheiynfrh1wqv+WXUFCIpI0LtI5W8FugS61GlFGu6/FvrQkxWYVMSE6GdOwY4pJKkYXXaQCqp5KgJp0YI7k8kyWfZuPtseGoJKbYiQNEcIw7SKg72vZGjXZfC91TAVqPhURquaWGUD9Ei9zYGOdqMDSz7poYEhN0lcM0UqDayk4rwrvT7Wl5lQlCvTy/znB+owpbBa2qWy0VJqCyox+rOBybzVX4k1YbuarWeNafYCwU+SNmMjLQjyOehmXmL+X/IL4b+Q3zoNqsw+iAqffkmNyx0cTkRo";
a[9] = aa[[9]]; a[10] = aa[[10]];
a[n_] := If[n < 9, aa[[n]], With[{t = Length@#[[1]] + 2}, Flatten[{ReplacePart[Array[0 &, t], # -> 1] & /@ {1, t + 1, t, 1, t + 1, t - 1, 1}, Drop[Flatten[{Take[#, 2], #}, 1] &@(PadLeft[PadRight[#, t - 1], t] & /@ #), 7]}, 1]
] &@a[n - 2]];

or, a non-recurrence solution:

a[n_] := If[n < 9, aa[[n]], Partition[ReplacePart[ConstantArray[0, n^2], Thread[# -> 1]] &@
With[{v = Join[{1, 3 #1, 1 + 3 #1, -1 + 6 #1, 1 + 6 #1}, LinearRecurrence[{0, 2, 0, -1}, {-2 + 8 #1, 2 + 8 #1, -3 + 10 #1, 3 + 10 #1}, # - 9], {(-3 - 8*#1 + 4*#1^2 + (-1)^#1*(-5 + 2*#1))/4, ((-1)^#1*(1 + (-1)^#1*(-1 - 6*#1 + 4*#1^2)))/4, ((-1)^#1*(1 + (-1)^#1*(-13 - 2*#1 + 4*#1^2)))/4, ((-1)^#1*(-1 + (-1)^#1*(9 - 2*#1 + 4*#1^2)))/4}] &@n}, 
If[EvenQ@n, v, ReplacePart[v, (Length@v - 4) -> v[[Length@v - 4]] + 1]]], n]];

eg

Manipulate[With[{b = Most@FixedPointList[
CellularAutomaton[{1018, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {#, 0}][[1, 2 ;; -2, 2 ;; -2]] &, a[n]]}, 
ArrayPlot[b[[length]], Mesh -> True]], 
{length, 1, If[n < 9, {1, 2, 5, 10, 15, 22, 29, 38}[[n]], n (n + 3)/2 - 7], 1, Appearance -> "Open"}, 
{{n, 10}, 1, 20, 1, Appearance -> "Open"}]

The above is smaller than the lower bound shown in this paper of $13 n^2/18-14 n/9-5/3$, but a quick search for all permutations at $n=5$ shows that the maximum percolation time requires $>n$ initial points.

Does the above construction result in the maximum percolation time for $n$ initial startpoints?

Sets containing $>n$ initial points

In addition, I am looking through the paper by Fabricio Benevides and Michał Przykucki on maximum bootstrap percolation time and I am having trouble finding an example (or seeing how there could be a set of points) that takes a greater time to complete than the one given in their example of a set for a $12\times 12$ grid on page $20$:

enter image description here

the following pattern is valid for every multiple of $12$ and requiring $4n/3-1$ initial points, takes $ n(17 n- 10)/24$ moves to complete:

enter image description here

manipu[n_, m_] := 
Manipulate[With[{b = Most@FixedPointList[
CellularAutomaton[{1018, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, 
{#, 0}][[1, 2 ;; -2, 2 ;; -2]] &, n]}, 
ArrayPlot[b[[length]], Mesh -> True]], {length, 1, m, 1, Appearance -> "Open"}];

m12[n_] := 
With[{y = Length@#}, manipu[#, y (17 y - 10)/24]] &@ With[{t = 12 n}, 
Flatten[{Take[Flatten[{PadRight[{1}, t], PadLeft[{1}, t], 
Array[0 &, t]} & /@ Range@Ceiling[t/6], 1], t/2], 
Reverse@(CenterArray[Join[{0, 0, 1}, Array[0 &, #], {1}], t] & /@
Range[8, t, 4]), {CenterArray[{0, 1, 0, 0, 0, 1}, t]}, 
{CenterArray[{1, 0, 1}, t]}, CenterArray[Join[{1}, 
Array[0 &, #], {1}], t] & /@ Range[6, t, 4]}, 1]];

m12[3]

This differes from their minimum percolation time: the set following the pattern given in their example takes $ 17 n^2/24 +O(n)$, yet they state the lower bound is $13n^2/18+O(n)$. It is close, $(\lim{n\rightarrow\infty (17 n^2/24)/(13n^2/18)=51/52})$, but I can't see how to construct a set of initial points that meets their lower bound. What am I missing?

$\endgroup$
  • $\begingroup$ hope you don't mind, I removed the soft question tag, as I don't think this question is one $\endgroup$ – j.c. Mar 30 '17 at 18:02
  • $\begingroup$ @j.c not at all :) $\endgroup$ – martin Mar 30 '17 at 18:07
  • $\begingroup$ I don't know how exactly you count, but that polynomial doesn't seem to match the values for $1\le n \le 3$. $\endgroup$ – domotorp Apr 3 '17 at 8:53
  • 1
    $\begingroup$ So if I understand well, you're claiming that the lower bound in their paper might be incorrect, right? As this question is quite specific, I would recommend that you email the authors, especially given that until now nobody here could give an answer. $\endgroup$ – domotorp Apr 3 '17 at 9:05
  • $\begingroup$ @domotorp thanks for the suggestion. Would you recommend I put a bounty on the question to be completely sure first? $\endgroup$ – martin Apr 3 '17 at 10:13
7
$\begingroup$

Thanks for your interest in our paper! A friend just messaged me linking to this thread. First, when the starting set has exactly $n$ infected sites, the maximum time is the integer nearest to $(5n^2 -2n)/8$ - see this paper.

Basically, to achieve this, you first infect a $2 \times \tfrac{n}{2}$ rectangle at the bottom of your square (in time $O(n)$), then grow it "from the corners" like in the pictures at the beginning of your question until the lower half of the square is infected (that takes time $\tfrac{\tfrac{n}{2}+n}{2} \tfrac{n}{2}+O(n) = \tfrac{3n^2}{8}+O(n)$), and you finish by infecting the rest horizontally, two rows at a time (that takes time $\tfrac12 \tfrac{n}2 n +O(n)= \tfrac{n^2}{4}+O(n)$). So as you see, in total this construction takes time $\tfrac{5n^2}{8}+O(n)$.

Now, regarding initial sets of arbitrary size, consider what happens when the value of $s$ in what we call the Mighty Crab is around $\tfrac{n}{3}$ (see Figure 12 in the paper you link to, which is also the one you copied here). If the only difference in your solution is that you hardcoded it to be $s=5$ then this should hopefully do the trick. Please let me know if anything is still unclear.

$\endgroup$
  • $\begingroup$ thsnks foryour response and your very clear answer! :) $\endgroup$ – martin Apr 21 '17 at 8:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.