Non-existence probabilities and lower tails in the critical regime via Belief Propagation

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of…