Cortes extremales de grafos aleatorios dispersos

Para los grafos aleatorios de Erdős–Rényi con grado promedio, y un grafo -regular aleatorio uniformemente en n vértices, probamos que con alta probabilidad el tamaño tanto del Max-Cut como de la bisección máxima son n (4+P*{4}+o () ) +o (n) mientras que el tamaño de la bisección mínima es n (4-P*{4}+o () ) +o (n). Nuestra derivación relaciona la energía libre del modelo de Ising antiferromagnético en tales grafos con la del modelo de Sherrington–Kirkpatrick, siendo P*0. 7632 la energía del estado fundamental del último, expresada analíticamente a través de la fórmula de Parisi.