{"id":"arxiv/2604.04652","url":"https://arxiv.org/abs/2604.04652","tags":["math.CO","math.PR"],"score":0,"title":"Non-existence probabilities and lower tails in the critical regime via Belief Propagation","domain":"math.CO","source":"arxiv","authors":["Matthew Jenssen","Will Perkins","Aditya Potukuchi","Michael Simkin"],"reviews":0,"subject":"math.CO","summary":"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 parameters in the `critical regime' between the regime amenable to hypergraph container methods and that amenable to Janson's inequality. Examples include lower tails and non-existence probabilities for subgraphs of random graphs and for $k$-term arithmetic progressions in random sets of integers. Our methods apply in the general framework of estimating the probability that a $p$-random subset of vertices in a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-06","reactions":{}}