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

\title{Common Transversals for Partitions of a Finite Set}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, \emph{Common transversals for partitions of a finite set}, Discrete
  Math. \textbf{51} (1984), 119--124.}\bigskip\end{center}

\begin{abstract} 
For $s \geq 2$, $ t \geq 1$, let $A_1,\dots,A_t$ be $s$-cell partitions of a finite set $X$. Assume that if $x,y \in X$, $x \ne y$, then $x,y$ belong to different cells of at least one of the partitions $A_i$. For each $k \geq 1$, let $c(s,t,k)$ be the least integer such that if $A_1,\dots,A_t$, $X$ satisfy the preceding conditions, and the smallest of all the cells of all the partitions has \emph{exactly} $k$ elements, and $|X| \geq c(s,t,k)$, then $A_1,\dots,A_t$ have a common transversal. The functions $b(s,t,k)$ are defined analogously, except that now the smallest of all the cells of all the partitions is only required to have \emph{at least} $k$ elements. Thus $b(s,t,1)$ involves no restriction on the sizes of the cells of the partitions. Note that $b(s,t,1) = \max\{c(s,t,k): k \geq 1\}$. 

We show, using essentially the method of Longyear~\cite{longyear1977}, that 

(1) $c(s,t,1) = s^t - s^{t - 1} - (s - 1)^{t - 1} + 2$, $s \geq 2$, $t \geq 1$, $(s,t) \ne (2,2)$;

(2) $c(s,3,s - 1) \geq s^3 - s^2 - (s - 1)^2 + s$, $s \geq 2$, $t = 3$;

(3) $c(s,t,(t - 1)(s - 1)^{t - 2}) \geq (t - 1)(t - 2)(s - 1)^{t - 2} + s(s - 1)^{t - 1} + 1$, $s \ge 2$, $t \geq 3$, $s \geq t - 2$;

(4) $b(s,2,[(s + 1)/2]) = 0$, $s \geq 2$, $t = 2$;

(5) $c(s,t,s^k) \geq s^t - s^{t - 1} - s^k(s - 1)^{t - k - 1} + s^k + 1$, $s \geq 2$, $k \geq 0$, $ t\geq k + 2$.
\end{abstract} 

\section{Introduction and definitions} \label{sec: 1} 

The functions $b(s,t,k)$ (defined above) were introduced by Longyear in~\cite{longyear1977}, who showed, among other results, that $b(s,2,1) = s^2 - 2s + 3$, $s \geq 3$.

The present author's primary interest is in the determination of the values of the function $b(s,t,1)$. In this note we give a number of partial results in this direction, mostly in the form of lower bounds obtained by various constructions. The exact values of $b(s,t,1)$, $s \geq 2$, however, are still unknown for all $t \geq 3$. 

Throughout, $A_1,\dots,A_t$ denote partitions of a finite set $X$, where each partition has $s$ cells, $s \geq 2$. We also assume that the partitions $A_1,\dots,A_t$ \emph{separate points} of $X$ in the sense that if $x,y \in X$, $x \ne y$, then $x,y$ belong to different cells of at least one of the partitions $A_i$. 

For each $i$, $ 1 \leq i \leq t$, we order the cells of $A_i$ so that $A_i = (A(i,1), \dots,A(i,s))$. Let $P(s,t)$ be the set of all $t$-tuples $a_1\cdots a_t$, where each coordinate $a_i$ is a member of $\{1,\dots,s\}$, $1 \leq i \leq t$. 

Now define a mapping $g$ from $X$ into $P(s,t)$ by setting, for each $x \in X$, 
\[ g(x) = a_1\cdots a_t, \quad x \in A(1,a_1) \cap \cdots \cap A(t,a_t). \]

Then, since $A_1,\dots,A_t$ separate the points of $X$, the mapping $g$ is injective. Also, for $1 \leq i \leq t$, $1 \leq j \leq s$, 
\[ A(i,j) = \{x \in X: \textup{the $i$th coordinate of $g(x)$ is $j$} \}, \]
so that the partitions $A_1,\dots,A_t$ can be recovered from $g(X)$.

Hence, from now on we shall identify $X$ with $g(X)$, and work entirely with subsets of $P(s,t)$. This idea is due to Longyear.

Recall that a \emph{transversal} of $A_i$ is a set $T$ of $s$ elements of $X$, one element from each of the $s$ cells of $A_i$. A \emph{common transversal} of $A_1,\dots,A_t$ is a set $T$ of $s$ elements of $X$ such that $T$ is a transversal of each $A_i$, $1 \leq i \leq t$. 

A \emph{complementary set} is a set $D$ of $s$ elements of $P(s,t)$ such that for each $i$, $1 \leq i \leq t$, the $i$th coordinates of the elements of $D$ run through $\{1,\dots,s\}$ in some order.

Note that the $s$-cell partitions $A_1,\dots,A_t$ of $X$ have a common transversal if and only if the subset $g(X)$ of $P(s,t)$ contains a complementary set. Hence the functions $c(s,t,k)$ and $b(s,t,k)$ defined above can be described as follows: 

Let $s,t$ be given, $s \geq 2$, $t \geq 1$. For a subset $Q$ of $P(s,t)$ and any $i,j$, where $1 \leq i \leq t$, $1 \leq j \leq s$, let $q(a_i = j)$ be the number of elements of $Q$ whose $i$th coordinate is $j$.

Then $c(s,t,k)$ is the smallest integer with the following property. If $Q$ is any subset of $P(s,t)$ such that $|Q| \geq c(s,t,k)$ and such that $k = \min\{q(a_i = j): 1 \leq i \leq t, 1\leq j \leq s\}$, then $Q$ contains a complementary set. Similarly, $b(s,t,k)$ is the smallest integer such that if $Q$ is any subset of $P(s,t)$ such that $|Q| \geq b(s,t,k)$ and such that 
\[ k \leq \min \{q(a_i = j): 1 \leq i \leq t, 1 \leq j \leq s\}, \]
then $Q$ contains a complementary set. 

Note that $c(s,t,k)$ is defined only for $k \geq 1$ (or else we may take $c(s,t,0) = |P(s,t)| + 1$), whereas $b(s,t,k)$ is defined for all $k \geq 0$.

Also note again that $b(s,t,k) \geq c(s,t,k)$ and that $b(s,t,1) = \max\{c(s,t,k): k \geq 1\}$.

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

The following lemma, which follows from simple counting, will be used repeatedly.

\begin{lemma} \label{lemma: 1} 
The set $P(s,t)$ contains $s!^{t - 1}$ complementary sets altogether, each element of $P(s,t)$ belongs to $(s - 1)!^{t - 1}$ complementary sets, and each compatible pair of elements of $P(s,t)$ belongs to $(s - 2)!^{t - 1}$ complementary sets.
\end{lemma}

\begin{thm} \label{thm: 1} \emph{(Longyear~\cite{longyear1977})}.
For $s \geq 2$, $t \geq 1$, 
\[ b(s,t,0) = s^t - s^{t - 1} + 1. \]
\end{thm}

\begin{proof}[Proof 1] (Longyear~\cite{longyear1977}).
Let $Q$ be a subset of $P(s,t)$ with $|Q| \geq s^t - s^{t - 1} + 1$. Let $B = P(s,t) - Q$. Then $|B| \leq s^{t - 1} - 1$, so by Lemma~\ref{lemma: 1} $B$ can intersect at most $|B|(s-1)!^{t - 1}$ complementary sets, and hence $Q$ contains a complementary set. This shows that $b(s,t,0) \leq s^t - s^{t -1 } + 1$. Now let $Q = P(s,t) - B$, where 
\[ B = \{a_1 \cdots a_t \in P(s,t): a_1 = 1\}. \]
Then $Q$ contains no complementary set, hence 
\[ b(s,t,0) \geq |Q| + 1 = s^t - s^{t - 1} + 1. \qedhere\]
\end{proof}

\begin{proof}[Proof 2]
We use induction on $t$, the case $t = 1$ being trivial. Assume the result for a given $t \geq 1$, and let $Q$ be a subset of $P(s,t + 1)$ with $|Q| \geq s^{t + 1} - s^t + 1$. For each $h$, $0 \leq h \leq s - 1$, let $B_h = \{a_1 \cdots a_t a_{t + 1} \in Q: a_{t + 1} - a_t \equiv h$ (mod $s$)$\}$. Then $Q$ is the disjoint union of the sets $B_h$, hence (re-numbering if necessary) we may assume that $|B_0| \geq s^t - s^{t - 1} + 1$. Now let $Q' = \{a_1 \cdots a_t: a_1 \cdots a_ta_t \in B_0\}$. Since $|Q'| = |B_0|$, the induction hypothesis implies that $Q'$ contains a complementary set $D'$. Then $Q$ contains the complementary set $D = \{a_1\cdots a_ta_t \in D'\}$.
\end{proof}

\begin{thm} \label{thm: 2} 
For $s \geq 2$, $t \geq 1$, $(s,t) \ne (2,2)$,
\[ c(s,t,1) = s^t - s^{t - 1} - (s - t)^{t - 1} + 2. \]
\end{thm}

\begin{proof}
When $t = 1$ there is nothing to prove. Hence assume that $t \geq 2$ and let $Q$ be a subset of $P(s,t)$ such that $|Q| \geq s^t - s^{t - 1} - (s - 1)^{t - 1} + 2$ and such that $1 = \min\{q(a_i = j): 1 \leq i \leq t, 1 \leq j \leq s\}$, where, as before, $q(a_i = j)$ is the number of elements of $Q$ whose $i$th coordinate is $j$. Let $B = P(s,t) - Q$, and assume without loss of generality that $1 = q(a_1 = 1)$, and that $B = B_1 \cup B_2$, where $B_1 = \{a_1 \cdots a_t \in P(s,t): a_1 = 1\} - \{11\cdots 1\}$ and $B_2 = B - B_1$. Now $|B| \leq s^{t - 1} + (s - 1)^{t - 1} - 2$, and $|B_1| = s^{t - 1} - 1$, so $|B_2| \leq (s - 1)^{t - 1} - 1$. The set $B_1$ meets every complementary set in $P(s,t)$ except for the $(s-1)!^{t - 1}$ complementary sets which contain the $t$-tuple $11 \cdots 1$. The set $B_2$ can meet at most $|B_2| (s-2)!^{t - 1}$ \emph{of these}. (The complementary sets containing $11 \cdots 1$). Since $|B_2| (s-2)!^{t - 1} < (s - 1)1^{t - 1}$, it follows that $Q$ contains a complementary set, and hence that $c(s,t,1) \leq s^t - s^{t - 1} - (s - 1)^{t - 1} + 2$. 

For the reverse inequality let $Q = P(s,t) - (B_1 \cup B_2)$, where $B_1$ is as above and 
\[ B_2 = \{a_1 \cdots a_t \in P(s,t): a_1 = 2, a_i \ne 1, 2 \leq i \leq t\}. \]
Then $B_1 \cup B_2$ meets every complementary set, hence $Q$ contains no complementary set, and $1 = q(a_1 = 1) = \min \{q(a_i = j): 1 \leq i \leq t, 1 \leq j \leq s\}$ (except in the single case $s = t = 2$, when $q(a_2 = 2) = 0$). Therefore $c(s,t,1) \geq |Q| + 1 = s^t - s^{t - 1} - (s - 1)^{t - 1} + 2$, $ s \geq 2$, $t \geq 1$, $(s,t) \ne (2,2)$.
\end{proof}

\begin{remark}
For the case $t = 2$, Longyear showed using Hall's theorem~\cite{hall1935} that $b(s,t,1) = s^2 - 2s + 3$, $s \geq 3$. Thus (checking the case $s = t = 2$ separately, where we find $b(2,2,1) = 2 = c(2,2,1)$)
\[ b(s,2,1) = c(s,2,1), \quad s \geq 2. \]
\end{remark}

\begin{thm} \label{thm: 3}
For $s \geq 2$, $t = 3$, 
\[ c(s,3,s - 1) \geq s^3 - s^2 - (s - 1)^2 + s. \]
\end{thm}

\begin{proof}
Let $Q$ be the set of all triple of the form $1a_21, a_111, a_1a_2b$, where $2 \leq a_1 \leq s$, $2 \leq a_2 \leq s$, $1 \leq b \leq s$. Then $Q$ contains no complementary set and $s - 1 = a(a_1 = 1) = \min\{q(a_i = j): 1 \leq i \leq 3, 1 \leq j \leq s\}$, hence $c(s,3,s - 1) \geq |Q| + 1 = 2(s - 1) + (s - 1)^2s + 1 = s^3 - s^2 - (s - 1)^2 + s$. \end{proof}

\begin{remark} Since $b(s,3,1) \geq c(s,3,s - 1)$, and $s^3 - s^2 - (s - 1)^s + s = c(s,3,1) + (s - 2)$, Theorem~\ref{thm: 3} gives $b(s,3,1) \geq c(s,3,1) + (s - 2)$. Thus $b(s,3,1) > c(s,3,1)$, $s > 2$. This is the only known case where $b(s,t,1) > c(s,t,1)$.
\end{remark}

\begin{thm} \label{thm: 4}
For $s \geq 2$, $t \geq 3$, $s \geq t - 2$,
\[ c(s,t,(t - 2)(s - 2)^{t - 2}) \geq (t - 1)(t - 2)(s - 1)^{t - 2} + s(s - 1)^{t - 1} + 1. \]
\end{thm}

\begin{proof} We generalize the contruction used in Theorem~\ref{thm: 3}. Let $Q$ be the set of all $t$-tuples of the form $1a_2a_3 \cdots a_{t - 1}b$, $a_11a_3 \cdots a_{t - 1} b$, $a_1a_2 1a_4 \cdots a_{t - 1} b$, \dots, $a_1a_2 \cdots a_{t - 2}1b$, $a_1a_2 \cdots a_{t - 2} a_{t - 1}c$, where $2 \leq a_1, \dots , a_{t - 1} \leq s$, $1 \leq b \leq t - 2$, $1 \leq c \leq s$. Then $Q$ contains no complementary set and it is easy to check that 
\[ (t - 2)(s - 1)^{t - 2} = q(a_1 = 1) = \min\{q(q_i = j): 1 \leq i \leq t, 1 \leq j \leq s\}, \]
hence 
\[ c(s,t,(t - 2)(s - 2)^{t - 2}) \geq |Q| + 1 = (t - 1)(t - 2)(s - 1)^{t - 2} + s(s - 1)^{t - 1} + 1. \qedhere \]
\end{proof}

\begin{cor}
Setting $s = t$ gives
\[ c(s,s,(s - 2)^{s - 2} \geq 2(s - 1)^s + 1, \quad s \geq 3. \]
\end{cor}

\begin{thm} \label{thm: 5}
For $s \geq 2$, 
\[ b(s,2,[(1/2)(s + 1)]) = 0. \]
(That is, if $Q$ is any subset of $P(s,2)$ with $q(a_i = j) \geq (1/2)(s + 1)$, $1 \leq i \leq 2$, $ 1\leq j \leq s$, then $Q$ contains a complementary set.)
\end{thm} 

\begin{proof} 
The $s \times s$ 0-1 matrix corresponding to $Q$ has at least $(1/2)(s + 1)$ 1's in each row and column. Any collection of $s - 1$ rows and columns must contain fewer than $(1/2)(s +1)$ rows or fewer than $(1/2)(s + 1)$ columns, and hence cannot cover all the 1's. Hence by K\"onig's theorem, there are $s$ 1's, no two in the same row or column, and therefore $Q$ contains a complementary set. (An alternative proof can be given using Hall's theorem.) \end{proof}

\begin{remark} 
For $1 \leq k \leq [(1/2)(s - 1)]$, let $Q_k$ be the subset of $P(s,2)$ consisting of all pairs $ab, cd$, where $1 \leq a \leq k + 1$, $1 \leq b \leq k$, $k + 2 \leq c \leq s$, $1 \leq d \leq s$. This construction shows that $c(s,2,k) \geq |Q_k| + 1 = (k + 1)k + (s - k - 1)s + 1$. (For $k = 1$, $s \ne 2$, equality holds by Theorem~\ref{thm: 2}.)
\end{remark}

\begin{thm} \label{thm: 6}
For $s \geq 2$, $k \geq 0$, $t \geq k + 2$, 
\[ c(s,t,s^k) \geq s^t - s^{t - 1} - s^k(s - 1)^{t - k - 1} + s^k + 1. \]
\end{thm}

\begin{proof} When $k = 0$ equality holds by Theorem~\ref{thm: 2}. Hence assume $k \geq 1$, and let $B = B_1 \cup B_2$, where
\begin{align*} 
B_1 &= \{a_1 \cdots a_t \in P(s,t): a_1 = 1\} - \{a_1 \cdots a_t \in P(s,t): a_1 = \cdots = a_{t - k} = 1\} \\
B_2 &= \{a_1 \cdots a_t \in P(s,t): a_1 = 2, a_2, \cdots , a_{t - k} \ne 1\}. \end{align*}
Then $B_1$ meets every complementary set in $P(s,t)$ except for those met by $\{a_1 \cdots a_t \in P(s,t): a_1 = \cdots = a_{t - k} = 1\}$, and each of these remaining complementary sets is met by $B_2$, therefore $Q = P(s,t) - B$ contains no complementary set. When $t \geq k + 2$, it is straightforward to check that 
\[ s^k = q(a_1 = 1) = \min\{q(a_i = j): 1 \leq i \leq t, 1 \leq j \leq s\}, \]
and hence 
\[ c(s,t,s^k) \geq |Q| + 1 = s^t - s^{t - 1} - s^k(s - 1)^{t - k -1} + s^k + 1, \quad s \geq 2, k \geq 1, t \geq k + 2. \qedhere \]
\end{proof}

\section{Remarks, questions, and conjectures} \label{sec: 3}

(1) Perhaps Proof 2 of Theorem~\ref{thm: 1} could be modified so as to give a result concerning $b(s,t,k)$ for $k > 0$.

(2) The construction of $Q$ in Theorem~\ref{thm: 6} seems very `efficient'. Perhaps equality holds for all $k$, and not just for $k = 0$.

(3) The construction which gives $b(s,3,1) > c(s,3,1)$, $s>2$ (Theorem~\ref{thm: 3}) fails to give $b(s,t,1) > c(s,t,1)$ for any $t >3 $ (proof of Theorem~\ref{thm: 4}). It would be interesting to know if $t = 3$ is any exceptional case, or if $b(s,t,1) > c(s,t,1)$, $s > 2$, for all $t \geq 3$. (If the latter holds, then $t = 2$ is an exceptional case.)

(4) Let $Q(s)$ be the subset of $P(s,s)$ constructed as in the proof of Theorem~\ref{thm: 4}, with $s = t$. Then $Q(s)$ is a `homogeneous' subset of $P(s,s)$ in the following sense. For each $i,j$, call the set $\{a_1 \cdots a_s \in P(s,s): a_i = j\}$ a \emph{hyperplane}. Then for every hyperplane $H(s)$ of $P(s,s)$, either $|Q(s) \cap H(s)| = (1/e + o(1))|H(s)|$ or $|Q(s) \cap H(s)| = (2/e + o(1))|H(s)|$ (as $s \to \infty$). Note that $|Q(s)| = (2/e + o(1))|P(s,s)|$.

\begin{conj} 
For every $\varepsilon > 0$ there exists $n(\varepsilon)$ such that if $s \geq n(\varepsilon)$ and $Q$ is any subset of $P(s,s)$ such that $|Q \cap H| > (1/e + \varepsilon)|H|$ for every hyperplane $H$ of $P(s,s)$, then $Q$ contains a complementary set.
\end{conj}

(5) For $s \geq 2$, $t \geq 1$, define $d(s,t)$ to be the smallest integer $h$ with the property that if $Q$ is any subset of $P(s,t)$ such that $h \leq \min\{q(a_i = j): 1 \leq i \leq t, 1 \leq j \leq s\}$, then $Q$ contains a complementary set. (In terms of partitions and transversals, $d(s,t)$ is the smallest integer $h$ with the property that if $A_1,\dots,A_t$ are $s$-cell partitions of the finite set $X$ which separate the points of $X$, and the smallest of all the cells in all the partitions has at least $h$ elements, then $A_1,\dots,A_t$ have a common transversal.)

Theorem~\ref{thm: 5} (and the Remark following) shows that $d(s,2) = [(1/2)(s + 1)]$. It would be interesting to find $d(s,t)$, or any upper bound for $d(s,t)$, for $t > 2$.

(6) Perhaps the most interesting of all the open questions is simply this: What is $b(s,3,1)$?

(7) Recently Livingston~\cite{livingston1983} has shown the following:
\begin{align*} c(s,t,k) &= s^k - s^{t - 1} - (s - 1)^{t - 1} + k + 1, \quad 1 \leq k \leq s - 1, s \geq 4, t \geq 3, \\
c(s,t,k) &= s^t - s^{t - 1} - s(s - 1)^{t - 1} + k + 1, \quad s \leq k \leq s(s - 1), \end{align*}
and either $s \geq 4$ and $t \geq 4$, or $s = k$ and $t = 3$.

\nocite{brown1976}


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