\makeatletter\let\ifGm@compatii\relax\makeatother
\documentclass[red]{beamer}
%\usepackage{beamerthemesplit}
\usepackage{url}
\usepackage{listings}
\usepackage{comment}
\usepackage{mathdots}
\usepackage{tikz}
\usetikzlibrary{graphs,graphs.standard,automata,positioning,arrows}
\usepackage{bm}
\newcommand{\COL}{{\rm COL}}

\DeclareMathOperator{\FC}{FC}
\DeclareMathOperator{\INT}{INT}
\DeclareMathOperator{\GAPS}{GAPS}
\DeclareMathOperator{\MATRIX}{MATRIX}
\DeclareMathOperator{\sign}{sign}

% This
% ANY LATEX paper.  Typically I'll use this file and some other file in the
% directory of the paper, this one for general math things, that one for
% things specific to that paper.
%
% font's used and general paper things.

\newcommand{\ERIN}{\isred{ERIN: }}
\newcommand{\BILL}{\isred{BILL: }}
\newcommand{\SQ}{{\rm SQ}}
\newcommand{\el}{\ell} 
\newcommand{\IO}{\exists^\infty}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\st}{\mathrel{:}}


\newcommand{\vp}[1]{\vec p_{#1}}
\newcommand{\vx}[1]{\vec x_{#1}}
\newcommand{\va}[1]{\vec a_{#1}}

\xdefinecolor{darkgreen}{rgb}{0, 0.50, 0}
\newcommand{\EVEN}{\rm EVEN}
\newcommand{\ODD}{\rm ODD}
\newcommand{\into}{\rightarrow}
\newcommand{\degg}{{\rm deg}}
\newcommand{\es}{\emptyset}
\newcommand{\spec}{{\rm spec}}
\newcommand{\bigfloor}[1]{{\biggl\lfloor {#1} \biggr\rfloor}}
\newcommand{\bigceiling}[1]{{\biggl\lceil {#1} \biggr\rceil}}
\newcommand{\isred}[1]{{\color{red} {\bf #1}}} 
\newcommand{\isblue}[1]{{\color{blue}{\bf #1}}} 
\newcommand{\isgreen}[1]{{\color{green} {#1}}} 

\newcommand{\isdarkgreen}[1]{{\color{darkgreen}{\bf #1}}} 
\newcommand{\isorange} [1]{{\color{orange} {\bf #1}}} 


\newcommand{\isdef}[1]{{\color{blue} {#1}}} 
\newcommand{\iscase}[1]{{\color{blue} {#1}}} 
\newcommand{\isnote}[1]{{\color{blue} {#1}}} 
\newcommand{\isexample}[1]{{\color{orange} {#1}}} 
\newcommand{\R}{\isred{R}} 
\newcommand{\B}{\isblue{B}} 
\newcommand{\G}{\color{darkgreen} G} 
\newcommand{\Y}{\color{purple} P} 

\newcommand{\RR} {\color{red} R}
\newcommand{\BB} {\color{blue} B}
\newcommand{\GG} {\color{green} G}
\newcommand{\YY} {\color{yellow} Y}

\newcommand{\RED} {\isred{RED} }
\newcommand{\REDns} {\isred{RED}}
\newcommand{\BLUE} {\isblue{BLUE} }
\newcommand{\BLUEns} {\isblue{BLUE}}


\newcommand{\itr}[1]{\color{red} {#1}}
\newcommand{\itb}[1]{\color{blue} {#1}}


\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\reals}{{\mathbb R}}
\newcommand{\sphere}{{\mathbb S}}
\newcommand{\complex}{{\mathbb C}}
\newcommand{\Rpos}{{\mathbb R}^+}
\newcommand{\ie}{\hbox{ i.e.  }}
\newcommand{\eg}{\hbox{ e.g.  }}


\newcommand{\Kobler}{K\"obler}
\newcommand{\Schoning}{Sch\"oning}
\newcommand{\Toran}{Tor\'an}
\newcommand{\Balcazar}{Balc{\'a}zar}
\newcommand{\Diaz}{D\'{\i}az}
\newcommand{\Gabarro}{Gabarr{\'o}}
\newcommand{\Laszlo}{L{\'a}szl{\'o}}
\newcommand{\Erdos}{Erd\"os }
\newcommand{\Erdosns}{Erd\"os}
\newcommand{\Sarkozy}{S{\'a}rk{\"o}zy }
\newcommand{\Sarkozyns}{S{\'a}rk{\"o}zy}
\newcommand{\Szekely}{Sz{\'e}kely }
\newcommand{\Szekelyns}{Sz{\'e}kely}
\newcommand{\Szemeredi}{Szemer{\'e}di }
\newcommand{\Szemeredins}{Szemer{\'e}di}
\newcommand{\Holder}{H{\"o}lder }
\newcommand{\Holderns}{H{\"o}lder}
\newcommand{\Chv}{Chv{\'a}tal }
\newcommand{\Chvns}{Chv{\'a}tal}




\begin{document}




\setbeamercolor{alerted_text}{fg=cyan}
\xdefinecolor{purplish}{cmyk}{0.75,0.75, 0, 0}
\xdefinecolor{purple}{cmyk}{0.75,0.75, 0, 0}
\colorlet{newred}{red!60!black}

\title{\bf There Is a 2-Coloring Of the Plane Without a mono Red 2-Stick or a mono Blue Big-Stick} 

\author{
\bf Exposition by William Gasarch-U of MD
}

\date{}

\maketitle

\begin{frame}\frametitle{\bf Credit Where Credit is Due}

The main result in these slides is due to Szlam (2001) and Conlon and Fox (2017). 

\end{frame} 


\begin{frame}\frametitle{\bf Recall the Notation $\mathbf{\reals^2\into (\el_a,\el_b)}$}

\isblue{Notation} Let $a,b\ge 2$.  $\reals^2 \into (\el_n,\el_m)$ means

\pause
\smallskip
For all $\COL \colon \reals^2 \into [2]$ there exists \isred{Red $\el_n$}  or \isblue{Blue $\el_m$}.

\pause
\smallskip
What about $\reals^2\into (\el_2,\el_b)$ with $b\ge 3$. 


\pause
\smallskip
We show the following (mod some lemmas):

\pause
\smallskip
There exist $d$, for all $n$, $\reals^n\into (\el_2,\el_{2^{dn}}))$ (Szlam 2001). 

\pause
\smallskip
There exists $d$, for all $n$, $\reals^2\not\into (\el_2,\el_{2^{dn}})$ (Conlon-Wu, 2017).
\end{frame} 


\begin{frame}\frametitle{\bf Main Result I}

Over the next few (many?) slides we will show

\pause
\smallskip

There exist $d$, for all $n$, $\reals^n\into (\el_2,\el_{2^{dn}}))$ (Szlam 2001). 

\end{frame}


\begin{frame}\frametitle{\bf Chromatic Number of $\reals^n$}

\isblue{Definition} $c(n)$ is the least number $c$ such that there exists

$$\COL \colon \reals^n \into [c]$$

with no mono unit stick. .

\pause
\smallskip

We will need a lower bound on $c(n)$. 

\end{frame} 


\begin{frame}\frametitle{\bf Lemma Needed For Lower Bound on $c(n)$}

\pause 
\isblue{Lemma} 

\pause 

Let $q$ be a prime power. Let $k\in\N$. 

\pause 

Let $F_1,\ldots,F_{\binom{[n]}{q-1}+1}\in \binom{[n]}{2q-1}$.

\pause 
Then there exists $1\le i<j\le \binom{[n]}{q-1}+1$ with 

$$|F_i\cap F_j|=q-1.$$
\end{frame}

\begin{frame}\frametitle{\bf Lower Bound on Chromatic Number of $\reals^n$}

\isblue{theorem}
For all $n$, 
$$c(n)>\ceil{\max_{q \hbox{ prime power}} \frac{\binom{n}{2q-1}}{\binom{n}{q-1}+1}}$$

\bigskip
\pause
Let $\COL \colon \reals^n \into [c(n)]$. 

\bigskip
\pause
We will define a finite set of points $S\subseteq \reals^n$ and then restrict 
$\COL$ to $S$. 
\end{frame}

\begin{frame}\frametitle{\bf The set $S$ and a Set System}

\pause 

Let $S\subseteq \reals^n$ be all of the vectors such that
\begin{itemize}
\item
$n-2q-1$ of the components are 0.
\item
$2q-1$ of the components are $\frac{1}{\sqrt{2q}}$.
\end{itemize}

Let $F \colon S\into \binom{[n]}{2q-1}$ by viewing each vector in $S$ as a bit vector
though with $\frac{1}{\sqrt{2q}}$ instead of 1.

\end{frame}

\begin{frame}\frametitle{\bf Claim about $S$ and $F$ and Proof}
\pause
\isblue{Claim} Let $u,v\in S$. If $|F(u)\cap F(v)|=f$ then $d(u,v)=2-\frac{f+1}{q}$. 
Hence $d(u,v)=1$ iff $|F(u)\cap F(v)|=q-1$. 

\pause
Assume $|F(u)\cap F(v)|=f$ then:

\pause
There are $f$ coordinates where $u$ and $v$ both have $\frac{1}{\sqrt{2q}}$.

\pause
There are $2q-1-f$ coordinates where $u$ has $\frac{1}{2q}$ and $v$ has 0.

\pause
There are $2q-1-f$ coordinates where $v$ has $\frac{1}{2q}$ and $u$ has 0.

\pause
There are $n-4q+f+2$ coordinates where $u$ and $v$ are both 0.

\pause
Hence $d(u,v)= 2\times (2q-1-f)\times \frac{1}{2q} = \frac{2q-1-f}{q} = 2-\frac{f+1}{q}$. 

\end{frame} 


\begin{frame}\frametitle{\bf Finish the Proof}

\pause
Restrict $\COL$ to $S$. 

\pause

Since $|S|=\binom{n}{2q-1}$ and there are $c$ colors, RED  must occur 

$$\ge \binom{n}{2q-1}/c = \binom{n}{q-1}+1 \hbox{ times }$$

\pause
Let $S'$ be the subset of $S$ that has that color. 

\pause 
Since $S'\subseteq \binom{[n]}{2q-1}$ and $|S'|\ge \binom{n}{q-1}+1$.

\pause
By Lemma there exists two elements of $S$ with intersection of size $q-1$,
say  $F(u)$ and $F(v)$. 

\pause
Since $|F(u)\cap F(v)|=q-1$, by the Claim, $d(u,v)=1$. 

\end{frame} 

\begin{frame}\frametitle{\bf So What is $c(n)$ Really?}

\pause 

From 
$$c(n)>\ceil{\max_{q \hbox{ prime power}} \frac{\binom{n}{2q-1}}{\binom{n}{q-1}+1}}$$

\pause

\begin{itemize}
\item
One can show there exists $d$, for all $n$,  $c(n)\ge 2^{dn}$. 
(KELIN- HAVE WE DONE THAT YET?)
\item
Kelin plotted the graph and it seems that $c(n)\le 2.54 \times 2^{0.266n}$. 
\end{itemize}
\end{frame}

\begin{frame}\frametitle{\bf $\reals^n\into (\el_2,\el_{2^{dn}})$}

\isblue{Theorem} There exists $d$ such that $\reals^n\into (\el_2,\el_{2^{dn}})$. 

\pause
Let $\COL \colon \reals^n \into [2]$. 

\pause 
There exists $d$, $c(n)>2^{dn}$. Let $m=2^{dn}$. 

\pause 
$\vec 1$ is the vector $(1,0,\ldots,0)$ in $\reals^n$. 

\pause
\isblue{Case 1} There is a BLUE $\el_m$. Done

\pause
\isblue{Case 2} There is no BLUE $\el_m$. See next slide.

\end{frame}

\begin{frame}\frametitle{\bf $\reals^n\into (\el_2,\el_{2^{dn}})$ Case 2}

\pause
\isblue{Case 2} There is no BLUE $\el_m$. We form a coloring $\COL \colon \reals^n \into [m]$ as follows:

\pause 
Given point $p\in \reals^n$ look at

$$p+\vec 1, p+ 2\vec 1, \ldots, p+ m\vec 1.$$

\pause 

Since there is no BLUE $\el_m$, there exists $i$ such that $\COL(p+i\vec 1)$ is RED. 

\pause 
Color $p$ with the least such $i$. 

\pause 

Since $c(n)> 2^{dn}$, $\exists$ $u,v\in\reals^n$ and $1\le i\le m$ such that 

\pause 
$d(u,v)=1$, and

\pause 
$u,v$ are the same color. 

\pause 
Hence $u+i\vec 1$ and $v+i\vec 1$ are both RED.
They form a RED $\el_2$. 
\end{frame}

\end{document} 

