Eu preciso construir um gráfico expansor d-regular para alguns pequenos d fixos (como 3 ou 4) de n vértices.
O que é o método mais fácil de fazer isso na prática? Construir um gráfico d-regular aleatório, comprovadamente a.a.s. um expansor?
Também li sobre as construções de Margulis e gráficos Ramanujan que são expansores e uma construção usando um produto em zigue-zague. A Wikipedia oferece uma visão geral agradável, mas muito curta: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 Mas qual método devo escolher 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 ou algo assim, para gerar praticamente uma sequência de gráficos expansores d-regulares?
É talvez mais fácil construir gráficos expansores bipartidos d-regulares?
Eu também tenho outra pergunta: e as famílias de expansores d-regulares ruins? Essa noção faz sentido? É possível construir uma família de gráficos d-regulares (que estão naturalmente conectados) que seja o pior possível em o sentido de um expansor?
Agradecemos antecipadamente.
Comentários
- Existem construções explícitas mais fáceis do que as que você listou , mas os gráficos aleatórios devem resolver o problema e ter parâmetros melhores.
- Você pode dar nomes ou referências às construções? Por melhores parâmetros, você quer dizer uma melhor expansão (borda), eu acho?
- 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. Não apenas a expansão da borda é maior, a y outra propriedade semelhante que é útil para o seu algoritmo provavelmente é satisfeita automaticamente por gráficos aleatórios.
- Ok, para o grau 3, o exemplo de Andr á s ou os gráficos aleatórios parece ser bom 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 grafos 3-reg que não seja um expansor. Mas isso é provavelmente muito difícil ou impossível?
- Faça uma união de $ K_4 $ s. Se você quiser um gráfico conectado, remova uma aresta de cada $ K_4 $ (formando um gráfico conhecido como gráfico de diamante) e conecte-os em um ciclo.
Resposta
Se você não se importa com gráficos com auto-loops, a família de expansores “mais fácil” é provavelmente esta, dando expansores 3-regulares.
Comece com algum número primo $ p $ e construa vértices numerados de $ 0 $ a $ p-1 $. Para cada vértice $ u \ ne 0 $, conecte $ u $ a $ u-1 $ e $ u + 1 $ , módulo $ p $. Também conecte $ u $ ao único vértice $ v $ de modo que $ uv \ equiv 1 \ mod p $.
Como exemplo, o gráfico de 7 vértices na família é um 7-ciclo com vértices numerados sequencialmente ao redor do ciclo; há auto-loops em $ 6 $, $ 0 $ e $ 1 $; finalmente, há acordes unindo $ 3 $ e $ 5 $ e $ 2 $ e $ 4 $.
Veja https://mathoverflow.net/questions/124708/an-expander-graph para maiores discussões e referências. Há muitas dicas mais detalhadas pesquisando em ” expansor “em CSTh eory , Math.SE e MO .
Como Yuval Filmus aponta, a construção aleatória provavelmente dará melhores resultados em geral, mas é claro que pode não render um expansor (especialmente para pequenos gráficos).
Comentários
- Obrigado pelo comentário. Eu tinha pesquisado por expansores antes em outros sites, mas não no MO, realmente parece haver mais resultados.
Resposta
Dado um gráfico regular aleatório é um expansor whp (siga a referência fornecida na documentação do código MATLAB com link abaixo), uma vez usei o seguinte: