¿Cuántos bordes garantiza un expansor?

Question

Los gráficos completos son buenos expansores. Si se eliminan algunas aristas de un gráfico completo, se obtiene un buen expansor. ¿Cuál es la proporción de aristas que hay que eliminar para que el grafo sea un mal expansor? ¿O hay algún resultado probabilístico?

Answer 1

Depende de su definición de "expansión", pero la respuesta siempre será eliminar todos los bordes a través de algún corte, y debe hacerlo lo más pequeño posible. Así, por ejemplo, si insiste en que todos los conjuntos de tamaño $t$ que tiene la expansión (y no para cualquier conjunto más pequeño), entonces usted necesita para eliminar $t(n-t)$ bordes para destruir la expansión. No hay mucha diferencia si dices que sólo quieres destruir la "buena" expansión en lugar de cualquier expansión.

Probabilísticamente, las cosas son muy diferentes. El gráfico aleatorio es un buen expansor para las $p$ , de nuevo lo que $p$ depende de su definición de expansión; si insiste en todos los conjuntos de tamaños entre $\varepsilon n$ y $(1-\varepsilon)n$ tener una buena expansión (para algunos $\varepsilon>0$ fijo) entonces $p$ puede ser del orden de $\log n/n$ .