Gráfico regular de circunferencia alta con un orden total "localmente uniforme" en los nodos

Definiciones

Sea y sea que d , r y g sean enteros positivos (con g > 2 r + 1 ).$\epsilon > 0$$d$$r$$g$$g > 2r+1$

Sea un gráfico finito simple, d- regular, no dirigido, con circunferencia de al menos g .$G = (V,E)$$d$$g$

Deje ser un orden total en V .$\le$$V$

Para cada , que V v ⊆ V consista en los nodos que están dentro de la distancia r desde v en G (la ruta más corta desde v hasta cualquier u ∈ V v tiene como máximo r bordes), y sea G v el subgrafo de G inducida por V v . Recordemos que asumimos que G tiene una circunferencia alta; por lo tanto, G v es un árbol. Sea ≤ v la restricción de ≤ a$v \in V$$V_v \subseteq V$$r$$v$$G$$v$$u \in V_v$$r$$G_v$$G$$V_v$$G$$G_v$$\le_v$$\le$ .$V_v$

Decimos que una arista es buena si ( G u , ≤ u ) y ( G v , ≤ v ) son isomorfas. Es decir, hay una biyección f : V u → V v que conserva las adyacencias ( { x , y } ∈ E iff { f ( x ) , f ( y $\{u,v\} \in E$$(G_u,\le_u)$$(G_v,\le_v)$$f\colon V_u \to V_v$$\{x,y\} \in E$ ) y orden ( x ≤ y iff f ( x ) ≤ f ( y ) ). De lo contrario, una ventaja esmala.$\{f(x),f(y)\} \in E$$x \le y$$f(x) \le f(y)$

Decimos que es ϵ -bueno si hay al menos ( 1 - ϵ ) | E | buenos bordes$(G,\le)$$\epsilon$$(1-\epsilon)|E|$

Pregunta

Deje . ¿Existe un ε par -buena ( G , ≤ ) para cualquier ε > 0 y cualquier r y g (con r « g )?$d = 4$$\epsilon$$(G,\le)$$\epsilon > 0$$r$$g$$r \ll g$

Observaciones:

• Me gustaría saber la respuesta para una general , pero d = 4 es el primer caso no trivial.$d$$d = 4$

• El tamaño de no importa, siempre que sea finito. No necesito una construcción de G ; La mera existencia o no existencia es suficiente.$G$$G$

Ejemplos

• Si , la respuesta es "sí". Simplemente podemos tomar un ciclo suficientemente largo y ordenar los nodos a lo largo del ciclo. Hay algunos bordes defectuosos cerca del borde que une el nodo más grande y el más pequeño, pero todos los demás bordes son buenos: para casi todos los nodos v , el par ( G v , ≤ v ) es solo una ruta con 2 nodos r + 1 en Un orden creciente.$d = 2$$v$$(G_v,\le_v)$$2r+1$

• Si , la respuesta es "sí". Simplemente tome un gráfico de alta circunferencia regular.$r = 0$

• Si es suficientemente pequeño, la respuesta es "sí" para cualquier par d . Simplemente tome un gráfico de cuadrícula ( d / 2 ) -dimensional (con los límites ajustados para hacerlo d- regular), y ordene los nodos lexicográficamente por sus coordenadas. Nuevamente, tenemos algunos bordes defectuosos cerca de los límites de la cuadrícula, pero podemos hacer que el número de bordes defectuosos sea arbitrariamente pequeño.$g$$d$$(d/2)$$d$

• Si no necesita ser finito, la respuesta es "sí" para cualquier par d . Un árbol infinito regular tiene un orden total tal que todos los bordes son buenos.$G$$d$

• Si es impar yr es suficientemente grande, la respuesta es "no". En esencia, Naor y Stockmeyer (1995) muestran que cada nodo incide en al menos un borde no bueno.$d$$r$

Antecedentes

(Esta sección se puede omitir de forma segura).

La pregunta está relacionada con los fundamentos de la informática distribuida, y en particular con los algoritmos locales .

Lo que nos gustaría entender es lo siguiente: en qué situaciones la existencia de un orden total ayuda a romper la simetría local en un sistema distribuido. Intuitivamente, cada nodo de G tiene que producir una salida que sea función de ( G v , ≤ v ) , es decir, una función de la vecindad local de v . Si un borde e = { u , v } es malo, hay información local que rompe la simetría disponible cerca de e , y los nodos u y v pueden producir diferentes salidas; si el borde es bueno, entonces los nodos$v$$G$$(G_v,\le_v)$$v$$e = \{u,v\}$$e$$u$$v$ y v son localmente indistinguibles y tienen que producir la misma salida.$u$$v$

Para muchos problemas gráficos clásicos se sabe que un orden total no ayuda (las relaciones mucho más débiles proporcionan esencialmente la misma cantidad de información que rompe la simetría), pero algunos casos aún están abiertos , y un resultado general que cubre el caso de todos Los gráficos de circunferencia podrían ser un gran avance.

Esta podría ser una pregunta beneficiosa para todos: independientemente de la respuesta, aprendemos algo nuevo. Si la respuesta es "sí", podríamos obtener nuevos y más fuertes resultados de límite inferior; Si la respuesta es "no", podríamos ser capaces de diseñar algoritmos más rápidos que exploten la información local de ruptura de simetría que está disponible en cualquier .$(G,\le)$

Por supuesto, en el mundo real no tenemos un orden total de ; tenemos algo más: cada nodo v ∈ V tiene una etiqueta única ℓ ( v ) ∈ N . Pero cerrar la brecha entre un pedido total y etiquetas únicas suele ser más sencillo; a menudo, un argumento similar a Ramsey muestra que (en el peor de los casos) las etiquetas no proporcionan información que no está disponible en un orden total.$V$$v \in V$$\ell(v) \in \mathbb{N}$

$(G,\le)$$\epsilon > 0$$r$$g$$d$

Para más detalles, consulte arXiv: 1201.6675 .