
\documentclass{beamer}

\usetheme{Warsaw}
\setbeamercovered{transparent}
\setbeamertemplate{navigation symbols}{}

\let\fact\relax
\let\note\relax

\usepackage{uwbgeom}
\usepackage[latin2]{inputenc}
\usepackage[mathscr]{euscript}
\usepackage{graphics}

\title{Hall triple systems}
\author[Mariusz Żynel]{Mariusz Żynel\\ \texttt{mariusz@math.uwb.edu.pl}}
\institute{%
    University of Białystok\\
    Institute of Mathematics}
\date[Ustroń 2012]{XIX-th Conference Geometry, Graphics, Computer, Ustroń 2012}

%% Private notation

\let\goth\mathfrak
\DeclareMathOperator{\STS}{STS}
\DeclareMathOperator{\SSys}{S}
\DeclareMathOperator{\GF}{GF}
\DeclareMathOperator{\PG}{PG}
\DeclareMathOperator{\AG}{AG}

\newenvironment{cmath}{%
  \par
  \smallskip
  \centering
  $
}{%
  $
  \par
  \smallskip
  \csname @endpetrue\endcsname
}

\newenvironment{ctext}{%
  \par
  \smallskip
  \centering
}{%
 \par
 \smallskip
 \csname @endpetrue\endcsname
}

\def\sts{{\sf S}}
\def\triop{\circledcirc}

\def\vebconf{{\sf C}_{16}}
\def\antipasz{{\sf C}_{14}}
\def\antinet{{\sf C}_{S}^{1}}
\def\antimitraa{{\sf C}_{A}}
\def\antimitrax{{\sf C}_{S}^2}



\begin{document}

\frame[plain]{\titlepage}

\section{Introduction}


\subsection{Motivations and references} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
  \frametitle{Motivations and references}
  \makebox[\linewidth]{\parbox{12.5cm}{%
  \begin{thebibliography}{9}\setlength{\leftmargin}{-5pt}
  \bibitem<1->{steiner}
    {\color{black} Steiner J.,}\\
    {\it Combinatorische Aufgabe},\\
    {\color{black} Journal für die Reine und Angewandte Mathematik, {\bf 45} (1853), 181--182.}
  \bibitem<2->{hall}
    {\color{black} M. Hall, Jr.,}\\
    {\it Automorphisms of Steiner triple systems},\\
    {\color{black} IBM J. Res. Develop. {\bf 4(5)} (1960), 460--472.}
  \bibitem<3->{czesi}
    {\color{black} D. Kr{\'a}l, E. M{\'a}\u{c}ajov{\'a}, A. P{\'o}r, J.-S. Sereni,}\\
    {\it Characterization of affine Steiner triple systems and Hall triple systems},\\
    {\color{black} Electronic Notes in Discrete Math. {\bf 29} (2007), 17--21.}
  \bibitem<4->{forbid}
    {\color{black} K. Petelczyc, M. Prażmowska, K. Prażmowski, M. Żynel,}\\
    {\it A note on characterizations of affine and Hall triple systems},\\
    {\color{black} Discrete Math. {\bf 312(15)} (2012), 2394--2396.}
  \end{thebibliography}}}
\end{frame}


\subsection{A bit of history} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse

\begin{frame}
  \frametitle{From music to combinatorics and geometry}
  \begin{itemize}
  \item[1844]
    Woolhouse poses a prize question \#1733 in the 
    \emph{Lady's and Gentlemen's Diary}.
  \item[1847]
    Kirkman solves the problem and publishes his results in 
    \emph{Cambridge and Dublin Mathematical Journal}.
  \item[1850]
    Kirkman poses a so called \structure{schoolgirl problem} in the 
    \emph{Lady's and Gentlemen's Diary}.
  \item[1853]
    Steiner independently reintroduces triple systems in 
    \emph{Journal für die Reine und Angewandte Mathematik}.
  \item[2004]
    Kaski and \"Osterg\r{a}rd compute the number of non-isomorphic 
    Steiner triple systems of order 19.
  \end{itemize}
\end{frame}

\fi

\begin{frame}
  \frametitle{Kirkman's schoolgirl problem}
  \begin{block}<1->{The problem (1850)}
    Fifteen young ladies in a school walk out three side by side for seven days
    in succession: it is required to arrange them daily so that no two shall
    walk twice side by side.
  \end{block}
  \begin{block}<2->{One of solutions}
    \begin{center}
      \tiny
      \begin{tabular}{ccccccc}
      Sunday 	   & Monday       & Tuesday      & Wednesday    & Thursday     & Friday       & Saturday    \\
      \hline
      01, 06, 11   & 01, 02, 05   & 02, 03, 06   & 05, 06, 09   & 03, 05, 11   & 05, 07, 13   & 11, 13, 04  \\
      02, 07, 12   & 03, 04, 07   & 04, 05, 08   & 07, 08, 11   & 04, 06, 12   & 06, 08, 14   & 12, 14, 05  \\
      03, 08, 13   & 08, 09, 12   & 09, 10, 13   & 12, 13, 01   & 07, 09, 15   & 09, 11, 02   & 15, 02, 08  \\
      04, 09, 14   & 10, 11, 14   & 11, 12, 15   & 14, 15, 03   & 08, 10, 01   & 10, 12, 03   & 01, 03, 09  \\
      05, 10, 15   & 13, 15, 06   & 14, 01, 07   & 02, 04, 10   & 13, 14, 02   & 15, 01, 04   & 06, 07, 10  \\
      \hline
      \end{tabular}
    \end{center}
  \end{block}
\end{frame}


\subsection{Steiner triple systems} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[shrink=10]
  \frametitle{Definition of a Steiner triple system}
  \begin{dfn}[Basic]<1->
    A \structure{Steiner Triple System} (STS) is a structure
    $\struct{S,\Lines}$, where  $S$ is a set whose elements are called
    \emph{points}, and the set $\Lines$ consists  of triples of $S$ called
    \emph{lines} (\emph{blocks}) such that every pair of points appears in a
    unique line. 
  \end{dfn}
  \begin{block}{}
    A Steiner triple system of $n$ points is said to be of \emph{order} $n$ and is
    denoted shortly by $\STS(n)$.
  \end{block}
  \begin{dfn}[General]<2->
    A \structure{Steiner system} with parameters $t, k, n$, written $\SSys(t,k,n)$, 
    is an $n$-element set $S$ together with a set of $k$-element subsets of $S$ called 
    \emph{blocks} with the property that each $t$-element subset of $S$ is contained in 
    exactly one block. 
  \end{dfn}
  \begin{block}{}<2->
    A Steiner triple system $\STS(n)$ is a $\SSys(2,3,n)$ Steiner system.
  \end{block}
\end{frame}

\begin{frame}
  \frametitle{Examples: Finite projective plane}
  \centering\includegraphics{fig-fpp.png}
  \par
  Projective plane of order 2 (Fano configuration), $\PG(2,2)$, $\STS(7)$.
  
  \bigskip

  Generally: a finite projective plane of order $q$, with the lines as blocks, is
  a Steiner system $\SSys(2, q+1,q^2+q+1)$.
\end{frame}

\begin{frame}
  \frametitle{Examples: Finite affine plane}
  \centering\includegraphics{fig-fap.png}
  \par
  Affine plane of order 3, $\AG(2,3)$, $\STS(9)$.
  
  \bigskip  
    
  Generaly: a finite affine plane of order $q$, with the lines as blocks, is 
  a Steiner system $\SSys(2, q, q^2)$.
\end{frame}

\begin{frame}
  \frametitle{Known facts}
  \begin{thm}<1->
    A Steiner triple system of order $n$ exists if and only if 
    \begin{cmath}
      n\equiv 1, 3\mod 6.
    \end{cmath}   
  \end{thm}
  
  \begin{block}{Known Steiner triple systems}<2->
    \begin{center}
      \begin{tabular}{cc}
        order & non-isomorphic STSs \\
        \hline
        3  & 1\\
        7  & 1\\
        9  & 1\\
        13 & 2\\
        15 & 80\\
        19 & 11 084 874 829\\
        \hline
      \end{tabular}
    \end{center}
  \end{block}
\end{frame}


\subsection{Hall triple systems}

\begin{frame}
  \frametitle{Definition of a Hall triple system}
  \begin{dfn}<1->
    A \structure{Hall Triple System} (HTS) is a Steiner triple system  where for
    every point $x$ there is a reflection in $x$ (i.e.\ an involutory automorphism
    that fixes exactly the point $x$).
  \end{dfn}
  \begin{thm}<2->
    A Steiner triple system is a Hall triple system iff any subsystem generated 
    by three non-collinear points is an affine plane $\AG(2, 3)$.
  \end{thm}
  \begin{dfn}<3->
    An \structure{Affine Triple System} (ATS) is an affine space over $\GF(3)$.
    It is a Steiner triple system.
  \end{dfn}  
\end{frame}


\section{Forbidden configurations}

\subsection{Mitre and anti-mitre}

\begin{frame}
  \frametitle{Mitre and variations of anti-mitre configurations}
  \centering\includegraphics{fig-mitre.png}
  \par
  \medskip
  Mitre, anti-mitre $\antimitraa$, $\antimitrax$, and another visualization of $\antimitrax$.
  \par
  \begin{thm}<2->
    An STS contains $\antimitrax$ iff it contains $\antimitraa$.
  \end{thm}
\end{frame}

\subsection{Pasch and anti-Pasch}

\begin{frame}
  \frametitle{Pasch and anti-Pasch configurations}
  \centering\includegraphics{fig-pasch.png}
  \par
  \medskip
  Pasch configuration $\vebconf$ and anti-Pasch configuration $\antipasz$.
  \par
  \begin{thm}<2->
    An STS is an HTS iff it does not contain any $\vebconf$ or $\antimitrax$ subconfiguration. 
  \end{thm}
\end{frame}

\subsection{Net and anti-net}

\begin{frame}
  \frametitle{Net and anti-net configurations}
  \centering\includegraphics{fig-net.png}
  \par
  \medskip
  Net configuration and anti-net configuration $\antinet$.
  \par
  \begin{thm}<2->
    An HTS is affine iff it does not contain any $\antinet$ subconfiguration. 
  \end{thm}
\end{frame}


\section{Algebraic connections}

\subsection{Steiner quasigroup}

\begin{frame}
  \frametitle{Steiner quasigroup}
  \begin{block}<1->{\emph{The-third-point-on-a-line} operation}
    Using a Steiner triple system $\struct{S, \Lines}$ we can define 
    a multiplication $\triop$ on the set $S$ by setting 
    \begin{itemize}
    \item
      $a\triop a = a$ for all $a\in S$, and 
    \item
      $a\triop b = c$ if $\set{a,b,c}\in\Lines$.
    \end{itemize}
    The multiplication $\triop$ so defined has the additional property that: 
    \begin{cmath}
      a\triop(b\triop a) = b. 
    \end{cmath}
    Hence we get $\struct{S, \triop}$ an idempotent, totally symmetric (and thus commutative) 
    quasigroup.
  \end{block}    
  \begin{block}<2->{} 
    Conversely, every (finite) idempotent, totally symmetric quasigroup
    arises from a Steiner triple system.
  \end{block}
\end{frame}

\subsection{Pasch axiom}

\begin{frame}
  \frametitle{Pasch axiom as an algebraic law}
  \centering\includegraphics{fig-paschaxiom.png}
  \par
     $$a\triop b = (p\triop a)\triop(p\triop b)$$
\end{frame}

\subsection{Hall requirement}

\begin{frame}
  \frametitle{Hall requirement as the distributivity law}
  \centering\includegraphics{fig-mitreaxiom.png}
  \par
     $$p\triop (a\triop b) = (p\triop a)\triop (p\triop b)$$
\end{frame}

\subsection{Net axiom}

\begin{frame}
  \frametitle{Net axiom as an algebraic law}
  \centering\includegraphics{fig-netaxiom.png}
  \begin{equation*}\tag{$\ast$}\label{algax:net}
    (a\triop b)\triop(c\triop d) = (a\triop c)\triop(b\triop d)
  \end{equation*}
  \begin{prop}<2->
    An STS is affine iff it satisfies \eqref{algax:net}.
  \end{prop}
\end{frame}

\subsection{Trilinear forms}

\begin{frame}
  \frametitle{Characterization of HTSs in terms of trilinear forms}
  \begin{block}<1->{Trilinear form}
  Let $K$ be a commutative field of characteristic not 2 and let
  $V=V(n,K)$ be a $n$-dimensional vector space over $K$. A mapping
  \begin{cmath}
    t\colon V\times V\times V\lto K
  \end{cmath}
  linear in each of its variables is called a \emph{trilinear} form.
  \end{block}
  \begin{block}<2->{}
    A trilinear form $t$ is said to be \emph{symplectic} when
    \begin{cmath}
      t(x,x,y) = t(x,y,x) = t(y,x,x) = 0.
    \end{cmath}
  \end{block}
  \begin{thm}<3->
    There is a one-to-one correspondence between non-equivalent trilinear
    symplectic forms  over $V(n, \GF(3))$ and Hall triple systems of order
    $3^{n+1}$ and rank $n+1$.
  \end{thm}
\end{frame}


\begin{frame}
  \thispagestyle{empty}
  \begin{centering}
    \begin{beamercolorbox}[sep=5pt,center,shadow=true,rounded=true]{part title}
      \usebeamerfont{part title}Thank you for your attention
    \end{beamercolorbox}
  \end{centering}
\end{frame}

\end{document}

