Zwykły wykres wysokiego obwodu z „lokalnie jednolitym” całkowitym porządkiem w węzłach

Definicje

Niech i niech d , r i g będą dodatnimi liczbami całkowitymi (z g > 2 r + 1 ).$\epsilon > 0$$d$$r$$g$$g > 2r+1$

Niech są proste, d -regular, nieukierunkowane skończonej wykres z obwodu co najmniej g .$G = (V,E)$$d$$g$

Niech być całkowity porządek na V .$\le$$V$

Dla każdego , niech V v ⊆ V składa się z węzłów, które znajdują się w odległości r od v w G (najkrótsza ścieżka od v do dowolnego u ∈ V v ma co najwyżej r krawędzie), i niech G v będzie podgraphem o G wywołane V v . Przypomnijmy, że założyliśmy, że G ma wysoki obwód; stąd G v jest drzewem. Niech ≤ v będzie ograniczeniem ≤ do$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$

Mówimy, że krawędź jest dobra, jeśli ( G u , ≤ u ) i ( G v , ≤ v ) są izomorficzne. Oznacza to, że istnieje bijection f : V u → V v, który zachowuje przylegania ( { 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$ ) i porządek ( x ≤ y iff f ( x ) ≤ f ( y ) ). W przeciwnym razie krawędź jestzła.$\{f(x),f(y)\} \in E$$x \le y$$f(x) \le f(y)$

Mówimy, że jest ϵ -dobry, jeśli jest co najmniej ( 1 - ϵ ) | E | dobre krawędzie.$(G,\le)$$\epsilon$$(1-\epsilon)|E|$

Pytanie

Niech . Czy istnieje takie ε -Dobra pary ( G , ≤ ) dla każdego ε > 0 i dowolnym R i g (z R « g )?$d = 4$$\epsilon$$(G,\le)$$\epsilon > 0$$r$$g$$r \ll g$

Uwagi:

• Chciałbym znać odpowiedź na ogólne , ale d = 4 to pierwszy przypadek niebanalny.$d$$d = 4$

• Rozmiar nie ma znaczenia, o ile jest skończony. Nie potrzebuję konstrukcji G ; wystarczy samo istnienie lub nieistnienie.$G$$G$

Przykłady

• Jeśli , odpowiedź brzmi „tak”. Możemy po prostu wziąć wystarczająco długi cykl i uporządkować węzły wzdłuż tego cyklu. W pobliżu krawędzi znajdują się złe krawędzie, które łączą największy i najmniejszy węzeł, ale wszystkie inne krawędzie są dobre: ​​dla prawie wszystkich węzłów v para ( G v , ≤ v ) jest po prostu ścieżką z 2 r + 1 węzłami w rosnące zamówienie.$d = 2$$v$$(G_v,\le_v)$$2r+1$

• Jeśli , odpowiedź brzmi „tak”. Po prostu weź regularny wykres wysokiego obwodu.$r = 0$

• Jeśli jest wystarczająco małe, odpowiedź brzmi „tak” dla dowolnego parzystego d . Wystarczy wziąć ( d / 2 ) wymiarową wykres siatki (z granicami owiniętych wokół aby d Dokładnie -regular) oraz kolejność węzłów leksykograficznie poprzez ich współrzędne. Znów mamy złe krawędzie w pobliżu granic siatki, ale możemy zmniejszyć liczbę złych krawędzi dowolnie.$g$$d$$(d/2)$$d$

• Jeśli nie musi być skończony, odpowiedź brzmi „tak” dla dowolnego parzystego d . Zwykłe nieskończone drzewo ma całkowitą kolejność, dzięki czemu wszystkie krawędzie są dobre.$G$$d$

• Jeśli jest nieparzyste, a r jest wystarczająco duże, odpowiedź brzmi „nie”. Zasadniczo Naor i Stockmeyer (1995) pokazują, że każdy węzeł podlega incydentowi z co najmniej jedną niesprzyjającą krawędzią.$d$$r$

tło

(Tę sekcję można bezpiecznie pominąć.)

Pytanie dotyczy podstaw przetwarzania rozproszonego, w szczególności lokalnych algorytmów .

Chcielibyśmy zrozumieć, co następuje: w jakich sytuacjach istnienie całkowitego porządku pomaga w łamaniu lokalnej symetrii w systemie rozproszonym. Intuicyjnie, każdy węzeł z G musi produkować wyjście, które jest funkcją ( G v , ≤ v ) , czyli funkcją lokalnym sąsiedztwie v . Jeśli zbocze e = { u , v } jest złe, w pobliżu e dostępne są lokalne informacje o łamaniu symetrii , a węzły u i v mogą wytwarzać różne dane wyjściowe; jeśli krawędź jest dobra, to węzły$v$$G$$(G_v,\le_v)$$v$$e = \{u,v\}$$e$$u$$v$ i v są lokalnie nie do odróżnienia i muszą dawać takie same wyniki.$u$$v$

W przypadku wielu klasycznych problemów graficznych wiadomo, że całkowity porządek nie pomaga (znacznie słabsze relacje dostarczają zasadniczo taką samą ilość informacji łamiącej symetrię), ale niektóre przypadki są nadal otwarte - i ogólny wynik obejmuje przypadek wszystkich wysokich wykresy obwodu mogą być przełomem.

Może to być pytanie korzystne dla obu stron: niezależnie od odpowiedzi uczymy się czegoś nowego. Jeśli odpowiedź brzmi „tak”, możemy być w stanie uzyskać nowe, silniejsze wyniki w dolnej granicy; jeśli odpowiedź brzmi „nie”, możemy być w stanie zaprojektować szybsze algorytmy, które wykorzystują informacje na temat łamania symetrii lokalnej, które są dostępne w dowolnym .$(G,\le)$

Oczywiście w prawdziwym świecie nie mamy całkowitego zamówienia na ; mamy coś więcej: każdy węzeł v ∈ V ma unikalną etykieta £ -l ( v ) ∈ N . Jednak wypełnienie luki między całkowitym zamówieniem a unikalnymi etykietami jest zwykle prostsze; często argument podobny do Ramseya pokazuje, że (w najgorszym przypadku) etykiety nie zawierają żadnych informacji, które nie są dostępne w całkowitej kolejności.$V$$v \in V$$\ell(v) \in \mathbb{N}$

Tak , takie pary istnieją dla dowolnego ϵ > 0 , dowolnego r , dowolnego g , i dowolnego parzystego d .$(G,\le)$$\epsilon > 0$$r$$g$$d$

Aby uzyskać szczegółowe informacje, zobacz arXiv: 1201.6675 .