%%%% 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}