Sampling and counting triangle-free graphs near the critical density

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We study the following combinatorial counting and sampling problems: can we efficiently sample from the Erdős-Rényi random graph $G(n,p)$ conditioned on triangle-freeness? Can we e…