Consider a directed acyclic graph $G(V,E)$ such that no three vertices satisfy the transitivity property. Formally, $$\forall u,v,w \in V, (u,v) \in E \wedge (v,w) \in E \Rightarrow (u,w) \not \in E$$
What is the maximum number of edges such a DAG can have, if $|V|=n$?
E.g. : if $|V|=3$, maximum edges can be 2. If vertex set be $V=\{A,B,C\}$, then $E=\{(A,B), (B,C)\}$ is one possible edge set of size 2.
PS : Encountered while solving the problem http://www.spoj.com/problems/GHOSTS. I need it to complete the proof of complexity of my algorithm.
Best Answer
Given an intransitive DAG, we can ignore the edge directions to give an undirected triangle-free graph (any triangle in the DAG would either imply a cycle or a transitive triple, both of which are disallowed).
Conversely, given a triangle-free undirected graph, we can orient the edges acyclically (draw the nodes in a horizontal line, and orient the edges left-to-right) to give an intransitive DAG.
So we're equivalently after the maximum number of edges in a triangle-free undirected graph on $n$ vertices. This is given by Turan's Theorem as $\lfloor n^2/4 \rfloor$.