\documentclass[landscape,pdftex]{slides}
\usepackage{amsfonts,amsmath,latexsym}
%\onlyslides{1-3}
\pagestyle{empty}
\newcommand{\heading}[1]{%
\begin{center}
{\large \bf {#1} }
\end{center}
}
\newcommand{\subheading}[1]{%
\mbox{\bf #1 }%
\vspace{1ex minus 1ex}\\}
\newcommand{\sketch}[0]{
\emph{Sketch: } }
\begin{document}
\title{Equivalence of seven major theorems in combinatorics}
\author{Robert D. Borgersen\\
umborger@cc.umanitoba.ca}
\date{November 26, 2004}
\maketitle
\begin{slide} \label{slide:one}
\heading{Abstract}
The seven following theorems, while
seemingly unrelated, are equivalent (i.e., any one of them may be
proved by assuming any other is true). These theorems relate to
graph theory, set theory, flow theory, and even marriage: Menger's
theorem (1929), K\"onig's theorem for matrices (1931), the
K\"onig-Egerv\'ary theorem (1931), Hall's marriage theorem (1935),
the Birkhoff-Von Neumann theorem (1946), Dilworth's theorem (1950)
and the Max Flow-Min Cut theorem (1962). I will attempt to explain
each theorem, and give some indications why all are equivalent.
\end{slide}
\begin{slide}
\heading{Graph Theory}
A \emph{graph} can be defined as a set of points, called
\emph{vertices} or \emph{nodes}, and a set of 2-element sets of
points, called \emph{edges}.
We say a graph is \emph{bipartite} if it's vertices can be
partitioned into two disjoint sets such that all edges in the
graph go from one set to the other. A \emph{covering} of the
edges in a graph is a set C of vertices such that each edge of the
graph contains at least one vertex of C.
\subheading{K\"{o}nig's Theorem} Let G be a bipartite graph. The
size of a maximum matching of G is equal to the size of a minimum
covering of G.
\end{slide}
\begin{slide}
\heading{Menger's Theorem}
Let G be a graph, v and w vertices in G, and S be a subset of
vertices. S is a \emph{vw-separating set} if there is no path from
v to w in $G \setminus S$. Two paths from v to w are
\emph{vertex-disjoint} if they only have v and w in common.
\subheading{Menger's Theorem (1929)} The maximum number of
vertex-disjoint paths connecting two distinct non-adjacent
vertices v and w is equal to the minimum number of vertices in a
vw-separating set.
\end{slide}
\begin{slide}
\heading{Flow Theory}
A \emph{directed graph} is a graph in which each edge has
associated with it a direction. A \emph{network} is a directed
graph with two distinct vertices singled out as the \emph{source}
s and the \emph{target} t, and with each edge assigned an integer
called it's \emph{capacity}.
Let S be a set of vertices, and S' it's complement. We define an
\emph{edge cut} [S, S'] as all the edges directed from S to S'. A
\emph{minimum edge cut} is one such that the sum of the capacities
of the edges in [S, S'] is a minimum.
The easiest example to see would be a system of pipes, with water
flowing from one source to one target where the capacities are the
diameter of the pipes. You can also look at any kind of product
distribution line as an example of a network.
\end{slide}
\begin{slide}
\heading{Flow Theory cont., and the Max-Flow Min-Cut theorem}
The \emph{flow} on an edge uv is f(u,v), a positive integer such
that f(u,v) $\leq$ the capacity of uv, and $f^+(v) = f^-(v)$ (the
out flow from v equals the inflow to v). We will say a
\emph{flow} in the network N is a valid assignment of flows on all
the edges. The value of a flow in N is $f^+(s) - f^-(s)$. A
\emph{maximum flow} is one whose value is maximum.
\subheading{The Max-Flow Min-Cut theorem} A value of a maximum
flow in a network N is equal to the value of a minimum cut of N.
\end{slide}
\begin{slide}
\heading{(0,1)-Matrices and the K\"{o}nig-Egerv\'{a}ry theorem}
The \emph{Term Rank} of a (0,1)-matrix is the largest number of 1s
that can be chosen from the matrix such that no 2 selected 1s lie
on the same line. A set S of rows and columns is a \emph{cover}
of a (0,1)-matrix if the matrix becomes a zero matrix after all
the lines in S have been deleted.
\subheading{K\"onig-Egerv\'ary theorem (1931)} The term rank of a
(0,1)-matrix is the cardinality of its smallest cover.
\end{slide}
\begin{slide}
\heading{The Birkhoff-Von Neumann Theorem}
A matrix D = ($d_{ij}$) with real non-negative entries is
\emph{Doubly Stochastic} if the sum of the entries in any row and
any column equals 1. A \emph{Permutation Matrix} is a doubly
stochastic matrix with entries 0 and 1, that is, a matrix with
exactly one 1 in each row and in each column. A matrix A is a
\emph{convex combination} of matrices $A_1, ..., A_s$ if there
exist non-negative reals $\lambda_1, ..., \lambda_s$ such that $A
= \sum^s_{i=1} \lambda_i A_i$ and $\sum^s_{i=1} \lambda_i = 1$.
\subheading{Birkhoff-Von Neumann Theorem (1946)} Any doubly
stochastic matrix can be written as a convex combination
permutation matrices.
\end{slide}
\begin{slide}
\heading{Hall's Theorem}
Let X be a set of elements. Let S = $\{S_1, ..., S_n\}$ be a
family of subsets of X. Then, a \emph{Sequence of Distinct
Representatives (SDR) for S} is a sequence \{$x_1, ..., x_n$\} of
pairwise distinct elements of X such that $x_i \in S_i, 1 \leq i
\leq n$
\subheading{Hall's Theorem} S has an SDR if and only if the union
of any k members of S contains at least k elements.
\begin{center}
Example: \\
X = \{1, 2, 3, 4, 5\} \\
$S_1$ = \{1, 2, 3\}, $S_2$ = \{1, 4, 5\}, $S_3$ = \{3, 5\}\\
SDR: \{1, 4, 5\}
\end{center}
\end{slide}
\begin{slide}
\heading{The Marriage Theorem}
This was the original motivation for Hall's Theorem:
Given a set of n men and a set of n women, let each man make a
list of the women he is willing to marry. Then each man can be
married to a woman on his list if, and only if, for every value of
k (1 $\leq$ k $\leq$ n), the union of any k of the lists contain
at least k names.
Similarly, we can apply this theorem to the Assignment Problem:
Given a set of n employees, fill out a list of the jobs each of
them would be able to preform. Then, we can give each person a
job suited to their abilities if, and only if, for every value of
k (1 $\leq$ k $\leq$ n), the union of any k of the lists contains
at least k jobs.
\end{slide}
\begin{slide}
\heading{Partially Ordered Sets and Dilworth's Theorem}
We define a \emph{Partially Ordered Set}, or a \emph{Poset}, as a
set P with a partial ordering $\leq$ defined on it's elements.
I.e, for any two elements x and y of P, either x $\leq$ y, y
$\leq$ x (x and y are comparable), or x $||$ y (x and y are
incomparable). A \emph{Chain} is any pairwise comparable subset of
P, and an \emph{Antichain} is any pairwise incomparable subset of
P.
\subheading{Dilworth's Theorem} Suppose that the largest antichain
in the poset P has size r. Then P can be partitioned into r
disjoint chains.
\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%KONIG <==> KONIG-EGERVARY%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{The K\"onig-Egerv\'ary theorem $\Leftrightarrow$
K\"onig's Theorem}
Let the bipartite graph G have bipartitions $X = \{x_1, x_2, ...,
x_m\}$ and $Y = \{y_1, y_2, ..., y_m\}$. Construct the m*n
adjacency matrix $A$ with $A_{ij}$ =1 if, and only if, there is an
edge joining $x_i$ to $y_j$. Now, the term rank of A is the
cardinality of a maximum matching in G, and the size of a smallest
cover of A is the size of a smallest covering of the edges of G.
So, we have that the K\"onig-Egerv\'ary Theorem $\Rightarrow$
K\"onig's Theorem. Conversely, since any (0,1)-matrix can be
interpreted as the adjacency matrix of some bipartite graph,
K\"onig's Theorem $\Rightarrow$ the K\"onig-Egerv\'ary Theorem.
\end{slide}
%%%%%%%%%%%%%%%%%%%%%%%%%
%HALL ==> KONIG-EGERVARY%
%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Hall's Theorem $\Rightarrow$ The K\"{o}nig-Egerv\'{a}ry
Theorem}
\sketch Let B be an m*n (0,1)-matrix, p = term rank of B, q =
cardinality of smallest cover.
Claim: p $\leq$ q. Removing r rows and s columns (r + s = q)
removes all the ones from the matrix. Thus, there are at most r +
s ones in different rows and columns. Thus p $\leq$ q.
\end{slide}
\begin{slide}
\heading{Hall's Theorem $\Rightarrow$ The K\"{o}nig-Egerv\'{a}ry
Theorem (cont.)}
Claim: p $\geq$ q. Permute the rows and columns of B (as figure).
Let $A_i$ = \{$j : j > s$ and $B_{ij}$ = 1\}. Note $|A_i| > 0$
for all i. Also, the union of any k of the $A_i$'s has at least k
elements. If not, we would be able to replace k rows of the
smallest cover with less than k columns. Thus, by Hall's theorem,
we have r ones in the top right, each in it's own row and column.
Similarly, we get s ones in the bottom left, each in it's own row
and column. So, p $\geq$ r + s = q. So, p = q.
\end{slide}
%%%%%%%%%%%%%%%%%%%
%DILWORTH ==> HALL%
%%%%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Dilworth's Theorem $\Rightarrow$ Hall's Theorem}
\sketch Let $S_1, S_2, ..., S_n$ be the subsets of $\{x_1, ...,
x_m\}$
Assume that the union of any k sets has at least k elements. Let
$X = \{S_1, S_2, ..., S_n, x_1, x_2, ..., x_m\}$ and define a
partial order on X such that $x_i < S_j$ iff $x_i \in A_j$, and
there are no other comparable elements.
The xi's form an antichain of length m, and it can be shown this
is the largest antichain. So, by Dilworth's theorem, we can
partition X into m chains, n of which have 2 elements, and the
rest have 1. The 2 element chains define an SDR.
\end{slide}
%%%%%%%%%%%%%%%%
%KONIG ==> HALL%
%%%%%%%%%%%%%%%%
\begin{slide}
\heading{Konig's Theorem $\Rightarrow$ Hall's Theorem}
\sketch Let $S = \{S_1, S_2, ..., S_n\}$ be a set of subsets of $X
= \{x_1, x_2, ..., x_m\}$ such that the union of any k members of
S contains at least k elements. Construct a bipartite graph G
with bipartitions X and Y = $\{1, ..., n\}$ in which $\{x_i, j\}$
is an edge if, and only if, $x_i \in S_j$.
Let $K \subseteq Y$. Define N(K) to be the set of vertices in X
such that each vertex in N(K) is joined to at least 1 vertex in K.
Equivalently, $N(K) = \bigcup_{i \in K} S_i$. By assumption,
$|N(K)| \geq |K|$ (1). Now, we need to show that there is a
matching of Y into X.
\end{slide}
\begin{slide}
\heading{Konig's Theorem $\Rightarrow$ Hall's Theorem (cont.)}
By K\"onig's Theorem, a complete matching from Y into X exists if
and only if the cardinality of every covering of the edges in this
graph is at least n.
Let C be a covering of G. Let $C_y = C \bigcap Y$. Then, $N(X
\setminus C_y)$ is a subset of $C \setminus C_y$ (2). Thus,
\begin{center}
$|C| = |C_y| + |C \setminus C_y|$\\
$\geq |C_y| + |N(X \setminus C_y)|$ (by (2)) \\
$\geq |C_y| + |X \setminus C_y|$ (by (1)) = m
\end{center}
\end{slide}
\begin{slide}
\heading{References}
\small{
\begin{itemize}
\item Balakrishnan, V. (1995): \emph{Schaum's Outline of Theory
and Problems of Combinatorics}. McGraw-Hill.
\item Bollobas, B. (1979): \emph{Graph Theory: An Introductory
Course}. Springer-Verlag.
\item Diestel, R. (1997): \emph{Graph Theory}. Springer.
\item Gould, R. (1988): \emph{Graph Theory}. Benjamin/Cummings.
\item Harary F. (1969): \emph{Graph Theory}. Addison-Wesley.
\item Jukna, S. (2001): \emph{Extremal Combinatorics with
Applications in Computer Science}. Springer.
\item Tutte, W. (1984): \emph{Graph Theory: Encyclopedia of
Mathematics and its Applications}. Addison-Wesley.
\end{itemize}}
\end{slide}
\end{document}