Homework 1

Deadline: Sept. 30, 22:00:00

1. Suppose five points are chosen inside an equilateral triangle with side length $1$. Show that there is at least one pair of points whose distance apart is at most $1/2$.

2. Let $\chi(G)$ be the chromatic number of graph $G$. Show that any graph $G$ must have at least $\binom{\chi(G)}{2}$ edges.

3. Suppose $G = (V, E)$ is a graph on $n$ vertices. For an edge $e = \{u, v\}$, let $t(e)$ be the number of triangles containing $e$, and $t(G)$ be the number of triangles in $G$.

   • Show that for each pair of adjacent vertices $(u, v)$, $\mathop{\rm deg}(u) + \mathop{\rm deg}(v) - t(\{u, v\}) \leq n$.
   • Summing over all edges $e = \{u, v\}$ we have $\sum_{e=\{u, v\}}(\mathop{\rm deg}(u) + \mathop{\rm deg}(v)) - \sum_e t(e) \leq n\cdot |E|.$ Show that $t(G) \geq \frac{|E|}{3n}(4|E|-n^2)$.

   Remark: This implies that a graph $G$ on n vertices with $|E| = n^2 /4 + 1$ edges not only contains one triangle (as it must be by Mantel’s theorem), but more than $n/3$.

4. Given a family $S_1, \ldots , S_n$ of subsets of $V = \{1, \ldots , n\}$, its intersection graph $G = (V, E)$ is defined by: $\{i, j\} \in E$ if and only if $S_i \cap S_j \neq \emptyset$. Suppose that the average size of $S_i$ is at least $r$, and the average size of $|S_i \cap S_j|$ for $\{i, j\}\in E$ is at most $k$. Show that $|E| \geq \frac{n}{k} \cdot \binom{r}{2}$.

   (Hint: Compute $\sum_{\{i,j\}\in E} |S_i \cap S_j|$.)

5. [Noga Alon, 1986] Let $S$ be a set of strings of length $n$ over some alphabet $\Omega$. Suppose that every two strings of $S$ differ in at least $d$ coordinates. Let $k$ be a number satisfying $d >n\cdot\bigl(1-1/\binom{k}{2}\bigr)$. Show that any $k$ distinct strings $v_1, \ldots , v_k$ of $S$ attain $k$ distinct values in at least one coordinate.

   (Hint: Assume the opposite and count the sum of distances between the $\binom{k}{2}$ pairs of $v_i$'s.)

6. Prove that for any positive integer $c$, there is a number $N = N(c)$ such that for any $c$-coloring of all subsets of $[N]$, $f : 2^{[N]} \rightarrow [c]$, there exists non-empty disjoint sets $X, Y \subseteq [N]$ such that $f(X)$, $f(Y)$ and $f(X \cup Y)$ are the same.