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$.

1. $\Delta = \frac{1}{6} \tr(A^3)$.
2. $\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.¹

Worst-Case Optimal Joins

• AGM bound?
• Generic Join