MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I need to find the maximum number of topological sorts on Direct Acyclic Graph of N-order. I've checked by running Depth first search algorithm on various Direct Acyclic graphs, and it looks like it is the size of Depth first search algorithm forest that created after running DFS on the graph. Or maybe I completely wrong or miss something. I also need to prove it. Any help will be appreciated. Thank you.

share|cite|improve this question
Please spell out your TLAs. I take it that DAG is directed acyclic graph and DFS is depth-first search. – Paul Taylor May 19 '13 at 18:48
Yes this is true. – conex May 19 '13 at 18:49
And for the record: TLA = three-letter acronym – André Henriques May 19 '13 at 19:09
Yes, sorry for wrong spelling, it's my first question here :) – conex May 19 '13 at 19:11
Now I can add "DAG graph" to my pet peeve list that includes such repetitions as "ICBM missiles", "AC current", "ATM machines", and "PIN numbers" (the last of which are occasionally called "personal PINs"). – Andreas Blass May 20 '13 at 17:36

This should be a comment, but I don't have the reputation.

Unless you specify more information about your graph, there is likely to be no good answer. To phrase your question in a more Mathoverflowese manner, you are looking for the number of linear extensions of a poset. This is known to be difficult in general, but formulas are known for some special cases.

share|cite|improve this answer

Your Answer


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.