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

Matthew Jenssen; Will Perkins; Aditya Potukuchi; Michael Simkin

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

Matthew Jenssen, Will Perkins, Aditya Potukuchi, Michael Simkin

arXivarxiv/2604.04652Apr 6, 2026math.COscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.04652
curl -X POST /api/v1/records/arxiv/2604.04652/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.04652/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'