III Combinatorics - Sperner systems

2Sperner systems

III Combinatorics

2 Sperner systems

In the next few chapters, we are going to try to understand the power set

(

)

of a set. One particularly important structure of

(

) 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

, the power set

(

) of

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

. For

example, we may ask what is the largest possible of an anti-chain in

. 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

= (

S, <

) is a graded poset if we can write

S as a disjoint union

S =

i=0

such that

– S

is an anti-chain; and

– x < y

iff there exists elements

< z

i+1

< ··· < z

such that

∈ S

Example. If X is a set, P(X) is an anti-chain with X

= X

(i)

If we want to obtain the largest anti-chain as possible, then we might try

with

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

, the maximal size of an antichain in

P(X) is



bn/2c



, witnessed by X

bn/2c

Proof.

is a chain and

is an antichain, then

|A ∩ C| ≤

1. So it suffices to

partition P(X) into

m = max







bn/2c





dn/2e



many chains.

We can do so using the injections constructed at the end of the previous

section. For

i ≥ b

, we can construct injections

i−1

→ X

such that

A ⊆ f

(

) for all

. By chaining these together, we get

chains ending in

Similarly, we can partition

(≤bn/2c)

into

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

be an antichain in

(

) with

|X|

Then

r=0

|A ∩ X

(r)





≤ 1.

In particular, |A| ≤ max







bn/2c



, as we already know.

Proof.

A chain

⊆ C

⊆ ··· ⊆ C

is maximal if it has

+ 1 elements.

Moreover, there are

! maximal chains, since we start with the empty set and

then, given

, we produce

i+1

by picking one unused element and adding it

to C

For every maximal chain

, we have

|C ∩ A| ≤

1. Moreover, every set of

elements appears in

n − k

)! maximal chains, by a similar counting argument

as above. So

A∈A

|A|!(n − |A|)! ≤ n!.

Then the result follows.

There are analogous results for posets more general than just

(

). To

formulate these results, we must introduce the following new terminology.

Definition (Shadow). Given A ⊆ S

, the shadow at level i −1 is

∂A = {x ∈ S

i−1

: x < y for some y ∈ A}.

Definition

(Downward-expanding poset)

A graded poset

= (

S, <

) is said to

be downward-expanding if

|∂A|

i−1

≥

|A|

for all A ⊆ A

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

i=0

|A ∩ S

The theorem is that the LYM inequality holds in general for any downward

expanding posets.

Theorem.

is downward expanding and

is an anti-chain, then

(

)

≤

In particular, |A| ≤ max

Since each S

is an anti-chain, the largest anti-chain has size max

Proof. We define the span of A to be

span A = max

6=∅

j − min

6=∅

We do induction on span A.

span A

= 0, then we are done. Otherwise, let

max

6=0

, and set

h−1

= ∂A

. Then since A is an anti-chain, we know A

h−1

∩ B

h−1

= ∅.

We set

A\A

∪B

h−1

. This is then another anti-chain, by the transitivity

of <. We then have

w(A) = w(A

) + w(A

) − w(B

h−1

) ≤ w(A

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



bn/2c



. This requires the notion of a regular poset.

Definition

(Regular poset)

We say a graded poset (

S, <

) is regular if for each

, there exists

, s

such that if

x ∈ A

, then

dominates

elements at level

i − 1, and is dominated by s

elements at level i + 1.

Proposition. An anti-chain in a regular poset has weight ≤ 1.

Proof.

Let

be the number of maximal chains of length (

+ 1), and for each

x ∈ S

, let m(x) be the number of maximal chains through x. Then

m(x) =

i=1

n−1

i=k

So if x, y ∈ S

, then m(x) = m(y).

Now since every maximal chain passes through a unique element in

, for

each x ∈ S

, we have

M =

x∈S

m(x) = |S

|m(x).

This gives the formula

m(x) =

now let

be an anti-chain. Then

meets each chain in

≤

1 elements. So we

have

M =

maximal chains

1 ≥

x∈A

m(x) =

i=0

|A ∩ S

| ·

So it follows that

|A ∩ S

≤ 1.

Let’s now turn to a different problem. Suppose

, . . . , x

∈ C

, with each

| ≥ 1. Given A ⊆ [n], we let

i∈A

We now seek the largest size of

such that

− x

| <

1 for all

A, B ∈ A

More precisely, we want to find the best choice of

, . . . , x

and

so that

|A|

is as large as possible while satisfying the above condition.

If we are really lazy, then we might just choose

= 1 for all

. By taking

A = [n]

bn/2c

, we can obtain |A| =



bn/2c



Erd¨os noticed this is the best bound if we require the x

to be real.

Theorem (Erd¨os, 1945). Let x

be all real, |x

| ≥ 1. For A ⊆ [n], let

i∈A

Let A ⊆ P(n). Then |A| ≤



bn/2c



Proof.

We claim that we may assume

≥

1 for all

. To see this, suppose we

instead had

−

2, say. Then whether or not

i ∈ A

determines whether

should include 0 or

−

2 in the sum. If we replace

with 2, then whether or not

i ∈ A

determines whether

should include 0 or 2. So replacing

with 2 just

essentially shifts all terms by 2, which doesn’t affect the difference.

But if we assume that

≥

1 for all

, then we are done, since

must be an

anti-chain, for if A, B ∈ A and A ( B, then x

− x

= 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

i+1

, . . . , C

n−i

}

symmetric if |C

| = j for all j.

Theorem. P(n) has a decomposition into symmetric chain.

Proof.

We prove by induction. In the case

= 1, we simply have to take

{∅, {1}}.

Now suppose

(

n −

1) has a symmetric chain decomposition

∪ ··· ∪ C

Given a symmetric chain

= {C

, C

i+1

, . . . , C

n−1−i

we obtain two chains C

(0)

, C

(1)

in P(n) by

(0)

= {C

, C

i+1

, . . . , C

n−1−i

, C

n−1−i

∪ {n}}

(1)

= {C

∪ {n}, C

i+1

∪ {n}, . . . , C

n−2−i

∪ {n}}.

Note that if

= 1, then

(1)

∅

, and we drop this. Under this convention, we

note that every A ∈ P(n) appears in exactly one C

(ε)

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

, the number of chains with

n + 1 − 2i sets is

`(n, i) ≡





−



i − 1



Theorem

(Kleitman, 1970)

Let

, x

, . . . , x

be vectors in a normed space

with norm kx

k ≥ 1 for all i. For A ∈ P(n), we set

i∈A

Let A ⊆ P(n) be such that kx

− x

k < 1. Then kAk ≤



bn/2c



This bound is indeed the best, since we can pick

for some

kxk ≥

and then we can pick A = [n]

bn/2c

Proof.

Call

F ⊆ P

(

) sparse if

− x

k ≥

1 for all

E, F ∈ F

E 6

. Note

that if

is sparse, then

|F ∩A| ≤

1. So if we can find a decomposition of

(

)

into



bn/2c



sparse sets, then we are done.

We call a partition

(

) =

∪···∪ F

symmetric if the number of families

with

+ 1

−

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

. When

= 1, we can take

{∅, {

}}

. Now suppose

∆

n−1

is a symmetric decomposition of P(n − 1) as F

∪ ··· ∪ F

Given

, we construct

(0)

and

(1)

“as before”. We pick some

D ∈ F

, to

be decided later, and we take

(0)

= F

∪ {D ∪ {n}}

(1)

= {E ∪{n} : E ∈ F

\ {D}}.

The resulting set is certainly still symmetric. The question is whether it is sparse,

and this is where the choice of

comes in. The collection

(1)

is certainly still

sparse, and we must pick a D such that F

(0)

is sparse.

To do so, we use Hahn–Banach to obtain a linear functional

such that

kfk

= 1 and

(

) =

k ≥

1. We can then pick

to maximize

(

). Then

we check that if E ∈ F

, then

f(x

D∪{n}

− x

) = f(x

) − f(x

) + f(x

By assumption,

(

)

≥

1 and

(

)

≥ f

(

). So this is

≥

1. Since

kfk

= 1, it

follows that kx

D∪{n}

− x

k ≥ 1.