En el paso de reducción de grados de la prueba de Dinur, el gráfico de entrada se transforma en un gráfico G ' reemplazando cada vértice v ∈ V ( G ) por un conjunto de vértices, c l o u d ( v ) , de modo que | c l o u d ( v ) | = d e g r e e G ( v ) , e imponiendo un gráfico expansor de grado d en c l o para todos v ∈ V ( G ) . Esto hace que G ' a d + 1 sea un gráfico regular, y la construcción asegura que la brecha se reduzca solo en un factor constante. Me preguntaba qué pasaría si impusiéramos un ciclo en cada nube. Traté de limitar la caída en la brecha, pero no pude hacerlo. Entonces, ¿la prueba se rompe en este paso?
fuente