This article is under construction!
Introduction
In this article, we are interested in counting triangles. More precisely, given an undirected graph $G = (V, E)$, we are interested in all triples $(i, j, k) \in V^3$ such that $(i, j), (j, k), (k, i) \in E$. Technically, we only care about the triples up to isomorphism — any permutation of the vertices in a triangle is an graph automorphism.
Let $\Delta$ be the number of triangles in $G$ up to isomorphism, and let $T$ be the set of $(i,j,k)$ as described above. Note that $\Delta = T/6$. In what follows, we will be precise about overcounting triangles when giving explicit expressions for $\Delta$, but we will ignore the (constant) factors when discussing asymptotic quantities.
Triangle Asymptotics
This is the main question: given $G$ with $m = E$ edges, how many triangles can it have?
We will show that show that $\Delta = O(m^{3/2})$. First, define \[A(u) = \{v \in V \mid v \in N(u) \text{ and }\deg(v)\geq\deg(u)\}.\] Then, for any triangle $(i, j, k)$ ordered such that $\deg(i) \leq \deg(j) \leq \deg(k)$, we have $k \in A(i) \cap A(j)$. It follows that \[T' = \bigcup_{(i,j) \in E} A(i) \cap A(j) \subseteq T,\quad\text{and}\quad \Delta \leq T'.\]
Now, call vertices with at least $\sqrt{m}$ degree heavy, and otherwise light. Notice that there are at most $\sqrt{m}$ heavy vertices, otherwise we'd end up with more than $m$ edges.
Hence for every intersection $A(i) \cap A(j)$:
 if $i$ is light, then $A(i) \leq N(i) < \sqrt{m}$ so $A(i) \cap A(j) < \sqrt{m}$;
 otherwise if $i$ is heavy, then $A(i) \leq \sqrt{m}$ since every $v\in A(i)$ must also be heavy, so $A(i) \cap A(j) \leq \sqrt{m}$.
Together, it follows that $T' \leq \sum_{(i,j)\in E} \sqrt{m} = m^{3/2}$, which completes the proof.
Multiplying Matrices
Let $A$ be the $n\times n$ adjacency matrix of $G$. Then $A^k_{i,j} = 1$ iff there's a path of length $k$ from $i$ to $j$.
 $\Delta = \frac{1}{6} \tr(A^3)$.
 $\Delta = \frac{1}{2} \sum_{i,j} C_{i,j}$, where $C_{i,j} = \sum_{k} A_{i,j} A_{i,k} A_{k, j} = A \odot A^2$.
In both cases, evaluating the intermediate product $A^2$ will incur $O(m^2)$ work.^{1}
WorstCase Optimal Joins
 AGM bound?
 Generic Join

Consider the case of the complete graph on $n$ vertices. ↩