Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 http://11011110.livejournal.com/233793.html 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|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. (sciencedirect.com/science/article/pii/0095895680900799) 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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.