Let . Then for sufficiently large , any graph on vertices without has edges.

Let be a hypergraph such that each hyperedge contains vertices and any two hyperedges share exactly one vertex in common. Suppose that is also not -colorable. Show that:

- every vertex belongs to at least two hyperedges of ;
- every two vertices belongs to exactly one hyperedge of .

Prove that every graph with edges has a -colorable subgraph with at least edges.

Let and . Prove that, for any matrix with distinct real entries, we can transform it to a new matrix by permuting columns, such that in none of the rows contain any monotone sub-sequence of length .

Let be vectors in of unit length , where is given by the Euclidean norm . Prove that there exist signs such that , and cannot be improved.

Consider the family of all pairs of disjoint -element subsets of . A set separates the pair if and . Prove that there exist sets such that every pair is separated by at least one of them.

(Bonus) Consider two boxes and . Suppose that box contains coins in it, where are independently identically distributed from an

*unknown*distribution over . You have opened a box and find coins inside.You now have

*one*chance to pick a box (not necessarily the one you opened). Is it possible for you to design a protocol such that the probability of you picking the box with more coins is greater than ? You could use some random bits to help you.