Ekspansi tidak seimbang "industri" yang efisien ruang

Saya mencari ekspander yang tidak seimbang yang "baik" dan "hemat ruang". Secara khusus, grafik reguler-kiri bipartit , , , dengan derajat kiri adalah ekspander -pengembang jika untuk setiap ukuran paling banyak , jumlah tetangga di setidaknya. Diketahui bahwa metode probabilistik menghasilkan grafik dengan dan . Namun, kita perlu| A | = n | B | = m d ( k , ϵ ) S ⊂ A k S B ( 1 - ϵ ) d | S | d = O ( log ( n / k ) / ϵ ) m = O ( k log ( $G=(A,B,E)$$|A|=n$$|B|=m$$d$$(k,\epsilon)$$S \subset A$$k$$S$$B$$(1-\epsilon)d|S|$$d=O(\log (n/k)/\epsilon)$O ( n d $m=O(k \log(n/k)/\epsilon^2)$$O(n d)$ruang untuk menyimpan grafik seperti itu. Selain itu, orang juga perlu mengakses penyimpanan ini ketika melakukan apa saja dengan grafik, yang bisa memakan biaya juga. Idealnya, orang ingin konstruksi eksplisit. Namun, sejauh yang saya tahu, konstruksi yang diketahui mencapai parameter yang masih agak jauh dari yang di atas (setidaknya terbukti demikian).

Pertanyaan saya: apakah ada konstruksi lain, mungkin non-eksplisit, yang mencapai batas "lebih dekat" dengan yang di atas, namun menggunakan "jauh lebih sedikit" daripada ruang ?$O(nd)$

Saya mencari jawaban dalam salah satu dari tiga kategori ini: (a) teorema (b) dugaan (c) pengamatan dan "cerita perang" seperti "kami melakukan ini dan itu sepertinya berhasil (semacam)". Yaitu, "industri" ekspander OK. Saya lebih suka (a) lebih dari (b) dan (b) lebih dari (c), tetapi pengemis tidak bisa menjadi pemilih :)

Berikut adalah contoh konstruksi tipe (c). Ambil fungsi hash linier acak (mod ), dan hubungkan setiap simpul ke . Saya dan murid saya melakukan beberapa percobaan di atasnya, dan sepertinya berhasil "baik". Apakah ada teorema atau dugaan tentang ini atau konstruksi terkait?h i : [ n ] → [ m ] m i h 1 ( i ) … h d ( i $d$$h_i: [n] \to [m]$$m$$i$$h_1(i) \ldots h_d(i)$

Terima kasih!

Eickmeyer dan Grohe (2010) membuktikan bahwa konstruksi calon Anda dapat dibuat eksplisit: take agak independen linear fungsi hash linear dan simpul kiri menghubungkan dengan simpul kanan . Eickmeyer dan Grohe menunjukkan bahwa konstruksi ini memberikan -pengembang dengan derajat kiri , setiap kali adalah bilangan bulat, himpunan simpul kiri memiliki ukuran , set simpul kanan memiliki ukuran , dan adalah kekuatan utama. Fungsi hash dipilih sedemikian rupah 1 , ... , h d v h 1 ( v ) , ... , h d ( $d$$h_1,\dots,h_d$$v$( k , ϵ ) d = k ( t - 1 ) / ( 2 ϵ ) t n = q t m = d q q > d h 1 , … , h d$h_1(v),\dots,h_d(v)$$(k,\epsilon)$$d=k(t-1)/(2\epsilon)$$t$$n=q^t$$m=dq$$q>d$$h_1,\dots,h_d$$t$ dari mereka adalah bebas linear.

Saya pikir bahwa dengan melihat survei / pembicaraan oleh Avi Wigderson dapat membantu dengan pertanyaan Anda. Berikut ini adalah slide dari ceramah terbaru: Tutorial Expander, Juni 2010 . Konstruksi dimulai pada halaman 40.

Mengenai kompleksitas ruang, saya pikir akan sangat membantu jika Anda menentukan operasi yang perlu Anda lakukan pada grafik. Jika saya tidak salah, beberapa konstruksi memungkinkan operasi seperti lingkungan komputasi di logspace.