Extenseurs asymétriques «industriels» à faible encombrement

Je recherche des expandeurs déséquilibrés qui sont "bons" et "peu encombrants". Plus précisément, un graphe bipartite gauche-régulier , , , avec le degré gauche est un -expander si pour tout de taille au plus , le nombre de voisins distincts de dans est au moins. On sait que la méthode probabiliste donne un tel graphique avec et . Cependant, il faut| 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)$espace pour stocker un tel graphique. De plus, il faut également accéder à ce stockage lorsque vous faites quoi que ce soit avec le graphique, ce qui peut également coûter cher. Idéalement, on souhaiterait une construction explicite. Cependant, pour autant que je sache, les constructions connues atteignent des paramètres qui sont encore quelque peu éloignés de ce qui précède (du moins de manière prouvée).

Ma question: existe-t-il d'autres constructions, éventuellement non explicites, qui atteignent des bornes "plus proches" de celles ci-dessus, tout en utilisant "nettement moins" que l' espace $O(nd)$ ?

Je cherche des réponses dans l'une de ces trois catégories: (a) théorèmes (b) conjectures (c) observations et "histoires de guerre" telles que "nous l'avons fait et cela a semblé fonctionner (en quelque sorte)". C'est-à-dire que les extenseurs "industriels" sont OK. Je préfère (a) à (b) et (b) à (c), mais les mendiants ne peuvent pas être des sélecteurs :)

Voici un exemple de construction de type (c). Prenez $d$ fonctions de hachage linéaires aléatoires $h_i: [n] \to [m]$ (mod $m$ ), et connectez chaque sommet $i$ à $h_1(i) \ldots h_d(i)$ . Mon élève et moi avons fait quelques expériences dessus, et cela a semblé fonctionner "très bien". Existe-t-il des théorèmes ou des conjectures à propos de cette construction ou de constructions connexes?

Merci!

Eickmeyer et Grohe (2010) prouvent que votre construction candidate peut être rendue explicite: prenez des fonctions de hachage linéaires quelque peu indépendantes linéairement h 1 , … , h d et connectez les sommets gauches v avec les sommets droits h 1 ( v ) , … , h d ( v ) . Eickmeyer et Grohe montrent que cette construction donne des expanseurs ( k , ϵ ) de degré gauche d = k ( t - 1 $d$$h_1,\dots,h_d$$v$$h_1(v),\dots,h_d(v)$$(k,\epsilon)$ , chaque fois que t est un entier, l'ensemble de sommets gauche a la taille n = q t , l'ensemble de sommets droit a la taille m = d q , et q > d est une puissance première. Les fonctions de hachage h 1 , … , h d sont choisies de telle sorte que tout t d'entre elles soit linéairement indépendant.$d=k(t-1)/(2\epsilon)$$t$$n=q^t$$m=dq$$q>d$$h_1,\dots,h_d$$t$

Je pensais qu'avoir un aperçu des sondages / conférences d'Avi Wigderson pourrait aider avec votre question. Voici les diapositives d'une conférence récente: Tutoriel Expander, juin 2010 . Les constructions commencent à la page 40.

En ce qui concerne la complexité de l'espace, je pense que cela peut être utile si vous spécifiez les opérations que vous devez effectuer sur le graphique. Si je ne me trompe pas, certaines constructions permettent des opérations comme le calcul de voisinage dans l'espace journal.