PC Seminar: Random 2-SAT revisited

Abstract: Like many other examples of random problems, random 2-SAT exhibits a sharp satisfiability phase transition. Due to its close connection with the percolation threshold of random directed graphs, this threshold has been known since the 1990s. However, calculating the number of solutions within the satisfiable regime turned out to be challenging. In this talk we will completely verify the 'replica symmetric formula' predicted by physicists. Subsequently we will take a closer look at the typical order of fluctuations and establish a central limit theorem. The talk is based on joint work with Dimitris Achlioptas, Arnab Chatterjee, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck, Connor Riddlesden, Maurice Rolvien, Pavel Zakharov, Guangyan Zhou and Haodong Zhu.

This is a seminar in our seminar series on Probability and Combinatorics (PC).