More combinatorics of sets fun
by shiningsunnyday, Dec 16, 2016, 5:24 PM
Combo 3 Week 4 Homework (Medium) wrote:
Let
and
be two positive integers and let
be a subset with
elements of the set
Prove that
contains
numbers
such that 









Solution
Define a poset with on the set
with
if 
The claim is that there exists a chain of length
among the set
This will then imply there exists a chain of length
among the set 
Lemma:
for 
Proof: Induction on
Now, by Mirsky's theorem, the length of the longest chain is the minimum number of anti-chains that partition
But Since
note that we can define anti-chains
such that
consists of all elements for which the largest power of
dividing it is
The conclusion follows.



The claim is that there exists a chain of length




Lemma:


Proof: Induction on

Now, by Mirsky's theorem, the length of the longest chain is the minimum number of anti-chains that partition






Tidbit
It feels really good as the material seems much easier compared to 5 months ago. I've done quite a few problems on posets already, so tomorrow time to knock out some problems with the theorems of Cauchy-Davenport, Schur, and Van der Waerden!