Esfera más grande en un "gráfico de cuadrícula"

Question

Deje $G=(V,E)$ ser un grafo no dirigido, que $V$ es un subconjunto de $\{1,\dotsc,N\} \times \{1,\dotsc,N\}$ y hay una arista entre el $2$ vértices si y sólo si tienen una idéntica coordinar y difieren en exactamente $1$ en la otra coordenada (podemos pensar en ello como una cuadrícula, con puntos en los que se omite, tal que se puede mover hacia arriba/abajo/derecha/izquierda).

El gráfico de $G$ define una métrica (por $d(v_1,v_2)=$mínimo número de aristas en un camino de$v_1$$v_2$). Una esfera se define como de costumbre: para $v \in V$, nos vamos a $S(v,r)=\{u \in V \mid d(v,u)=r\}$.

¿Qué es $\max\limits_{v,r}|S(v,r)|$? Un asintótica expresión en términos de $N$ sería suficiente. Tengo la fuerte sospecha de es $O(N)$ porque eso es lo que tenemos si $V=\{1,\dotsc,N\} \times \{1,\dotsc,N\}$ (i.e: ningún punto omitido) y tome $v=(N/2,N/2)$$r=N/2$.

Answer 1

Me voy a mi original $N^{\log_23}\approx N^{1.585}$ construcción a continuación, ya que es más fácil de entender y verificar, pero he encontrado una mejora de la $N^{\log_2(3+\sqrt{17})-1}\approx N^{1.833}$ construcción:

He aumentado el tiempo por el marco a $2$ segundos para que sea más fácil ver el principio. (Por cierto, Mac OS de vista previa le permite navegar a través de los fotogramas individuales con las teclas del cursor si se descarga la imagen.)

He aquí una imagen estática de una etapa intermedia:

Cada rama saca $3$ ramas de la próxima generación y $2$ de la generación después de eso, por lo que el crecimiento está determinado por la recurrencia

$$a_{k+2}=3a_{k+1}+2a_k$$

con characterstic valores de $(3\pm\sqrt{17})/2$. Por lo tanto, el número de puntos es$\sim k^{(3+\sqrt{17})/2}$$N=2k+1$, lo $\underset{v,r}{\max}|S(v,r)|$$\Omega(N^{\log_2(3+\sqrt{17})-1})\approx \Omega(N^{1.833})$.

He aquí una no muy rigurosa argumento de que el número está en el hecho de $\Omega(N^{2-\epsilon})$ cualquier $\epsilon>0$. Buscando en las etapas posteriores de las construcciones, ver las áreas en las que no se llenan. La razón por la que no se llenan es que están cerca de los puntos a los que se llega temprano y sería más complicado "malgastar el tiempo suficiente" para llegar a estas áreas lo suficientemente tarde --, habría que agregar rutas que van de ida y vuelta un par de veces y, a continuación, que brotan en estas áreas. Pero el "costo" de ir y venir de un cierto número de veces, el número de puntos utilizados por esos caminos, es lineal en $N$, mientras que la zona que puede ser llenado con ellos es cuadrática en $N$. Por ello, puede no ser posible de manera eficiente llenar todos los agujeros pequeños que se quedan por el final de la etapa, pero para cualquier patrón de los caminos en las zonas de vacío, que puede ser aplicado en todas las etapas, excepto la última $s$ etapas, donde $s$ depende de la "espesor" del patrón. Pero estos $s$ etapas sólo nos da un factor constante de $4^s$ en el número de puntos; simplemente podemos caer sin cambiar la forma asintótica de la dependencia en $N$. Así que podemos seguir construyendo más y más complicados caminos en las zonas de vacío, y el costo de usar un par de filas de puntos asintóticamente no importa ya que el número de $s$ de etapas en las que se hace imposible establecer estas rutas de acceso es independiente de la $N$, mientras que el número de etapas en las que el coste de los caminos es insignificante en comparación con el áreas abiertas por ellos crece con $N$. Creo que esto demuestra que el número es $\Omega(N^{2-\epsilon})$ cualquier $\epsilon>0$, aunque puede ser un poco tedioso de escribir el argumento a cabo rigurosamente.

Aquí está el original de $N^{\log_23}\approx N^{1.585}$ construcción:

He aquí una versión estática:

Las imágenes se escalan para que quepa en el ancho de la columna; se puede abrir en una nueva pestaña/ventana para obtener la máxima resolución (por la derecha o ctrl-clic).

Todos los puntos brillantes en los extremos de los segmentos están a la misma distancia del centro. Algunos de estos se alcanzan en diferentes formas; me contó el número de puntos distintos, mientras que el dibujo de los marcos. El conteo de $k=0$, y sin contar el marco inicial con $4$ puntos, hay $4(3^k+2^k)$ puntos distintos en el $k$-th marco, con $N=2^{k+1}+1$, por lo que tenemos

$$\underset{v,r}{\max}|S(v,r)|>4\cdot3^{\log_2(N-1)-1}>3^{\log_2(N-1)}\sim3^{\log_2N}=N^{\log_23}\;.$$

Sospecho que el número también es $O(N^{\log_23})$, pero no he encontrado una prueba todavía.

P. S.: acabo de darme cuenta de que la construcción era demasiado complicada, casi la misma figura puede ser construido en una forma más sencilla y directa, lo que evita los puntos en que se alcanza dos veces y hace evidente que el número de puntos que se triplicó en cada paso:

(De nuevo, haga ctrl-clic en la imagen y abrir en una nueva pestaña/ventana para conseguir la plena resultion -- se ve mucho mejor :-)

Aquí el número de puntos en la $k$th marco es, simplemente,$\frac433^k$.

P. P. S: me acabo de dar cuenta que ya hay automáticamente una arista entre puntos adyacentes, que en realidad necesitan el doble de $N$ a ser capaz de darse cuenta sólo las conexiones mostradas en las imágenes; pero eso es sólo un factor constante para que no se cambie el $\Omega(N^{\log_23})$ conclusión.

Answer 2

Es posible lograr una esfera de tamaño $O(n^2)$ mediante el uso de la "H fractal".

Definir $$V=\left\{ (x,y)\in\{1,\ldots,N\}\times\{1,\ldots,N\} {\ \Enorme|\ } \begin{aligned} 2\mid x \ \ \wedge\ \ l(x)+1 \in g(y) \\ or\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \,\,\\ 4\mid y \ \ \wedge\ \ l(y) \in g(x) \ \ \ \ \ \ \ \,\, \end{aligned} \right\}$$ donde $g(n)$ es el conjunto de $k$ para que el archivo binario "$2^k$s" y "$2^{k+1}$s" dígitos de $n$ difieren, y $l(n)=\mbox{min}(g(n))$.

Aquí está una foto para $N=15$.

   . . . . . . . # . . . . . . .
   . # . . . # . # . # . . . # .
   . # . . . # . # . # . . . # .
   . # # # # # . # . # # # # # .
   . # . # . # . # . # . # . # .
   . # . # . # . # . # . # . # .
   . . . # . . . # . . . # . . .
   . . . # # # # # # # # # . . .
   . . . # . . . . . . . # . . .
   . # . # . # . . . # . # . # .
   . # . # . # . . . # . # . # .
   . # # # # # . . . # # # # # .
   . # . . . # . . . # . . . # .
   . # . . . # . . . # . . . # .
   . . . . . . . . . . . . . . .

El tamaño de una esfera centrada en la parte superior, al $N$ es una potencia de 2, es $N^2/16$. Teniendo en cuenta la conectividad como $N$ crece, podemos ver que para todos los $N$, hay una esfera de tamaño, al menos,$N^2/36$.

---

(El problema con "el Plus fractal" (subyacente Joriki muy simpáticas animaciones) es que a pesar de que se llena el espacio, la más cercana de las cuatro ventajas (no está dibujado en esas animaciones) está más cerca que las otras tres y así no contribuir a la esfera. El H fractal no tiene este problema porque la ruta a cualquier parte de la H empieza por ir al centro.)

---

[añadido por joriki]

Aquí una animación de esta muy bonito solución – como con los demás, usted puede hacer clic derecho para abrir en una nueva ventana en tamaño completo o abrir en Mac OS previa para examinar los fotogramas individuales en el ocio.

Answer 3

Añadido. Yo entendido y juzgado mal la pregunta. Como @Jyrki puntos, el conjunto $V$ es relevante para el problema (y sin ella, la pregunta, como la de mi respuesta, se convierte en trivial), la distancia entre el $(x_1, y_1)$ $(x_2, y_2)$ no $|x_1 - x_2| + |y_1-y_2|$, y así sucesivamente. Yo soy sólo mantener la respuesta de los registros.

---

Un intento equivocado.

Espero haber entendido bien su pregunta. No veo cómo $V$ es relevante para el problema.

Vamos a probar que cualquier esfera es, de hecho, de tamaño $O(N)$. Arreglar cualquier centro de $v = (v_1, v_2)$ y un radio de $0 \leq r \leq 2N-2$. (El límite superior $2N-2$ es el diámetro de la gráfica.) La esfera de $S$ se define como el conjunto de puntos de $(v_1+x,v_2+y)$ tal que $|x| + |y| = r$. Claramente, $-r \leq x \leq r$; por otra parte, para cualquier valor de $x$, hay en la mayoría de las $2$ posibles valores de $y$, es decir,$\pm(r-|x|)$. Así, el número total de puntos es en la mayoría de las $$\sum_{x=-r}^r 2 = 2(2r+1) \leq 2(4N-4+1) = O(N) .$$