Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Does large mean "many edges"? –  Rasmus Sep 30 '10 at 11:21
    
Yes, I mean, with the most edges. It just occurred to me that you can always split the vertices into two equal parts and connect each vertex in one part with each vertex in the other (creating a bipartite graph). I've edited the questions accordingly. –  reinierpost Sep 30 '10 at 11:27
    
At the moment I don't see a larger graph either. –  Rasmus Sep 30 '10 at 11:33
    
What exactly do you mean by a transitively reduced graph? –  Aryabhata Sep 30 '10 at 14:29
    

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
Perfect. Thank you! –  reinierpost Oct 1 '10 at 7:54

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)$.

share|improve this answer
    
Very insightful, thank you! This proves that bipartite graphs are the largest (which is what I wanted to know) but not that there aren't any other largest graphs. –  reinierpost Oct 1 '10 at 8:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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