Makalah untuk kredit untuk partisi spektral grafik

Jika adalah diarahkan grafik -regular dan adalah bagian dari simpul-simpul kardinalitas , sebut ekspansi tepi dari kuantitas$G=(V,E)$$d$$S$$\leq |V|/2$$S$

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Dimana adalah jumlah sisi dengan satu titik akhir di dan satu titik akhir di . Maka masalah Edge Expansion adalah menemukan himpunan dengan yang meminimalkan . Sebut perluasan dari set optimal.$Edges(A,B)$$A$$B$$S$$|S|\leq |V|/2$$\phi(S)$$\phi(G)$

The Algoritma Partisi spektral untuk masalah Ujung Ekspansi bekerja dengan mencari vektor eigen dari nilai eigen terbesar kedua , matriks ketetanggaan dari , dan kemudian mempertimbangkan semua `` ambang batas set '' dalam bentuk atas semua ambang batas . Jika kita membiarkan menjadi nilai eigen terbesar kedua dari matriks , maka analisis Algoritma Pemisahan Spektral menunjukkan bahwa set ambang terbaik ditemukan oleh algoritma memenuhi$x$$A$$G$$S$$\{ v : x(v) \leq t \}$$t$$\lambda_2$$\frac 1d \cdot A$$S_{SP}$

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

Yang mengikuti dari Ketidaksetaraan Cheeger's

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

dan

$1-\lambda_2 \leq 2 \phi(G)$

Apa makalah pertama yang membuat klaim seperti itu? Makalah apa yang memberi penghargaan untuk ide-ide itu? Inilah yang saya dapatkan:

• N. Alon dan VD Milman. , ketidaksetaraan isoperimetrik untuk grafik, dan superkonsentrator, Journal of Combinatorial Theory, Series B, 1985, 38 (1): 73-88 $\lambda_1$

  Buktikan hasil dalam semangat "sederhana" Ketidakseimbangan Cheeger , tetapi untuk ekspansi verteks alih-alih ekspansi tepi. Mengakui bahwa hubungan antara ekspansi tepi dan nilai eigen adalah versi diskrit dari masalah yang dipelajari oleh Cheeger di $1-\lambda_2 \leq 2\phi(G)$

  J. Cheeger. Batas bawah untuk nilai eigen terkecil dari Laplacian. Masalah dalam Analisis, 1970.

• N. Alon. Nilai eigen dan ekspander. Combinatorica. 6 (2): 83-96, 1986.

  Membuktikan hasil dalam semangat ketidaksetaraan Cheeger yang sulit tetapi untuk ekspansi vertex alih-alih ekspansi edge. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

• A. Sinclair, M. Jerrum. Perkiraan penghitungan, pembentukan seragam, dan pencampuran rantai Markov dengan cepat. Informasi dan Komputasi 82: 93-133, 1989 (Versi konferensi 1987)

  Buktikan ketidaksetaraan Cheeger sebagaimana disebutkan di atas. (Makalah mereka mempelajari _konduktansi_ rantai Markov yang dapat dibalik waktu, yang terjadi sama dengan _edge expansion_ dalam grafik reguler.) Mereka menghargai karya Alon dan Milman dan Alon untuk tekniknya. Mereka juga memuji Aldous untuk ikatan terkait antara waktu pencampuran dan ekspansi edge dalam grafik reguler.

• M Mihail. Konduktansi dan konvergensi rantai Markov - perlakuan kombinasi ekspander. FOCS 1989, halaman 526-531

  Sementara poin utama dari makalah ini adalah bahwa tekniknya berlaku untuk rantai Markov non-waktu-reversibel, ketika diterapkan pada grafik tidak berarah reguler, ia memiliki keunggulan dibandingkan karya sebelumnya: itu menunjukkan bahwa jika seseorang menjalankan algoritme partisiig spektral dengan arbitrary vektor, kita masih mendapatkan ketimpangan mana adalah hasil bagi Rayleigh dari vektor. Argumen Alon, Milman, Sinclair dan Jerrum membutuhkan vektor eigen yang sebenarnya. Ini relevan dengan algoritma partisi spektral cepat yang menggunakan perkiraan vektor eigen. $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$$\lambda'$

Kapan signifikansi algoritmik dari hasil di atas, sebagai algoritma partisi grafik, pertama kali dikenali? Makalah di atas tidak memiliki diskusi seperti itu.

Tampaknya makalah pertama yang memperkenalkan serangkaian ide ini (menggunakan invarian aljabar , nilai eigen terkecil kedua dari grafik Laplacian, untuk mengikat berbagai sifat grafik) ke teori graf adalah "Konektivitas Aljabar Aljabar Grafik" Fiedler dalam Matematika Cekoslowakia Jurnal. Itu muncul pada tahun 1973, kira-kira pada waktu yang sama dengan kertas Cheeger (1970), yang berhubungan dengan manifold. Saya tidak yakin siapa yang pertama mengamati paralel antara grafik dan manifold dalam hal itu. kadang-kadang disebut nomor Fiedler.$\lambda_2$$\lambda_2$

Menariknya, ada komentar di akhir makalah Fiedler, menunjukkan laporan teknis independen oleh Anderson dan Morley berjudul Eigenvalues ​​of the Laplacian on a Graph from 1971, yang tampaknya memiliki ide serupa. Namun, makalah karya Anderson dan Morley dengan judul yang sama hanya muncul di Aljabar Linier dan Multilinear pada tahun 1985.

Beberapa referensi tambahan yang saya ingat dari era itu:

1) Diaconis dan Stroock, Batas geometris untuk nilai eigen rantai Markov, The Annals of Applied Probability, 1991; tapi saya ingat pernah mengerjakan pracetak pada tahun 1990. Makalah ini pada gilirannya merujuk

2) Dodziuk, persamaan Perbedaan, ketimpangan isoperimetri dan transiensi jalan acak tertentu, Transaksi Masyarakat Matematika Amerika, 1984.

Juga, makalah "pendamping algoritmik" yang penting bagi Sinclair dan Jerrum pada waktu itu adalah

3) Dyer Frieze Kannan, Algoritma Waktu Polinomial Acak untuk Mendekati Volume Badan Cembung, STOC 89. Tentu saja, hasilnya di sini dibangun di atas SJ.