Grafik lingkar tinggi reguler dengan urutan total "seragam lokal" pada node

Definisi

Misalkan dan misalkan d , r , dan g adalah bilangan bulat positif (dengan g > 2 r + 1 ).$\epsilon > 0$$d$$r$$g$$g > 2r+1$

Misalkan menjadi grafik berhingga sederhana, d- teratur, tidak terarah, dengan ketebalan setidaknya g .$G = (V,E)$$d$$g$

Mari menjadi urutan total pada V .$\le$$V$

Untuk setiap , biarkan V v ⊆ V terdiri dari node yang berada dalam jarak r dari v di G (jalur terpendek dari v untuk setiap u ∈ V v memiliki paling r tepi), dan membiarkan G v menjadi subgraph yang dari G yang diinduksi oleh V v . Ingatlah bahwa kami berasumsi bahwa G memiliki ketebalan yang tinggi; maka G v adalah pohon. Biarkan ≤ v menjadi batasan ≤ to$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$

Kami mengatakan bahwa keunggulan adalah baik jika ( G u , ≤ u ) dan ( G v , ≤ v ) isomorfik. Yaitu, ada sebuah bijih f : V u → V v yang mempertahankan kedekatan ( { 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$ ) dan pesan ( x ≤ y iff f ( x ) ≤ f ( y ) ). Kalau tidak, ujung ituburuk.$\{f(x),f(y)\} \in E$$x \le y$$f(x) \le f(y)$

Kami mengatakan bahwa adalah ϵ -baik jika setidaknya ada ( 1 - ϵ ) | E | tepi yang bagus.$(G,\le)$$\epsilon$$(1-\epsilon)|E|$

Pertanyaan

Misalkan . Apakah ada pasangan ϵ -good ( G , ≤ ) untuk setiap ϵ > 0 dan r dan g (dengan r ≪ g )?$d = 4$$\epsilon$$(G,\le)$$\epsilon > 0$$r$$g$$r \ll g$

Catatan:

• Saya ingin tahu jawaban untuk umum , tetapi d = 4 adalah kasus non-sepele pertama.$d$$d = 4$

• Ukuran tidak masalah, asalkan terbatas. Saya tidak membutuhkan konstruksi G ; keberadaan atau ketidakberadaan saja sudah cukup.$G$$G$

Contohnya

• Jika , jawabannya adalah "ya". Kita cukup mengambil siklus yang cukup panjang, dan memesan node di sepanjang siklus. Ada beberapa tepi buruk di dekat tepi yang bergabung terbesar dan node terkecil, tetapi yang lainnya akan baik: untuk hampir semua node v , pasangan ( G v , ≤ v ) hanya jalan dengan 2 r + 1 node di pesanan meningkat.$d = 2$$v$$(G_v,\le_v)$$2r+1$

• Jika , jawabannya adalah "ya". Ambil saja grafik dengan ketebalan tinggi biasa.$r = 0$

• Jika cukup kecil, jawabannya adalah "ya" untuk setiap genap d . Ambil saja grafik grid -dimensional ( d / 2 ) (dengan batas-batas yang dililit untuk membuatnya menjadi -d reguler), dan pesan node secara leksikografis berdasarkan koordinatnya. Sekali lagi kita memiliki beberapa tepi buruk di dekat batas-batas grid, tetapi kita dapat membuat jumlah tepi buruk menjadi kecil secara sewenang-wenang.$g$$d$$(d/2)$$d$

• Jika tidak perlu terbatas, jawabannya adalah "ya" bahkan untuk setiap d . Pohon infinite reguler memiliki urutan total sehingga semua sisi bagus.$G$$d$

• Jika ganjil dan r cukup besar, jawabannya adalah "tidak". Pada dasarnya, Naor & Stockmeyer (1995) menunjukkan bahwa setiap node adalah insiden setidaknya satu sisi yang tidak baik.$d$$r$

Latar Belakang

(Bagian ini dapat dilewati dengan aman.)

Pertanyaannya terkait dengan dasar-dasar komputasi terdistribusi, dan khususnya untuk algoritma lokal .

$v$$G$$(G_v,\le_v)$$v$$e = \{u,v\}$$e$$u$$v$$u$$v$

Untuk banyak masalah grafik klasik diketahui bahwa urutan total tidak membantu (hubungan yang jauh lebih lemah pada dasarnya memberikan jumlah yang sama dari informasi pemecahan simetri), tetapi beberapa kasus masih terbuka - dan hasil umum yang mencakup semua kasus tinggi grafik ketebalan bisa menjadi terobosan.

$(G,\le)$

$V$$v \in V$$\ell(v) \in \mathbb{N}$

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

Untuk detailnya, lihat arXiv: 1201.6675 .