Como praticamente construir gráficos de expansão regulares?

Eu preciso construir um gráfico de expansão d-regular para alguns pequenos d fixos (como 3 ou 4) de n vértices.

Qual é o método mais fácil de fazer isso na prática? Construindo um gráfico d-regular aleatório, que provou ser um expansor?

Também li sobre construções Margulis e gráficos Ramanujan que são expansores e uma construção usando um produto em zig-zag. A Wikipedia fornece uma visão geral agradável, mas muito curta: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Mas qual método eu escolho na prática?

Para mim, esses métodos parecem todos muito complicados de implementar e, em particular, de entender e talvez bastante específicos. Não existem métodos mais fáceis, talvez baseados em permutações, para gerar praticamente uma sequência de gráficos expansores regulares d?

Talvez seja mais fácil construir gráficos expansores bipartidos d-regulares?

Também tenho outra pergunta: e as famílias de expansores D-regulares ruins? Essa noção faz sentido? Pode-se construir uma família de gráficos d-regulares (que obviamente estão conectados) o mais ruim possível no sentido de um expansor?

Desde já, obrigado.

graph-theory combinatorics cryptography discrete-mathematics expanders user2145167
fonte

Existem construções explícitas mais fáceis do que as listadas, mas gráficos aleatórios devem fazer o truque e ter melhores parâmetros.

Yuval Filmus

Você pode dar nomes ou referências às construções? Por parâmetros melhores, você quer dizer uma expansão melhor (de ponta), eu acho?

user2145167

András deu o exemplo que eu tinha em mente, mas, em geral, gráficos aleatórios são (quase sempre) melhores do que construções explícitas. A expansão da borda não é apenas maior, qualquer outra propriedade semelhante que seja útil para o seu algoritmo é provavelmente automaticamente satisfeita por gráficos aleatórios.

Yuval Filmus

Ok, para o grau 3, o exemplo da András ou os gráficos aleatórios parecem bons o suficiente para a minha aplicação. Seria interessante, em particular no que diz respeito aos gráficos aleatórios, construir uma família de gráficos de 3 reg que não seja um expansor. Mas isso é provavelmente muito difícil ou não é possível?

usar o seguinte comando

Faça uma união de

s. Se você deseja um gráfico conectado, remova uma aresta de cada

(formando um gráfico conhecido como gráfico de diamante) e conecte-os em um ciclo.

K_{4}

$K_4$

K_{4}

$K_4$

Yuval Filmus

Respostas:

Se você não se importa com gráficos com auto-loops, provavelmente a família de expansores "mais fácil" é essa, fornecendo expansores três vezes regulares.

Comece com algum número primo e construa vértices numerados de a . Para cada vértice , conecte a e , módulo . Conecte também ao vértice exclusivo modo que $p$ $0$ $p-1$ $u \ne 0$ $u$ $u-1$ $u+1$ $p$ $u$ $v$ . $uv \equiv 1 \mod p$

Como exemplo, o gráfico de 7 vértices na família é um ciclo de 7 com vértices numerados sequencialmente ao redor do ciclo; existem auto-loops em , e ; finalmente, há acordes unindo e e e . $6$ $0$ $1$ $3$ $5$ $2$ $4$

Consulte /mathpro/124708/an-expander-graph para mais discussões e referências. Existem muitos indicadores mais detalhados pesquisando no "expansor" em CSTheory , Math.SE e MO .

Como Yuval Filmus aponta, é provável que a construção aleatória dê melhores resultados em geral, mas é claro que pode não produzir um expansor (especialmente para gráficos pequenos).

András Salamon
fonte

Obrigado pela observação. Eu já havia pesquisado expansores antes em outros sites, mas não no MO, realmente parece haver mais resultados.

usar o seguinte comando

Dado que um gráfico regular aleatório é um expansor whp (siga a referência fornecida na documentação do código MATLAB vinculada abaixo), uma vez eu usei o seguinte:

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

Hoda
fonte