Lesson 3

Optional Problems.

1. (20 points) Let \(G=(V,E)\) be a simple graph. Each \(v\in V\) has a list \(S(v)\) of colors with \(|S(v)|\ge 10d\) for some \(d\ge1\). Moreover, for each \(v\) and color \(c\in S(v)\), at most \(d\) neighbors \(u\) of \(v\) have \(c\in S(u)\). Prove there is a proper coloring choosing the color of each \(v\) from \(S(v)\).
   Hint:

   Color each vertex independently and uniformly from \(S(v)\). Apply the Lovász Local Lemma to show that a proper list-coloring exists.
2. (20 points) A hypergraph \(H=(V,E)\) has property \(B\) if its vertices can be \(2\)‑colored so that no edge is monochromatic. Suppose every edge has size at least \(k\), and each edge intersects at most \(d\) other edges. Prove that if \(e(d+1)\le 2^{k-1}\), then \(H\) has property \(B\).
3. (20 points) Structured bichromatic edge coloring. Let \(K_{n}\) denote the complete (undirected) graph on \(n\) vertices. Show that if \[4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}}\le 1,\] then it is possible to color the edges of \(K_{n}\) with two colors so that it has no monochromatic \(K_{k}\) subgraph, that is, no clique of size \(k\) in the colored \(K_{n}\) with all \(\binom{k}{2}\) edges assigned the same color.