%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-48/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 for Three Partitions}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, \emph{Common transversals for three partitions}, Bogazici University
  J. \textbf{10} (1983), 47--49.}\bigskip\end{center}

\begin{abstract}
This note contains some questions and a result concerning common transversals for partitions (and in particular for three partitions) of a finite set.
\end{abstract}

In a famous paper of 1935~\cite{hall1935}, Philip Hall gave the first (and still the best!) necessary and sufficient condition for the existence of a system of distinct representatives, or transversal, of a family of sets.

(A set $T$ is a \emph{transversal} of the family $A = (A(1),\dots,A(s))$ if there is a bijection $f$ from $\{1,\dots,s\}$ onto $T$ such that $f(i)$ is an element of $A(i)$, $1 \leq i \leq s$. Hall's Theorem, beautiful in its simplicity, states that if $A = (A(1),\dots,A(s))$ is any family of $s$ sets (not necessarily distinct), then a transversal for the family $A$ exists if and only if the following condition holds: For each $k$, $1 \leq k \leq s$, the union of any $k$ of the sets $A(i)$ contains at least $k$ elements.)

One of the most singular open questions in transversal theory~\cite{mirsky1971} is the question of whether or not there exists a simple necessary and sufficient condition for the existence of a common transversal for three families.

(If several families of sets are given, say $A_1,\dots,A_t$, where $A = (A(i,1),\dots,A(i,s))$, $1 \leq i \leq t$, a set $T$ is a \emph{common transversal} of $A_1,\dots,A_t$ if $T$ is a transversal of each $A_i$, $1 \leq i \leq t$. Hall's theorem immediately gives a simple necessary and sufficient condition for the existence of a common transversal of two families.)

Recently, Judith Q. Longyear~\cite{longyear1977} discovered an extremely simple \emph{sufficient} condition for the existence of a common transversal for any number of families. (See~\cite{longyear1977} for details.)

Among other results, Longyear showed that if $A_1,A_2$ are $s$-cell partitions of a set $X$ with the property that distinct elements of $X$ belong to distinct cells of $A_1$, or to distinct cells of $A_2$, then $A_1,A_2$ have a common transversal if $|X| > s^2 - 2s + 2$, and that $s^2 - 2s + 2$ is best possible.

This result can be visualized in the following way. Let $L(s)$ be the $s \times s$ square of lattice points in the plane defined by $L(s) = (a_1,a_2): 0 \leq a_1,a_2 \leq s- 1\}$, and let $X$ be a subset of $L(s)$. Call the sets $X \cap \{(a_1,a_2):a_1 = j\}$, $0 \leq j \leq s-1$, the \emph{columns of $X$}, and the sets $X \cap \{(a_1,a_2): a_2 = j\}$, $0 \leq j \leq s - 1$, the \emph{rows of $X$}. Then regarding the columns of $X$ as the cells of a partition $A_1$ of $X$, and regarding the rows of $X$ as the cells of a partition $A_2$ of $X$, Longyear's result says that the maximum size of a subset $X$ of $L(s)$ such that each row and each column of $X$ is non-empty and $X$ does \emph{not} contain any subset $T$ meeting each row and each column of $X$ in exactly one element, is $|X| = s^2 - 2s + 2$.

In this note we want to call attention to a number of questions related to this result, and especially to the $3$-dimensional case, referred to in the title.

Thus let $M(s)$ be the $s \times s \times s$ cube of lattice points defined by $M(s) = \{(a_1,a_2,a_3): 0 \leq a_1,a_2,a_3 \leq s - 1\}$, and let $X$ be a subset of $M(s)$. The \emph{planes of $X$} are the $3$s sets $X \cap \{(a_1,a_2,a_3): a_i = j\}$, $ 1\leq i \leq 3$, $0 \leq j \leq s - 1$.

What is the maximum size $f(s)$ of a subset $X$ of $M(s)$ such that each plane of $X$ is non-empty and $X$ does not contain any subset $T$ meeting each plane of $X$ in exactly one point?

Taking $X = M(s) \cap \{(x,0,0), (0,y,0), (x,y,z): x \ne 0, y \ne 0\}$ shows that $2(s-1) + s(s-1)^2 \leq f(s)$. It is also known (\cite{longyear1977}) that $f(s) \leq s^3 - s^2$. Probably one can show that $f(s) = s^3 - (2 + o(1))s^2$ as $s \to \infty$. Best of all would be to find the exact value of $f(s)$! (the author is inclined to believe that the construction above is ``best possible", so that $f(s) = 2(s-1)+ (s-1)^2s$.)

It is natural to generalize this problem to the $t$-dimensional ``cube" $M(s,t) = \{(a_1,\dots,a_t): 0 \leq a_i \leq s - 1, 1 \leq i \leq t\}$. When $X$ is a subset of $M(s,t)$, the \emph{hyperplanes of $X$} are the sets $X \cap \{(a_1,\dots,a_t): a_i = j\}$, $1 \leq i \leq t$, $ 0 \leq j \leq s - 1$. What is the maximum size $f(s,t)$ of a subset $X$ of $M(s,t)$ such that each hyperplane of $X$ is non-empty and $X$ does not contain any subset $T$ meeting each hyperplane of $X$ in exactly one point? Is it possible that the computation of $f(s,t)$ for all $s,t$ is an NP-complete problem?

Setting $s = t$, and generalizing the construction above which gives $2(s - 1) + (s - 1)^2s \leq f(s)$ (see~\cite{brown1984-1} for details) leads to the following \emph{conjecture}. For every $\epsilon > 0$ there exists $n(\epsilon)$ such that if $s \geq n(\epsilon)$ and $X$ is any subset of $M(s,s)$ with each hyperplane of $X$ containing at least $(1/e + \epsilon)s^{-1}$ points, then $X$ contains a subset $T$ meeting each hyperplane of $X$ in exactly one point (where $e = 2.718\dots$). 

Other related questions can be found in~\cite{brown1984-1} and~\cite{longyear1977}.


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