Assignment 1
This assignment is a work-in-progress. A few new questions will be added after each lecture. The idea being that each new question applies or extends something covered in the lecture.
Lecture 1 (Sep 3 & 4)
When discussing graphs, $K_n$ denotes the graph with $n$ vertices $v_1,\ldots,v_n$ that contains all possible edges. That is, $K_n$ has vertex set $V(K_n)=\{v_1,\ldots,v_n\}$ and edge set $E(K_n)=\{v_iv_j: 1\le i< j\le n\}$. Here is what $K_3$, $K_4$, and $K_5$ look like when we draw them:
The graph $K_3$ is also called a $3$-cycle and sometimes called a triangle.
Question: Describe (or just draw) $K_1$ and $K_2$
For the rest of this question, when we use the word colouring we mean a colouring of the edges of a graph where each edge is coloured red or is coloured blue. When we use the term red $K_s$ we mean a colouring of $K_s$ where all edges are coloured red. When we use the term blue $K_t$ we mean a colouring of $K_t$ in which all edges are coloured blue.
For positive integers $s$ and $t$, let $R(s,t)$ denote the minimum integer $n$ such that any colouring of $K_n$ contains a red $K_s$ or a blue $K_t$.
In the first class, we showed that $R(3,3)\le 6$. Any colouring of $K_6$ contains a red $K_3$ (a red triangle) or it contains a blue $K_3$ (a blue triangle).
Question: Prove that $R(3,3)>5$ by showing how to colour the edges of $K_5$ with the colours red and blue so that the resulting graph has no red triangle and no blue triangle.
Take a minute to convince yourself that, for any $s$ and $t$, $R(s,t)=R(t,s)$, since we can always swap the colours red and blue.
Question: What is the value of $R(3,2)$?
Hint: The proof that $R(3,3)\le 6$, from the first lecture contains the answer to this question.
Question: What is the value of $R(s,2)$ for each integer $s\ge 2$?
Question: Prove that, for any integers $s, t\ge 3$, $R(s,t)\le R(s-1,t)+R(s,t-1)$.
Hint: The proof is very similar to the proof that $R(3,3)\le 6$ that, when looked at the right way, shows that $R(3,3)\le R(3,2)+R(2,3)$. The main difference is that, in that proof, we have an assumption, without loss of generality, that $r\ge b$. In the current setting, that assumption is no longer valid so you should split the argument into two cases instead.