Expansores desequilibrados "industriales" que ahorran espacio

Estoy buscando expansores desequilibrados que sean "buenos" y "eficientes en espacio". Específicamente, un gráfico bipartito izquierdo-regular , , , con grado izquierdo es un -expansor si para cualquier de tamaño máximo , el número de vecinos distintos de en es al menos. Se sabe que los rendimientos método Probabilístico un gráfico de este tipo con y . Sin embargo, uno necesita| 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)$espacio para almacenar dicho gráfico. También es necesario acceder a este almacenamiento cuando se hace algo con el gráfico, lo que también puede costar. Idealmente, a uno le gustaría una construcción explícita. Sin embargo, hasta donde yo sé, las construcciones conocidas logran parámetros que aún están un poco lejos de lo anterior (al menos de manera demostrable).

Mi pregunta: ¿hay otras construcciones, posiblemente no explícitas, que alcanzan límites "más cercanos" a los anteriores, pero que usan "significativamente menos" que el espacio ?$O(nd)$

Estoy buscando respuestas en cualquiera de estas tres categorías: (a) teoremas (b) conjeturas (c) observaciones e "historias de guerra" como "hicimos esto y parecía funcionar (más o menos)". Es decir, los expansores "industriales" están bien. Prefiero (a) sobre (b) y (b) sobre (c), pero los mendigos no pueden ser elegidos :)

Aquí hay un ejemplo de una construcción de tipo (c). Tome funciones hash lineales aleatorias (mod ) y conecte cada vértice a . Mi estudiante y yo hicimos algunos experimentos al respecto, y pareció funcionar "bien". ¿Hay algún teorema o conjetura sobre esto o construcciones relacionadas?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)$

¡Gracias!

Eickmeyer y Grohe (2010) demuestran que su construcción candidata puede hacerse explícita: tome funciones hash lineales linealmente independientes h 1 , ... , h d y conecte los vértices izquierdos v con los vértices derechos h 1 ( v ) , ... , h d ( v ) . Eickmeyer y Grohe muestran que esta construcción da ( k , ϵ ) -expansores con grado izquierdo d = k ( t - 1 $d$$h_1,\dots,h_d$$v$$h_1(v),\dots,h_d(v)$$(k,\epsilon)$ , siempre que t es un número entero, el conjunto de vértices izquierdo tiene un tamaño n = q t , el conjunto de vértices derecho tiene un tamaño m = d q , y q > d es una potencia principal. Las funciones hash h 1 , ... , h d se eligen de tal manera que cualquier t de ellos son linealmente independientes.$d=k(t-1)/(2\epsilon)$$t$$n=q^t$$m=dq$$q>d$$h_1,\dots,h_d$$t$

Pensé que echar un vistazo a las encuestas / charlas de Avi Wigderson puede ayudar con su pregunta. Aquí hay diapositivas de una charla reciente: Tutorial de expansor, junio de 2010 . Las construcciones comienzan en la página 40.

En cuanto a la complejidad del espacio, creo que puede ser útil si especifica las operaciones que necesita realizar en el gráfico. Si no me equivoco, algunas construcciones permiten la operación como calcular vecindad en el espacio de registro.