%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-55/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{thm}{Theorem}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{fact}{Fact}

\title{Common Transversals}
\author{T. C. Brown \\ Communicated by P. Erd\H{o}s}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Common transversals}, J. Combin. Theory Ser. A \textbf{21}
  (1976), 80--85.}\bigskip\end{center}

\begin{abstract} 
Given $t$ families, each family consisting of $s$ finite sets, we show that if the families ``separate points" in a natural way, and if the union of all the sets in all the families contains more than $(s + 1)^t - s^{t-1} - 1$ elements, then a common transversal of the $t$ families exists. In case each family is a covering family, the bound is $s^t - s^{t-1}$. Both of these bounds are best possible. This work extends recent work of Longyear~\cite{longyear1977}.
\end{abstract}

\section{Introduction and statement of results} \label{sec: 1}

Throughout this paper, the symbol $\mathcal{F}$ will always denote a family of $t$ families of sets, each of the $t$ families consisting of $s$ finite, but not necessarily distinct or nonempty, sets. The symbol $\Omega$ will always denote the union of all of the sets contained in all of the $t$ families. Thus $\mathcal{F} = (F_1,F_2,\dots,F_t)$, where for each $j$, $1 \leq j \leq t$, $F_j = (F_j(1),F_j(2),\dots,F_j(s))$ is a family of $s$ (finite, but not necessarily distinct or nonempty) sets, and $\Omega = \bigcup \{F_j(i): 1 \leq j \leq t, 1 \leq i \leq s\}$ (or more briefly, $\Omega = \bigcup \bigcup \mathcal{F}$). We always assume that $\mathcal{F}$ \emph{separates points} of $\Omega$ in the following sense. Letting $F_j(0) = \Omega \setminus \bigcup F_j$, $1 \leq j \leq t$, we require
\[ \left| \bigcap \{F_j(a_j): 1 \leq j \leq t \} \right| \leq 1 \]
for every $t$-tuple $(a_1,a_2,\dots,a_t)$, where $0 \leq a_j \leq s$, $1 \leq j \leq t$. Note that this immediately implies $|\Omega| \leq (s+1)^t - 1$ (since $|\bigcap \{F_j(0): 1 \leq j \leq t\}| = 0$), and that in the case where each $F_j$ covers $\Omega$ (so that $F_j(0) = \emptyset$) we have $|\Omega| \leq s^t$.

Recall that the set $T$ is a \emph{transversal} (sometimes called a \emph{system of distinct representatives} or SDR) of the family $F_j$ if there is a bijection $\varphi: T \mapsto \{1,2,\dots,s\}$ such that $x \in F_j(\varphi(x))$ for all $x \in T$. The set $T$ is a \emph{common transversal} of $F_1,F_2,\dots,F_t$ if $T$ is simultaneously a transversal of each $F_j$, $1 \leq j \leq t$.

In this paper the following results are proved, which extend recent results of Judith Q. Longyear~\cite{longyear1977}. Longyear proved, among other things, Theorem~\ref{thm: 1}(b) below in the case where each family $F_j$ is assumed to consist of mutually disjoint sets. Theorem~\ref{thm: 1}(b) can be obtained as a corollary to her result. We give an alternative proof. 

\begin{thm} \label{thm: 1} 
Let $\mathcal{F}$ and $\Omega$ be as in the first paragraph of this paper, and assume further that each family $F_j$ covers $\Omega$, that is, $\bigcup F_j = \Omega$, $1 \leq j \leq t$. 

(a) If $|\Omega| > s^t - s^{t-1}$ then each family $F_j$ has a transversal, and $s^t - s^{t-1}$ is best possible.

(b) If $|\Omega| > s^t - s^{t - 1}$ then a common transversal of $F_1,F_2,\dots,F_t$ exists, and $s^t - s^{t-1}$ is best possible.
\end{thm}

\begin{thm} \label{thm: 2}
Let $\mathcal{F}$ and $\Omega$ be as in the first paragraph of this paper.

(a) If $|\Omega| > (s + 1)^t - (s + 1)^{t-1} - 1$ then each family $F_j$ has a transversal, and $(s + 1)^t - (s + 1)^{t-1} - 1$ is best possible.

(b) If $|\Omega| > (s + 1)^t - s^{t-1} - 1$ then a common transversal of $F_1,F_2,\dots,F_t$ exists, and $(s + 1)^t - s^{t-1} - 1$ is best possible.
\end{thm}

\section{Proofs} \label{sec: 2}

Let us show first of all that the bounds given in Theorems~\ref{thm: 1} and~\ref{thm: 2} are best possible.

For Theorem~\ref{thm: 1}(a) and Theorem~\ref{thm: 1}(b) let 
\[ \Omega = \{(a_1,a_2,\dots,a_t): 1 \leq a_j \leq s, 1 \leq j \leq t-1, 1 \leq a_t \leq s-1\}. \]
For all $j,i$, $1 \leq j \leq t$, $ 1\leq i \leq s$, let $F_j(i) = \{\omega \in \Omega:$ the $j$th coordinate of $\omega$ equals $i\}$. Note that $F_t(s) = \emptyset$, so that $F_t$ has no transversal. It is easy to see that $|\Omega| = s^t - s^{t-1}$, each $F_j$ covers $\Omega$, $1 \leq j \leq t$, and $\mathcal{F} = (F_1,F_2,\dots, F_t)$ separates points. 

For Theorem~\ref{thm: 2}(a), we let 
\[ \Omega = \{(a_1,a_2,\dots,a_t): 0 \leq a_j \leq s, 1 \leq j \leq t-1, 0 \leq a_t \leq s-1\} \setminus \{(0,0,\dots,0)\}. \]
For all $j,i$, $1 \leq j \leq t$, $1 \leq i \leq s$, let 
\[ F_j(i) = \{\omega \in \Omega: \textup{the $j$th coordinate of $\omega$ equals $i$} \}. \]
Again $F_t(s) = \emptyset$ so $F_t$ has no transversal, and it is easy to see that $|\Omega| = (s + 1)^t - (s + 1)^{t-1} - 1$, $\Omega = \bigcup \bigcup \mathcal{F}$, and $\mathcal{F} = (F_1,F_2,\dots,F_t)$ separates points.

For Theorem~\ref{thm: 2}(b), let $\Omega$ be the set of all $t$-tuples $(a_1,a_2,\dots,a_t)$, $0 \leq a_j \leq s$, $1 \leq j \leq t$, \emph{excluding} the set $(\{(a_1,a_2,\dots,a_t): 1 \leq a_j \leq s, 1 \leq j \leq t-1, a_t = s\} \cup \{(0,0,\dots,0)\})$. For all $j,i,$ $1 \leq j \leq t$, $1 \leq i \leq s$, let 
\[ F_j(i) = \{\omega \in \Omega: \textup{the $j$th coordinate of $\omega$ equals $i$} \}. \]

Then any element $\omega$ of $F_t(s)$ must have its $j_0$th coordinate equal to $0$ for some $j_0 \ne t$, and hence $\omega$ cannot represent any set in the family $F_{j_0}$, therefore $\omega$ cannot belong to any common transversal of $F_1,F_2,\dots,F_t$. Therefore no common transversal exists. Again it is easy to see that $|\Omega| = (s + 1)^t - s^{t-1} - 1$, $\Omega = \bigcup \bigcup \mathcal{F}$, and $\mathcal{F} = (F_1,F_2,\dots,F_t)$ separates points.

Throughout the remaining proofs, the following notation will be used. It is therefore fixed once and for all. For $t \geq 2$, let $X$ be the set of all $(t-1)$-tuples $(a_1,a_2,\dots,a_{t-1})$, where each $a_j$, $1 \leq j \leq t- 1$ satisfies $1 \leq a_j \leq s$. Note that $|X| = s^{t-1}$. For each $x = (a_1,a_2,\dots,a_{t-1}) \in X$, we denote by $f(x)$ the set $\bigcap\{F_j(a_j): 1 \leq j \leq t-1\}$. Then since $\mathcal{F}$ distinguishes points and each $F_j$ covers $\Omega$ we have $|f(x) \cap F_t(i)| \leq 1$ for all $x \in X$ and all $i$, $1 \leq i \leq s$, and $\Omega = \bigcup \{f(x): x \in X\}$.

\begin{proof}[Proof of Theorem~\ref{thm: 1}(a)]
The case $t = 1$ follows from the various definitions, so we assume $t \geq 2$, and without loss of generality we restrict our attention to $F_t$. We shall make use of the classical result of P. Hall~\cite{hall1935} according to which $F_t$ has a transversal if and only if $|\bigcup \{F_t(i): i \in I\}| \geq |I|$ for all $I \subset \{1,2,\dots,s\}$. Suppose that $F_t$ does not have a transversal, and that $|F_t(i_1) \cup F_t(i_2) \cup \cdots \cup F_t(i_{k-1})$ $(F_t(i_k) = \emptyset$ if $k = 1$), hence $\Omega = \bigcup \{ F_t(i): 1 \leq i \leq s, i \ne i_k\}$. Then 
\begin{align*}
|\Omega| &= \left| \left( \bigcup \{f(x): x \in X\} \right) \cap \left( \bigcup \{F_t(i): 1 \leq i \leq s, i \ne i_k\} \right) \right| \\
&= \left| \bigcup \{f(x) \cap F_t(i): x \in X, 1 \leq i \leq s, i \ne i_k\} \right| \\
&\leq |\{(x,i): x \in X, 1 \leq i \leq s, i \ne i_k\}| \\
&= s^{t-1}(s - 1) = s^t - s^{t-1}, 
\end{align*}
contrary to the hypothesis of the Theorem. Hence $F_t$ and similarly each $F_j$, has a transversal.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm: 1}(b)]
Since the family $F_t = (F_t(1), F_t(2), \dots, F_t(s))$ has a transversal (by Theorem~\ref{thm: 1}(a)) and covers $\Omega$, we can replace $F_t$ by a \emph{partition} $G = (G(1),G(2),\dots,G(s))$ such that $G(i) \subset F_t(i)$ for all $i$, $1 \leq i \leq s$. (The partition $G$ can be constructed as follows. Let $\{\omega_1,\omega_2,\dots,\omega_s\}$ be a transversal of $F_t$, where $\omega_i \in F_t(i)$, $1 \leq i \leq s$. Let 
\begin{align*}
G(1) &= F_t(1) \setminus\{\omega_2,\dots,\omega_s\}, \\
G(2) &= F_t(2) \setminus ( G(1) \cup \{\omega_3,\dots,\omega_s\}), \\
G(3) &= F_t(3) \setminus (G(1) \cup G(2) \cup \{\omega_4,\dots,\omega_s\}), \\
&\vdots \\
G(s) &= F_t(s) \setminus (G(1) \cup G(2) \cup \cdots \cup G(s-1)). 
\end{align*}
Then $\mathcal{F}' = (F_1,F_2,\dots,F_{t-1},G)$ distinguishes points, hence $|f(x) \cap G(i)| \leq 1$ for all $x \in X$ and all $i$, $1 \leq i \leq s$, and any common transversal of $F_1,F_2,\dots,F_{t-1}$, $G$ is a common transversal of $F_1,F_2,\dots,F_t$. 

At this point we could in fact replace \emph{every} $F_j$ by a partition (since we know by Theorem~\ref{thm: 1}(a) that every $F_j$ has a transversal); however, it is not necessary, and so we do not. 

We now demonstrate the existence of a common trasversal of $F_1,F_2,\dots,F_{t-1},G$. 

To this end we define a \emph{diagonal} of $X$ to be a subset $D$ of $X$ such that $|D| = s$ and for each $j$, $1 \leq j \leq t - 1$, the $j$th coordinates of the elements of $D$ run through $\{1,2,\dots,s\}$ in some order. Note that whenever $D = \{x_1,x_2,\dots,x_s\}$ is a diagonal, $\omega_k \in f(x_k)$, $ 1 \leq k \leq s$, and $\omega_1,\omega_2,\dots,\omega_s$ are all distinct, then $\{\omega_1,\omega_2,\dots,\omega_s\}$ is a common transversal of $F_1,F_2,\dots,F_{t-1}$.

Now we let $\mathcal{D}$ be some fixed collection of \emph{mutually disjoint} diagonals of $X$ whose union is $X$, $X = \bigcup \mathcal{D}$. (The existence of $\mathcal{D}$ can be shown by induction on $t$.)

Since $|X| = s^{t-1}$ and every diagonal has $s$ elements, we have $|\mathcal{D}| = s^{t-2}$. For any diagonal $D$, let $f(D) = \bigcup \{f(x): x \in D\}$. Then 
\[ \Omega = \bigcup \{f(x): x \in X\} = \bigcup \{f(D): D \in \mathcal{D}\}. \]
Now
\[ s^t - s^{t-1} < |\Omega| \leq \sum_{D \in \mathcal{D}} |f(D)| \leq |\mathcal{D}| \max\{|f(D)| : D \in \mathcal{D}\}, \]
hence $s^2 - s < \max\{|f(D)|: D \in \mathcal{D}\}$.

We now fix a diagonal $D$ with $s^2 - s < |f(D)|$. Let $D = \{x_1,x_2,\dots,x_s\}$, and define, for $ 1\leq i \leq s$, $1 \leq j \leq s$, 
\[ e_{ij} = \begin{cases} 1 &\textup{if $f(x_i) \cap G(j) \ne \emptyset$} \\
0 &\textup{otherwise}. \end{cases} \]

Then since $|f(x_i) \cap G(j)| \leq 1$ for all $i,j$, and $G$ is a partition of $\Omega$, the $s \times s$ 0-1 matrix $(e_{ij})$ contains exactly $|f(D)|$, and hence more than $s^2 - s$, 1's. Therefore there exist (as can be shown by induction on $s$) indices $i_1j_1, i_2j_2, \dots, i_sj_s$ such that $e_{i_1j_1} = e_{i_2j_2} = \cdots = e_{i_sj_s} = 1$ and $\{i_1,i_2,\dots,i_s\} = \{j_1,j_2,\dots,j_s\} = \{1,2,\dots,s\}$.

Now let $\{\omega_k\} = f(x_{i_k}) \cap G(j_k)$, $1 \leq k \leq s$. Then since $G$ is a partition, $\omega_1,\omega_2,\dots,\omega_s$ are all distinct, and hence $\{\omega_1,\omega_2,\dots,\omega_s\}$ is not only a transversal of $G$ but is also (since $\{x_1,x_2,\dots,x_s\}$ is a diagonal) a common transversal of $F_1,F_2,\dots,F_{t-1}$. Therefore $\{\omega_1,\omega_2,\dots,\omega_s\}$ is a common transversal of $F_1,F_2,\dots,F_{t-1}, G$, and hence of $F_1,F_2,\dots,F_t$. 

This completes the proof of Theorem~\ref{thm: 1}(b).
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm: 2}(a)]
Recall that for each $j$, $1 \leq j \leq t$, $F_j(0)$ denotes the complement in $\Omega$ of the union of the family $F_j$, that is, $F_j(0) = \Omega \setminus \bigcup \{F_j(i): 1 \leq i \leq s\}$. If now for each $j$, $1 \leq j \leq t$, we let 
\[ G_j = (F_j(0), F_j(1), \dots, F_j(s)), \]
and let $\mathcal{G} = (G_1,G_2,\dots,G_t)$, then $\mathcal{G}$ separates points and each family $G_j$ covers $\Omega$, therefore we may proceed exactly as in the proof of Theorem~\ref{thm: 1}(a), where now we have $t$ families with $s + 1$ sets in each family. Furthermore, since we know that $\bigcap \{F_j(0): 1 \leq j \leq t\} = \emptyset$ (this is so because $\bigcup \{F_j(i): 1 \leq j \leq t, 1 \leq i \leq s\} = \Omega$), the last inequality in the proof of Theorem~\ref{thm: 1}(a) can be replaced by 
\begin{align*}
|\Omega| &\leq |\{(x,i): x \in X, 0 \leq i \leq s, i \ne i_k, (i,x) \ne (0,(0,0,\dots,0))\}| \\
&= (s + 1)^t - (s+1)^{t-1} - 1. \end{align*}

This proves Theorem~\ref{thm: 2}(a).
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm: 2}(b)]
For each $j$, $1 \leq j \leq t$, let $\Omega_j = \bigcup F_j$, and let 
\[ \Omega_0 = \bigcap \{\Omega_j: 1\leq j \leq t\}. \]
For each $j$, $1 \leq j \leq t$, $1 \leq i \leq s$, let $G_j(i) = F_j(i) \cap \Omega_0$, $G_j = (G_j(1),G_j(2),\dots,G_j(s))$, and 
\[ \mathcal{G} = (G_1,G_2,\dots,G_t). \]
Then for each $j$, $1 \leq j \leq t$, $\Omega_0 = \bigcup G_j$. Also, since $G_j(i) \subset F_j(i)$, for all $j,i,$ the family $\mathcal{G}$ separates points. Thus, by Theorem~\ref{thm: 1}(b), it suffices now to show that $|\Omega_0| > s^t - s^{t-1}$, since any common transversal of $G_1,G_2,\dots,G_t$ is also a common transversal of $F_1,F_2,\dots,F_t$. Since $\mathcal{F}$ separates points, the cardinal of $\Omega \setminus \Omega_0$ cannot exceed the cardinal of the set of all those $t$-tuples $(a_1,a_2,\dots,a_t)$, $0 \leq a_j \leq s$, having at least one coordinate equal to $0$ (excluding $(0,0,\dots,0)$). That is, $|\Omega \setminus \Omega_0| \leq (s + 1)^t - s^t - 1$. Hence 
\begin{align*} 
(s + 1)^t - s^{t-1} - 1 &< |\Omega| = |\Omega_0| + |\Omega\setminus \Omega_0| \\
&\leq |\Omega_0| + (s + 1)^t - s^t - 1, \end{align*}
and therefore
\[ |\Omega_0| > s^t - s^{t-1}. \]
This completes the proof of Theorem~\ref{thm: 2}(b).
\end{proof} 


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