Expansores desbalanceados "industriais" com eficiência de espaço

Estou procurando expansores desequilibrados que sejam "bons" e "com eficiência de espaço". Especificamente, um gráfico regular esquerdo bipartido , | Um | = n , | B | = m , com o grau esquerdo d, é um expansor ( k , ϵ ) se, para qualquer S ⊂ A de tamanho no máximo k , o número de vizinhos distintos de S em B for pelo menos ( 1 $G=(A,B,E)$$|A|=n$$|B|=m$$d$$(k,\epsilon)$$S \subset A$$k$$S$$B$. Sabe-se que o método probabilístico produz um gráfico com d = O ( log ( n / k ) / ϵ ) e m = O ( k log ( n / k ) / ϵ 2 ) . No entanto, é preciso O ( n d $(1-\epsilon)d|S|$$d=O(\log (n/k)/\epsilon)$$m=O(k \log(n/k)/\epsilon^2)$$O(n d)$espaço para armazenar esse gráfico. Também é necessário acessar esse armazenamento ao fazer qualquer coisa com o gráfico, que também pode custar. Idealmente, alguém gostaria de uma construção explícita. No entanto, tanto quanto eu sei, construções conhecidas atingem parâmetros que ainda estão um pouco longe do acima (pelo menos de maneira provável).

Minha pergunta: existem outras construções, possivelmente não explícitas, que atingem limites "mais próximos" dos anteriores, mas usam "significativamente menos" que o espaço ?$O(nd)$

Estou procurando respostas em qualquer uma dessas três categorias: (a) teoremas (b) conjecturas (c) observações e "histórias de guerra" como "fizemos isso e parecia que funcionou (mais ou menos)". Ou seja, expansores "industriais" são bons. Eu prefiro (a) sobre (b) e (b) sobre (c), mas mendigos não podem escolher :)

Aqui está um exemplo de uma construção do tipo (c). Tome funções aleatórias lineares de hash h i : [ n ] → [ m ] (mod m ) e conecte cada vértice i a h 1 ( i ) … h d ( i ) . Eu e meu aluno fizemos alguns experimentos e pareceu funcionar "bem". Existem teoremas ou conjecturas sobre esta ou construções relacionadas?$d$$h_i: [n] \to [m]$$m$$i$$h_1(i) \ldots h_d(i)$

Obrigado!

Eickmeyer e Grohe (2010) provar que a sua construção candidato pode ser explicitado: Tomada tanto linearmente independentes funções hash linear h 1 , ... , h d e vértices esquerdo de conexão v com vértices certas h 1 ( v ) , ... , h d ( v ) . Eickmeyer e Grohe mostram que essa construção dá ( k , ϵ ) -expansores com grau esquerdo d = k ( t - 1 $d$$h_1,\dots,h_d$$v$$h_1(v),\dots,h_d(v)$$(k,\epsilon)$ , sempre que t é um número inteiro, o conjunto de vértices esquerdo tem tamanho n = q t , o conjunto de vértices direito tem tamanho m = d q e q > d é uma potência primária. As funções de hash h 1 , … , h d são escolhidas de forma que qualquer t deles seja linearmente independente.$d=k(t-1)/(2\epsilon)$$t$$n=q^t$$m=dq$$q>d$$h_1,\dots,h_d$$t$

Eu pensei que dar uma olhada nas pesquisas / palestras de Avi Wigderson pode ajudar com sua pergunta. Aqui estão os slides de uma palestra recente: Tutorial do Expansor, junho de 2010 . As construções começam na página 40.

Em relação à complexidade do espaço, acho que pode ser útil se você especificar as operações que precisa executar no gráfico. Se não me engano, algumas construções permitem operações como a vizinhança de computação no espaço de logs.