\documentclass{beamer}
\usepackage{amsfonts}
\usepackage{amsmath, amssymb}
\usepackage{graphicx}
\usepackage{textpos}
\usepackage{beamerthemeBenny}

\setlength{\TPHorizModule}{1pt}
\setlength{\TPVertModule}{1pt}

\definecolor{blue200}{rgb}{0, 0, 0.784}
\definecolor{red200}{rgb}{0.784, 0, 0}
\definecolor{pogray50}{rgb}{0.5, 0.5, 0.5}
\definecolor{red80}{rgb}{0.8, 0, 0}
\definecolor{green50}{rgb}{0, 0.5, 0}
\definecolor{grayLO}{rgb}{0.6, 0.6, 0.6}
\definecolor{redHI}{rgb}{1, 0, 0}
\definecolor{greenHI}{rgb}{0, 0.8, 0}
\definecolor{blueHI}{rgb}{0, 0, 1}


\newdimen\offsetpoX
\newdimen\offsetpoY
\newcount\opaquenesspo
\newcount\opaquenesspob

\newcommand{\whp}{\textbf{whp}}
\newcommand{\pr}{\mathbb{P}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\bin}{\text{Bin}}
\newcommand{\lsim}{\lesssim}
\newcommand{\gsim}{\gtrsim}
\newcommand{\CR}{\text{cr}}


%\newcommand{\transition}{}
\newcommand{\transition}{\transfade}

\newcommand{\vsp}{\vspace{3mm}}

\def\mathbi#1{\textbf{\em #1}}

\begin{document}

\title{\sc Triples}
\author{\sl \large Po-Shen Loh\\
{\footnotesize Carnegie Mellon University}
}
\date{}



\frame{\titlepage}

\section{Introduction}


\subsection{Puzzle}
\begin{frame}
  \frametitle{\sc Puzzle}
  \transition

  \begin{exampleblock}{\sc \small Valid sequence}
    \hspace{10pt} (1, 1, 1)\\
    \hspace{10pt} (1, 2, 3)\\
    \hspace{10pt} (1, 4, 4)\\
    \hspace{10pt} (2, 5, 1)
    \hfill
    \emph{for every two rows, at least two coordinates increase}
    \hspace{5pt}\mbox{}\\
    \hspace{10pt} (3, 1, 5)\\
    \hspace{10pt} (1, 6, 6)\\
    \hspace{10pt} (2, 7, 8)
  \end{exampleblock}

  \pause

  \begin{alertblock}{\sc \small Question}
    What's the length of longest valid sequence from $\{1, \ldots, L\}$?
  \end{alertblock}

  \pause
  
  \begin{block}{\sc \small Observation}
    The length is at most $L^2$.
  \end{block}

\end{frame}





\subsection{Monotone sequences}
\begin{frame}
  \frametitle{\sc Monotone sequences}
  \transition

  \begin{block}{\sc \small Theorem (Erd\H{o}s-Szekeres 1935)}
    Every permutation of $\{1, \ldots, n\}$ has a monotone subsequence of
    length at least $\sqrt{n}$.
  \end{block}

  \pause

  \begin{exampleblock}{\sc \small Example}
    \begin{center}
      \begin{tabular}[h]{ccccccc}
        1 & 5 & 2 & \textbf{7} & 3 & \textbf{6} & \textbf{4}
      \end{tabular}
    \end{center}
  \end{exampleblock}
  
  \pause

  \noindent \textbf{Proof.} Under each number, write lengths of longest
  increasing and decreasing subsequences ending there.

  \begin{center}
    \begin{tabular}[h]{c|ccccccc}
      & \textbf{1} & \textbf{5} & \textbf{2} & \textbf{7} & \textbf{3} &
      \textbf{6} & \textbf{4} \\
      \hline
      inc. & 1 & 2 & 2 & 3 & 3 & 4 & 4 \\
      dec. & 1 & 1 & 2 & 1 & 2 & 2 & 3 
    \end{tabular}
  \end{center}
  
\end{frame}




\subsection{Ordered Ramsey Theory}
\begin{frame}
  \frametitle{\sc Ordered Ramsey Theory}
  \transition

  \begin{block}{\sc \small Proposition}
    Every 2-coloring of edges of $K_{\{1, \ldots, n\}}$ has a monochromatic
    forward path of length at least $\sqrt{n}$.
  \end{block}

  \pause

  \textbf{Proof.} Under each vertex, write lengths of longest
  red/blue paths ending there.

  \centerline{\includegraphics[width=0.5\linewidth]{kn-2col}}

  \pause

  \textbf{Tight:}

  \centerline{\includegraphics[width=0.5\linewidth]{kn-2col-tight}}
  
\end{frame}



\subsection{Ordered Ramsey Theory}
\begin{frame}
  \frametitle{\sc Ordered Ramsey Theory}
  \transition

  \begin{block}{\sc \small Proposition}
    Every 3-coloring of edges of $K_{\{1, \ldots, n\}}$ has a monochromatic
    forward path of length at least $\sqrt[3]{n}$.
  \end{block}

  \pause

  \noindent \textbf{Proof.} Under each number, write lengths of longest
  red/blue/green paths ending there.

  \centerline{\includegraphics[width=0.5\linewidth]{kn-3col}}

  \pause

  \textbf{Tight:}

  \centerline{\includegraphics[width=0.5\linewidth]{kn-3col-tight}}

  
\end{frame}


\subsection{$3-1\neq 1$}
\begin{frame}
  \frametitle{$3-1\neq 1$}
  \transition

  \begin{block}{\sc \small Proposition}
    Every 3-coloring of edges of $K_{\{1, \ldots, n\}}$ has a non-rainbow
    forward path of length at least $\sqrt[3]{n}$.
  \end{block}

  \pause

  \noindent \textbf{Proof.} Under each number, write lengths of longest
  red-free/blue-free/green-free paths ending there.

  \centerline{\includegraphics[width=0.5\linewidth]{kn-3col2}}

  \pause

  \begin{block}{\sc \small Already Deduced}
    Every 3-coloring of edges of $K_{\{1, \ldots, n\}}$ has a non-rainbow
    forward path of length at least $\sqrt{n}$.
  \end{block}
  
\end{frame}




\subsection{Construction}
\begin{frame}
  \frametitle{\sc Construction}
  \transition

  \begin{block}{\sc \small Already Deduced}
    Every 3-coloring of edges of $K_{\{1, \ldots, n\}}$ has a non-rainbow
    forward path of length at least $\sqrt{n}$.
  \end{block}

  \pause

  \begin{block}{\sc \small Proposition}
    There is a 3-coloring of edges of $K_{\{1, \ldots, n\}}$ where all
    non-rainbow forward paths have length at most $n^{2/3}$.

    \medskip

    \centerline{\includegraphics[width=0.5\linewidth]{kn-3col-tight}}
  \end{block}

  \pause

  \begin{block}{\sc \small Corollary}
    There is a valid sequence of triples of length at least $L^{3/2}$.
  \end{block}

  \pause

  \begin{block}{\sc \small Observation}
    Every valid sequence of triples has length at most $L^2$.
  \end{block}
  
\end{frame}


\subsection{$k$-majority tournaments}
\begin{frame}
  \frametitle{\sc $k$-majority tournaments}
  \transition

  \begin{exampleblock}{\sc \small Definition}
    Given $n$ vertices, and $2k-1$ preference orderings on them
    (permutations of $1,\ldots,n$), the $k$-majority tournament has
    $\overrightarrow{ij}$ when majority of orderings prefer $i$ over $j$.
  \end{exampleblock}

  \bigskip

  \pause

  Much research on these objects, from
  \begin{itemize}
    \item social choice theory
    \item extremal combinatorics
  \end{itemize}

  \pause

  \bigskip

  \begin{block}{\sc \small Application to Ramsey}
    Potential source of constructions: control size of largest transitive
    subtournament.
  \end{block}
  
\end{frame}



\subsection{Ramsey}
\begin{frame}
  \frametitle{\sc Ramsey}
  \transition

  \begin{block}{\sc \small Theorem (Erd\H{o}s-Szekeres)}
    Every 2-coloring of edges of $K_n$ contains a monochromatic clique of
    order at least $\frac{1}{2} \log_2 n$.
  \end{block}

  \pause

  \begin{block}{\sc \small Theorem (Erd\H{o}s), probabilistic method}
    There is a 2-coloring of the edges of $K_n$ where all monochromatic
    cliques have order at most $2 \log_2 n$.
  \end{block}

  \pause

  \begin{alertblock}{\sc \small Challenge}
    Discover interesting new Ramsey constructions, esp.\ explicit.
  \end{alertblock}
  
\end{frame}



\subsection{Ramsey Constructions}
\begin{frame}
  \frametitle{\sc Ramsey constructions}
  \transition

  \textbf{Vertex set.} $n = r^{2k-1}$, write as $(2k-1)$-tuples from $1,
  \ldots, r$.

  \bigskip
  \pause

  \textbf{Preference orderings.} $2k-1$ in total
  
  \begin{enumerate}
    \item Lexicographic.
      \pause
    \item Lexicographic, coordinates prioritized 2, 3, \ldots, $r$, 1.
      \pause
    \item Lexicographic, coordinates prioritized 3, 4, \ldots, $r$, 1, 2.
    \item etc.
  \end{enumerate}
  
  \pause

  \emph{Other orderings of less-significant coordinates should be used.}

  \pause

  \begin{block}{\sc \small Special transitive subtournaments}
    If no tiebreaks necessary, for every two tuples, the later one is
    greater in at least half the coordinates.
  \end{block}

\end{frame}




\subsection{Result}
\begin{frame}
  \frametitle{\sc Result}
  \transition

  \begin{block}{\sc \small Corollary}
    There is a valid sequence of triples of length at least $L^{3/2}$.
  \end{block}


  \begin{block}{\sc \small Observation}
    Every valid sequence of triples has length at most $L^2$.
  \end{block}
  
  \pause
  \bigskip

  \begin{block}{\sc \small Theorem (L.)}
    There is a valid sequence of triples of length at most $L^2 / \log^* L$.
  \end{block}

  \begin{exampleblock}{\sc \small Definition}
    Tower function $T(n) = 2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}$. Inverse
    function is $\log^* n$.
  \end{exampleblock}
\end{frame}


\section{Proof}

\subsection{Auxiliary graph}
\begin{frame}
  \frametitle{\sc Auxiliary graph}
  \transition

  \centerline{\includegraphics[width=0.7\linewidth]{graph-def}}
  
\end{frame}


\subsection{Matching}
\begin{frame}
  \frametitle{\sc Matching}
  \transition

  \begin{block}{\sc \small Observation}
    Same-labeled edges form a matching.
  \end{block}

  \textbf{Proof.}

  \centerline{\includegraphics[width=0.7\linewidth]{graph-matching}}

\end{frame}



\subsection{Non-crossing matching}
\begin{frame}
  \frametitle{\sc Non-crossing matching}
  \transition

  \begin{block}{\sc \small Observation}
    Same-labeled edges form a non-crossing matching.
  \end{block}

  \textbf{Proof.}

  \centerline{\includegraphics[width=0.7\linewidth]{graph-noncross-matching}}

\end{frame}



\subsection{Induced matching}
\begin{frame}
  \frametitle{\sc Induced matching}
  \transition

  \begin{block}{\sc \small Observation}
    Same-labeled edges form an induced matching.
  \end{block}

  \textbf{Proof.}

  \centerline{\includegraphics[width=0.7\linewidth]{graph-induced-matching}}

\end{frame}


\subsection{Ruzsa-Sz\'emeredi}
\begin{frame}
  \frametitle{\sc Ruzsa-Sz\'emeredi}
  \transition

  \begin{alertblock}{\sc \small Question}
    Given a graph with $2n$ vertices, where edges can be decomposed into
    $n$ induced matchings. What is maximum possible number of edges?
  \end{alertblock}

  \bigskip
  \pause

  \begin{block}{\sc \small Theorem (Ruzsa-Sz\'emeredi)}
    Maximum is $n^2 / \log^* n$ edges.
  \end{block}

  \pause

  \begin{block}{\sc \small Theorem (Fox)}
    Maximum is $n^2 / e^{\log^* n}$ edges.
  \end{block}

  \pause

  \begin{block}{\sc \small Theorem (Ruzsa-Sz\'emeredi)}
    It is possible to achieve $n^2 / e^{\sqrt{\log n}}$ edges.
  \end{block}

\end{frame}



\subsection{Sigma-free}
\begin{frame}
  \frametitle{\sc $\Sigma$-free matching}
  \transition

  \begin{block}{\sc \small Observation}
    Same-labeled edges form a $\Sigma$-free matching.
  \end{block}

  \textbf{Proof.}

  \centerline{\includegraphics[width=0.7\linewidth]{graph-sigmafree-matching}}

\end{frame}




\subsection{Ruzsa-Sz\'emeredi generalizations}
\begin{frame}
  \frametitle{\sc Ruzsa-Sz\'emeredi generalizations}
  \transition

  \begin{alertblock}{\sc \small Question}
    Given a graph with $2n$ vertices, where edges can be decomposed into
    $n$ matchings that are $\Sigma$-free. What is maximum possible number
    of edges?
  \end{alertblock}

  \pause

  \begin{block}{\sc \small Proposition}
    If also forbid ``floppy'' $\Sigma$, max number of edges is at most
    $n^{3/2}$.
  \end{block}

  \pause

  \begin{alertblock}{\sc \small Question}
    Given a graph with $2n$ vertices, where edges can be decomposed into
    $n$ matchings that are  $\xi$-free. What is maximum possible number of
    edges?
  \end{alertblock}

  \medskip

  \emph{Any improved bound transfers to triples problem.}


\end{frame}

\end{document}
