# Maximizing edges in directed acyclic graph

Question: What is the maximum number of edges in a non-transitive directed acyclic graph on $n$ vertices?

Here nontransitive means, if there is an edge between $A$ and $B$, and an edge between $B$ and $C$, then there cannot be an edge between $A$ and $C$.

For example, see the following image: Easier(?) question: What is the asymptotic behavior of the maximum number of edges in the limit as the number of vertices $n \rightarrow \infty$? Eg., $\#\mathrm{edges}=O(?)$.

Comment: Someone else asked this question in the computer science stack exchange, but the question got deleted. The question piqued my curiosity but I can't figure it out, which is why I'm reposting here.

## 1 Answer

The answer is $\lfloor\frac{n^2}4\rfloor$.

First, your graph can't have any triangles; neither of the two ways to orient a triangle satisfies your requirements.

By Turán's theorem, or rather the special case known as Mantel's theorem, a triangle-free (simple) graph on $n$ vertices has at most $\lfloor\frac{n^2}4\rfloor$ edges. The maximum is attained by the complete bipartite graph $K_{\lfloor\frac n2\rfloor,\lceil\frac n2\rceil}$. If all the edges are directed from one partite set to the other, there are no cycles and everything is fine.

• Ahh perfect! I was thinking about the directed bipartite graph as well, but doubted it's optimality. – Nick Alger Feb 2 '14 at 3:57