How big are transitively reduced graphs?

Question

What is the largest transitively reduced acyclic connected graph on $n$ vertices, for every $n$?

How many edges $e$ does it have? How does $e$ grow as a function of $n$? Faster than $n^2/4$?

Answer 1

Since the transitively reduced graph $G$ is acyclic, there is a corresponding undirected simple graph $G'$, which can be formed by ignoring the direction of the edge. The number of edges in $G$ is same as the number of edges in $G'$.

For $G$ to be transitively reduced, a necessary condition is the $G'$ must not contain any triangles.

It is well known (Turan's/Mantel's theorem) that any simple undirected graph on $n$ vertices and more than $n^2/4$ edges has a triangle.

It is also known that the undirected graph on $n$ vertices with maximum edges and no triangles is the complete bipartite graph $K_{[n/2],[n/2]}$ (for instance check out: http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA28, exercise 4)

From your comments, it looks like you found a $G$ whose corresponding $G'$ is $K_{[n/2],[n/2]}$ and so that proves it.

Answer 2

Bipartite graph is the largest.

Proof: Suppose G is a graph, v is it's vertex. Let $L(v)$ is equal to the maximal length of a directed path, which starts in $v$. Let $L(G)=max_{v\in G} L(v)$. If $L(G)=1$, the graph is bipartite. In order to prove, that bipartite graph is the largest, I will prove, that for any graph $G$ such that $L(G)>1$ there exists graph $H$ with the same number of vertices and edges, such that $L(G)>L(H)$.

Note, that any vertex with $L(v)=0$ has only inbound connections. This connections are from vertices w with $L(w)=1$. We will do graph $H$ in two steps.
Step 1. Remove all vertices with $L(v)=0$, and edges to them. Note that $L(G)$ has been decreased. Step 2. Add all the vertices, removed on step 1. Add edges, removed on step 1, but reverse their direction. Call the new graph $H$. Note, that it has the same number of vertices and edges and $L(H) < L(G)$.