Necesito construir un gráfico expansor d-regular para algunos pequeños d fijos (como 3 o 4) de n vértices.
¿Qué Cuál es el método más fácil para hacer esto en la práctica? Construir un gráfico d-regular aleatorio, que se ha demostrado que es a.a.s. ¿un expansor?
También leí sobre las construcciones de Margulis y los gráficos de Ramanujan que son expansores y una construcción que utiliza un producto en zig-zag. Wikipedia ofrece una descripción general agradable pero muy breve: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 ¿Pero qué método elijo en la práctica?
Para mí, todos estos métodos parecen muy complicados de implementar y, en particular, de comprender y tal vez bastante específicos. ¿No hay métodos más fáciles, quizás basados en permutaciones o algo así, para generar prácticamente una secuencia de gráficos expansores d-regulares?
¿Es quizás más fácil construir gráficos expansores bipartitos d-regulares?
También tengo otra pregunta: ¿qué pasa con las familias de expansores d-regulares malos? ¿Tiene sentido tal noción? ¿Se puede construir una familia de gráficos d-regulares (que, por supuesto, están conectados) que sea lo más malo posible en el sentido de un expansor?
Gracias de antemano.
Comentarios
- Hay construcciones explícitas más fáciles que las que enumeraste , pero las gráficas aleatorias deberían funcionar y tener mejores parámetros.
- ¿Puede dar nombres o referencias de las construcciones? Por mejores parámetros, ¿quiere decir una mejor expansión (borde), supongo?
- Andr á s dio el ejemplo que tenía en mente, pero en general, los gráficos aleatorios son (casi siempre) mejores que las construcciones explícitas. No solo la expansión del borde es más grande, un y otra propiedad similar que es útil para su algoritmo probablemente se satisfaga automáticamente mediante gráficos aleatorios.
- Ok, para el grado 3, el ejemplo de Andr á s o los gráficos aleatorios parece ser lo suficientemente bueno para mi aplicación. Sería interesante, en particular con respecto a los gráficos aleatorios, construir una familia de gráficos de 3 registros que no sea un expansor. ¿Pero esto es probablemente muy difícil o imposible?
- Tome una unión de $ K_4 $ s. Si desea un gráfico conectado, elimine un borde de cada $ K_4 $ (formando un gráfico conocido como gráfico de diamante) y conéctelos en un ciclo.
Respuesta
Si no le importan los gráficos con bucles automáticos, la familia de expansores «más fácil» es probablemente esta, que ofrece expansores que son 3 regulares.
Comienza con un número primo $ p $ y construye vértices numerados $ 0 $ a $ p-1 $. Para cada vértice $ u \ ne 0 $, conecta $ u $ a $ u-1 $ y $ u + 1 $ , módulo $ p $. También conecte $ u $ al vértice único $ v $ de manera que $ uv \ equiv 1 \ mod p $.
Como ejemplo, el gráfico de 7 vértices de la familia es un ciclo de 7 con vértices numerados secuencialmente alrededor del ciclo; hay ciclos propios en $ 6 $, $ 0 $ y $ 1 $; finalmente, hay acordes que unen $ 3 $ y $ 5 $, y $ 2 $ y $ 4 $.
Consulte https://mathoverflow.net/questions/124708/an-expander-graph para obtener más información y referencias. Hay muchas sugerencias más detalladas si busca en » expansor «en CSTh eory , Math.SE y MO .
Como señala Yuval Filmus, es probable que la construcción aleatoria dé mejores resultados en general, pero, por supuesto, puede que no produzca un expansor (especialmente para gráficos pequeños).
Comentarios
Respuesta
Dado un gráfico regular aleatorio es un expansor whp (siga la referencia dada en la documentación del código MATLAB vinculado a continuación), una vez usé lo siguiente: