1
$\begingroup$

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: enter image description here

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.

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.