An Optimal Algorithm for Triangle Counting in the Stream

We present a new algorithm for approximating the number of triangles in a graph $G$ whose edges arrive as an arbitrary order stream. If $m$ is the number of edges in $G$, $T$ the number of triangles, ${\mathrm{\Delta }}_E$ the maximum number of triangles which share a single edge, and ${\mathrm{\Delta }}_V$ the maximum number of triangles which share a single vertex, then our algorithm requires space: $$\tilde{O}(\frac{m}{T}\cdot ({\mathrm{\Delta }}_E+\sqrt{{\mathrm{\Delta }}_V}))$$ Taken with the $\Omega\left(\frac{m \Delta_E}{T}\right)$ lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the $\mathrm{\Omega }\left(\frac{m\sqrt{{\mathrm{\Delta }}_V}}{T}\right)$ lower bound of Kallaugher and Price (SODA 2017), our algorithm is optimal up to log factors, resolving the complexity of a classic problem in graph streaming.