\documentclass[17pt, landscape]{foils}
\usepackage{amssymb, amsthm,graphics}

\addtolength{\textwidth}{2cm}
\addtolength{\hoffset}{-1cm}
\addtolength{\textheight}{2cm}
\addtolength{\voffset}{-1cm}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}

\newcommand{\Z}{\mathbb Z}

\begin{document}
\title{Coloring Cubic Graphs by Steiner Triple Systems}
\date{January 15, 2004}
\author{D\'avid P\'al}
\maketitle

\begin{center}
advisor Martin \v Skoviera\\

\bigskip
\includegraphics{projective15.pdf}

\bigskip
Comenius University

\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Ordinary Edge Colorings}

%% obrazok kubickeho grafu ofarbeneho troma farbami.

\begin{itemize}
\item Let $G$ be a cubic graph. 
\item Using some set of colors we color its egdes.
\item The colors of the edges meeting at a vertex must be all distinct.
\end{itemize}

%% \bigskip

\begin{theorem}[Vizing, 1964]
Cubic graph can be colored by either 3 or 4 colors.
\end{theorem}

\begin{figure}
\begin{center}
\includegraphics{cubic}
\hspace{3cm}
\includegraphics{petersen}
\end{center}
\caption{Three-sided prism and the Petersen graph}
\end{figure}

Graphs that need 4 colors are called \emph{Snarks}.
Snarks include all graphs with a bridge, Petersen graph and infinitely
many others.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Steiner Triple Systems}

\begin{itemize}
\item We would like somehow to extend ordinary 3-colorings, to be able to color (some) Snarks.
\item We allow more than one triple of colors of egdes at a vertex.
\item Two colors should determine third.
\end{itemize}

\begin{figure}
\begin{center}
\includegraphics{23}
\end{center}
\caption{Green edge and blue edge imply color of the third red edge.}
\end{figure}

\bigskip

\begin{definition}
\emph{Steiner triple system} (STS for short) $\mathcal S$ is a tuple $\mathcal S = (P, T)$.
$P$ is set of finite set of points (contaning at least three
elements). $T$ is system of 3-element-subsets of points such that each
pair of points is contained in exactly one set of $T$.
\end{definition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Examples of Steiner Triple Systems}

\begin{itemize}
\item Trivial STS $= (\{1,2,3\},\{\{1,2,3\}\})$.
\item Fano plane $\mathcal F = PG(2,2) = (\Z_2 \times \Z_2 \times \Z_2
- \{0,0,0\}, \{\{x,y,z\} \ |\ x+y+z = 0 \} )$

\end{itemize}

\begin{figure}
\begin{center}
\includegraphics{fano-plane}
\end{center}
\caption{Fano plane}
\end{figure}


\begin{figure}
\begin{center}
\includegraphics{aff9}
\end{center}
\caption{Affine plane AG(2,3)}
\end{figure}

Affine plane $AG(2,3) = (\Z_3 \times \Z_3, \{\{x,y,z\} \ |\ x+y+z = 0\} )$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Configurations in STS}

Combinatorial designers deal also with configurations in Steiner
triple systems. For example $C_{15}$ can be found in every nontrivial
system.

\begin{figure}
\begin{center}
\includegraphics{C14}
\hspace{3cm}
\includegraphics{C15}
\end{center}
\caption{Cofingurations $C_{14}$ and $C_{15}$.}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Steiner Colorings}

\begin{definition}
Let $G=(V,E)$ be cubic graph and let $\mathcal S = (P,T)$ be Steiner
triple system. \emph{Steiner coloring} is a map $\phi : E
\to P$ such that colors of the three incident edges at each vertex form
a triple of $\mathcal S$.
\end{definition}

The general question is: "Which systems color which graphs?".

\begin{figure}
\begin{center}
\includegraphics{bridge}
\end{center}
\caption{Graph with a bridge colored by the affine plane AG(2,3)}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Known Results and Open Problems}

{\large Known results}

\begin{itemize}
\item There exists a system of order 381 that colors all the cubic graphs.
\item Every nontrivial system colors all bridgeless graphs.
\item Projective systems cannot color graphs with bridges.
\item Decision problem "Is given graph is a Snark?" is NP-complete.
\end{itemize}

{\large Open problems}

\begin{itemize}
\item What is the smallest system that colors everything?
\item What can be colored by affine systems?
\item Minimize the number of triples used in a coloring.
\item What configurations can color what?
\item Find effective (i.e. polynomial) coloring algorithms.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Connection with Perfect Matchings}

\begin{theorem}[Petersen, 1891]
Every bridgeless cubic graph has a perfect matching.
\end{theorem}

\begin{figure}
\begin{center}
\includegraphics{matching.pdf}
\caption{Perfect matching in the Petersen graph}
\end{center}
\end{figure}

\bigskip

\begin{conjecture}[Fan-Raspaud, 1994]
Every bridgeless cubic graph contains three perfect matchings with empty intersection.
\end{conjecture}

\bigskip

\begin{conjecture}[Berge-Fulkerson]
Every bridgeless cubic graph contains six perfect matchings such that
each edge appears in exactly two of them.
\end{conjecture}

Both these conjectures can be formulated in terms of Steiner colorings
(or coloring by configurations).

\end{document}

