9
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Chad Musick
    Commented Oct 26, 2011 at 6:45
  • $\begingroup$ 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? $\endgroup$
    – David Eppstein
    Commented Oct 26, 2011 at 18:15
  • $\begingroup$ 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. $\endgroup$
    – Chad Musick
    Commented Oct 26, 2011 at 23:47

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .