Mixing
Clarifications on proof of Sperner's Theorem
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Here I am considering a set $X$ with $|X| = n$ and it's power set $ mathcal P(X)$.
Denote by $X^(i)$ the set of elements of $mathcal P(X)$ with $i$ elements, and consider $mathcal P(X)$ as a poset ordered by $A < B Leftrightarrow A subset B$.
Then in my lecture notes, we have Sperner's Theorem saying the largest size of an anti-chain in $mathcal P(X)$ is $binomnlfloor n/2 rfloor$, witnessed by $X^(lfloor n/2 rfloor)$.
Then, to prove this: on realising that for any chain $C$ and anti-chain $A$ of $mathcal P(X)$ we have that $|C cap A| leq 1$, my notes say that: "it is sufficient to partition $mathcal P(X)$ into $binomnlfloor n/2 rfloor$
chains".
I understand that on partitioning $mathcal P(X)$ into this many chains, then we have that an anti-chain can have at most one non-trivial intersection with each of them. Further, we may notice (with appropriately chosen chains) that $X^lfloor n/2 rfloor$ is indeed a witness to the case of an antichain of size $binomnlfloor n/2 rfloor$. Together this tells us the maximal anti-chain size is at least $binomnlfloor n/2 rfloor.$
Why then do we now know there can't be an anti chain that is longer? From what I can tell this proof has given us the wrong bound (lower instead of upper) on the size of the largest possible anti-chain. I expect that I have misunderstood something crucial here, or missed an assumed result, and I would be very grateful if you could point it out to me.
I apologise if I haven't been clear enough here. I have understood what I said here but likely only because I have my lecture notes in front of me. If there is something worth clarifying please let me know.
In case it is important: the method by which we construct the $binomnlfloor n/2 rfloor$ chains is by using complete matchings from either $X^(i-1)$ to $X^(i)$ or from $X^(i)$ to $X^(i-1)$ (order depending on the size of $i$) by viewing $(X^(i),X^(i-1))$ as a biregular, bipartite graph.
combinatorics
asked Jul 29 at 18:01
user366818
704310
add a comment |Â
up vote
1
down vote
favorite
Here I am considering a set $X$ with $|X| = n$ and it's power set $ mathcal P(X)$.
Denote by $X^(i)$ the set of elements of $mathcal P(X)$ with $i$ elements, and consider $mathcal P(X)$ as a poset ordered by $A < B Leftrightarrow A subset B$.
Then in my lecture notes, we have Sperner's Theorem saying the largest size of an anti-chain in $mathcal P(X)$ is $binomnlfloor n/2 rfloor$, witnessed by $X^(lfloor n/2 rfloor)$.
Then, to prove this: on realising that for any chain $C$ and anti-chain $A$ of $mathcal P(X)$ we have that $|C cap A| leq 1$, my notes say that: "it is sufficient to partition $mathcal P(X)$ into $binomnlfloor n/2 rfloor$
chains".
I understand that on partitioning $mathcal P(X)$ into this many chains, then we have that an anti-chain can have at most one non-trivial intersection with each of them. Further, we may notice (with appropriately chosen chains) that $X^lfloor n/2 rfloor$ is indeed a witness to the case of an antichain of size $binomnlfloor n/2 rfloor$. Together this tells us the maximal anti-chain size is at least $binomnlfloor n/2 rfloor.$
Why then do we now know there can't be an anti chain that is longer? From what I can tell this proof has given us the wrong bound (lower instead of upper) on the size of the largest possible anti-chain. I expect that I have misunderstood something crucial here, or missed an assumed result, and I would be very grateful if you could point it out to me.
I apologise if I haven't been clear enough here. I have understood what I said here but likely only because I have my lecture notes in front of me. If there is something worth clarifying please let me know.
In case it is important: the method by which we construct the $binomnlfloor n/2 rfloor$ chains is by using complete matchings from either $X^(i-1)$ to $X^(i)$ or from $X^(i)$ to $X^(i-1)$ (order depending on the size of $i$) by viewing $(X^(i),X^(i-1))$ as a biregular, bipartite graph.
combinatorics
asked Jul 29 at 18:01
user366818
704310
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Here I am considering a set $X$ with $|X| = n$ and it's power set $ mathcal P(X)$.
Denote by $X^(i)$ the set of elements of $mathcal P(X)$ with $i$ elements, and consider $mathcal P(X)$ as a poset ordered by $A < B Leftrightarrow A subset B$.
Then in my lecture notes, we have Sperner's Theorem saying the largest size of an anti-chain in $mathcal P(X)$ is $binomnlfloor n/2 rfloor$, witnessed by $X^(lfloor n/2 rfloor)$.
Then, to prove this: on realising that for any chain $C$ and anti-chain $A$ of $mathcal P(X)$ we have that $|C cap A| leq 1$, my notes say that: "it is sufficient to partition $mathcal P(X)$ into $binomnlfloor n/2 rfloor$
chains".
I understand that on partitioning $mathcal P(X)$ into this many chains, then we have that an anti-chain can have at most one non-trivial intersection with each of them. Further, we may notice (with appropriately chosen chains) that $X^lfloor n/2 rfloor$ is indeed a witness to the case of an antichain of size $binomnlfloor n/2 rfloor$. Together this tells us the maximal anti-chain size is at least $binomnlfloor n/2 rfloor.$
Why then do we now know there can't be an anti chain that is longer? From what I can tell this proof has given us the wrong bound (lower instead of upper) on the size of the largest possible anti-chain. I expect that I have misunderstood something crucial here, or missed an assumed result, and I would be very grateful if you could point it out to me.
I apologise if I haven't been clear enough here. I have understood what I said here but likely only because I have my lecture notes in front of me. If there is something worth clarifying please let me know.
In case it is important: the method by which we construct the $binomnlfloor n/2 rfloor$ chains is by using complete matchings from either $X^(i-1)$ to $X^(i)$ or from $X^(i)$ to $X^(i-1)$ (order depending on the size of $i$) by viewing $(X^(i),X^(i-1))$ as a biregular, bipartite graph.
combinatorics
asked Jul 29 at 18:01
user366818
704310
Here I am considering a set $X$ with $|X| = n$ and it's power set $ mathcal P(X)$.
Denote by $X^(i)$ the set of elements of $mathcal P(X)$ with $i$ elements, and consider $mathcal P(X)$ as a poset ordered by $A < B Leftrightarrow A subset B$.
Then in my lecture notes, we have Sperner's Theorem saying the largest size of an anti-chain in $mathcal P(X)$ is $binomnlfloor n/2 rfloor$, witnessed by $X^(lfloor n/2 rfloor)$.
Then, to prove this: on realising that for any chain $C$ and anti-chain $A$ of $mathcal P(X)$ we have that $|C cap A| leq 1$, my notes say that: "it is sufficient to partition $mathcal P(X)$ into $binomnlfloor n/2 rfloor$
chains".
I understand that on partitioning $mathcal P(X)$ into this many chains, then we have that an anti-chain can have at most one non-trivial intersection with each of them. Further, we may notice (with appropriately chosen chains) that $X^lfloor n/2 rfloor$ is indeed a witness to the case of an antichain of size $binomnlfloor n/2 rfloor$. Together this tells us the maximal anti-chain size is at least $binomnlfloor n/2 rfloor.$
Why then do we now know there can't be an anti chain that is longer? From what I can tell this proof has given us the wrong bound (lower instead of upper) on the size of the largest possible anti-chain. I expect that I have misunderstood something crucial here, or missed an assumed result, and I would be very grateful if you could point it out to me.
I apologise if I haven't been clear enough here. I have understood what I said here but likely only because I have my lecture notes in front of me. If there is something worth clarifying please let me know.
In case it is important: the method by which we construct the $binomnlfloor n/2 rfloor$ chains is by using complete matchings from either $X^(i-1)$ to $X^(i)$ or from $X^(i)$ to $X^(i-1)$ (order depending on the size of $i$) by viewing $(X^(i),X^(i-1))$ as a biregular, bipartite graph.
combinatorics
asked Jul 29 at 18:01
user366818
704310
asked Jul 29 at 18:01
user366818
704310
asked Jul 29 at 18:01
user366818
704310
asked Jul 29 at 18:01
user366818
704310
704310
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
You have chains $C_1,ldots,C_m$ where $m=binomn[n/2]$. Each element
of $mathcal P(X)$ is in exactly one $C_j$. So each element of an antichain
$cal A$ has at most one element in each $C_j$, but each element of $cal A$ is in some $C_j$, so there are at most $m$ elements in $cal A$.
I prefer the proof from the LYM inequality....
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
1
it was so simple all along, i feel silly. Thank you for pointing this out to me!
– user366818
Jul 29 at 18:31
add a comment |Â
up vote
-1
down vote
On the one hand, you have $calP$ partitioned into $m= n choose lceil fracn2rceil$ chains via the proof in the later part of your post @user, which gives the upper bound of $m$ on the size of the largest antichain.
On the other hand, you have been given an explicit antichain with precisely $m$ elements--namely all subsets of $[n]$ with precisely $lceil fracn2 rceil$ elements, this gives the lower bound of $m$ on the size of the largest antichain.
If both the upper bound and the lower bound on the size of the largest antichain is $m$, then it follows that the size of the largest antichain must indeed be $m$.
answered Jul 30 at 17:19
Mike
1,665110
Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct.
– Mike
Jul 30 at 19:38
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
You have chains $C_1,ldots,C_m$ where $m=binomn[n/2]$. Each element
of $mathcal P(X)$ is in exactly one $C_j$. So each element of an antichain
$cal A$ has at most one element in each $C_j$, but each element of $cal A$ is in some $C_j$, so there are at most $m$ elements in $cal A$.
I prefer the proof from the LYM inequality....
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
1
it was so simple all along, i feel silly. Thank you for pointing this out to me!
– user366818
Jul 29 at 18:31
add a comment |Â
up vote
3
down vote
accepted
You have chains $C_1,ldots,C_m$ where $m=binomn[n/2]$. Each element
of $mathcal P(X)$ is in exactly one $C_j$. So each element of an antichain
$cal A$ has at most one element in each $C_j$, but each element of $cal A$ is in some $C_j$, so there are at most $m$ elements in $cal A$.
I prefer the proof from the LYM inequality....
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
1
it was so simple all along, i feel silly. Thank you for pointing this out to me!
– user366818
Jul 29 at 18:31
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
You have chains $C_1,ldots,C_m$ where $m=binomn[n/2]$. Each element
of $mathcal P(X)$ is in exactly one $C_j$. So each element of an antichain
$cal A$ has at most one element in each $C_j$, but each element of $cal A$ is in some $C_j$, so there are at most $m$ elements in $cal A$.
I prefer the proof from the LYM inequality....
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
You have chains $C_1,ldots,C_m$ where $m=binomn[n/2]$. Each element
of $mathcal P(X)$ is in exactly one $C_j$. So each element of an antichain
$cal A$ has at most one element in each $C_j$, but each element of $cal A$ is in some $C_j$, so there are at most $m$ elements in $cal A$.
I prefer the proof from the LYM inequality....
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
answered Jul 29 at 18:12
Lord Shark the Unknown
84.5k950111
84.5k950111
1
it was so simple all along, i feel silly. Thank you for pointing this out to me!
– user366818
Jul 29 at 18:31
add a comment |Â
1
it was so simple all along, i feel silly. Thank you for pointing this out to me!
– user366818
Jul 29 at 18:31
1
1
it was so simple all along, i feel silly. Thank you for pointing this out to me!
– user366818
Jul 29 at 18:31
it was so simple all along, i feel silly. Thank you for pointing this out to me!
– user366818
Jul 29 at 18:31
add a comment |Â
up vote
-1
down vote
On the one hand, you have $calP$ partitioned into $m= n choose lceil fracn2rceil$ chains via the proof in the later part of your post @user, which gives the upper bound of $m$ on the size of the largest antichain.
On the other hand, you have been given an explicit antichain with precisely $m$ elements--namely all subsets of $[n]$ with precisely $lceil fracn2 rceil$ elements, this gives the lower bound of $m$ on the size of the largest antichain.
If both the upper bound and the lower bound on the size of the largest antichain is $m$, then it follows that the size of the largest antichain must indeed be $m$.
answered Jul 30 at 17:19
Mike
1,665110
Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct.
– Mike
Jul 30 at 19:38
add a comment |Â
up vote
-1
down vote
On the one hand, you have $calP$ partitioned into $m= n choose lceil fracn2rceil$ chains via the proof in the later part of your post @user, which gives the upper bound of $m$ on the size of the largest antichain.
On the other hand, you have been given an explicit antichain with precisely $m$ elements--namely all subsets of $[n]$ with precisely $lceil fracn2 rceil$ elements, this gives the lower bound of $m$ on the size of the largest antichain.
If both the upper bound and the lower bound on the size of the largest antichain is $m$, then it follows that the size of the largest antichain must indeed be $m$.
answered Jul 30 at 17:19
Mike
1,665110
Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct.
– Mike
Jul 30 at 19:38
add a comment |Â
up vote
-1
down vote
up vote
-1
down vote
On the one hand, you have $calP$ partitioned into $m= n choose lceil fracn2rceil$ chains via the proof in the later part of your post @user, which gives the upper bound of $m$ on the size of the largest antichain.
On the other hand, you have been given an explicit antichain with precisely $m$ elements--namely all subsets of $[n]$ with precisely $lceil fracn2 rceil$ elements, this gives the lower bound of $m$ on the size of the largest antichain.
If both the upper bound and the lower bound on the size of the largest antichain is $m$, then it follows that the size of the largest antichain must indeed be $m$.
answered Jul 30 at 17:19
Mike
1,665110
On the one hand, you have $calP$ partitioned into $m= n choose lceil fracn2rceil$ chains via the proof in the later part of your post @user, which gives the upper bound of $m$ on the size of the largest antichain.
On the other hand, you have been given an explicit antichain with precisely $m$ elements--namely all subsets of $[n]$ with precisely $lceil fracn2 rceil$ elements, this gives the lower bound of $m$ on the size of the largest antichain.
If both the upper bound and the lower bound on the size of the largest antichain is $m$, then it follows that the size of the largest antichain must indeed be $m$.
answered Jul 30 at 17:19
Mike
1,665110
answered Jul 30 at 17:19
Mike
1,665110
answered Jul 30 at 17:19
Mike
1,665110
answered Jul 30 at 17:19
Mike
1,665110
1,665110
Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct.
– Mike
Jul 30 at 19:38
add a comment |Â
Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct.
– Mike
Jul 30 at 19:38
Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct.
– Mike
Jul 30 at 19:38
Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct.
– Mike
Jul 30 at 19:38
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2866273%2fclarifications-on-proof-of-sperners-theorem%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password