MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

If a partial order on $n$ elements has $m$ incomparable pairs, then its covering graph (aka Hasse diagram aka transitive reduction, the graph of pairs of elements that are comparable but are not the endpoints of a chain of three or more elements) can only have $O(n+m)$ edges, and this is tight — see for a proof.

I tried doing some literature searches but the relevant keywords are broad and the topic itself is rather specific, so I didn't find it. (I did find some papers on cover-incomparability graphs, the unions of the covering graph and the incomparability graph.) Is this known, and if so, can someone provide a reference please?

share|cite|improve this question
You might try: András Frank, On chain and antichain families of a partially ordered set, Journal of Combinatorial Theory, Series B, Volume 29, Issue 2, October 1980, Pages 176-184, ISSN 0095-8956, 10.1016/0095-8956(80)90079-9. ( The result is not exactly what you are looking for, but it seems to me that what you ask about is directly implied by it. – Chad Musick Oct 26 '11 at 6:45
Thanks for the reference. Maybe I'm being slow this morning but I don't see the implication clearly, though. Which proposition in Frank's paper is the one that directly implies this one? – David Eppstein Oct 26 '11 at 18:15
Looking at this again today, it doesn't seem all that direct to me. I think I see how to construct the argument from Frank's Theorem 3, but it requires a fair amount of care. – Chad Musick Oct 26 '11 at 23:47

Your Answer


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

Browse other questions tagged or ask your own question.