M. Simkin

collaborators

3 papers

math.CO2025

On fractional triangle decompositions of random graphs

Ghaura Mahabaduge, Michael Simkin

We prove that with high probability $G (n, p)$ with $p \geq n^{- 4/11 + o (1)}$ admits a fractional triangle decomposition (FTD), i.e., a nonnegative weighting of its triangles such th…

math.PR2024

Lower tails for triangles inside the critical window

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We study the probability that the random graph $G (n, p)$ is triangle-free. When $p = o (n^{- 1/2})$ or $p = I ¨ (n^{- 1/2})$ the asymptotics of the logarithm of this probability are known…

cs.DS2024

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…