Welcome to MathOverflow

Question

2

I feel a little embarrassed to be asking this question here, since I think it should be much easier than I'm making it, but here goes:

Given a finite poset P, does there necessarily exist some chain that intersects every maximal antichain? (Note: By maximal antichain, I mean that there's no antichain strictly containing our antichain.) The answer seems to be "no" for infinite posets, but I can't find either a reference or a proof when it comes to finite posets.

Sorry if this is an undergrad-homework-level problem...

flag	asked Oct 20 2009 at 6:10 Harrison Brown 7,821●1●28●77

1

On the other hand, there does exists a chain that intersects every antichain of maximum size. – Richard Stanley Feb 5 2011 at 4:00

David Eppstein · Accepted Answer · 2009-10-20 06:37:33Z UTC

5

No.

Consider the poset of subsets of {x,y,z} under inclusion. The maximal chain Ø, {x}, {x,y}, {x, y, z} does not intersect every maximal antichain: it misses the maximal antichain {y}, {x,z}. By symmetry every other maximal chain also misses some maximal antichain.

answered Oct 20 2009 at 6:37

David Eppstein
9,233●1●21●41

Oh, duh! I think I actually had this counterexample myself the other day, but didn't realize that it was important. Hmm, okay... I need to think about this some more, then. Thanks! – Harrison Brown Oct 20 2009 at 6:41

Chains intersecting antichains in finite posets

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.