Homework 2

Deadline: Sept. 14, 22:00:00
  1. Let . Then for sufficiently large , any graph on vertices without has edges.

  2. 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 .
  3. Prove that every graph with edges has a -colorable subgraph with at least edges.

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

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

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

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