%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-57/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem*{spern}{Sperner's Lemma}
\newtheorem*{thm}{Theorem}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{ack}{Acknowledgements}

\title{A Proof of Sperner's Lemma via Hall's Theorem}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{A proof of Sperner's lemma via Hall's theorem}, Proc. Camb.
  Philos. Soc. \textbf{78} (1975), 387.}\bigskip\end{center}

\emph{Sperner's Lemma.} Let $S$ be a Sperner set of subsets of $\{1,2,\dots,n\}$. (That is, for $A,B \in S$, if $A \ne B$ then $A \not\subset B$ and $B \not\subset A$.) Then $|S| \leq \binom{n}{\lfloor n/2 \rfloor}$.

\begin{lemma} \label{lemma: 1}
Let $A_1,\dots,A_m$ be distinct $k$-element subsets of $\{1,2,\dots,n\}$, where $k \geq \lfloor n/2 \rfloor + 1$. Let $\mathcal{B}_i = \{B \subset A_i: |B| = k-1\}$ $( 1 \leq i \leq m)$. Then $\{\mathcal{B}_1, \dots, \mathcal{B}_m\}$ has a system of distinct representatives.
\end{lemma}

\begin{proof}[Proof of lemma]
We use Hall's Theorem, and to simplify notation we show only that $| \mathcal{B}_1 \cup \cdots \cup \mathcal{B}_m| \geq m$. Let $B \in \mathcal{B}_1 \cup \cdots \cup \mathcal{B}_m$, and let 
\[ e = \{i: B \in \mathcal{B}_i\} = \{i: B \subset A_i\}. \]
Since the $A_i$ are distinct $k$-element sets and $|B| = k-1$, we have $n \geq k - 1 + |e|$, and this with $k \geq \lfloor n/2 \rfloor + 1$ gives $|e| \leq k$. Then since $|\mathcal{B}_i| = k$ $(1 \leq i \leq m)$, we obtain $|\mathcal{B}_1 \cup \cdots \cup \mathcal{B}_m| \geq km/k = m$.
\end{proof}

\begin{proof}[Proof of Sperner's Lemma] Let $k = \max\{|A|: A \in S\}$. If $k \geq \lfloor n/2 \rfloor + 1$, let
\[ \{A_1, \dots,A_m\} = \{A \in S: |A| = k\}. \]
By the lemma, there are distinct sets $\phi(A_i)$ $(1 \leq i \leq m)$, such that $\phi(A_i) \subset A_i$ and $|\phi(A_i)| = k -1$. Thus in $S$ we may replace each $A_i$ by $\phi(A_i)$ $(1 \leq i \leq m)$, to obtain a new Sperner set $S'$ such that $|S'| = |S|$ and $A \in S' \Rightarrow |A| \leq k - 1$. Repeating this process as many times as required, we obtain a Sperner set $S^*$ such that $|S^*| = |S|$ and $A \in S^* \Rightarrow |A| \leq \lfloor n/2 \rfloor$. 

Now let $T = \{\{1,2,\dots,n\}\setminus A: A \in S^*\}$. Then $T$ is a Sperner set, $|T| = |S|$, and 
\[ A \in T \Rightarrow |A| \geq \lfloor n/2 \rfloor. \]
Thus, applying the above process to $T$, we obtain finally a Sperner set $T^*$ such that $|T^*| = |S|$ and $A \in T^* \Rightarrow |A| = \lfloor n/2\rfloor$. Thus $|S| \leq \binom{n}{\lfloor n/2 \rfloor}$. 
\end{proof}

\nocite{hall1935,lubell1966,sperner1928}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}