Bagaimana cara membuat grafik expander biasa?

Saya perlu membuat d-regular expander graph untuk beberapa simpul tetap kecil (seperti 3 atau 4) dari n simpul.

Apa metode termudah untuk melakukan ini dalam praktek? Membuat grafik d-reguler acak, yang terbukti sebagai expander?

Saya juga membaca tentang konstruksi Margulis dan grafik Ramanujan yang merupakan ekspander dan konstruksi yang menggunakan produk zig-zag. Wikipedia memberikan ikhtisar yang bagus tapi sangat singkat: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Tapi metode apa yang saya pilih dalam praktik?

Bagi saya, metode ini tampaknya sangat rumit untuk diterapkan dan khususnya untuk dipahami dan mungkin sangat spesifik. Apakah tidak ada metode yang lebih mudah, mungkin berdasarkan permutasi atau lebih, untuk secara praktis menghasilkan urutan grafik ekspander d-reguler?

Apakah mungkin lebih mudah untuk membuat grafik d-reguler bipartite expander?

Saya juga punya pertanyaan lain: Bagaimana dengan keluarga ekspander buruk biasa? Apakah gagasan seperti itu masuk akal? Bisakah seseorang membuat keluarga grafik d-reguler (yang tentu saja terhubung) yang seburuk mungkin dalam arti expander?

Terima kasih sebelumnya.

graph-theory combinatorics cryptography discrete-mathematics expanders pengguna2145167
sumber

Ada konstruksi eksplisit yang lebih mudah daripada yang Anda daftarkan, tetapi grafik acak harus melakukan trik dan memiliki parameter yang lebih baik.

Yuval Filmus

Bisakah Anda memberi nama atau referensi konstruksi? Dengan parameter yang lebih baik, maksud Anda ekspansi (tepi) yang lebih baik, saya kira?

user2145167

András memberikan contoh yang ada dalam pikiran saya, tetapi secara umum, grafik acak (hampir selalu) lebih baik daripada konstruksi eksplisit. Tidak hanya perluasan tepi yang lebih besar, properti serupa lainnya yang membantu algoritme Anda mungkin secara otomatis dipenuhi oleh grafik acak.

Yuval Filmus

Ok, untuk tingkat 3, contoh András atau grafik acak tampaknya cukup baik untuk aplikasi saya. Akan menarik, khususnya berkenaan dengan grafik acak, untuk membangun keluarga grafik 3-reg yang bukan ekspander. Tapi ini mungkin sangat sulit atau tidak mungkin?

user2145167

Ambil penyatuan

s. Jika Anda ingin grafik terhubung, hapus satu sisi dari masing-masing

(membentuk grafik yang dikenal sebagai grafik berlian), dan hubungkan mereka dalam satu siklus.

K_{4}

$K_4$

K_{4}

$K_4$

Yuval Filmus

Jawaban:

Jika Anda tidak keberatan grafik dengan loop-diri, keluarga ekspander "termudah" mungkin yang ini, memberikan ekspander yang 3-reguler.

Mulailah dengan beberapa bilangan prima , dan buat simpul bernomor hingga . Untuk setiap simpul , hubungkan ke dan , modulo . Juga sambungkan dengan simpul unik sehingga $p$ $0$ $p-1$ $u \ne 0$ $u$ $u-1$ $u+1$ $p$ $u$ $v$ . $uv \equiv 1 \mod p$

Sebagai contoh, grafik 7-simpul dalam keluarga adalah 7-siklus dengan simpul diberi nomor secara berurutan di sekitar siklus; ada loop otomatis pada , , dan ; Akhirnya, ada akor yang bergabung dengan dan , dan dan . $6$ $0$ $1$ $3$ $5$ $2$ $4$

Lihat /mathpro/124708/an-expander-graph untuk diskusi dan referensi lebih lanjut. Ada banyak petunjuk yang lebih rinci dengan mencari "expander" di CSTheory , Math.SE , dan MO .

Seperti yang ditunjukkan Yuval Filmus, konstruksi acak cenderung memberikan hasil yang lebih baik secara umum, tetapi tentu saja tidak dapat menghasilkan expander (terutama untuk grafik kecil).

András Salamon
sumber

Terima kasih atas komentarnya. Saya telah mencari ekspander sebelumnya di situs lain tetapi tidak di MO, sepertinya ada lebih banyak hasil.

user2145167

Mengingat grafik reguler acak adalah expander whp (ikuti referensi yang diberikan dalam dokumentasi kode MATLAB yang ditautkan di bawah), saya pernah menggunakan yang berikut ini:

http://www.mathworks.com/matlabcentral/fileexchange/29786-random- regular-generator/content/randRegGraph/createRandRegGraph.m

Hoda
sumber