Combinatorics and Probability
First Midterm - April 13, 2005

Instructor: László Babai


Important. Do NOT use books, handouts, notes, scrap paper. Show all your work.

  1. (15 points) Prove the Kovári-Sós-Turán Theorem: if a graph on $n$ vertices does not contain a 4-cycle then $m \lesssim (1/2)n^{3/2}$ where $m$ is the number of edges. Define the notation ``$\lesssim$'' (``less than or asymptotically equal to'').

  2. (15 points) Let $k\ge 1$. Prove Fisher's inequality: if $A_1,\dots,A_m\subseteq [n]$ are distinct sets and $(\forall i\neq j)(\vert A_i\cap A_j\vert=k)$ then $m\le n$. Define the concepts used.

  3. (14 points) Prove Erdos's Ramsey bound:

    \begin{displaymath}n \not\to (1+2\log_2 n, 1+2\log_2 n).\end{displaymath}

    Explain this result in mathematical English (use proper quantifiers).

  4. (14 points) Esther Klein pointed out that among 5 points in the plane, no three of which is are on a line, there are always four which form a convex quadrilateral. Use this fact and Ramsey's Theorem to prove that $(\forall k)(\exists n)$ such that no matter how we place $n$ points in the plane such that no three are on a line, $k$ of them will form a convex $k$-gon. Clearly state the case of Ramsey's Theorem you are using; use the Erdos-Rado arrow notation.

  5. (14 points) A tile is a unit square, divided into four parts (``quadrants'') by its diagonals; each of the four parts is colored. The sides of a tile are designated as North, East, South and West.

    We have a set of $k$ tiles and an infinite supply of identical copies of each of the $k$ tiles. We want to tile the entire plane (cover the plane with nonoverlapping tiles) obeying the following rules: each tile must fill a square in the unit square grid; the North side of each tile must point up, the East side to the right, the South side down, and the West side to the left; and adjacent tiles must have the same color in their adjacent quadrants.

    Prove: if $(\forall n)$ the $n\times n$ square can be tiled in this manner then the entire plane can.

  6. (28 points) Prove: every triangle-free graph with $n$ vertices has chromatic number $O(\sqrt{n})$.