Máximo $2$ -D tiempo de percolación bootstrap para $n$ puntos en un $n\times n$ rejilla

Question

¿Es el máximo percolación de arranque tiempo para $n$ puntos en un $n\times n$ rejilla $\big{|}\left \lceil{(n^2-3)/2}\right \rceil + n - 1 \big{|}$ para $1\leq n\leq 8$ y $n(n+3)/2-7$ para $n\geq 9$ ?

A continuación se presentan algunas posibles posiciones de partida para $1\leq n\leq 12$ :

y un posible método de construcción para $n\geq 10$ (basado en las posiciones iniciales de $n-2$ ):

$\hspace{2em}$

En Mathematica Esto podría construirse de la siguiente manera:

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]];

o, una solución de no recurrencia:

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]];

Por ejemplo,

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"}]

Lo anterior es menor que el límite inferior mostrado en este documento de $13 n^2/18-14 n/9-5/3$ pero una búsqueda rápida de todas las permutaciones en $n=5$ muestra que el tiempo máximo de percolación requiere $>n$ puntos iniciales.

La construcción anterior da como resultado el tiempo máximo de percolación para $n$ ¿puntos de partida iniciales?

Conjuntos que contienen $>n$ puntos iniciales

Además, estoy buscando a través de el papel de Fabricio Benevides y Micha Przykucki sobre el tiempo máximo de percolación del bootstrap y me cuesta encontrar un ejemplo (o ver cómo hay podría sea un conjunto de puntos) que tarda más tiempo en completarse que el dado en su ejemplo de un conjunto para un $12\times 12$ cuadrícula en la página $20$ :

el siguiente patrón es válido para cada múltiplo de $12$ y requiriendo $4n/3-1$ puntos iniciales, toma $ n(17 n- 10)/24$ movimientos para completar:

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]

Esto difiere de su tiempo mínimo de percolación: el conjunto que sigue el patrón dado en su ejemplo tarda $ 17 n^2/24 +O(n)$ Sin embargo, afirman que el límite inferior es $13n^2/18+O(n)$ . Está cerca, $(\lim{n\rightarrow\infty (17 n^2/24)/(13n^2/18)=51/52})$ pero no veo cómo construir un conjunto de puntos iniciales que cumpla con su límite inferior. ¿Qué me falta?

Answer 1

Espero que no sea un problema si copio mi respuesta de MathOverflow aquí también.

Gracias por su interés en nuestro periódico. Un amigo me acaba de enviar un mensaje enlazando con este hilo. En primer lugar, cuando el conjunto inicial tiene exactamente $n$ sitios infectados, el tiempo máximo es el número entero más cercano a $(5n^2 -2n)/8$ - ver este documento .

Básicamente, para conseguirlo, primero se infecta un $2 \times \tfrac{n}{2}$ rectángulo en la parte inferior de su plaza (en tiempo $O(n)$ ), y luego hacerla crecer "desde las esquinas" como en las fotos al principio de tu pregunta hasta que la mitad inferior del cuadrado esté infectada (eso lleva tiempo $\tfrac{\tfrac{n}{2}+n}{2} \tfrac{n}{2}+O(n) = \tfrac{3n^2}{8}+O(n)$ ), y terminas infectando el resto horizontalmente, dos filas a la vez (eso lleva tiempo $\tfrac12 \tfrac{n}2 n +O(n)= \tfrac{n^2}{4}+O(n)$ ). Así que como ves, en total esta construcción lleva tiempo $\tfrac{5n^2}{8}+O(n)$ .

Ahora, con respecto a los conjuntos iniciales de tamaño arbitrario, considere lo que sucede cuando el valor de $s$ en lo que llamamos el Cangrejo Poderoso es alrededor de $\tfrac{n}{3}$ (véase la figura 12 del artículo que enlazas, que es también el que has copiado aquí). Si la única diferencia en tu solución es que la has codificado para que sea $s=5$ entonces esto debería hacer el truco. Por favor, hágame saber si hay algo que todavía no está claro.