6 papers
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…
Optimal detection of planted stars via a random energy model
Ijay Narang, Will Perkins, Timothy L. H. Wee
We study the problem of detecting a planted star in the Erd{Å}s--R{é}nyi random graph , formulated as a hypothesis test. We determine the scaling window for critical dete…
On the chromatic number of random triangle-free graphs
Clayton Mizgerd, Will Perkins, Yuzhou Wang
We study the chromatic number of typical triangle-free graphs with edges and establish the width of the scaling window for the transitions…
On the evolution of structure in triangle-free graphs
Matthew Jenssen, Will Perkins, Aditya Potukuchi
We study the typical structure and the number of triangle-free graphs with vertices and edges where is large enough so that a typical triangle-free graph has a cut cont…
The typical structure of dense claw-free graphs
Will Perkins, Sam van der Poel
We analyze the asymptotic number and typical structure of claw-free graphs at constant edge densities. The first of our main results is a formula for the asymptotics of the logarit…
Lower tails for triangles inside the critical window
Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
We study the probability that the random graph is triangle-free. When or the asymptotics of the logarithm of this probability are known…