Tentang dugaan ekspansi set kecil

Diberikan grafik dan ingin dihitung . ( )) `` ekspansi set kecil dugaan "menyatakan bahwa NP-Sulit untuk menentukan apakah ini di bawah atau di atas untukδ > 0 h ( G , δ ) = m i n | S | ≤ δ | V | ϕ ( S ) ϕ ( S ) = E ( S , ˉ S$G=(V,E)$$\delta > 0$$h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$ Ε1-εε=1/O(log($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - \vert S\vert \} }$$\epsilon$$1-\epsilon$$\epsilon = 1/O(log(\frac{1}{\delta} ) )$

Untuk konteks, perhatikan bahwa adalah konstanta Cheeger yang dikenal sebagai NP-hard to bound. Tetapi tampaknya ada nilai (yang mana?) Yang dapat dihitung dalam waktu polinomial?δϕ(G,δ$h(G,\delta = \frac{1}{2})$$\delta$$\phi(G,\delta)$

Menuju pemahaman dugaan ekspansi kecil yang tampaknya membuktikan pernyataan ini,

• Jika adalah rentang vektor eigen Laplacian dari sehingga nilai eigennya kurang dari beberapa dan jika setiap memenuhi lalu untuk setiap himpunan sedemikian rupa sehingga kami memilikiG λ ∈ [ 0 , 1 $W$$G$$\lambda \in [0,1]$E i [ w 4 i ] ≤ C ( E i [ w 2 i ] ) 2 S | S | ≤ δ | V | ϕ ( S ) ≥ λ ( 1 - $w \in W$$\mathbb{E}_i[w_i^4 ] \leq C ( E_i [w_i ^2 ] )^2$$S$$\vert S \vert \leq \delta \vert V \vert$$\phi(S) \geq \lambda(1 - \sqrt{C \delta} )$

[Referensi, Lemma 8 di sini, http://www.boazbarak.org/sos/files/lec2d.pdf ]

Pertanyaan saya adalah,

• Bagaimana teorema di atas membantu memahami dugaan yang dinyatakan di awal? Apa hubungan keduanya?

• Mengapa vektor seperti eksis seperti yang diminta dalam teorema? Apa intuisi di balik memandangi ?$w$$w$

• Apa intuisi di balik memilih nilai spesifik seperti dalam pernyataan dugaan?$\epsilon$

Saya pikir yang berikut ini harus menjawab pertanyaan Anda, meskipun tidak dalam urutan yang sama.

Formulasi asli dari dugaan ekspansi set kecil menyatakan bahwa, analog dengan Konjektur Game Unik, untuk setiap terdapat sehingga sulit untuk menentukan apakah dalam grafik adalah "YA" kasus di mana ada set -sized dengan ekspansi kurang dari atau itu adalah "TIDAK" kasus di mana setiap set -sized memiliki ekspansi setidaknya . Makalah Raghavendra, Steuerer, dan Tulsiani https://www.cs.cornell.edu/~dsteurer/papers/ssereductions.pdf menunjukkan bahwa ini setara dengan kasus di manaδ > 0 G δ ϵ δ 1 - ϵ ϵ = O ( log ( 1 / δ ) ) δ ′ ≥ δ δ ′ ϵ ϵ = O ( log ( 1 / δ ) ) 1 / δ $\epsilon >0$$\delta>0$$G$$\delta$$\epsilon$$\delta$$1-\epsilon$$\epsilon = O(\log (1/\delta))$dan faktanya dalam kasus NO, untuk setiap , set ukuran memiliki setidaknya ekspansi yang sama seperti pada " -noisy Gaussian graph" (lihat kertas untuk pernyataan yang tepat). Alasan untuk hubungan adalah karena ini adalah hubungan antara parameter-parameter tersebut dalam grafik noise Gaussian. Hasil Raghavendra et al ini dapat dianggap sebagai analog ekspansi kecil untuk karya Khot, Kindler, Mossell dan O'Donnell yang menunjukkan hasil yang serupa untuk game unik, memberikan hubungan yang sangat tepat antara parameter (yang dalam pengaturan game unik dikenal sebagai ukuran alfabet) dan$\delta' \geq \delta$$\delta'$$\epsilon$$\epsilon = O(\log (1/\delta))$$1/\delta$$\epsilon$.

Hasil yang Anda sebutkan dibahas dalam catatan kuliah saya adalah dari Bagian 8 di makalah saya dengan Brandao, Harrow, Kelner, Steurer dan Zhou ( https://www.cs.cornell.edu/~dsteurer/papers/hypercontract.pdf ). Apa yang kami tunjukkan di sana, secara kasar, adalah bahwa grafik adalah set expander kecil jika dan hanya jika rentang vektor eigen yang sesuai dengan nilai eigen rendah Laplaciannya tidak mengandung vektor "secara analitik jarang".

Intuisi adalah sebagai berikut: pertimbangkan dua ekstrem berikut:

1) Vektor acak . Dalam hal ini, distribusi entri adalah kira-kira distribusi Gaussian, dan karenanya ini memuaskan bahwa .w E i w 4 i = O ( E i w 2 i ) $w$$w$$\mathbb{E}_i w_i^4 = O(\mathbb{E}_i w_i^2)^2$

2) Vektor yang merupakan vektor karakteristik dari himpunan (yaitu memiliki pada koordinat yang dimiliki himpunan, dan pada yang lain). Dalam hal ini, .δ 1 0 E i w 4 i = δ ≫ δ 2 = ( E i w 2 i ) $w$$\delta$$1$$0$$\mathbb{E}_i w_i^4 = \delta \gg \delta^2 = (\mathbb{E}_i w_i^2)^2$

Sekarang, secara kasar, subruang sesuai dengan nilai eigen lebih kecil dari dari Laplacian berhubungan dengan set yang memiliki ekspansi paling banyak dalam grafik. Jadi, jika ada set -sized dengan ekspansi seperti itu maka akan ada vektor (yaitu proyeksi vektor karakteristik dari set ini ke ) dengan . Arah lain (yang lebih sulit untuk dibuktikan tetapi ternyata benar) adalah bahwa jika ada vektor dengan properti ini maka kita juga dapat menemukan himpunan dengan ukuran dengan ekspansi yang tidak terlalu baik.ϵ ϵ δ w W E i w 4 i ≫ ( E i w 2 i ) 2 w o ( 1 $W$$\epsilon$$\epsilon$$\delta$$w$$W$$\mathbb{E}_i w_i^4 \gg (\mathbb{E}_i w_i^2)^2$$w$$o(1)$