% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{}{}{} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography %\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} %\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments %\theoremstyle{plain} %\newtheorem{theorem}{Theorem} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{fact}[theorem]{Fact} %\newtheorem{observation}[theorem]{Observation} %\newtheorem{claim}[theorem]{Claim} %\theoremstyle{definition} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{example}[theorem]{Example} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{open}[theorem]{Open Problem} %\newtheorem{problem}[theorem]{Problem} %\newtheorem{question}[theorem]{Question} %\theoremstyle{remark} %\newtheorem{remark}[theorem]{Remark} %\newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%% our packages %%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage[scr, scaled=1.1]{rsfso} %same as mathrsfs script, using \mathcal{}, but less slanted \usepackage{tikz} \tikzstyle{white vertex}=[circle,minimum size=15pt,inner sep=0pt] \tikzstyle{vertex}=[circle,edge=black!100,minimum size=12pt,inner sep=0pt] \tikzstyle{edge} = [draw,line width=0.8pt,-,black!100] \tikzstyle{black arrow} = [draw,line width=1pt,>=latex, ->,black!100] \tikzstyle{black bi-arrow} = [draw,line width=1pt,>=latex, <->,black!100] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%% our macros %%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\comment}[1]{} \newcommand\define[1]{\textit{#1}} \newcommand\definehere[1]{\textit{#1}} \newcommand{\kvloop}[1]{K_{#1}^{\hbox{\tiny{loop}}}} \newcommand{\qi}[2]{\hbox{QI}(#1, #2)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Binary covering arrays on tournaments} % input author, affiliation, address and support information as follows; % the address should include the country, and does not have to include % the street address %%%%%%%%%%%%%% what we had for the time-being \author{Elizabeth Maltais \thanks{Supported by OGS.} ${}^{,1,2}$\qquad Lucia Moura \thanks{Supported by NSERC Discovery grant.} ${}^{,1}$\qquad Mike Newman ${}^{\dag,2}$\\ \small ${}^{1\:}$School of Electrical Engineering and Computer Science\\[-0.8ex] \small ${}^{2\:}$Department of Mathematics and Statistics\\[-0.8ex] \small University of Ottawa\\[-0.8ex] \small Ottawa, Canada\\ \small\tt emaltais@uottawa.ca, lucia@eecs.uottawa.ca, mnewman@uottawa.ca\\ %%%%%%%%%%%%%%%%%%%%%%% \comment{%%%%%%%%%% \and Lucia Moura \thanks{Supported by NASA grant ABC123.}\\ \small School of Electrical Engineering and Computer Science\\[-0.8ex] \small University of Ottawa\\[-0.8ex] \small Ottawa, Canada\\ \small\tt lucia@eecs.uottawa.ca \and Mike Newman \thanks{Supported by NASA grant ABC123.}\\ \small Department of Mathematics and Statistics\\[-0.8ex] \small University of Ottawa\\[-0.8ex] \small Ottawa, Canada\\ \small\tt mnewman@uottawa.ca }%%%%%%%%%%%%%%%%%%%%% } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \dateline{May 19, 2016}{Mar 10, 2018}{TBD} %\small Mathematics Subject Classifications: 05D05, 05B30} \MSC{05D05, 05B30} \Copyright{The authors. Released under the CC BY-ND license (International 4.0).} \begin{document} \maketitle \begin{abstract} We introduce graph-dependent covering arrays which generalize covering arrays on graphs, introduced by Meagher and Stevens (2005), and graph-dependent partition systems, studied by Gargano, K\"orner, and Vaccaro (1994). A covering array $\hbox{CA}(n; 2, G, H)$ (of strength 2) on column graph $G$ and alphabet graph $H$ is an $n\times |V(G)|$ array with symbols $V(H)$ such that for every arc $ij \in E(G)$ and for every arc $ab\in E(H)$, there exists a row $\vec{r} = (r_{1},\dots, r_{|V(G)|})$ such that $(r_{i}, r_{j}) = (a,b)$. We prove bounds on $n$ when $G$ is a tournament graph and $E(H)$ consists of the edge $(0,1)$, which corresponds to a directed version of Sperner's 1928 theorem. For two infinite families of column graphs, transitive and so-called circular tournaments, we give constructions of covering arrays which are optimal infinitely often. % keywords are optional \bigskip\noindent \textbf{Keywords:} covering array, Sperner system, covering array on graph \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{sec:intro} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Covering arrays are generalizations of orthogonal arrays that have been largely studied for their combinatorial interest and applications to software and network testing (see~\cite{Col2004} and references therein). Meagher and Stevens~\cite{MeaSte2005} extended the definition of a covering array to include a graph structure related to its columns, which we call a \define{column graph}. While covering arrays optimize the number of tests required to test all pairwise interactions between parameters of a system, the graph structure introduced in~\cite{MeaSte2005} is used to specify pairs of parameters that are known not to interact, yielding further reductions in the number of tests required. In addition to this increase in efficiency, their paper provides interesting connections between graph homomorphisms and Sperner systems. Tracing back to the work of Gargano, K\"orner, and Vaccaro~\cite{GarKorVac1993, GarKorVac1994} on Sperner capacities, another generalization of covering arrays, different from that introduced in~\cite{MeaSte2005}, is implicitly considered. A graph (which we call an \define{alphabet graph} to distinguish it from the column graphs considered in~\cite{MeaSte2005}) is used to encode pairs of symbols which must appear in every two distinct columns of the array. Using the terminology given in~\cite{GarKorVac1994}, classical covering arrays of strength 2 correspond to ``graph-dependent partition systems'', where the alphabet graph being considered is complete with a loop on every vertex. While their work includes the case of classical covering arrays, it also implicitly defines another generalization of covering arrays, where the pairwise coverage requirement is restricted to pairs of symbols specified by the edges of the alphabet graph. In this paper, we unify both types of graphs associated with covering arrays, generalizing the definition of covering arrays to graph-dependent covering arrays. Like in~\cite{MeaSte2005}, the binary alphabet case provides interesting connections with extremal set theory. We also consider the more general case of directed alphabet graphs. For a positive integer $n$, we write $[n]$ to denote the set of integers $\{1,\dots, n\}$. Throughout, the symbols $n$, $v$, and $k$ are used to represent positive integers. A complete graph on $k$ vertices is denoted $K_k$, and $\kvloop{v}$ denotes the graph $K_v$ with a loop on each vertex. \begin{definition}(\textsc{Graph-dependent Covering Array}) Let $G$ be a loopless directed graph with no parallel arcs, and let $V(G) = [k]$. Let $H$ be a directed graph with no parallel arcs, and let $V(H) = [v]$. A \definehere{covering array on $G$ and $H$}, denoted $\hbox{CA}(n; 2, G, H)$, \index{CA} is an $n\times k$ array with symbols from the alphabet $[v]$ and satisfying the following property: for every arc $ij \in E(G)$ and for every arc $ab\in E(H)$, there exists a row $r_l = (r_{l1},\dots, r_{lk})$ such that $(r_{li}, r_{lj}) = (a,b)$. The graphs $G$ and $H$ of a $\hbox{CA}(n; 2, G, H)$ are called the \define{column graph} and \define{alphabet graph}, respectively. The \define{covering array number for $G$ and $H$}, denoted $\hbox{CAN}(2, G, H)$, is the smallest integer $n$ for which a $\hbox{CA}(n; 2, G, H)$ exists. \end{definition} \begin{figure}[h] \begin{center} \begin{tikzpicture}[scale=0.95] \node[white vertex] (h) at (-0.5, 1.5){$H$}; \node[vertex] (1) at (-1,0){\tiny{1}}; \node[vertex] (2) at (0, 0.5){\tiny{2}}; \node[vertex] (3) at (0, -0.5){\tiny{3}}; \path[edge] (2)--(1)--(3); \node[vertex] (g1) at (1,1.5){\tiny{1}}; \node[vertex] (g2) at (2,1.5){\tiny{2}}; \node[vertex] (g3) at (3,1.5){\tiny{3}}; \node[vertex] (g4) at (4,1.5){\tiny{4}}; \path[edge] (g1)--(g2)--(g3)--(g4); \path[edge] (g1) edge [bend left] (g4); \node[white vertex] (g) at (2.5, 2.5){$G$}; \draw (1,0) node (c1) {\scriptsize{$\begin{array}{c} 1 \\ 1 \\ 2 \\ 3 \\ \end{array}$}}; \draw (2,0) node (c2) {\scriptsize{$\begin{array}{c} 2 \\ 3 \\ 1 \\ 1 \\ \end{array}$}}; \draw (3,0) node (c3) {\scriptsize{$\begin{array}{c} 1 \\ 1 \\ 2 \\ 3 \\ \end{array}$}}; \draw (4,0) node (c4) {\scriptsize{$\begin{array}{c} 2 \\ 3 \\ 1 \\ 1 \\ \end{array}$}}; \end{tikzpicture} \begin{tikzpicture}[scale=0.95] \node[white vertex] (blank) at (-3, 0){}; \node[white vertex] (h) at (-0.5, 1.5){$H'$}; \node[vertex] (1) at (-1,0){\tiny{1}}; \node[vertex] (2) at (0, 0.5){\tiny{2}}; \node[vertex] (3) at (0, -0.5){\tiny{3}}; \path[black arrow] (1) edge (2); \path[black arrow] (1) edge (3); \node[vertex] (g1) at (1,1.5){\tiny{1}}; \node[vertex] (g2) at (2,1.5){\tiny{2}}; \node[vertex] (g3) at (3,1.5){\tiny{3}}; \node[vertex] (g4) at (4,1.5){\tiny{4}}; \path[black arrow] (g1) edge (g2); \path[black arrow] (g2) edge [bend left] (g1); \path[black arrow] (g3) edge (g2); \path[black arrow] (g3) edge (g4); \path[black arrow] (g1) edge [bend left] (g4); \node[white vertex] (g) at (2.5, 2.5){$G'$}; \draw (1,0) node (c1) {\scriptsize{$\begin{array}{c} 1 \\ 1 \\ 2 \\ 3 \\ \end{array}$}}; \draw (2,0) node (c2) {\scriptsize{$\begin{array}{c} 2 \\ 3 \\ 1 \\ 1 \\ \end{array}$}}; \draw (3,0) node (c3) {\scriptsize{$\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ \end{array}$}}; \draw (4,0) node (c4) {\scriptsize{$\begin{array}{c} 2 \\ 3 \\ 3 \\ 3 \\ \end{array}$}}; \end{tikzpicture} \caption{Graph-dependent covering arrays.} \label{fig:S3andDirectedExample} \end{center} \end{figure} In Figure~\ref{fig:S3andDirectedExample}, we give two examples of column--alphabet graph pairs with corresponding covering arrays. The left example has undirected column and alphabet graphs, whereas the right example is directed; the underlying graphs of $G'$ and $H'$ are $G$ and $H$, respectively. Let $\vec{x} = (x_1,\dots, x_n)$ and $\vec{y} = (y_1,\dots, y_n)$ be two $v$-ary $n$-tuples, that is, $\vec{x}, \vec{y} \in [v]^n$. If, for every arc $ab\in E(H)$, there exists an index $i\in [n]$ such that $x_i = a$ and $y_i = b$, then we say that $\vec{x}$ is \definehere{$H$-dependent} with $\vec{y}$. In a $\hbox{CA}(n; 2, G, H)$, for all arcs $ij\in E(G)$, the $i$th column must be $H$-dependent with the $j$th column. Alphabet graphs and column graphs can in fact be undirected; if so, then our convention is to consider them as directed graphs in which each undirected edge corresponds to two oppositely oriented arcs. With our convention, the notion of $H$-dependence is a symmetric relation if and only if $H$ is an undirected alphabet graph. If one of $G$ or $H$ is undirected, then, in terms of covering arrays on $G$ and $H$, we can assume that both $G$ and $H$ are undirected. There may be situations in which it makes sense to allow alphabet graphs and column graphs to have parallel arcs, and to allow column graphs to have loops. Parallel arcs could encode the desired multiplicities of coverage (for specified pairs of symbols indicated by parallel arcs of the alphabet graph or entirely between columns specified by parallel arcs of the column graph). This would be analogous to the ``index" parameter of classical covering arrays. In the present paper, we do not consider these situations, but mention them as possible lines of future investigation. Some special cases that have been considered in the literature are the following: \vspace*{-0.1cm} \begin{itemize}\itemsep-3pt \item If the alphabet graph is $K_2$ and the column graph is $K_k$, then the columns of a $\hbox{CA}(n; 2, K_k, K_2)$ correspond to an antichain of subsets of $[n]$. In this case, Sperner's Theorem~\cite{Spe1928} gives $\hbox{CAN}(2, K_k, K_2) = \min\left\{n : k \leq {n\choose \lfloor n/2 \rfloor}\right\}$. \item If the alphabet graph is complete on $v$ vertices and has a loop on each vertex and the column graph is complete, then a $\hbox{CA}(n; 2, K_k, \kvloop{v})$ corresponds to a classical $v$-ary covering array of strength two, denoted $\hbox{CA}(n; 2, k, v)$. The columns of a $\hbox{CA}(n; 2, k, v)$ correspond to what is known as a ``qualitatively independent" collection of $v$-partitions of $[n]$.\footnote{For the particular alphabet graph $\kvloop{v}$, the notion of being $\kvloop{v}$-\textit{dependent} corresponds to being \textit{qualitatively independent}. Despite this discord in terminology, we adopted ``graph-dependent" since it captures the fact that the symbol coverage of our covering arrays on $G$ and $H$ depends on the edges of both of these accessory graphs. Moreover, the terminology and definition of ``graph-dependent partition systems" was already introduced in~\cite{GarKorVac1994} in order to generalize qualitative independence.} For a survey on classical covering arrays, see~\cite{Col2004}. \item If the alphabet graph is $\kvloop{v}$ and the column graph is $G$, then a $\hbox{CA}(n; 2, G, \kvloop{v})$ is what is known as a ``covering array on $G$," which we denote by $\hbox{CA}(n; 2, G, v)$. Covering arrays on (undirected column) graphs model testing applications where some factors are known not to interact. See~\cite{MeaSte2005} for more details. \item If the alphabet graph is $H$ and the column graph is complete, then the columns of a $\hbox{CA}(n; 2, K_k, H)$ correspond to an ``$H$-dependent collection" of $|V(H)|$-ary $n$-tuples, that is, a collection $\mathscr{C} = \{\vec{x}_1,\dots, \vec{x}_k\}$ in which $\vec{x}_i$ is $H$-dependent with $\vec{x}_j$ for every ordered pair of two distinct elements $\vec{x}_i,\vec{x}_j\in \mathscr{C}$. Asymptotic information-theoretic results related to $H$-dependent collections have been studied in~\cite{GarKorVac1993, GarKorVac1994}. \end{itemize} In Section~\ref{sec:DependenceGraphs}, we define $H$-dependence graphs and characterize graph-dependent covering arrays in terms of graph homomorphisms to $H$-dependence graphs. In the remaining sections, we focus on directed column graphs together with the binary alphabet graph $T_2$, where $V(T_2) = \{0,1\}$ and $E(T_2) = \{(0,1)\}$. In Section~\ref{sec:bounds-CAsGT2}, we give bounds for $\hbox{CAN}(2, G', T_2)$, where $G'$ is a directed column graph. In Section~\ref{sec:bounds-CAsTkT2}, we establish bounds for $\hbox{CAN}(2, G', T_2)$, where $G'$ is a tournament, that is, an orientation of a complete graph. In this case, determining $\hbox{CAN}(2, G', T_2)$ corresponds to an oriented version of Sperner's Theorem. In Section~\ref{sec:transitiveTournaments}, we give optimal constructions for covering arrays on transitive tournament column graphs, and we use these in Section~\ref{sec:asymptoticBounds} to obtain tight asymptotic bounds for the covering array number for all tournaments with alphabet graph $T_2$. In Section~\ref{sec:circularTournaments}, we consider another particular family of tournament column graphs which we call circular tournaments. We give constructions for covering arrays on circular tournaments and alphabet graph $T_2$; we show that these constructions are optimal infinitely often. In Section~\ref{sec:tournamentDataQuestions}, we conclude by giving some experimental data and open problems for binary covering arrays on tournaments. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{$H$-dependence graphs}\label{sec:DependenceGraphs} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we give a class of graphs, called $H$-dependence graphs, which characterizes the problem of determining $\hbox{CAN}(2, G, H)$ in terms of graph homomorphisms. The $H$-dependence graphs are the natural extension of qualitative independence graphs which were defined by Meagher and Stevens~\cite{MeaSte2005} when they characterized covering arrays on (undirected column) graphs via homomorphisms. Let $G$ and $H$ be graphs. A map $f:V(G)\rightarrow V(H)$ is a \define{homomorphism} of $G$ to $H$ if $f(u)f(v)\in E(H)$ whenever $uv\in E(G)$. If there exists a homomorphism of $G$ to $H$, then we say that $G$ is \definehere{homomorphic to} $H$ and we write $G\rightarrow H$. If $G\rightarrow H$ and $H\rightarrow G$, then we say that $G$ and $H$ are \define{homomorphically equivalent}. \begin{definition} Let $H$ be an alphabet graph with $V(H) = [v]$. The \definehere{$H$-dependence graph}, denoted $\qi{n}{H}$, is the graph with $V(\qi{n}{H}) = [v]^n$ and $\vec{x}\vec{y}\in E(\qi{n}{H})$ if and only if $\vec{x}$ is $H$-dependent with $\vec{y}$. \end{definition} If $H$ is undirected, then the $H$-dependence graph is a symmetric digraph, hence we consider it as an undirected graph. \begin{remark} If the alphabet graph is $\kvloop{v}$, that is, complete with a loop on every vertex, then our $\kvloop{v}$-dependence graph $\qi{n}{\kvloop{v}}$ is a proper supergraph of the qualitative independence graph with parameters $n$ and $v$, denoted $\qi{n}{v}$; see~\cite[Definition 10]{MeaSte2005}. In fact, $\qi{n}{\kvloop{v}}$ is homomorphically equivalent to the qualitative independence graph $\qi{n}{v}$. That $\qi{n}{v}\rightarrow \qi{n}{\kvloop{v}}$ is clear by inclusion. That $\qi{n}{\kvloop{v}}\rightarrow \qi{n}{v}$ follows from~\cite[Theorem 1]{MeaSte2005}. \end{remark} The next two results are straightforward extensions of analogous results given in~\cite{MeaSte2005}. %[Theorem 1, Lemma 1, Corollary 1]{MeaSte2005} \begin{proposition}\label{prop:CA(n,G,H)iffHomToQI(n,H)} Let $G$ be a column graph and let $H$ be an alphabet graph. Then there exists a $\hbox{CA}(n; 2, G, H)$ if and only if there is a homomorphism $G\rightarrow\qi{n}{H}$. In particular, \[\hbox{CAN}(2, G, H) = \min\{n : G\rightarrow \qi{n}{H}\}.\] \end{proposition} \begin{proof} Let $V(G) = [k]$ and let $V(H) = [v]$. If there exists a $\hbox{CA}(n; 2, G, H)$, then its columns are vertices of $\qi{n}{H}$. Define a map $f:V(G)\rightarrow V(\qi{n}{H})$ given by $f(i) = C_i$, where $C_i$ denotes the $i$th column of the $\hbox{CA}(n; 2, G, H)$ and $C_i = (c_{1i},\dots, c_{ni})\in [v]^n$ for each $i\in [k]$. If $ij\in E(G)$, then, for all $ab\in E(H)$, there exists an index $l \in [n]$ such that $c_{li} = a$ and $c_{lj} = b$. By definition of the $H$-dependence graph $\qi{n}{H}$, the vertex $C_i$ is adjacent to $C_j$ in $\qi{n}{H}$. Thus, $f$ defines a homomorphism. If there exists a homomorphism $f:V(G)\rightarrow V(\qi{n}{H})$, then we can build an $n\times k$ array with columns $C_1, \dots, C_k$ given by $C_i = f(i)$ for each $i\in[k]$. By the definition of $\qi{n}{H}$, it follows that this array is a $\hbox{CA}(n; 2, G, H)$. \end{proof} \begin{proposition}\label{prop:homBoundsOnCAN(G,H)} Let $H$ be an alphabet graph and let $G_1$ and $G_2$ be column graphs. If there is a homomorphism $G_1\rightarrow G_2$, then \[\hbox{CAN}(2, G_1, H) \leq \hbox{CAN}(2, G_2, H).\] In particular, for an undirected column graph $G$, we have \[\hbox{CAN}(2, K_{\omega(G)}, H) \leq \hbox{CAN}(2, G, H) \leq \hbox{CAN}(2, K_{\chi(G)}, H),\] where $\omega(G)$ and $\chi(G)$ denote the clique number and chromatic number of $G$. \qed \end{proposition} If $H_1$ and $H_2$ are alphabet graphs such that $V(H_1) = V(H_2) = [v]$ and $E(H_1)\subseteq E(H_2)$, then every pair of $H_2$-dependent $v$-ary $n$-tuples $\vec{x}$ and $\vec{y}$ are necessarily $H_1$-dependent. Thus, we have the following lemma. \begin{lemma} Let $H_1$ and $H_2$ be alphabet graphs such that $V(H_1) = V(H_2)$ and $E(H_1)\subseteq E(H_2)$. Then, for every $n$, the $H_2$-dependence graph $\qi{n}{H_2}$ is a subgraph of the $H_1$-dependence graph $\qi{n}{H_1}$. \qed \end{lemma} Going forward, the focus of this paper is on one particular directed alphabet graph: the transitive tournament on two vertices, which we denote by $T_2$. The vertex set of $T_2$ is $V(T_2) = \{0,1\}$ and its edge set is $E(T_2) = \{(0,1)\}$. The alphabet graph $T_2$ is the natural directed alphabet graph to consider on a binary alphabet. In Figure~\ref{fig:T2dependenceGraphs}, we give the $T_2$-dependence graphs $\qi{2}{T_2}$ and $\qi{3}{T_2}$. \begin{figure}[htb] \begin{center} \begin{tikzpicture} \node[white vertex] (blk) at (0,-1){}; \node[white vertex] (bk) at (0,5){}; \draw (0,0) node (00){\tiny{$\begin{array}{|c|} \hline 0 \\ 0 \\ \hline \end{array}$}}; \draw (-2,2) node (10){\tiny{$\begin{array}{|c|} \hline 1 \\ 0 \\ \hline \end{array}$}}; \draw (2,2) node (01){\tiny{$\begin{array}{|c|} \hline 0 \\ 1 \\ \hline \end{array}$}}; \draw (0,4) node (11){\tiny{$\begin{array}{|c|} \hline 1 \\ 1 \\ \hline \end{array}$}}; \path[black arrow] (00) edge (01); \path[black arrow] (00) edge (10); \path[black arrow] (00) edge (11); \path[black bi-arrow] (10) --(01); \path[black arrow] (01) edge (11); \path[black arrow] (10) edge (11); \end{tikzpicture} \begin{tikzpicture} \node[white vertex] (blank) at (-4, 0){}; \draw (0,0) node (000) {\tiny{$\begin{array}{|c|}\hline 0 \\ 0 \\ 0 \\ \hline \end{array}$}}; \draw (-2,1.9) node (001) {\tiny{$\begin{array}{|c|}\hline 0 \\ 0 \\ 1 \\ \hline \end{array}$}}; \draw (0,1.9) node (010) {\tiny{$\begin{array}{|c|}\hline 0 \\ 1 \\ 0 \\ \hline \end{array}$}}; \draw (2,1.9) node (100) {\tiny{$\begin{array}{|c|}\hline 1 \\ 0 \\ 0 \\ \hline \end{array}$}}; \draw (-2,4) node (110) {\tiny{$\begin{array}{|c|}\hline 1 \\ 1 \\ 0 \\ \hline \end{array}$}}; \draw (0,4) node (101) {\tiny{$\begin{array}{|c|}\hline 1 \\ 0 \\ 1 \\ \hline \end{array}$}}; \draw (2,4) node (011) {\tiny{$\begin{array}{|c|}\hline 0 \\ 1 \\ 1 \\ \hline \end{array}$}}; \draw (0,6) node (111) {\tiny{$\begin{array}{|c|}\hline 1 \\ 1 \\ 1 \\ \hline \end{array}$}}; \path[black arrow] (000)--(001); \path[black arrow] (000)--(010); \path[black arrow] (000)--(100); \path[black arrow] (000)--(110); \path[black arrow] (000)--(011); \path[black arrow] (000)edge [out=115, in=-115](101); \path[black arrow] (000)edge [out=65, in=290](111); \path[black arrow] (110)--(111); \path[black arrow] (101)--(111); \path[black arrow] (011)--(111); \path[black arrow] (001)--(101); \path[black arrow] (001)--(011); \path[black arrow] (010)--(110); \path[black arrow] (010)--(011); \path[black arrow] (100)--(110); \path[black arrow] (100)--(110); \path[black arrow] (001)--(111); \path[black arrow] (100)--(111); \path[black arrow] (100)--(101); \path[black arrow] (010) edge [out=125, in=250] (111); \path[black bi-arrow] (001)--(010); \path[black bi-arrow] (010)--(100); \path[black bi-arrow] (110)--(101); \path[black bi-arrow] (101)--(011); \path[black bi-arrow] (001)--(110); \path[black bi-arrow] (010)--(101); \path[black bi-arrow] (100)--(011); \path[black bi-arrow] (110) edge [out=35, in=145](011); \path[black bi-arrow] (001) edge [out=-35, in=-145](100); \end{tikzpicture} \caption{The $T_2$-dependence graphs $\qi{2}{T_2}$ and $\qi{3}{T_2}$. \label{fig:T2dependenceGraphs}} \end{center} \end{figure} A graph that is not homomorphic to any proper subgraph of itself is called a \define{core}. Every graph $G$ is homomorphic to a unique, up to isomorphism, core, denoted $G^{\bullet}$, such that $G^{\bullet}$ is an induced subgraph of $G$; see~\cite[Corollary 1.32]{HelNes2004}. Since every pair of distinct vertices in the $T_2$-dependence graph $\qi{n}{T_2}$ is joined by at least one arc, and since $\qi{n}{T_2}$ has no loops, it follows that $\qi{n}{T_2}$ is a core. \begin{lemma} For each $n\geq 1$, the $T_2$-dependence graph $\qi{n}{T_2}$ is a core.\qed \end{lemma} The vertex set of $\qi{n}{T_2}$ is the set of binary $n$-tuples, hence $|V(\qi{n}{T_2})| = 2^n$. Binary $n$-tuples are in bijection with the subsets of $[n]$ as follows. If $\vec{x}=(x_1,\dots,x_n)\in \{0,1\}^n$, then $\vec{x}$ corresponds to the subset $A_{\vec{x}} = \{i \in [n] : x_i = 1\}$. In terms of subsets of $[n]$, a binary $n$-tuple $\vec{x}$ is $T_2$-dependent with another binary $n$-tuple $\vec{y}$ if and only if the corresponding subsets $A_{\vec{x}},A_{\vec{y}}\subseteq [n]$ satisfy $A_{\vec{y}}\nsubseteq A_{\vec{x}}$. We often make use of this correspondence and refer to vertices of $\qi{n}{T_2}$ as subsets or $n$-tuples interchangeably. The \define{rank} of a binary $n$-tuple $\vec{x}$ is the number of times that `1' is an entry of $\vec{x}$. Equivalently, the rank of $\vec{x}$ is the cardinality $|A_{\vec{x}}|$. \begin{lemma}\label{lem:QInT2isMostlySymmetricDigraph} The graph $\qi{n}{T_2}$ has exactly $2^{2n-1} + 2^{n-1} - 3^n$ pairs of distinct vertices $A$ and $B$ such that both $AB$ and $BA$ are arcs of $\qi{n}{T_2}$. In particular, as $n\rightarrow \infty$, the proportion $(2^{2n-1} + 2^{n-1} - 3^n)/{2^n \choose 2}\rightarrow 1$, where ${2^n \choose 2}$ is the total number of pairs of vertices in $\qi{n}{T_2}$. \end{lemma} \begin{proof} First, we show that the number of pairs of distinct vertices $A, B\in V(\qi{n}{T_2})$ such that exactly one of $AB$ and $BA$ is an arc of $\qi{n}{T_2}$ is $3^n - 2^n$. Consider the vertices of $\qi{n}{T_2}$ as subsets of $[n]$. Each $k$-set is a proper subset of ${n-k\choose i}$ sets of rank $k+i$. For each fixed $k$-set $A$, the number of subsets in which $A$ is properly contained is thus equal to \[\sum_{i = 1}^{n-k}{n-k\choose i} = 2^{n-k} -1.\] Summing over all sets of rank $k$ and summing over all ranks $k\in\{0,1,\dots, n\}$, we have \[\sum_{k=0}^n{n\choose k}(2^{n-k}-1) = \sum_{k=0}^n{n\choose k}2^{n-k} - \sum_{k=0}^n{n\choose k} = 2^n\sum_{k=0}^n{n\choose k}\left(\frac{1}{2}\right)^k - 2^n = 3^n - 2^n\] pairs of distinct vertices $A, B\in V(\qi{n}{T_2})$ such that $A\subset B$. These are the only pairs of vertices for which $BA \in E(\qi{n}{T_2})$ and $AB \not\in E(\qi{n}{T_2})$. Thus, there are $3^n - 2^n$ pairs of distinct vertices in $V(\qi{n}{T_2})$ such that exactly one of $AB$ and $BA$ is an arc of $\qi{n}{T_2}$. Now, there are ${2^n \choose 2}$ pairs of distinct vertices in $\qi{n}{T_2}$, of which $3^n - 2^n$ pairs are not symmetrically adjacent. Thus, the number of symmetrically adjacent pairs is ${2^n\choose 2} - [3^n - 2^n] = 2^{n-1}(2^n-1) - 3^n + 2^n= 2^{2n-1} + 2^{n-1} - 3^n$. Asymptotically, we have \[\lim_{n\rightarrow\infty}\frac{2^{2n-1} + 2^{n-1} - 3^n}{{2^n \choose 2}} = \lim_{n\rightarrow \infty} \frac{4^n + 2^n - 2\cdot 3^n}{4^n - 2^n} = 1.\qedhere\] \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Bounds for binary covering arrays on directed column graphs}\label{sec:bounds-CAsGT2} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we investigate the problem of finding $\hbox{CAN}(2, G', T_2)$ for directed column graphs $G'$. We give bounds which compare the covering array number for a directed column graph $G'$ and alphabet graph $T_2$ with a binary covering array on the underlying graph $G$ of $G'$. Throughout this section, we use $G$ to denote the underlying graph of a given directed graph $G'$. For a graph $G$ and integers $k$, $v$, we denote $\hbox{CAN}(2, K_k,\kvloop{v})$ simply as $\hbox{CAN}(2, k, v)$, and we denote $\hbox{CAN}(2, G, \kvloop{v})$ by $\hbox{CAN}(2, G, v)$. \begin{theorem}\label{thm:logboundForG'} Let $G'$ be a directed graph with at least one arc, and let $G$ be its underlying graph. Then \[\lceil\log_2\chi(G)\rceil \leq \hbox{CAN}(2, G', T_2) \leq \hbox{CAN}(2, G, 2)-1.\] \end{theorem} \begin{proof} For the lower bound, let $m=\hbox{CAN}(2,G',T_2)$, and consider a $\hbox{CA}(m; 2, G', T_2)$. The columns of this array form a proper vertex-colouring of $G$ since adjacent vertices in $G$ correspond to columns of the $\hbox{CA}(m; 2, G', T_2)$ that must be $T_2$-dependent in some direction which makes these columns distinct. Therefore $\chi(G)\leq2^{m}$, and so $\lceil\log_2\chi(G)\rceil\leq m =\hbox{CAN}(2, G', T_2)$. For the upper bound, let $n = \hbox{CAN}(2, G, 2)$ and consider an optimal $\hbox{CA}(n; 2, G, 2)$. We may assume without loss of generality that the first row is all zeros. Delete this row and we are left with a $\hbox{CA}(n-1; 2, G', K_2)$, for any (directed) subgraph $G' \subseteq G$. Thus, $\hbox{CAN}(2, G', T_2) \leq \hbox{CAN}(2, G', K_2)\leq \hbox{CAN}(2, G, 2)-1$. \end{proof} For $G'$ with $\chi(G) = 2$, we have a complete characterization of directed graphs that achieve the lower bound of Theorem~\ref{thm:logboundForG'}, based on the following definition and observations. We call a directed graph $G'$ a \define{consistently oriented bipartite graph} if the underlying graph of $G'$ is bipartite and there is a bipartition $(X, Y)$ of $V(G')$ such that all arcs of $G'$ are directed from $X$ to $Y$. If $G'$ is a directed graph, then $\hbox{CAN}(2,G',T_2)$ can be equivalently defined as the minimum number of consistently oriented bipartite subgraphs into which one can partition the arc set of $G'$. Indeed, the set of arcs of $G'$ covered by any particular row of a $\hbox{CA}(n; 2, G', T_2)$ forms a consistently oriented bipartite subgraph. In particular, the condition $\hbox{CAN}(2,G',T_2)=1$ is equivalent to there being a homomorphism $G' \to \qi{1}{T_2}\cong T_2$, which is equivalent to $G'$ being a consistently oriented bipartite graph. For $\chi(G) = 2$, the lower bound of Theorem~\ref{thm:logboundForG'} holds with equality if and only if $\hbox{CAN}(2, G', T_2) = 1$, which means the lower bound of Theorem~\ref{thm:logboundForG'} is achieved solely by consistently oriented bipartite graphs. For higher chromatic numbers, we do not have complete characterizations of graphs achieving the lower bound of Theorem~\ref{thm:logboundForG'}; however, for $\chi(G) = 3, 4$, we do have a necessary condition, as follows. If $G'$ contains a directed odd cycle, then by~\cite[Lemma~4.4.11]{Mal2016}, we have $\hbox{CAN}(2, G', T_2) \geq 3$. For $\chi(G) = 3, 4$, the lower bound of Theorem~\ref{thm:logboundForG'} is given by $\hbox{CAN}(2, G', T_2) \geq 2$. Thus, for these chromatic numbers, a necessary condition to achieve the lower bound of Theorem~\ref{thm:logboundForG'} is for $G'$ to be free of any directed odd cycles. For all chromatic numbers $\chi\geq 2$, there exist directed graphs $G'$ for which the lower bound of Theorem~\ref{thm:logboundForG'} holds with equality. Specifically, if $G'$ is a transitive $k$-tournament, then the underlying graph of $G'$ is $K_k$; in this case, $\hbox{CAN}(2, G', T_2) = \lceil\log_2k\rceil = \lceil\log_2\chi(G)\rceil$ (see Section~\ref{sec:transitiveTournaments} for more details). To see that the upper bound of Theorem~\ref{thm:logboundForG'} holds with equality infinitely often, let $G'$ be a directed graph such that $G'$ contains a directed odd cycle $\vec{C}_{2l+1}$ and the underlying graph $G$ of $G'$ satisfies $\chi(G) = 3$. Since $\chi(G) = 3$, it follows from~\cite[Theorem 1]{MeaSte2005} that $\hbox{CAN}(2, G, 2) = 4$. In this case, the upper bound of Theorem~\ref{thm:logboundForG'} is $\hbox{CAN}(2, G, 2) -1 = 4-1=3$. Now, let $K_3^*$ denote $K_3$ in which each undirected edge is considered as two oppositely oriented arcs. We have that $G'\rightarrow K_3^*\rightarrow\qi{3}{T_2}$ and, since homomorphisms compose, $\hbox{CAN}(2, G', T_2)\leq 3$ by Proposition~\ref{prop:CA(n,G,H)iffHomToQI(n,H)}. Finally, since $G'$ contains $\vec{C}_{2l+1}$, it follows from~\cite[Lemma~4.4.11]{Mal2016} that $\hbox{CAN}(2, G', T_2) \geq 3$. Thus $\hbox{CAN}(2, G', T_2) = 3$, which, in this case, achieves the upper bound of Theorem~\ref{thm:logboundForG'}. More examples of directed column graphs whose covering array numbers achieve the upper bound of Theorem~\ref{thm:logboundForG'} can be found in Appendix~\ref{app:tournamentData}; these examples are tournament column graphs whose underlying graphs have chromatic numbers $\chi = 3, 5, 9$ (see ``adjacency vectors" given in Table~\ref{tab:tournamentsdata} for $k = 3, 5, 9$). Tournament column graphs are explored in more detail in Section~\ref{sec:bounds-CAsTkT2}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Bounds for binary covering arrays on tournaments}\label{sec:bounds-CAsTkT2} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we give bounds on $\hbox{CAN}(2, G', T_2)$ where the column graph $G'$ is a $k$-tournament. We consider two specific families of tournaments as column graphs: transitive tournaments and ``circular" tournaments. We give constructions which are optimal infinitely often for these families of column graphs. A \definehere{$k$-tournament} is an orientation of the complete graph $K_k$. Our convention for $k$-tournaments is to label the vertices as $1,2,\dots, k$ (except when $k=2$ in which case we use 0 and 1). We are interested in $k$-tournaments as column graphs with $T_2$ as the alphabet graph. Among all $k$-tournaments, is there one with the largest covering array number? Do binary covering arrays on $k$-tournaments generally require as many rows as classical binary covering arrays? First, since the $T_2$-dependence graph $\qi{n}{T_2}$ has no loops while the underlying graph of a tournament is complete, any homomorphism of a tournament to $\qi{n}{T_2}$ must be vertex-injective. Thus, the analogue of Proposition~\ref{prop:CA(n,G,H)iffHomToQI(n,H)} for binary covering arrays on tournaments is the following. \begin{proposition}\label{prop:tournamentCAN(T_2)iffSubgraphQI-T_2} Let $O_k$ be any $k$-tournament. Then there exists a $\hbox{CA}(n; 2, O_k, T_2)$ if and only if $O_k$ is a subgraph of $\qi{n}{T_2}$. In particular, \[\hbox{CAN}(2, O_k, T_2) = \min\{n: O_k\subseteq \qi{n}{T_2}\}.\tag*{\qed}\] \end{proposition} Since the underlying graph of a $k$-tournament is the complete graph $K_k$ with $\chi(K_k) = k$, Theorem~\ref{thm:logboundForG'} gives the following bound. \begin{corollary}\label{cor:CANvsCANTournamentsBound} Let $O_k$ be a $k$-tournament. Then \[\lceil\log_2k\rceil \leq \hbox{CAN}(2, O_k, T_2) \leq \hbox{CAN}(2, k, 2)-1.\tag*{\qed}\] \end{corollary} For $k$-tournaments, the upper bound of Corollary~\ref{cor:CANvsCANTournamentsBound} can be tightened as follows. \begin{theorem}\label{thm:boundsForCAN2TournamentT2} Let $k\geq 2$ and let $O_k$ be any $k$-tournament. Then \[\lceil \log_2k\rceil \leq \hbox{CAN}(2, O_k, T_2)\leq \min\left\{n : k \leq 2\textstyle{n-1\choose\lfloor (n-1)/2\rfloor}\right\}.\] \end{theorem} \begin{proof} The lower bound is given by Corollary~\ref{cor:CANvsCANTournamentsBound}. To prove the upper bound, we give a construction as follows. Let $n$ be a positive integer such that $2\leq k\leq 2{n-1\choose \lfloor (n-1)/2 \rfloor}$. Then $\lfloor k/2 \rfloor \leq \lceil k/2 \rceil \leq {n-1\choose \lfloor (n-1)/2 \rfloor}$. Take any maximum matching $M$ of $K_k$ (the underlying graph of $O_k$). Partition $V(O_k)$ into two parts of sizes $\lceil k/2 \rceil$ and $\lfloor k/2 \rfloor$ such that the ends of all edges in $M$ are oriented from the first part to the second in $O_k$ (if $k$ is odd, we add the unmatched vertex to the first part). Relabel the vertices of $O_k$ so that the vertices of the first part of the partition are labelled $1,\dots, \lceil k/2\rceil$, and the vertices of the second part are labelled $\lceil k/2 \rceil + 1,\dots, k$. To construct a $\hbox{CA}(n; 2, O_k, T_2)$, we first build an $(n-1)\times k$ array with columns $C_1,\dots, C_k$ corresponding to $\lfloor \frac{n-1}{2} \rfloor$-subsets of $[n-1]$ as follows. Take $\lceil k/2 \rceil$ of the $\lfloor \frac{n-1}{2}\rfloor$-subsets of $[n-1]$ in some order, followed by the same first $\lfloor k/2 \rfloor$ columns repeated in the same order, that is, $C_1,\dots, C_{\lceil k/2 \rceil}$ are distinct $\lfloor \frac{n-1}{2} \rfloor$-sets and $C_{i + \lceil k/2 \rceil} = C_i$ for $1\leq i \leq \lfloor k/2 \rfloor$. Add an $n$th row to cover the arcs of $M$. This additional row has zeros as its first $\lceil k/2 \rceil$ entries and ones as its last $\lfloor k/2 \rfloor$ entries. Since every two distinct $\lfloor \frac{n-1}{2} \rfloor$-sets are $K_2$-dependent, any two distinct columns $C_i$ and $C_j$ (of length $n-1$) are $K_2$-dependent except when $|j - i| = \lceil k/2 \rceil$. The extra row ensures that we cover the arcs of $M$. Note, when $k=2$, this extra row is in fact the only row of the constructed array. Thus, we have constructed a $\hbox{CA}(n; 2, O_k, T_2)$, and it follows that $\hbox{CAN}(2, O_k, T_2)\leq n$ whenever $k\leq 2{n-1\choose \lfloor (n-1)/2 \rfloor}$. \end{proof} For $k$-tournament column graphs, the upper bound given in Theorem~\ref{thm:boundsForCAN2TournamentT2} is an improvement over the upper bound given in Corollary~\ref{cor:CANvsCANTournamentsBound} infinitely often. An exact expression for the upper bound of Corollary~\ref{cor:CANvsCANTournamentsBound} is known~\cite{Kat1973, KleSpe1973}, and this can be rewritten as follows: \[\hbox{CAN}(2, k, 2) - 1 = \min\left\{n:k\leq\textstyle{n-1\choose \lfloor n/2 \rfloor -1}\right\} - 1 = \min\left\{n : k \leq \textstyle{n\choose \lfloor(n+1)/2\rfloor - 1}\right\}.\] For all $n$, we have $2{n-1\choose\lfloor (n-1)/2\rfloor} > {n\choose \lfloor(n+1)/2\rfloor - 1}$. Consequently, for all $k\geq 2$, we have \begin{equation}\label{eq:hound} \min\left\{n : k \leq 2\textstyle{n-1\choose\lfloor (n-1)/2\rfloor}\right\}\leq \min\left\{n : k \leq \textstyle{n\choose \lfloor(n+1)/2\rfloor - 1}\right\} = \hbox{CAN}(2,k, 2) - 1. \end{equation} For each $n\geq 1$, for all $k$ lying in the range ${n\choose \lfloor(n+1)/2\rfloor - 1} < k \leq 2\textstyle{n-1\choose\lfloor (n-1)/2\rfloor}$, the inequality in~\eqref{eq:hound} is strict. Thus, for infinitely many $k$-tournaments, the upper bound given in Theorem~\ref{thm:boundsForCAN2TournamentT2} is a strict improvement over that given in Corollary~\ref{cor:CANvsCANTournamentsBound}. For fixed $k$, we are interested in the spectrum of covering array numbers which arises when we consider all $k$-tournament column graphs. Are the bounds of Theorem~\ref{thm:boundsForCAN2TournamentT2} achieved for all $k$? Among all $k$-tournaments, which ones have the largest or smallest covering array numbers? For the lower bound of Theorem~\ref{thm:boundsForCAN2TournamentT2}, we have a complete answer by applying Proposition~\ref{prop:tournamentCAN(T_2)iffSubgraphQI-T_2}. \begin{theorem}\label{thm:tournsAchievingLogKLB} A $k$-tournament $O_k$ achieves the lower bound of Theorem~\ref{thm:boundsForCAN2TournamentT2} if and only if $O_k$ is a subgraph of the $T_2$-dependence graph $\qi{\lceil \log_2 k \rceil}{T_2}$. \qed \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Transitive tournaments}\label{sec:transitiveTournaments} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Aside from the general answer given by Theorem~\ref{thm:tournsAchievingLogKLB}, we also have a specific infinite family of tournament column graphs achieving the lower bound of Theorem~\ref{thm:boundsForCAN2TournamentT2}, namely, transitive tournaments. Let $k\geq 2$. The \definehere{transitive $k$-tournament}, denoted $T_k$, is the tournament with $V(T_k) = [k]$ and arcs $ij\in E(T_k)$ if and only if $ij$ and $j + 2l = i+t$ for some $t\in\{1,\dots, l-1\}$, and for all $j=i+l$ such that $i\in \{1,\dots, l\}$. By definition of $\Omega_{2l+1}$, we have $ij\in E(\Omega_{2l+1})$ whenever either $ij$ and $j + 2l + 1 = i+t$ for some $t\in\{1,\dots, l\}$. Thus, whenever $ij\in E(\Omega_{2l})$, it follows that $g(i)g(j) = ij\in E(Y)$. Therefore, $g$ is a vertex-injective homomorphism of $\Omega_{2l}$ to $Y$. Since $\Omega_{2l}$ is a tournament, it follows that $g$ is an isomorphism. By Proposition~\ref{prop:circularTournamentAutGroups}, $\Omega_{2l+1}$ is vertex-transitive. Therefore, we can delete any vertex of $\Omega_{2l+1}$ in order to obtain a copy of $\Omega_{2l}$. Now, let $k = 2l$ and let $X$ denote $\Omega_k$ with the vertex $l$ deleted. We claim that $\Omega_{k-1}\cong X$. Define a bijection $f:V(\Omega_{k-1})\rightarrow V(X)$ by $f(i) = i$ for $1\leq i \leq l-1$ and $f(i) = i+1$ for $l\leq i\leq k-1$. Suppose $ij\in E(\Omega_{2l-1})$. Consider the following cases: \begin{enumerate} \item If $1\leq i < j\leq l-1$, then $f(i)f(j) = ij$. By definition of $\Omega_{2l-1}$, we must have $j = i+t$ for some $t\in\{1,\dots,l-2\}$. Thus, $j = i+t$ for some $ti$. Then $1\leq j-i \leq k$. In this case, we consider all possibilities for the parity of $i$ and $j$. If $i$ and $j$ have the same parity, then $1\leq \lceil j/2 \rceil - \lceil i/2 \rceil = j/2 -i/2 \leq k/2$; in these cases, the $i$th column of $A$ ($C_{\lceil i/2\rceil}$) and the $j$th column of $A$ ($C_{\lceil j/2\rceil}$) cover $\{(i,0), (j, 1)\}$ since the $\hbox{CA}(n; 2, \Omega_k^+, T_2)$ must cover $\{(\lceil i/2 \rceil, 0), (\lceil j/2 \rceil, 1)\}$. If $i$ and $j$ have opposite parity, then $1\leq j-i \leq k-1$, since $k$ is even. It now follows that $0\leq \lceil j/2 \rceil - \lceil i/2 \rceil \leq j/2 + 1/2 - i/2 \leq k/2$. If $\lceil j/2 \rceil - \lceil i/2 \rceil = 0$, then $i$ and $j$ correspond to the same column $C_{j/2}$; in this case, $j = i+1$ and the extra row of alternating zeros and ones covers $\{(i,0), (j,1)\}$. Otherwise, $1\leq \lceil j/2 \rceil - \lceil i/2 \rceil \leq j/2 + 1/2 - i/2 \leq k/2$; in these cases, the $i$th column of $A$ ($C_{\lceil i/2\rceil}$) and the $j$th column of $A$ ($C_{\lceil j/2\rceil}$) cover $\{(i,0), (j, 1)\}$ since the $\hbox{CA}(n; 2, \Omega_k^+, T_2)$ must cover $\{(\lceil i/2 \rceil, 0), (\lceil j/2 \rceil, 1)\}$. Now, suppose $j0$, we have \begin{align} \hbox{CAN}(2, \Omega_{2^{L+1}}^+, T_2) &\leq \hbox{CAN}(2, \Omega_{2^{L}}^+, T_2) + 1 \notag\\ &\leq \hbox{CAN}(2, \Omega_2^+, T_2) + L \notag\\ &= 2+L. \label{eq:hog} \end{align} Let $k\leq 2^{L+1}$. Then $\hbox{CAN}(2, \Omega_k, T_2) \leq \hbox{CAN}(2, \Omega_{2^{L+1}}^+, T_2)$ since $\Omega_k\subseteq \Omega_{2^{L+1}}\subset \Omega_{2^{L+1}}^+$. Using this fact, the bound given in~\eqref{eq:hog}, and the lower bound of Theorem~\ref{thm:boundsForCAN2TournamentT2}, for all $k$ such that $2^L< k \leq 2^{L+1}$, we have \[\lceil\log_2k\rceil \leq \hbox{CAN}(2, \Omega_{k}, T_2) \leq \hbox{CAN}(2, \Omega_{2^{L+1}}^+, T_2) \leq L+2 = \lceil\log_2k\rceil + 1. \tag*{\qedhere}\] \end{proof} Similarly, we use Proposition~\ref{prop:CANomega2kleqCANomegak+1} to show that there are infinitely many values of $k$ for which $\hbox{CAN}(2, \Omega_k, T_2) = \lceil \log_2k\rceil$. \begin{theorem}\label{thm:infinitelyManyOptimalCircularTournaments} Let $m$ be an even integer. If there exists a $\hbox{CA}(\lceil\log_2m\rceil; 2, \Omega_m^+, T_2)$, then, for all $L\geq 0$ and for all $k$ such that $2^{L+\lceil\log_2m\rceil-1} < k \leq m\cdot 2^L$, we have \[\hbox{CAN}(2, \Omega_{k}, T_2) = \lceil\log_2k\rceil.\] \end{theorem} \begin{proof} Suppose a $\hbox{CA}(\lceil\log_2m\rceil; 2, \Omega_m^+, T_2)$ exists for some even integer $m$. By applying Proposition~\ref{prop:CANomega2kleqCANomegak+1} iteratively, for all $L>0$, we have \begin{align} \hbox{CAN}(2, \Omega_{m\cdot 2^L}^+, T_2) &\leq \hbox{CAN}(2, \Omega_{m\cdot 2^{L-1}}^+, T_2) + 1\notag\\ &\leq \hbox{CAN}(2, \Omega_{m}^+, T_2) + L\notag\\ &\leq\lceil\log_2m\rceil + L\label{eq:fox} \end{align} Now, fix $L\geq 0$ and let $k$ be an integer such that $2^{L+\lceil\log_2m\rceil-1} < k \leq m\cdot 2^L$. Then $\lceil \log_2 k \rceil = \lceil\log_2m\rceil + L$. Since we have the inclusions $\Omega_k\subseteq \Omega_{m\cdot2^L} \subset \Omega_{m\cdot2^L}^+$, it follows from Proposition~\ref{prop:homBoundsOnCAN(G,H)} that $\hbox{CAN}(2, \Omega_k, T_2) \leq \hbox{CAN}(2, \Omega_{m\cdot 2^L}^+, T_2)$. Now, by Theorem~\ref{thm:boundsForCAN2TournamentT2} and~\eqref{eq:fox}, for all $k$ such that $2^{L+\lceil\log_2m\rceil-1} < k \leq m\cdot 2^L$, we have \[\lceil\log_2k\rceil \leq \hbox{CAN}(2, \Omega_k, T_2) \leq \hbox{CAN}(2, \Omega_{m\cdot 2^L}^+, T_2) \leq \lceil\log_2m\rceil + L = \lceil\log_2k\rceil.\qedhere\] \end{proof} \begin{corollary}\label{cor:CircTournLowerBoundInfinitelyOften} For all integers $L\geq 0$ and for any integer $k$ such that $2^{L+4} < k \leq 20\cdot 2^L$, the covering array number for covering arrays on circular $k$-tournament column graphs and the alphabet graph $T_2$ is given by \[\hbox{CAN}(2, \Omega_k, T_2) = \lceil \log_2k \rceil.\] \end{corollary} \begin{proof} For $m = 20$, we have $\lceil \log_2m\rceil = 5$. The following is a $\hbox{CA}(\lceil\log_220\rceil; 2, \Omega_{20}^+, T_2)$: \begin{center} \tabcolsep=2pt \begin{tabular}{|cccccccccccccccccccc|} \multicolumn{1}{c}{\tiny{1}} & \tiny{2} & \tiny{3} & \tiny{4} & \tiny{5} & \tiny{6} & \tiny{7} & \tiny{8} & \tiny{9} & \tiny{10} & \tiny{11} & \tiny{12} & \tiny{13} & \tiny{14} & \tiny{15} & \tiny{16} & \tiny{17} & \tiny{18} & \tiny{19} & \multicolumn{1}{c}{\tiny{20}}\\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline \end{tabular} \end{center} By applying Theorem~\ref{thm:infinitelyManyOptimalCircularTournaments} with $m = 20$, it follows that for all $L\geq 0$, for all $k$ such that $2^{L+\lceil\log_220\rceil -1} < k \leq 20\cdot2^L$, we have $\hbox{CAN}(2, \Omega_k, T_2) = \lceil\log_2k\rceil.$ \end{proof} \begin{remark}\label{rem:choosingm} For any even $m$ such that a $\hbox{CA}(\lceil\log_2m\rceil; 2, \Omega_m^+, T_2)$ exists, we can apply Theorem~\ref{thm:infinitelyManyOptimalCircularTournaments} to obtain a result like Corollary~\ref{cor:CircTournLowerBoundInfinitelyOften}. For each $L\geq 0$, the value of $m$ that maximizes the range $2^{L+\lceil\log_2m\rceil - 1} < k \leq m\cdot 2^L$ corresponds to an even value of $m$ for which $m/{2^{\lceil\log_2m\rceil - 1}}$ is as close to $2$ as possible. \end{remark} By computer search, we determined $\hbox{CAN}(2, \Omega_k, T_2)$ for all $k\leq 37$. We also determined $\hbox{CAN}(2, \Omega_k^+, T_2)$ for all even values of $k\leq 36$. The only values of $k\leq 37$ for which $\hbox{CAN}(2, \Omega_k, T_2) = \lceil\log_2k\rceil$ are $k \in \{2, 9, 17, 18, 19, 20, 33, 34, 35, 36, 37\}$. The only even values of $k\leq 36$ for which $\hbox{CAN}(2, \Omega_k^+, T_2) = \lceil\log_2k\rceil$ are $k \in \{18, 20, 34, 36\}$. Among these values, $m = 20$ was our best candidate for obtaining the strongest version of Corollary~\ref{cor:CircTournLowerBoundInfinitelyOften} with respect to Remark~\ref{rem:choosingm}. For $k=2$ and $k=9$, examples of the $\hbox{CA}(\lceil\log_2\rceil; 2, \Omega_k, T_2)$ obtained from our computer search are given here: \quad$\hbox{CA}(1; 2, \Omega_2, T_2)$\qquad \small \tabcolsep=2pt \begin{tabular}{|cc|} \multicolumn{1}{c}{\tiny{1}} &\multicolumn{1}{c}{\tiny{2}}\\ \hline 0 & 1 \\ \hline \end{tabular} \normalsize \hfill $\hbox{CA}(4; 2, \Omega_9, T_2)$\qquad \small \tabcolsep=2pt \begin{tabular}{|ccccccccc|} \multicolumn{1}{c}{\tiny{1}} &\tiny{2} &\tiny{3} &\tiny{4} &\tiny{5} &\tiny{6} &\tiny{7} &\tiny{8} &\multicolumn{1}{c}{\tiny{9}}\\ \hline 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0\\ \hline \end{tabular} \normalsize \qquad\qquad \medskip \noindent One example of a $\hbox{CA}(5; 2, \Omega_{20}^+, T_2)$ obtained in our search is given in Corollary~\ref{cor:CircTournLowerBoundInfinitelyOften}. From this array, we obtain a $\hbox{CA}(6; 2, \Omega_{40}^+, T_2)$ using Proposition~\ref{prop:CANomega2kleqCANomegak+1}. By removing appropriate columns from the $\hbox{CA}(5; 2, \Omega_{40}^+, T_2)$ which correspond to the way in which $\Omega_{k-1}\subset\Omega_k$, we obtain optimal $\hbox{CA}(\lceil\log_2k\rceil, \Omega_k, T_2)$ for $k = 38, 39$. Hence, the next value of $k$ for which the covering array number is unknown is 41. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Data and questions for binary covering arrays on tournaments}\label{sec:tournamentDataQuestions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Transitive tournaments and circular tournaments meet the lower bound of Theorem~\ref{thm:boundsForCAN2TournamentT2} for infinitely many values of $k$. We are interested in knowing how often the upper bound of Theorem~\ref{thm:boundsForCAN2TournamentT2} is met, or whether there is a tighter bound for tournament column graphs. Using a computer search and the database of tournaments given in~\cite{McK2017}, for each $k\leq 9$, we determined $\hbox{CAN}(2,O_k, T_2)$ for every $k$-tournament $O_k$ (up to isomorphism). Our findings are summarized in Table~\ref{tab:tournamentAnalysis} and more details are given in Appendix~\ref{app:tournamentData}. In Table~\ref{tab:tournamentAnalysis}, we use L.B. and U.B. to denote the lower and upper bounds of Theorem~\ref{thm:boundsForCAN2TournamentT2}, respectively. In Table~\ref{tab:tournamentAnalysis}, we write CAN to abbreviate the covering array number on a given tournament column graph with alphabet graph $T_2$. \begin{table}[htb] \begin{center} \begin{tabular}{|c||c|c|l|} \hline $k$ & L.B. & U.B. & $k$-tournaments achieving U.B. \\ \hline \hline 2 & 1 & 1 & $T_2$ (the unique 2-tournament)\\ \hline 3 & 2 & 3 & only $\Omega_3$\\ \hline 4 & 2 & 3 & exactly those 4-tournaments that contain $\Omega_3$ as a subgraph\\ \hline 5 & 3 & 4 & only $\Omega_5$\\ \hline 6 & 3 & 4 & $\Omega_6$ and 12 others (not all contain $\Omega_5$ as a subgraph)\\ \hline 7 & 3 & 5 & no 7-tournaments achieve U.B.\\ & & & $\Omega_7$ and 380 others with $\hbox{CAN}=4$\\ \hline 8 & 3 & 5 & no 8-tournaments achieve U.B.\\ & & & $\Omega_8$ and 6836 others with $\hbox{CAN}=4$\\ \hline 9 & 4 & 5 & only two 9-tournaments achieve U.B. (neither is isomorphic to $\Omega_9$)\\ \hline \end{tabular} \caption{Summary of analysis for small tournaments.\label{tab:tournamentAnalysis}} \end{center} \end{table} Our analysis of small tournaments shows that for $k\in \{2, 3, 4, 5, 6, 9\}$, the upper bound of Theorem~\ref{thm:boundsForCAN2TournamentT2} is attained. \begin{problem}\label{pro:numericalUBonCANtournaments} Determine whether the upper bound of Theorem~\ref{thm:boundsForCAN2TournamentT2} is met infinitely often. If not, determine a tight numerical upper bound on $\hbox{CAN}(2, O_k, T_2)$ for any $k$-tournament $O_k$. \end{problem} Based on our data in Table~\ref{tab:tournamentAnalysis}, we ask whether the bounds of Theorem~\ref{thm:logkCircularlogkplusone} hold for all $k$-tournaments. \begin{problem} For any $k$-tournament $O_k$, is $\hbox{CAN}(2, O_k, T_2) \in \{\lceil\log_2k\rceil, \lceil\log_2k\rceil + 1\}$? \end{problem} For circular tournaments in particular, Theorem~\ref{thm:logkCircularlogkplusone} determines $\hbox{CAN}(2, \Omega_k, T_2)$ to within 1 row. The following problem is also of interest. \begin{problem} For each $L\geq2$, for all $k$ in the range $2^{L-1}=latex, ->,gray!80!black] (7) edge (4); \path[draw,line width=1.1pt,>=latex, ->,gray!80!black] (8) edge (5); \path[draw,line width=1.1pt,>=latex, ->,gray!80!black] (9) edge (6); \path[draw,line width=1pt,>=latex, ->,red!90!black] (4) edge (8); \path[draw,line width=1pt,>=latex, ->,red!90!black] (4) edge (9); \path[draw,line width=1pt,>=latex, ->,red!90!black] (5) edge (7); \path[draw,line width=1pt,>=latex, ->,red!90!black] (5) edge (9); \path[draw,line width=1pt,>=latex, ->,red!90!black] (6) edge (7); \path[draw,line width=1pt,>=latex, ->,red!90!black] (6) edge (8); \path[draw,line width=1pt,>=latex, ->,green!60!black] (1) edge (4); \path[draw,line width=1pt,>=latex, ->,green!60!black] (1) edge (5); \path[draw,line width=1pt,>=latex, ->,green!60!black] (1) edge (6); \path[draw,line width=1pt,>=latex, ->,green!60!black] (3) edge (4); \path[draw,line width=1pt,>=latex, ->,green!60!black] (3) edge (5); \path[draw,line width=1pt,>=latex, ->,green!60!black] (3) edge (6); \path[draw,line width=1pt,>=latex, ->,green!60!black] (2) edge (7); \path[draw,line width=1pt,>=latex, ->,green!60!black] (2) edge (8); \path[draw,line width=1pt,>=latex, ->,green!60!black] (2) edge (9); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (4) edge (2); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (5) edge (2); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (6) edge (2); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (7) edge (1); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (8) edge (1); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (9) edge (1); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (7) edge (3); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (8) edge (3); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (9) edge (3); \node[white vertex] (x) at (0, -2.5){$X_{9a}$}; \end{tikzpicture} \qquad\qquad\qquad \begin{tikzpicture}[scale=0.78] \node[vertex](1) at (-1.5, 3.5){\tiny{1}}; \node[vertex](2) at (0, 3.5){\tiny{2}}; \node[vertex](3) at (1.5, 3.5){\tiny{3}}; \path[black arrow] (1)--(2); \path[black arrow] (2)--(3); \path[black arrow] (3) edge [bend right](1); \node[vertex](4) at (-3, 1.5){\tiny{4}}; \node[vertex](5) at (-3, 0){\tiny{5}}; \node[vertex](6) at (-3, -1.5){\tiny{6}}; \path[black arrow] (4)--(5); \path[black arrow] (5)--(6); \path[black arrow] (6) edge [bend left](4); \node[vertex](7) at (3, 1.5){\tiny{7}}; \node[vertex](8) at (3, 0){\tiny{8}}; \node[vertex](9) at (3, -1.5){\tiny{9}}; \path[black arrow] (9)--(8); \path[black arrow] (8)--(7); \path[black arrow] (7) edge [bend left](9); \path[draw,line width=1.1pt,>=latex, ->,gray!80!black] (7) edge (4); \path[draw,line width=1.1pt,>=latex, ->,gray!80!black] (8) edge (5); \path[draw,line width=1.1pt,>=latex, ->,gray!80!black] (9) edge (6); \path[draw,line width=1pt,>=latex, ->,red!90!black] (4) edge (8); \path[draw,line width=1pt,>=latex, ->,red!90!black] (4) edge (9); \path[draw,line width=1pt,>=latex, ->,red!90!black] (5) edge (7); \path[draw,line width=1pt,>=latex, ->,red!90!black] (5) edge (9); \path[draw,line width=1pt,>=latex, ->,red!90!black] (6) edge (7); \path[draw,line width=1pt,>=latex, ->,red!90!black] (6) edge (8); \path[draw,line width=1pt,>=latex, ->,green!60!black] (1) edge (4); \path[draw,line width=1pt,>=latex, ->,green!60!black] (1) edge (5); \path[draw,line width=1pt,>=latex, ->,green!60!black!] (1) edge (6); \path[draw,line width=1pt,>=latex, ->,green!60!black] (3) edge (4); \path[draw,line width=1pt,>=latex, ->,green!60!black!] (3) edge (5); \path[draw,line width=1pt,>=latex, ->,green!60!black!] (3) edge (6); \path[draw,line width=1pt,>=latex, ->,green!60!black] (2) edge (7); \path[draw,line width=1pt,>=latex, ->,green!60!black!] (2) edge (8); \path[draw,line width=1pt,>=latex, ->,green!60!black!] (2) edge (9); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (4) edge (2); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (5) edge (2); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (6) edge (2); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (7) edge (1); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (8) edge (1); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (9) edge (1); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (7) edge (3); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (8) edge (3); \path[draw,line width=1pt,>=latex, ->,blue!90!black] (9) edge (3); \node[white vertex] (x) at (0, -2.5){$X_{9b}$}; \end{tikzpicture} \end{center} \noindent The exceptional 9-tournaments $X_{9a}$ and $X_{9b}$ are both regular with in- and outdegree 4. Both are isomorphic to their own reversal. Neither is isomorphic to $\Omega_9$. Both have exactly three automorphisms which correspond to the rotations of the directed 3-cycle $(4, 5, 6)$ (and simultaneous rotations of the directed 3-cycles on vertices $7, 8, 9$) while the vertices $1, 2, 3$ remain fixed. In $X_{9a}$ and $X_{9b}$, the directed 3-cycles on vertices $7, 8, 9$ are oppositely oriented. From our computer search, we know that $\hbox{CAN}(2, X_{9a}, T_2)>4$. On the other hand, since $9 <{5\choose 2}$, finding a $\hbox{CA}(5; 2, X_{9a}, T_2)$ is easy; simply take columns corresponding to the 2-subsets of $\{1,\dots, 5\}$ which form an antichain. The same works for $X_{9b}$. \end{document}