Bukti diperoleh hanya melalui teori grafik spektral

28

Saya memiliki minat yang meningkat pada teori grafik spektral, yang menurut saya menarik, dan saya sudah mulai mengumpulkan beberapa dokumen yang belum saya baca lebih teliti daripada yang saya miliki sejauh ini.

Namun, saya ingin tahu tentang pernyataan yang muncul di beberapa sumber (misalnya di sana ), yang mengatakan pada dasarnya bahwa beberapa hasil dalam teori grafik telah terbukti menggunakan teknik berbasis spektrum saja, dan sejauh ini, tidak ada bukti bahwa Bypass teknik-teknik tersebut diketahui.

Kecuali saya melewatkan itu, saya tidak ingat melihat contoh seperti itu dalam literatur yang saya baca sejauh ini. Apakah ada di antara Anda yang tahu contoh hasil seperti itu?

graph-theory co.combinatorics proofs spectral-graph-theory Anthony Labarre
sumber

Judul pertanyaan menunjukkan bahwa Anda meminta bukti yang hanya dapat diperoleh dengan menggunakan teori grafik spektral, tetapi Anda meminta bukti yang sampai sekarang hanya diperoleh oleh teori grafik spektral. Ini adalah dua pertanyaan yang sangat berbeda. Jadi seperti berdiri, judulnya menyesatkan, itulah sebabnya saya mengubahnya.

Dave Clarke

@Dave aku melakukan rollback

Suresh Venkat

5

Bab 7 dari Spectra of Graphs oleh Cvetković, Doob, dan Sachs memberikan banyak contoh teorema yang pernyataannya tidak menyebutkan spektrum secara eksplisit tetapi dapat dibuktikan menggunakan teknik spektral. Dugaan saya adalah bahwa banyak dari ini tidak memiliki bukti non-spektral yang diketahui, meskipun Anda harus memverifikasi ini berdasarkan kasus per kasus. Tentu saja dalam banyak kasus bukti paling sederhana atau paling alami menggunakan spektra.

Timothy Chow

@Timothy Chow: Terima kasih, saya akan mencoba untuk mendapatkannya.

Anthony Labarre

@TimothyChow: Saya kira Anda harus menjawabnya.

Suresh Venkat

12

The Hoffman-Singleton teorema .

Colin McQuillan
sumber

Hoffman-Singleton adalah pikiran pertamaku juga. Tetapi, saya tidak tahu apakah ada bukti non-spektral dan jika tidak ada karena itu terlalu sulit atau karena tidak ada yang mencoba. Bukti standar cukup rapi dan ringkas, jadi saya tidak tahu apa motivasi untuk mendapatkan bukti non-spektral.

mhum

9

Bagaimana dengan hasil ini pada komputasi kuantum.

Mario Szegedy. Quantum Speed-Up dari Algoritma Berbasis Rantai Markov. Dalam FOCS'04.

Dia memperluas rantai Markov ke kuantum rantai Markov, dan menunjukkan bahwa waktu memukul kuantum dibatasi oleh akar kuadrat dari waktu memukul klasik. Dia melakukan ini dengan menghubungkan vektor singular dari rantai Markov klasik ke vektor singular dari rantai Markov kuantum. Sebelum tulisan ini, tidak ada hubungan yang diketahui antara random dan quantum walks. Saya tidak bisa membayangkan bagaimana melakukan hal yang sama menggunakan teknik non-spektral.

Marcos Villagra
sumber

8

Saya pikir itu teorema persahabatan (lihat juga makalah Huneke ) adalah contoh yang baik meskipun secara tegas sekarang ada bukti teorema pertemanan yang menghindari nilai eigen. Bukti yang menghindari nilai eigen sepenuhnya jauh lebih berantakan daripada bukti spektral.

(Teorema persahabatan menyatakan bahwa jika dalam ruangan orang, setiap pasangan orang memiliki satu teman yang sama, maka ada seseorang yang mengenal orang lain.)

Timothy Chow
sumber

8

$L_G$ $G = (V,E,w)$ $G$ $H$ $x \in R^V$

x^{T} {L.}_{H} x (1 - ϵ) \leq x^{T} {L.}_{G} x \leq x^{T} {L.}_{H} x (1 + ϵ) .

$x^T L_H x (1-\epsilon) \le x^T L_G x \le x^T L_H x (1+\epsilon).$

O (n / ϵ^{2})

$O(n/\epsilon^2)$

Meskipun pernyataan teorema masih bisa diperdebatkan bukan "inheren spektral," saya tidak berpikir itu diketahui bagaimana seseorang bisa mendapatkan hasil ini atau hasil seperti itu tanpa menggunakan teknik spektral.

Lev Reyzin
sumber

Agak bisa diperdebatkan apakah pernyataan itu tidak inheren spektral. Dalam pengertian literal, Anda benar, tetapi satu-satunya alasan yang dapat saya pikirkan mengapa bentuk kuadratik muncul adalah spektral.

Suresh Venkat

1

F (A) = {x^{T} A x : | | x | |_{2} = 1}

$F(A) = \{x^TAx: ||x||_2 = 1\}$

O (n / ϵ^{2})

$O(n/\epsilon^2)$

Tentu - tetapi orang bisa membayangkan mendapatkan sparsifier ini dengan cara lain. Tapi, ya, ini mungkin bukan contoh terbaik ...

Lev Reyzin

Bukti diperoleh hanya melalui teori grafik spektral

Jawaban: