\documentclass[10pt,envcountsect]{beamer}

\mode<presentation> {
  \usetheme{Warsaw}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{pstricks}
\usepackage{multicol}



\begin{document}

\title{Episode 20 -- Ramsey numbers}
\subtitle{European section -- Season 2}
\date{}

\begin{frame}
  \titlepage
\end{frame}


\begin{frame}{A party problem}

\Large 
You're organising a party. Some of the guests will know each other, while others won't. For the sake of simplicity, we admit that the relation of knowing each other is symmetric.

What is the least number of guest to invite so that at least $m$ people will mutually know each other, or at least $n$ people will be complete strangers ? 


\end{frame}


\begin{frame}{A very simple party problem}

\LARGE 
What is the least number of guest to invite so that at least $2$ people will mutually know each other, or at least $2$ people will be complete strangers ? 


\end{frame}


\begin{frame}{A simple enough party problem}

\LARGE 
What is the least number of guest to invite so that at least $3$ people will mutually know each other, or at least $2$ people will be complete strangers ? 


\end{frame}


\begin{frame}{A just as simple party problem}

\LARGE 
What is the least number of guest to invite so that at least $2$ people will mutually know each other, or at least $3$ people will be complete strangers ? 


\end{frame}

\begin{frame}{A not so simple party problem}

\LARGE 
What is the least number of guest to invite so that at least $3$ people will mutually know each other, or at least $3$ people will be complete strangers ? 


\end{frame}

\begin{frame}{A difficult party problem}

\LARGE 
What is the least number of guest to invite so that at least $4$ people will mutually know each other, or at least $3$ people will be complete strangers ? 


\end{frame}

\begin{frame}{Mathematical model}

\LARGE Turn this problem into a graph problem.

\end{frame}


\begin{frame}{Complete graphs}

\pause

\begin{center}
\begin{tabular}{ccc}
$K_2$ &  &  \\
\includegraphics[width=3cm]{s02e20/K2.eps} &&\\
 &  &  \\
&& \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Complete graphs}

\begin{center}
\begin{tabular}{ccc}
$K_2$ & $K_3$ &  \\
\includegraphics[width=3cm]{s02e20/K2.eps} &
\includegraphics[width=3cm]{s02e20/K3.eps} &
 \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Complete graphs}

\begin{center}
\begin{tabular}{ccc}
$K_2$ & $K_3$ & $K_4$ \\
\includegraphics[width=3cm]{s02e20/K2.eps} &
\includegraphics[width=3cm]{s02e20/K3.eps} &
\includegraphics[width=3cm]{s02e20/K4.eps} \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Complete graphs}

\begin{center}
\begin{tabular}{ccc}
$K_2$ & $K_3$ & $K_4$ \\
\includegraphics[width=3cm]{s02e20/K2.eps} &
\includegraphics[width=3cm]{s02e20/K3.eps} &
\includegraphics[width=3cm]{s02e20/K4.eps} \\
$K_5$ &  &  \\
\includegraphics[width=3cm]{s02e20/K5.eps} &
& \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Complete graphs}

\begin{center}
\begin{tabular}{ccc}
$K_2$ & $K_3$ & $K_4$ \\
\includegraphics[width=3cm]{s02e20/K2.eps} &
\includegraphics[width=3cm]{s02e20/K3.eps} &
\includegraphics[width=3cm]{s02e20/K4.eps} \\
$K_5$ & $K_6$ &  \\
\includegraphics[width=3cm]{s02e20/K5.eps} &
\includegraphics[width=3cm]{s02e20/K6.eps} &
 \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Complete graphs}

\begin{center}
\begin{tabular}{ccc}
$K_2$ & $K_3$ & $K_4$ \\
\includegraphics[width=3cm]{s02e20/K2.eps} &
\includegraphics[width=3cm]{s02e20/K3.eps} &
\includegraphics[width=3cm]{s02e20/K4.eps} \\
$K_5$ & $K_6$ & $K_7$ \\
\includegraphics[width=3cm]{s02e20/K5.eps} &
\includegraphics[width=3cm]{s02e20/K6.eps} &
\includegraphics[width=3cm]{s02e20/K7.eps} \\
\end{tabular}
\end{center}

\end{frame}

\begin{frame}{Frank P. Ramsey}

\begin{center}
\includegraphics[height=6cm]{s02e20/ramsey.eps}
\end{center}

\end{frame}

\begin{frame}{Ramsey's problem}

\Large

What is the lowest value of $r$ such that when the edges of $K_r$ are colored red or blue, there exists either a
complete subgraph on $m$ vertices which is entirely red, or a complete subgraph on $n$ vertices which is entirely blue. 

\bigskip\pause

This number is a \emph{Ramsey number}, noted $R(m,n)$.

\end{frame}

\begin{frame}{Some simple Ramsey numbers}

\LARGE
\pause

\begin{center}
\begin{minipage}{5cm}

\begin{itemize}
\item $R(2,2)=\pause 2$\pause
\item $R(3,2)=\pause 3$\pause
\item $R(m,2)=\pause m$
\end{itemize}

\end{minipage}
\end{center}

\end{frame}

\begin{frame}{$R(3,3)\geq 5$}

\pause

\begin{multicols}{2}
\includegraphics[width=5cm]{s02e20/K5.eps}
\pause
\includegraphics[width=5cm]{s02e20/K5colored.eps}
\end{multicols}


\end{frame}

\begin{frame}{$R(3,3)=6$}

\large


Suppose the edges of a complete graph on 6 vertices are coloured red and blue. Pick a vertex $v$. 

\begin{center}
\includegraphics[width=5cm]{s02e20/K6.eps}
\end{center}

\end{frame}

\begin{frame}{$R(3,3)=6$}

\large

There are 5 edges incident to $v$ and so (by the pigeonhole principle) at least 3 of them must be the same colour.

\begin{center}
\includegraphics[width=5cm]{s02e20/K6.eps}
\end{center}

\end{frame}

\begin{frame}{$R(3,3)=6$}

\large

Without loss of generality we can assume at least 3 of these edges, connecting to vertices $r$, $s$ and $t$, are blue.
(If not, exchange red and blue in what follows.) 

\begin{center}
\includegraphics[width=5cm]{s02e20/K6.eps}
\end{center}

\end{frame}

\begin{frame}{$R(3,3)=6$}


\large

If any of the edges $rs$, $rt$, $st$ are also blue then we have an entirely blue triangle. 

\begin{center}
\includegraphics[width=5cm]{s02e20/K6.eps}
\end{center}

\end{frame}

\begin{frame}{$R(3,3)=6$}


\large

If not, then those three edges are all red and we have an entirely red triangle.

\begin{center}
\includegraphics[width=5cm]{s02e20/K6.eps}
\end{center}


\end{frame}



\begin{frame}{What about $R(5,5)$ and $R(6,6)$ ?}

\large

Erdös asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of $R(5,5)$ or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value.\pause

But suppose, instead, that they ask for $R(6,6)$. In that case, he believes, we should attempt to destroy the aliens. 



\end{frame}



\end{document}
