1 - Set Systems Flashcards
(23 cards)
What is a chain?
What is an antichain?
How long can a chain be? Prove this.
This is a set system in which for any two elements, one must be contained in the other.
An antichain is a set system in which any two elements are not contained in each other.
Firstly, assume that we have a chain of length larger than n+1. Then if the smallest set in our chain has size k, then the biggest has size larger than k+n. Which is obviously false, since X only has n elements and k is non negative. Hence, the largest chain can have a maximum size n+1, and we can find chains of this size, so this is the maximum.
What is a set system on X?
What is Xr normally defined as when r is an integer?
How do we make the power set of X into a graph?
What is this graph called, and why is it given this name?
If X is a set, then A is a set system on X if A is a subset of the power system of X.
Xr is the set system on X given by all subsets of X of size r.
We let the vertices of the graph be the power set P(X), and then say a and B are joined IFF there symmetric difference has size 1.
If X has size n, we call this the discrete cube Qn. This is because, if we label the elements of X by 1,…,n then if we identify a set A<X by a
0-1 sequence of length n in the natural way, this indicator function gives a map from Qn to the unit cube in Rn and is a bijection to the vertices of this cube.
What is sperner’s lemma?
What is the idea behind its proof?
Prove sperner’s lemma.
Sperner’s lemma gives you a bound for the size of the biggest antichain. specifically it says that the largest an antichain can be is n choose n/2.
The proof of sperner uses the idea that an antichain must be made of of points from distinct chains, and we try and partition P(X) into chains which will tell us how large a maximal antichain could be.
We decompose P(X) into n choose n/2 chains. This will suffice by the above remark.
It suffices to show that for all rn/2 there is a matching from Xr to X(r-1). Given this, we can then join these matchings together to decompose P(X) into a set of chains each meeting the middle layer once, and so there are exactly n choose n/2 chains partitioning P(X).
So, for r<1 and so are done by symmetry.
Define the lower shadow of a set system A<Xr.
The lower shadow of A contained in the layer Xr is the set δA of sets in the layer below which are contained in some element in A.
What is local LYM?
Prove it.
Local LYM states that for all r, and A= |A|/(nCr)
To prove this, count the number of edges from A to δA in two directions. It is then obvious.
What is the LYM inequality?
Prove it twice.
LYM inequality:
Let A be an antichain in P(X). Then:
Σ|A^Xr|/(nCr) =< 1
Where we sum over all r.
Proof 1: (bubble down with local LYM)
Write Ar for A^Xr.
We have |An|/(nCn)<=1.
Now induct using this idea and local LYM to extend the sum.
Proof 2:
Choose at random and uniformly, a maximal length chain C. For an r-set A, we have Prob(A in C)=1/(nCr).
This shows that, letting B be an antichain, the events C meets Br are disjoint, so P(C meets B) is just the sum of these probabilities but
P(C meets Br)=|Br|/(nCr), and this gives the rest.
Prove Sperner’s lemma using LYM inequality.
Trivially, (nC[n/2])>=(nCr) for all r, so by multiplying the LYM inequality by this and using this inequality, we see that the size of the disjoint union if the Br is at most (nC[n/2]) which is sperner.
When do we get equality in LYM?
Well, using the bubble down with local LYM proof, we must have equality in each step of using local LYM. BUT, for equality in local LYM, we need that for any set A, if we pick any i in A and j not in A, there must be A’=(A-i)Uj in Br, and so Br must be the whole layer or nothing. So we get equality in LYM IFF our set system is a whole level. Hence, we have equality in Sperner IFF our set system is a middle layer.
Local LYM gives us a lower bound on δA. What are the faults in this bound?
The bound is not sharp, as you only have equality when at the extremes, ie A is empty or a whole layer.
What is the Lexicographic ordering on Xr?
What is the slogan for Lex?
The Lexicographic (or Lex, or Dictionary ordering) on Xr is, for A having elements ai and B having elements bi, ordered, then we say A<b></b>
What is the colexicographic or Colex ordering?
What is the slogan for Colex?
For A,B in Xr with elements ai, bi in order, we say A<b>j.</b>
The slogan for Colex is “avoid large elements”.
Define an initial segment of an ordering on Xr.
What is bad about initial segments in Lex?
What is good about IS in Colex?
An initial segment of an ordering on Xr is a set A of r-sets which contains all r-sets in the total ordering up to some specific set, and none after this. Ie it is just “taking the first n r-sets” in some ordering.
In Lex, initial segments don’t cap the size of the largest element. So for example, if n is large and say r is 2, the initial segment of Lex is:
(1,2),(1,3),(1,4),(1,5),(1,6),….
In Colex, [m]r is an initial segment of [m+1]r, so can view Colex as an enumeration of Nr. So if the elements in a particular r-set are bounded we will get to it quickly using Colex.
What is an ij-compression of A<Xr
ij-compressed?
Since Colex prefers lower numbers, we define for i of the same size, with a smaller shadow. Eventually we want to show that by taking a sequence of compressions of this nature we end at a minimal compression which looks like Colex.
A family A is ij-compressed if Cij(A)=A.
Prove that the ij- compression of a family A<Xr decreases shadow.
Set A’=Cij(A). Then suppose there is B in δA’-δA. We try to show that this tells us there is a set B’ in δA-δA’ and so the size of this difference is bigger than that of the first, and so δΑ>δΑ’.
Now B is in δA’-δA. So BUx in A’ for some x not in B. But BUx is not in A. BUx is the compression of some set D in A. Hence, i is in BUx, and j is not. So D=BUxUj-i.
If x=i, then BUj is in A, and B would be in δΑ, a contradiction. So x is not i and so i is in B, and j is not in B, since its not in BUx.
We claim that BUj-i=B’ is in δA-δA’.
Well, B’Ux is in A so B’ is in δA. So why is B’ not in δΑ’? Well if it was, then B’Uy is in A, and y is not i or j, since if y=i then BUj is in A’, and so as this is just the compression of A, implies BUj is in A, which is a contradiction. So j is in B’Uy, and i is not. This is also a contradiction as B’Uy was in A’, which is ij-compressed, and so B’Uy and BUy would be in A, which again is a contradiction.
Hence we are done.
What does it mean when we say A<Xr of the same size, but is left compressed and has smaller shadow.
It means Cij(A)=A for all i<j such that Cij(Ak) is not Ak, and set Cij(A)=Ak+1
This must terminate, as this always lowers the sum of elements in sets contained in Ak. The final term Ak is thus left compressed, and by before, compressions lower the size of the shadow.
Define, for U,V<Xr.
Why do we have to be careful with this definition and treatment of the shadow?
For B in Xr, set Cuv(B)=BUU-V if V is contained in B and U is disjoint from B, and let this be B otherwise.
So essentially replace V by U wherever possible.
Then set Cuv(A)={Cuv(B):B in A}U{B in A:Cuv(B) is in A}
This is the UV compression of A.
Note that Cuv(A) has the same size as A
Performing a UV-compression can increase the shadow!
Let U, V be disjoint subsets of X of the same size. Let A
Write A’=Cuv(A). Pick some B in δA’-δA. We show that U is contained in B, and C is disjoint from it, and that BUV-U is in δA-δA’.
This will then say that any ‘new’ element in the shadow contains U and is disjoint from V, and came from an element in A which is not in the new shadow, which is enough, since then the new shadow must be smaller.
So, we have BUx in A’, for some x, and BUx not in A. So that U is in BUx, and V is disjoint from it, and BUxUV-U is in A. So V^B is empty and if x is in U, then there is some y in V such that A is (U-x,V-y) compresses, so from BUxUV-U in A we would get BUy is in A, contradicting B not being in δA.
So we know that U is in B and V is disjoint from it.
Now, BUV-U is in δA since BUxUV-U is in A. Suppose it is also in δA’. Then (BUV-U)Uw is in A’ for some w, and so in A as it contains V so did not move.
If w is in U we get a contradiction as B is not in δA.
If w is not in U we get a similar contradiction.
So overall the assumption BUV-U is in δA’ is false, and we are done.
State the Kruskal-katana theorem.
If A< the shadow of A.
So essentially -“Colex wins” when trying to minimise lower shadow.
Prove the Kruskal-katana theorem
Let Γ be the set of all pairs (U,V) of subsets of X of the same size, disjoint, and the maximum element of U less than the maximum element of V.
Then define the sequence A0,A1,… by:
A=A0
Having defined Ak, if Ak is UV compressed for all (U,V) in Γ, then stop.
Otherwise, among all Pairs (U,V) in Γ with Ak not UV compressed, choose one with smallest |U|. Then for all u in U, we have
(U-{u},V-{min(v)}) is in Γ, and so in particular, Ak must be
(U-{u},V-{min(v)}) compressed, and so by a previous lemma, taking the UV compression of Ak decreases the shadow, and so set
A(k+1)=Cuv(Ak).
This sequence must terminate, since we are removing maximal elements everytime, and so taking the sum over all elements of 2^x, this sequence decreases at every step, and so it terminates.
The final system is B=Ak and has the same size as A but is UV compressed for all pairs in Γ and has smaller lower shadow than A.
CLAIM: the only such B is in fact an initial segment of Colex.
Proof:
Suppose B not an IS of Colex. Then if we order Xr in Colex, there is some A not in B and A’ in B with A before A’ in this ordering.
So, by definition of Colex, the max of (A’\A) is greater than that of (A\A’). So in particular, ((A\A’),(A’\A)) is in Γ. So then if we take this compression of A’ we get A, which contradicts our assumptions on B.
Define the upper shadow of A for minimising upper shadow.
The upper shadow of A is defined by:
δ+Α={BUx : B is in A, and x isn’t in B} < X(r+1)
Well, suppose A for any B in Xr. Hence, the result follows using Kruskal-katana.
Define the multiple lower shadow of A=(kC r-t).
We define δt(A)=δ(δ(…(δΑ))..)
Where there are t deltas.
Use Kruskal-katana, and the fact that the lower shadow of an IS of Colex, is another IS of Colex.
Define an intersecting family.
What is the largest size an intersecting family can be?
Find an example of such a family.
A<X, only one of B and its compliment can be in A, so the size is restricted by X/2.
Let A be the set of all subsets of X containing a 1. This is intersecting and has size X/2.
What is the Erdos-ko-rado theorem?
Proof?
For r=(n-1 C r). Now we have a contradiction, since this set is disjoint in Xr from A, and the sum of there sizes is larger than Xr.
