Graphique régulier à circonférence élevée avec un ordre total «localement uniforme» sur les nœuds

Définitions

Soit et soit , et des entiers positifs (avec ).$\epsilon > 0$r g g > 2 r + $d$$r$$g$$g > 2r+1$

Soit un graphe simple, régulier, non orienté, fini avec une circonférence au moins .d $G = (V,E)$$d$$g$

Let être un ordre total sur .$\le$$V$

Pour chaque , soit les nœuds qui sont à distance de dans (le chemin le plus court de vers tout a au plus bords), et soit le sous-graphe de induit par . Rappelons que nous avons supposé que avait une circonférence élevée; donc est un arbre. Soit la restriction de à .V v ⊆ V r v G v u ∈ V v r G v G V v$v \in V$$V_v \subseteq V$$r$$v$$G$$v$$u \in V_v$$r$$G_v$$G$$V_v$$G$≤ v ≤ V $G_v$$\le_v$$\le$$V_v$

On dit qu'une arête est bonne si et sont isomorphes. Autrement dit, il y a une bijection qui préserve les contiguïtés ( ssi ) et l'ordre ( ssi ). Sinon, un bord est mauvais .( G u , ≤ u ) ( G v , ≤ v ) f : V u → V v { x , y } ∈ E { f ( x ) , f ( y ) } ∈ E x ≤ y 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$$\{f(x),f(y)\} \in E$$x \le y$$f(x) \le f(y)$

On dit que est -bien s'il y a au moinsbons bords.ϵ ( 1 - ϵ ) | E $(G,\le)$$\epsilon$$(1-\epsilon)|E|$

Question

Soit . Existe-t-il une paire -good pour tout et tout et (avec )?ϵ ( G , ≤ ) ϵ > 0 r g r ≪ $d = 4$$\epsilon$$(G,\le)$$\epsilon > 0$$r$$g$$r \ll g$

Remarques:

• Je voudrais connaître la réponse pour un général , mais est le premier cas non trivial.d = $d$$d = 4$

• La taille de n'a pas d'importance, tant qu'elle est finie. Je n'ai pas besoin d'une construction de ; une simple existence ou non-existence suffit.$G$$G$

Exemples

• Si , la réponse est "oui". Nous pouvons simplement prendre un cycle suffisamment long et ordonner les nœuds le long du cycle. Il y a de mauvais bords près du bord qui rejoint le plus grand et le plus petit nœud, mais tous les autres bords sont bons: pour presque tous les nœuds , la paire n'est qu'un chemin avec nœuds dans une augmentation ordre.v ( G v , ≤ v ) 2 r + $d = 2$$v$$(G_v,\le_v)$$2r+1$

• Si , la réponse est "oui". Prenez simplement un graphique régulier de haut-circonférence.$r = 0$

• Si est suffisamment petit, la réponse est "oui" pour tout pair . Prenez simplement un graphique en grille -dimensionnel (avec les limites enroulées pour le rendre régulier), et ordonnez les nœuds lexicographiquement par leurs coordonnées. Encore une fois, nous avons quelques mauvais bords près des limites de la grille, mais nous pouvons rendre le nombre de mauvais bords arbitrairement petit.d ( d / 2 ) $g$$d$$(d/2)$$d$

• Si n'a pas besoin d'être fini, la réponse est "oui" pour tout pair . Un arbre infini régulier a un ordre total tel que tous les bords sont bons.$G$$d$

• Si est impair et que est suffisamment grand, la réponse est "non". Essentiellement, Naor et Stockmeyer (1995) montrent que chaque nœud est incident avec au moins un bord non bon.$d$$r$

Contexte

(Cette section peut être ignorée en toute sécurité.)

La question est liée aux fondements de l'informatique distribuée, et en particulier aux algorithmes locaux .

Ce que nous voudrions comprendre est le suivant: dans quelles situations l'existence d'un ordre total aide à la rupture de symétrie locale dans un système distribué. Intuitivement, chaque nœud de doit produire une sortie qui est fonction de , c'est-à-dire une fonction du voisinage local de . Si un bord est mauvais, il y a des informations locales de rupture de symétrie disponibles près de , et les nœuds et peuvent produire des sorties différentes; si le bord est bon, alors les nœuds et sont localement indiscernables et ils doivent produire la même sortie.G ( G v , ≤ v ) v e = { u , v } e u v u $v$$G$$(G_v,\le_v)$$v$$e = \{u,v\}$$e$$u$$v$$u$$v$

Pour de nombreux problèmes de graphe classique, il est connu qu'un ordre total n'aide pas (des relations beaucoup plus faibles fournissent essentiellement la même quantité d'informations brisant la symétrie), mais certains cas sont toujours ouverts - et un résultat général qui couvre le cas de tous les les graphiques de circonférence pourraient être une percée.

Cela pourrait être une question gagnant-gagnant: quelle que soit la réponse, nous apprenons quelque chose de nouveau. Si la réponse est «oui», nous pourrions être en mesure de dériver de nouveaux résultats de borne inférieure plus solides; si la réponse est «non», nous pourrions être en mesure de concevoir des algorithmes plus rapides qui exploitent les informations locales de rupture de symétrie disponibles dans n'importe quel .$(G,\le)$

Bien sûr, dans le monde réel, nous n'avons pas d'ordre total sur ; nous avons quelque chose de plus: chaque nœud a une étiquette unique . Mais combler l'écart entre une commande totale et des étiquettes uniques est généralement plus simple; Souvent, un argument de type Ramsey montre que (dans le pire des cas) les étiquettes ne fournissent aucune information qui n'est pas disponible dans un ordre total.v ∈ V ℓ ( v ) ∈ $V$$v \in V$$\ell(v) \in \mathbb{N}$

Oui , de telles paires existent pour tout , tout , tout et tout même .ϵ > 0 r g $(G,\le)$$\epsilon > 0$$r$$g$$d$

Pour plus de détails, voir arXiv: 1201.6675 .