Homework 2

Deadline: Sept. 14, 22:00:00

1. Let $s \geq t \geq 2$. Then for sufficiently large $n$, any graph on $n$ vertices without $K_{s,t}$ has $O(s^{1/t}n^{2−1/t})$ edges.

2. Let $H = (V,\mathcal{F})$ be a hypergraph such that each hyperedge contains $\geq 3$ vertices and any two hyperedges share exactly one vertex in common. Suppose that $H$ is also not $2$-colorable. Show that:

   • every vertex $v$ belongs to at least two hyperedges of $\mathcal{F}$;
   • every two vertices $u, v$ belongs to exactly one hyperedge of $\mathcal{F}$.

3. Prove that every graph with $m$ edges has a $k$-colorable subgraph with at least $(1-1/k)m$ edges.

4. Let $n \geq 4$ and $t \geq 3\sqrt{n}$. Prove that, for any $n \times n$ matrix $A$ with distinct real entries, we can transform it to a new matrix $B$ by permuting columns, such that in $B$ none of the rows contain any monotone sub-sequence of length $t$.

5. Let $v_1, \ldots, v_n$ be $n$ vectors in $\mathbb{R}^n$ of unit length $\lVert v_i \rVert = 1$, where $\lVert v \rVert$ is given by the Euclidean norm $\lVert v \rVert=\sqrt{\langle v, v \rangle} =\sqrt{v^{\mathsf{T}}v}$. Prove that there exist signs $\epsilon_i = \pm 1$ such that $\lVert \epsilon_1v_1 + \cdots + \epsilon_n v_n\rVert \leq \sqrt{n}$, and $\sqrt{n}$ cannot be improved.

6. Consider the family of all pairs $(A, B)$ of disjoint $k$-element subsets of $[n]$. A set $Y$ separates the pair $(A, B)$ if $A \subseteq Y$ and $B \cap Y = \emptyset$. Prove that there exist $\ell = 2k4^k \ln n$ sets such that every pair $(A, B)$ is separated by at least one of them.

7. (Bonus) Consider two boxes $B_1$ and $B_2$. Suppose that box $B_i$ contains $c_i$ coins in it, where $c_1, c_2$ are independently identically distributed from an unknown distribution $D$ over $\mathbb{N}$. You have opened a box and find $c$ 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 $1/2$ ? You could use some random bits to help you.