Mathematicians have spent years trying to find a Hamiltonian cycle in graphs. In 2023, Benny Sudakov and his colleagues found a breakthrough, proving that expanders graphs always contain such cycles. Expander graphs behave like random graphs but do not require randomness, making them highly interconnected and efficient for various applications like online social networks and improving algorithms. By combining the concepts of sorting networks and Pósa rotation, Sudakov’s team was able to prove their conjecture and establish a fundamental connection with computer science. This breakthrough opens new possibilities for future research and practical applications.
https://www.quantamagazine.org/in-highly-connected-networks-theres-always-a-loop-20240607/