What is the maximum number of directed triangles contained in an oriented complete graph?

Question

Assume there are $n$ vertices, every pair of vertices is connected by an arrow. Then how many directed triangles (for example{ $(1,2),(2,3),(3,1)$})does a graph of this type contain at most?

Answer 1

This kind of digraph is called a tournament. (The idea is a round-robin tournament, with an edge directed from the winner of a game to the loser.) So, you are asking for the maximum number of (directed) $3$-cycles in a tournament.

This problem was solved in "On the Method of Paired Comparisons," by M.G. Kendall and B. Babington Smith, Biometrika, Vol. 31, No. 3/4 (Mar., 1940), pp. 324-345. The answer is $$\cases{\frac{n^3-n}{24},&$n$ odd\\\frac{n^3-4n}{24},&$n$ even}$$

The paper is available on JSTOR

Answer 2

Call triangles that are not directed triangles transitive ones. A transitive triangle with arcs $(a,b)$, $(a,c)$, $(b,c)$ is said to start at $a$ and end at $c$.

For a vertex $v$ with out-degree $k$, there are $\binom k2$ transitive triangles starting at $v$ (formed by $v$ and any two vertices with an arc from $v$) and $\binom{n-k-1}{2}$ transitive triangles ending at $v$ (formed by $v$ and any two triangles with an arc to $v$). The sum $\binom k2 + \binom{n-k-1}{2}$ is minimized when $k = \lfloor \frac{n-1}{2}\rfloor$ or $k = \lceil \frac{n-1}{2} \rceil$.

If we add up this number over all vertices, we get a number that's at least $$ n \binom{\lfloor \frac{n-1}{2}\rfloor}{2} + n \binom{\lceil \frac{n-1}{2} \rceil}{2} $$ and this counts each transitive triangle twice: once for the vertex where it starts, and once for the vertex where it ends. So the total number of transitive triangles is at least half of the value above. This is achieved precisely when every out-degree is either $\lfloor \frac{n-1}{2}\rfloor$ or $\lceil \frac{n-1}{2} \rceil$, and this is not hard to do for any value of $n$.

This tells us the minimum number of transitive triangles, and so the maximum number of directed triangles is just however many are left: it is at most $$ \binom n3 - \frac12\left(n \binom{\lfloor \frac{n-1}{2}\rfloor}{2} + n \binom{\lceil \frac{n-1}{2} \rceil}{2}\right) $$ which is roughly $\frac14 \binom n3$.