Welcome to Math Overflow

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 at 6:10 Harrison Brown 5,183●1●4●39

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

4

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 at 6:37

David Eppstein
3,199●6●13

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 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