Konduktansi dan diameter dalam grafik reguler

Diberikan graf biasa, tidak berarah , apa hubungan antara diameternya - didefinisikan sebagai jarak terbesar antara dua node - dan konduktansinya, didefinisikan sebagai mana adalah jumlah tepi yang melintasi antara dan . $G=(V,E)$

min_{S \subset V} \frac{e (S, S^{c})}{min (| S |, | S^{c} |)},

$\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},$

e (S, S^{c})

$e(S,S^c)$

S

$S$

S^{c}

$S^c$

Lebih konkret kira saya tahu diameter setidaknya (atau sebagian besar) $D$ . Apa yang dikatakan di sini tentang konduktansi, jika ada? Dan, sebaliknya, anggaplah saya tahu konduktansi paling banyak (atau setidaknya) $\alpha$ . Apa artinya ini tentang diameter, jika ada?

graph-theory co.combinatorics expanders Robinson
sumber

Sepertinya properti yang Anda tanyakan adalah ekspansi grafik alih-alih konduktansi grafik, yang didefinisikan sebagai

min_{S \subseteq V} e (S, \bar{S}) / min {v o l (S), v o l (\bar{S})}

$\min_{S \subseteq V} \ {e(S,\overline{S})}/{\min\{\mathsf{vol}(S), \mathsf{vol}(\overline{S})\}}$ , di mana

v o l (S)

$\mathsf{vol}(S)$ didefinisikan sebagai

\sum_{v \in S} \deg (v)

$\sum_{v \in S} \deg(v)$ . Properti mana yang Anda inginkan ??

Hsien-Chih Chang 張顯之

@ Hsien-Chi Chang - karena grafiknya teratur, saya percaya konduktansi dan ekspansi harus sama dengan faktor multiplikasi derajat

d

$d$ .

robinson

Ah, saya tidak memperhatikan bahwa grafiknya teratur. Terima kasih untuk penjelasannya.

Hsien-Chih Chang 張顯之

@ Hsien-ChihChang 張顯之: Saya pikir ekspansi grafik dan konduktansi grafik adalah konsep yang sama. Apakah Anda memiliki referensi tentang definisi dalam komentar Anda?

Tim

Seperti yang dicatat Hsieh, definisi konduktansi Anda tidak sesuai dengan yang saya tahu dengan faktor $d$ , di mana $d$ adalah derajat grafik reguler. Ini juga dikenal sebagai ekspansi tepi untuk grafik biasa.

Hubungan antara ekspansi tepi dan diameter cukup mudah ditunjukkan. Secara intuitif, expander adalah "seperti" grafik yang lengkap, sehingga semua simpul "dekat" satu sama lain. Secara lebih formal, mari

min_{S \subseteq V} \frac{e (S, S^{c})}{d \cdot min {| S |, | S^{c} |}} \geq α

$\min_{S \subseteq V}\ { \frac{ e(S, S^c) }{ d \cdot \min\{|S|, |S^c|\} }} \geq \alpha$

Ambil sembarang simpul dengan . Setidaknya adatepi yang keluar dari dan karena adalah teratur, lingkungan (termasuk itu sendiri) berukuran paling tidak. Menerapkan klaim ini secara induktif, mulai dari untuk setiap vertex , kita melihat bahwa untuk beberapa , 's -hop lingkungan memiliki ukuran setidaknya . Oleh karena itu, lingkungan -hop dari titik mana pun $S$ $|S| \leq |V|/2$ $\alpha d |S|$ $S$ $G$ $d$ $S$ $S$ $(1+\alpha)|S|$ $S = \{u\}$ $u$ $t = O(\log_{1 + \alpha } |V|)$ $u$ $t$ $|V|/2$ $t+1$ $v$ harus memotong lingkungan -hop , atau grafik akan memiliki lebih darisimpul, sebuah kontradiksi. Jadi kamu punya $t$ $u$ $|V|$

D = O (\frac{\log | V |}{\log (1 + α)})

$D = O\left(\frac{\log |V|}{\log (1 + \alpha)}\right)$

Tentu saja, ini juga berarti bahwa memiliki batas bawah pada diameter menyiratkan batas atas pada ekspansi tepi.

Saya tidak berpikir diameter kecil menyiratkan konduktansi. Jika Anda tidak memaksa grafik biasa (dan menggunakan definisi Hsieh), maka dua grafik lengkap yang dihubungkan oleh satu sisi memberikan contoh berlawanan.

Sasho Nikolov
sumber

Saya akan memposting jawaban dan sekarang saya tidak perlu, saya hanya dapat meningkatkan jawaban Anda sebagai gantinya;) Terima kasih atas jawaban yang baik!

Hsien-Chih Chang 張顯之

Saya berharap total waktu yang Anda dan saya habiskan untuk penelitian dapat dikurangi :)

Sasho Nikolov

@robinson: fakta sederhana dan pencampuran cepat ini adalah dasar dari banyak (kebanyakan?) aplikasi keluarga expander dari grafik reguler. properti berdiameter kecil misalnya adalah dasar dari aplikasi untuk menyelesaikan konektivitas st di logspace

Sasho Nikolov

jawaban asli saya memiliki bug: argumen yang saya tulis adalah untuk ekspansi dhuwur, tapi kami sedang bekerja dengan perluasan sisi di sini. Saya telah memperbaiki bug, dan terikat sekarang sedikit lebih buruk

Sasho Nikolov

Konduktansi dan diameter dalam grafik reguler

Jawaban: