3
$\begingroup$

Sperners theorem is about antichains (subsets of powerset of n elements for which no pair of elements contains the other) for example if we choose from

row 5: {a,b,c,d} row 4: {a,b,c} {a,b,d} {a,c,d} {b,c,d} row 3: {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} <-- middle row is biggest row 2: {a} {b} {c} {d} row 1: {} 

we find {a,b,c} {a,c,d} {b,d} is an antichain of size 3. It looks like the biggest antichain is the middle row {a,b} {a,c} {a,d} {b,c} {b,d} {c,d}.

To prove that is always the case take an antichain and pick all the elements from the lowest row R below the middle (flip the antichain upside down by taking the complement of every element if it's not below the middle). There must be at least |R| gaps in the above row: so push everything in the bottom row up one and it's still an antichain. Repeat until everything is in the middle row.

Any ideas where the mistake in this is?

  • 1
    @spernerslemma: the tricky part is choosing $f$ to be an injection.2012-10-09

1 Answers 1

1

If by $R$ you mean the set of element of the lowest row, then this argument can be made to work. But an argument is needed: why can $R$ be pushed around in this way? In other words, why is the "upper shadow" of $R$ least as large as $R$? (Here upper shadows are defined at https://mathoverflow.net/questions/10679/sperners-theorem-and-pushing-shadows-around/10689#10689 for example.)