2Sperner systems

III Combinatorics



2 Sperner systems
In the next few chapters, we are going to try to understand the power set
P
(
X
)
of a set. One particularly important structure of
P
(
X
) is that it is a graded
poset. A lot of the questions we ask can be formulated for arbitrary (graded)
posets, but often we will only answer them for power sets, since that is what we
are interested in.
Definition
(Chain)
.
A subset
C S
of a poset is a chain if any two of its
elements are comparable.
Definition
(Anti-chain)
.
A subset
A S
is an anti-chain if no two of its
elements are comparable.
Given a set
X
, the power set
P
(
X
) of
X
can be viewed as a Boolean lattice.
This is a poset by saying A < B if A ( B.
In general, there are many questions we can ask about a poset
P
. For
example, we may ask what is the largest possible of an anti-chain in
P
. While
this is quite hard in general, we may be able to produce answers if we impose
some extra structure on our posets. One particularly useful notion is that of a
graded poset.
Definition
(Graded poset)
.
We say
P
= (
S, <
) is a graded poset if we can write
S as a disjoint union
S =
n
a
i=0
S
i
such that
S
i
is an anti-chain; and
x < y
iff there exists elements
x
=
z
i
< z
i+1
< ··· < z
j
=
y
such that
z
h
S
h
.
Example. If X is a set, P(X) is an anti-chain with X
i
= X
(i)
.
If we want to obtain the largest anti-chain as possible, then we might try
X
i
with
i
=
b
n
2
c
. But is this actually the largest possible? Or can we construct
some funny-looking anti-chain that is even larger? Sperner says no.
Theorem
(Sperner, 1928)
.
For
|X|
=
n
, the maximal size of an antichain in
P(X) is
n
bn/2c
, witnessed by X
bn/2c
.
Proof.
If
C
is a chain and
A
is an antichain, then
|A C|
1. So it suffices to
partition P(X) into
m = max
k
n
k
=
n
bn/2c
=
n
dn/2e
many chains.
We can do so using the injections constructed at the end of the previous
section. For
i b
n
2
c
, we can construct injections
f
i
:
X
i1
X
i
such that
A f
i
(
A
) for all
A
. By chaining these together, we get
m
chains ending in
X
b
n
2
c
.
Similarly, we can partition
X
(≤bn/2c)
into
m
chains with each chain ending
in X
(bn/2c)
. Then glue them together.
Another way to prove this result is to provide an alternative measure on how
large an antichain can be, and this gives a stronger result.
Theorem
(LYM inequality)
.
Let
A
be an antichain in
P
(
X
) with
|X|
=
n
.
Then
n
X
r=0
|A X
(r)
|
n
r
1.
In particular, |A| max
r
n
r
=
n
bn/2c
, as we already know.
Proof.
A chain
C
0
C
1
··· C
m
is maximal if it has
n
+ 1 elements.
Moreover, there are
n
! maximal chains, since we start with the empty set and
then, given
C
i
, we produce
C
i+1
by picking one unused element and adding it
to C
i
.
For every maximal chain
C
, we have
|C A|
1. Moreover, every set of
k
elements appears in
k
!(
n k
)! maximal chains, by a similar counting argument
as above. So
X
A∈A
|A|!(n |A|)! n!.
Then the result follows.
There are analogous results for posets more general than just
P
(
X
). To
formulate these results, we must introduce the following new terminology.
Definition (Shadow). Given A S
i
, the shadow at level i 1 is
A = {x S
i1
: x < y for some y A}.
Definition
(Downward-expanding poset)
.
A graded poset
P
= (
S, <
) is said to
be downward-expanding if
|A|
|S
i1
|
|A|
|S
i
|
for all A A
i
.
We similarly define upward-expanding, and say a poset is expanding if it is
upward or downward expanding.
Definition (Weight). The weight of a set A S is
w(A) =
n
X
i=0
|A S
i
|
|S
i
|
.
The theorem is that the LYM inequality holds in general for any downward
expanding posets.
Theorem.
If
P
is downward expanding and
A
is an anti-chain, then
w
(
A
)
1.
In particular, |A| max
i
|S
i
|.
Since each S
i
is an anti-chain, the largest anti-chain has size max
i
|S
i
|.
Proof. We define the span of A to be
span A = max
A
j
6=
j min
A
i
6=
i.
We do induction on span A.
If
span A
= 0, then we are done. Otherwise, let
h
i
=
max
A
j
6=0
j
, and set
B
h1
= A
h
. Then since A is an anti-chain, we know A
h1
B
h1
= .
We set
A
0
=
A\A
h
B
h1
. This is then another anti-chain, by the transitivity
of <. We then have
w(A) = w(A
0
) + w(A
h
) w(B
h1
) w(A
0
) 1,
where the first inequality uses the downward-expanding hypothesis and the
second is the induction hypothesis.
We may want to mimic our other proof of the fact that the largest size of an
antichain in P(X) is
n
bn/2c
. This requires the notion of a regular poset.
Definition
(Regular poset)
.
We say a graded poset (
S, <
) is regular if for each
i
, there exists
r
i
, s
i
such that if
x A
i
, then
x
dominates
r
i
elements at level
i 1, and is dominated by s
i
elements at level i + 1.
Proposition. An anti-chain in a regular poset has weight 1.
Proof.
Let
M
be the number of maximal chains of length (
n
+ 1), and for each
x S
k
, let m(x) be the number of maximal chains through x. Then
m(x) =
k
Y
i=1
r
i
n1
Y
i=k
s
i
.
So if x, y S
i
, then m(x) = m(y).
Now since every maximal chain passes through a unique element in
S
i
, for
each x S
i
, we have
M =
X
xS
i
m(x) = |S
i
|m(x).
This gives the formula
m(x) =
M
|S
i
|
.
now let
A
be an anti-chain. Then
A
meets each chain in
1 elements. So we
have
M =
X
maximal chains
1
X
xA
m(x) =
n
X
i=0
|A S
i
| ·
M
|S
i
|
.
So it follows that
X
|A S
i
|
|S
i
|
1.
Let’s now turn to a different problem. Suppose
x
1
, . . . , x
n
C
, with each
|x
i
| 1. Given A [n], we let
x
A
=
X
iA
x
i
.
We now seek the largest size of
A
such that
|x
A
x
B
| <
1 for all
A, B A
.
More precisely, we want to find the best choice of
x
1
, . . . , x
n
and
A
so that
|A|
is as large as possible while satisfying the above condition.
If we are really lazy, then we might just choose
x
i
= 1 for all
i
. By taking
A = [n]
bn/2c
, we can obtain |A| =
n
bn/2c
.
Erd¨os noticed this is the best bound if we require the x
i
to be real.
Theorem (Erd¨os, 1945). Let x
i
be all real, |x
i
| 1. For A [n], let
x
A
=
X
iA
x
i
.
Let A P(n). Then |A|
n
bn/2c
.
Proof.
We claim that we may assume
x
i
1 for all
i
. To see this, suppose we
instead had
x
1
=
2, say. Then whether or not
i A
determines whether
x
A
should include 0 or
2 in the sum. If we replace
x
i
with 2, then whether or not
i A
determines whether
x
A
should include 0 or 2. So replacing
x
i
with 2 just
essentially shifts all terms by 2, which doesn’t affect the difference.
But if we assume that
x
i
1 for all
i
, then we are done, since
A
must be an
anti-chain, for if A, B A and A ( B, then x
B
x
A
= x
B\A
1.
Doing it for complex numbers is considerably harder. In 1970, Kleitman
found a gorgeous proof for every normed space. This involves the notion of a
symmetric decomposition. To motivate this, we first consider the notion of a
symmetric chain.
Definition
(Symmetric chain)
.
We say a chain
C
=
{C
i
, C
i+1
, . . . , C
ni
}
is
symmetric if |C
j
| = j for all j.
Theorem. P(n) has a decomposition into symmetric chain.
Proof.
We prove by induction. In the case
n
= 1, we simply have to take
{∅, {1}}.
Now suppose
P
(
n
1) has a symmetric chain decomposition
C
1
··· C
t
.
Given a symmetric chain
C
j
= {C
i
, C
i+1
, . . . , C
n1i
},
we obtain two chains C
(0)
j
, C
(1)
j
in P(n) by
C
(0)
j
= {C
i
, C
i+1
, . . . , C
n1i
, C
n1i
{n}}
C
(1)
j
= {C
i
{n}, C
i+1
{n}, . . . , C
n2i
{n}}.
Note that if
|C
j
|
= 1, then
C
(1)
j
=
, and we drop this. Under this convention, we
note that every A P(n) appears in exactly one C
(ε)
j
, and so we are done.
We are not going to actually need the notion of symmetric chains in our
proof. What we need is the “profile” of a symmetric chain decomposition. By a
simple counting argument, we see that for 0
i
n
2
, the number of chains with
n + 1 2i sets is
`(n, i)
n
i
n
i 1
.
Theorem
(Kleitman, 1970)
.
Let
x
1
, x
2
, . . . , x
n
be vectors in a normed space
with norm kx
I
k 1 for all i. For A P(n), we set
x
A
=
X
iA
x
i
.
Let A P(n) be such that kx
A
x
B
k < 1. Then kAk
n
bn/2c
.
This bound is indeed the best, since we can pick
x
i
=
x
for some
kxk
1,
and then we can pick A = [n]
bn/2c
.
Proof.
Call
F P
(
n
) sparse if
kx
E
x
F
k
1 for all
E, F F
,
E 6
=
F
. Note
that if
F
is sparse, then
|F A|
1. So if we can find a decomposition of
P
(
n
)
into
n
bn/2c
sparse sets, then we are done.
We call a partition
P
(
n
) =
F
1
··· F
t
symmetric if the number of families
with
n
+ 1
2
i
sets is
`
(
n, i
), i.e. the “profile” is that of a symmetric chain
decomposition.
Claim. P(n) has a symmetric decomposition into sparse families.
We again induct on
n
. When
n
= 1, we can take
{∅, {
1
}}
. Now suppose
n1
is a symmetric decomposition of P(n 1) as F
1
··· F
t
.
Given
F
j
, we construct
F
(0)
j
and
F
(1)
j
“as before”. We pick some
D F
j
, to
be decided later, and we take
F
(0)
j
= F
j
{D {n}}
F
(1)
j
= {E {n} : E F
j
\ {D}}.
The resulting set is certainly still symmetric. The question is whether it is sparse,
and this is where the choice of
D
comes in. The collection
F
(1)
j
is certainly still
sparse, and we must pick a D such that F
(0)
j
is sparse.
To do so, we use Hahn–Banach to obtain a linear functional
f
such that
kfk
= 1 and
f
(
x
n
) =
kx
n
k
1. We can then pick
D
to maximize
f
(
x
D
). Then
we check that if E F
j
, then
f(x
D∪{n}
x
2
) = f(x
D
) f(x
E
) + f(x
n
).
By assumption,
f
(
x
n
)
1 and
f
(
x
D
)
f
(
x
E
). So this is
1. Since
kfk
= 1, it
follows that kx
D∪{n}
x
E
k 1.