% 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 $i<j$.



\begin{theorem}\label{thm:CANTk=logk}
Let $k\geq 2$. Then $\hbox{CAN}(2, T_k, T_2) = \lceil\log_2(k)\rceil = \min\{ n : k \leq 2^n\}.$
\end{theorem}

\begin{proof} Let $A$ and $B$ be subsets of $[n]$ (corresponding to vertices of $\qi{n}{T_2}$). Notice that $AB\in E(\qi{n}{T_2})$ if and only if $B\nsubseteq A$.   We can thus
 order the vertices of $\qi{n}{T_2}$ in non-descending order of  rank, and this ordering has the property that $AB\in E(\qi{n}{T_2})$ whenever $A$ precedes $B$.
 With this ordering in place, it is clear that $\qi{n}{T_2}$ contains $T_{2^n}$ as an induced subgraph since there is a strict total ordering on the vertices of $T_{2^n}$.
It now follows that for all $k\leq 2^n$ there exist homomorphisms $T_k\rightarrow T_{2^n}\rightarrow \qi{n}{T_2}$.  By Proposition~\ref{prop:CA(n,G,H)iffHomToQI(n,H)}, we have $\hbox{CAN}(2, T_k, T_2)\leq \lceil\log_2k\rceil.$
By Theorem~\ref{thm:boundsForCAN2TournamentT2}, we have $\hbox{CAN}(2, T_k, T_2)\geq \lceil \log_2k\rceil$, which completes the proof.
\end{proof}


The proof of Theorem~\ref{thm:CANTk=logk} provides a simple construction for $\hbox{CA}(\lceil\log_2k\rceil; 2, T_k, T_2)$.  If $n = \lceil \log_2k\rceil$, then $k$ columns corresponding to subsets of $[n]$ in non-descending order of rank form the columns of a  $\hbox{CA}(\lceil \log_2k\rceil; 2, T_k, T_2)$.  In the following theorem, we use this construction for transitive tournaments to build binary covering arrays.  The construction we provide in Theorem~\ref{thm:transTournConstructionOfCAs} is not optimal in general; however, it is optimal asymptotically, and it produces binary covering arrays built from  blocks of rows corresponding to the simple construction for binary covering arrays on transitive tournaments.


\begin{theorem}\label{thm:transTournConstructionOfCAs}
 For each integer $k\geq 2$, there exists an integer $m\leq \lceil\log_2k\rceil +1$ such that \[\hbox{CAN}(2, k, 2)\leq \hbox{CAN}(2, T_k, T_2) + \hbox{CAN}(2, T_m, T_2)+2.\]
 In particular,  \[\hbox{CAN}(2, k, 2)\leq \lceil\log_2k\rceil + \lceil\log_2(\lceil\log_2k\rceil + 1)\rceil+2.\]
\end{theorem}

\begin{proof}
  Let $n = \lceil\log_2k\rceil$, and let $m$ be the minimum number of binomial coefficients needed to write
$k \leq {n\choose a_1}+{n\choose a_2}+\dots+{n\choose a_m}$, where $0\leq a_1 < a_2 <\dots<a_m\leq n$. Clearly, $m \leq n+1 = \lceil \log_2k\rceil + 1.$


Now, build a $\hbox{CA}(n; 2, T_k, T_2)$ as described in the proof of Theorem~\ref{thm:CANTk=logk}.  Without loss of generality, we may assume that the columns of the $\hbox{CA}(n; 2, T_k, T_2)$ correspond to the subsets of $[n]$ of ranks $a_1, a_2,\dots, a_{m-1}$ and (as many as needed of) the $a_m$-subsets of $[n]$, sorted in non-decreasing order of rank.  Note, for each $i\in [m]$, the columns corresponding to the $a_i$-subsets form an antichain and are thus already $K_2$-dependent.    We extend this $\hbox{CA}(n; 2, T_k, T_2)$ into a $\hbox{CA}(n + \lceil\log_2m\rceil; 2, K_k, K_2)$ by appending to it at most $\lceil\log_2(\lceil \log_2k \rceil + 1)\rceil$ additional rows.  These additional rows correspond to the rows of a $\hbox{CA}(\lceil \log_2m \rceil; 2, T_m, T_2)$ whose columns we denote by $C_1, C_2,\dots, C_m$.  Under each column of the $\hbox{CA}(n; 2, T_k, T_2)$ that corresponds to an $a_i$-subset of $[n]$, we put a copy of $C_{m-i+1}$, as depicted in Figure~\ref{fig:TransTournArray}.

\begin{figure}[htb]
\begin{center}
$\underbrace{\overbrace{\begin{array}{|ccc|}\hline
                                  &&\\
                                  &&\\
                                  &&\\
                                  &&\\
                                 \hline
                                 \hline
                                  &&\\
                                  C_m &\cdots & C_m\\
                                   &&\\
                                  \hline
                               \end{array}}^{\hbox{$a_1$-sets}}}_{\hbox{${n\choose a_1}$ times}}
\underbrace{\overbrace{\begin{array}{|cccc|}\hline
                                  && &\\
                                  && &\\
                                   & & &\\
                                  && &\\
                                  \hline
                                  \hline
                                   & & &\\
                                   C_{m-1}&C_{m-1} &\cdots & C_{m-1}\\
                                   & & &\\
                                  \hline
                                 \end{array}}^{\hbox{$a_2$-sets}}}_{\hbox{${n\choose a_2}$ times}} \  \cdots \underbrace{\overbrace{\begin{array}{|ccc|}\hline
                                  &&\\
                                  &&\\
                                  &&\\
                                  &&\\
                                  \hline
                                  \hline
                                   & & \\
                                   C_1  &\cdots & C_1\\
                                   & & \\
                                  \hline
                                \end{array}}^{\hbox{$a_m$-sets}}}_{\hbox{up to ${n\choose a_m}$ times}}$

\caption{Construction of $\hbox{CA}(\lceil\log_2k\rceil+\lceil\log_2m\rceil; 2, K_k, K_2)$, where $m\leq \lceil\log_2k\rceil+1$. \label{fig:TransTournArray}}
\end{center}
\end{figure}


The array given in Figure~\ref{fig:TransTournArray} is indeed a $\hbox{CA}(n+\lceil\log_2m\rceil; 2, K_k, K_2)$. Thus, we have
\begin{align}
\hbox{CAN}(2, K_k, K_2)
&\leq \hbox{CAN}(2, T_k, T_2) + \hbox{CAN}(2, T_m, T_2)\notag\\
&\leq \hbox{CAN}(2, T_k, T_2) + \hbox{CAN}(2, T_{\lceil\log_2k\rceil+1}, T_2)\notag\\
&=\lceil\log_2k\rceil + \lceil\log_2(\lceil \log_2k \rceil + 1)\rceil\label{bound:transTournConstruction}
\end{align}
By adding two constant rows to the $\hbox{CA}(n+\lceil\log_2m\rceil; 2, K_k, K_2)$, namely a row of all zeros and another row of all ones, we get a $\hbox{CA}(n+\lceil\log_2m\rceil +2; 2, k, 2)$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Asymptotic bounds}\label{sec:asymptoticBounds}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

For directed column graphs $G'$ and alphabet graph $T_2$, we now show that, asymptotically, $\hbox{CAN}(2, G', T_2)$ grows logarithmically with respect to the chromatic number of the underlying graph of $G'$.


\begin{theorem}\label{thm:asymptoticLogChi}
For each $c\geq 2$, let $G_c'$ be some directed graph with underlying graph $G_c$ satisfying $\chi(G_c) = c$.  Then
\[\lim_{c\rightarrow\infty}\hbox{CAN}(2, G_c', T_2)/\log_2\chi(G_c) = 1.\]
\end{theorem}

\begin{proof}
Since $\hbox{CAN}(2, G_c', T_2) \leq \hbox{CAN}(2, \chi(G_c), 2)$, it follows from Theorems~\ref{thm:logboundForG'} and~\ref{thm:transTournConstructionOfCAs} that, for each $c\geq 2$, we have
\begin{align*}
\lceil\log_2\chi(G_c)\rceil \leq \hbox{CAN}(2, G_c', T_2)\leq \lceil\log_2\chi(G_c)\rceil + \lceil\log_2(\lceil\log_2\chi(G_c)\rceil + 1)\rceil + 1.
\end{align*}
Clearly, the above bounds are asymptotically equal to $\log_2\chi(G_c)$, as $c\rightarrow\infty$.
\end{proof}


\begin{corollary}\label{thm:CANTkasymptoticLogk}
For each $k\geq 2$, let $O_k$ denote some $k$-tournament.  Then
\[\lim_{k\rightarrow\infty}\hbox{CAN}(2, O_k, T_2)/\log_2k = 1.\tag*{\qed}\]
\end{corollary}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Circular tournaments}\label{sec:circularTournaments}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


In addition to transitive tournaments, we consider one other infinite family of tournament column graphs, which we call circular tournaments.  We prove that the covering array number for circular $k$-tournaments and alphabet graph $T_2$ is always $\lceil\log_2k\rceil$ or $\lceil\log_2k\rceil +1$.





\begin{definition}The \definehere{circular $k$-tournament},  denoted $\Omega_k$, has vertex set $V(\Omega_k) = [k]$ and arcs as follows.  If $k$ is odd, then  $ij\in E(\Omega_k)$ if and only if $j = i+t$ for some $t$ such that $1\leq t \leq \lfloor k/2 \rfloor$ (addition is done modulo $k$).  If $k$ is even, then $ij \in E(\Omega_k)$ whenever $j = i+t$ for some $t$ such that $1\leq t <  k/2$ (addition is done modulo $k$); moreover, $(i, i+k/2)\in E(\Omega_k)$ for all $i$ such that $1\leq i \leq k/2$.
\end{definition}

In Figure~\ref{fig:circularTournaments}, we depict several circular $k$-tournaments.

\begin{figure}[htb]
\begin{center}
\begin{tikzpicture}[scale=1.2]
\node[white vertex] (0) at (0.5,-0.3){$\Omega_2$};
\node[vertex](1) at (0,1){\tiny{1}};
\node[vertex](2) at (1,1){\tiny{2}};
\path[black arrow] (1)--(2);
\end{tikzpicture}
\begin{tikzpicture}[scale=1.2]
\node[white vertex] (blank) at (-0.4, 0){};
\node[white vertex] (0) at (0.5,-0.8){$\Omega_3$};
\node[vertex](1) at (0,1){\tiny{1}};
\node[vertex](2) at (1,1){\tiny{2}};
\node[vertex](3) at (0.5,0){\tiny{3}};
\path[black arrow] (1)--(2);\path[black arrow] (2)--(3); \path[black arrow] (3)--(1);
\end{tikzpicture}
\begin{tikzpicture}[scale=1.2]
\node[white vertex] (blank) at (-0.5, 0){};
\node[white vertex] (0) at (0.5,-0.8){$\Omega_4$};
\node[vertex](1) at (0,1){\tiny{1}};
\node[vertex](2) at (1,1){\tiny{2}};
\node[vertex](3) at (1,0){\tiny{3}};
\node[vertex](4) at (0,0){\tiny{4}};
\path[black arrow] (1)--(2); \path[black arrow] (2)--(3);\path[black arrow] (3)--(4); \path[black arrow] (4)--(1);
\path[black arrow] (1)--(3);\path[black arrow] (2)--(4);
\end{tikzpicture}
\begin{tikzpicture}[scale=1.2]
\node[white vertex] (blank) at (-1.2, 0){};
\node[white vertex] (0) at (0,-1.2){$\Omega_5$};
\node[vertex] (1) at (0,1){\tiny{1}};
\node[vertex] (2) at (0.8,0.4){\tiny{2}};
\node[vertex] (3) at (0.5, -0.5){\tiny{3}};
\node[vertex] (4) at (-0.5, -0.5){\tiny{4}};
\node[vertex] (5) at (-0.8, 0.4){\tiny{5}};
\path[black arrow] (1)--(2); \path[black arrow] (2)--(3);\path[black arrow] (3)--(4);\path[black arrow] (4)--(5);\path[black arrow] (5)--(1);
\path[black arrow] (1)--(3); \path[black arrow] (3)--(5); \path[black arrow] (5)--(2); \path[black arrow] (2)--(4); \path[black arrow] (4)--(1);
\end{tikzpicture}
\begin{tikzpicture}[scale=1.2]
\node[white vertex] (blank) at (-1.3, 0){};
\node[white vertex] (0) at (0,-1.5){$\Omega_6$};
\node[vertex] (1) at (0,1){\tiny{1}};
\node[vertex] (2) at (0.9,0.5){\tiny{2}};
\node[vertex] (3) at (0.9, -0.5){\tiny{3}};
\node[vertex] (4) at (0, -1){\tiny{4}};
\node[vertex] (5) at (-0.9, -0.5){\tiny{5}};
\node[vertex] (6) at (-0.9, 0.5){\tiny{6}};
\path[black arrow] (1)--(2); \path[black arrow] (2)--(3);\path[black arrow] (3)--(4);\path[black arrow] (4)--(5);\path[black arrow] (5)--(6);
\path[black arrow] (6)--(1);
\path[black arrow] (1)--(3); \path[black arrow] (2)--(4); \path[black arrow] (3)--(5); \path[black arrow] (4)--(6); \path[black arrow] (5)--(1);
\path[black arrow] (6)--(2); \path[black arrow] (1)--(4); \path[black arrow] (2)--(5); \path[black arrow] (3)--(6);
\end{tikzpicture}
\caption{Circular tournaments. \label{fig:circularTournaments}}
\end{center}
\end{figure}







 Determining  $\hbox{CAN}(2, \Omega_k, T_2)$ for all $k$ is an interesting extremal problem that corresponds to an oriented version of Sperner's Theorem~\cite{Spe1928}.  In terms of covering arrays, Sperner's Theorem determines $\hbox{CAN}(2, K_k, K_2)$ for all $k$.

Here, we give some important properties of circular tournaments.

\begin{proposition}\label{prop:circularTournamentAutGroups}
If $k$ is odd, then the circular tournament $\Omega_k$ is vertex-transitive.
If $k$ is even, then the automorphism group of $\Omega_k$ is trivial.
\end{proposition}

\begin{proof}
Let $k$ be odd, and let $i,j\in V(\Omega_k)$ be two distinct vertices.  We can write $j = i+x \pmod k$ for a unique $x\in \{1,\dots, k-1\}$.   The map $f:V(\Omega_k)\rightarrow V(\Omega_k)$ given by $f(u) = u+x\pmod k$ is an automorphism such that $f(i) = j$.  Thus, when $k$ is odd, $\Omega_k$ is vertex-transitive, as claimed.

Now, let $k$ be even and write $k = 2l$.  The vertices of $\Omega_{k}$ are of two types: the vertices labelled $1,2,\dots, l$ which have outdegree $l$ and indegree $l-1$, and the vertices labelled $l+1,l+2,\dots,2l$ which have outdegree $l-1$ and indegree $l$.  Suppose $f:V(\Omega_k)\rightarrow  V(\Omega_k)$ is an automorphism such that $f(i) = j$ for some vertices $i,j\in V(\Omega_k)$. If $i\in \{1,\dots, l\}$, then in order for its in- and outdegree to match, $j$ must also be from among the vertices  in the set $\{1,\dots, l\}$.  In order for the neighbours of $i$ and $j$ to have the correct in- and outdegrees, both $i$ and $j$ must have the same number of neighbours from the set $\{l+1,\dots, 2l\}$.  This can happen only if $i = j$.
The argument when $i\in\{l+1,\dots, 2l\}$ is similar.  Thus, when $k$ is even, the automorphism group of $\Omega_k$ is trivial.
\end{proof}

\begin{proposition}\label{prop:InclusionOfCircularTournaments}
For all $k\geq 3$, the circular tournament $\Omega_{k}$ contains an induced subgraph isomorphic to $\Omega_{k-1}$.  In particular, when $k = 2l+1$, we can delete any vertex to obtain a copy of $\Omega_{2l}$.  When $k = 2l$, we can delete either vertex $l$ or $l+1$ from $\Omega_{2l}$ in order to obtain a copy of $\Omega_{2l-1}$.
\end{proposition}

\begin{proof}
Let $k=2l+1$, and let $Y$ denote the subgraph of $\Omega_{2l+1}$ in which the vertex $2l+1$ is deleted.  Define a bijection $g:V(\Omega_{2l})\rightarrow V(Y)$ by $g(i) = i$ for $1\leq i\leq 2l$.  By definition of $\Omega_{2l}$, we have $ij\in E(\Omega_{2l})$ whenever either $i<j$ and $j = i+t$ for some $t\in\{1,\dots, l-1\}$, or $i>j$ 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 $i<j$ and $j = i+t$ for some $t\in\{1,\dots, l\}$, or $i>j$ 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 $t<l$, and by definition of $\Omega_{2l}$, we have $f(i)f(j) \in E(X)$.
  \item If  $1\leq i\leq l-1$ and $l\leq j\leq 2l-1$, then $f(i)f(j) = i(j+1)$. By definition of $\Omega_{2l-1}$, we must have $j = i+t$ for some $t\in\{1,\dots,l-1\}$.  Thus, $t<l$ and so $f(i)f(j) \in E(X)$.
  \item If  $l\leq i < j\leq 2l-1$, then $f(i)f(j) = (i+1)(j+1)$. By definition of $\Omega_{2l-1}$, we must have $j = i+t$ for some $t\in\{1,\dots,l-1\}$.  Thus, $j+1 = i+1+t$ for some $t<l$ and so $f(i)f(j) \in E(X)$.
  \item If  $l\leq i\leq 2l-1$ and $1\leq j\leq l-1$, then $f(i)f(j) = (i+1)j$. By definition of $\Omega_{2l-1}$, we must have $j + 2l-1 = i+t$ for some $t\in\{1,\dots,l-1\}$.  Thus, $j + 2l = i+1 + t$ and so, by definition of $\Omega_{2l}$, we have $f(i)f(j) \in E(X)$.
\end{enumerate}


Since the above cases cover all arcs of the tournament $\Omega_{2l-1}$, it follows that $f$ is an isomorphism. Similarly, we can show that $\Omega_{2l-1}$ is isomorphic to the subgraph of $\Omega_{2l}$ in which the vertex $l-1$ is deleted.
\end{proof}


Next, we give a recursive construction for covering arrays with alphabet graph $T_2$ in which  we make use of a supergraph of the circular tournament, which we denote $\Omega_k^+$, defined for even values of $k$ as follows. Let $k$ be even. The vertex set of $\Omega_k^+$ is $V(\Omega_k^+) = [k]$ and  $ij\in E(\Omega_k)$ if and only if $j = i+t$ for some $t$ such that $1\leq t \leq k/2$ (addition is done modulo $k$).  The  difference between $\Omega_k$ and $\Omega_k^+$ is that $\Omega_k^+$ has a pair of oppositely oriented arcs joining the vertices $i, j\in [k]$ with  $|j-i| = k/2$.  In particular, $\Omega_k^+$ is not a tournament, but does contain subgraphs isomorphic to $\Omega_m$, for all $m\leq k$.  Consequently, we have $\hbox{CAN}(2,\Omega_m, T_2)\leq \hbox{CAN}(2, \Omega_k^+, T_2)$ for all circular tournaments $\Omega_m$ with $m\leq k$.

\begin{proposition}\label{prop:CANomega2kleqCANomegak+1}
Let $k$ be even. Then $\hbox{CAN}(2, \Omega_{2k}^+, T_2) \leq \hbox{CAN}(2, \Omega_k^+, T_2) + 1$.
\end{proposition}


\begin{proof}
Let $n = \hbox{CAN}(2, \Omega_k^+, T_2)$.  For $1\leq j \leq k$,
let $C_j$ denote the $j$th column of a $\hbox{CA}(n; 2, \Omega_k^+, T_2)$.  Take two copies of this array and interleave their columns as shown in Figure~\ref{fig:recursiveOmega+}. Add a row of alternating zeros and ones. Let us call the array we obtain $A$.

\begin{figure}[htb]
\begin{center}
\begin{tikzpicture}
\node[white vertex] (a) at (-1,-0.25){$A$};
\draw (0,0) node (1){\tiny{$\begin{array}{|c|}\hline
                              \\ \\
                             C_1 \\
                              \\ \\ \hline
                           \end{array}$}};
\draw (1,0) node (11){\tiny{$\begin{array}{|c|}\hline
                              \\ \\
                             C_1 \\
                              \\ \\ \hline
                           \end{array}$}};
\draw (2,0) node (2){\tiny{$\begin{array}{|c|}\hline
                              \\ \\
                             C_2 \\
                              \\ \\ \hline
                           \end{array}$}};
\draw (3,0) node (21){\tiny{$\begin{array}{|c|}\hline
                              \\ \\
                             C_2 \\
                              \\  \\ \hline
                           \end{array}$}};
\draw (4,0) node (d) {$\cdots$};
\draw (5,0) node (2){\tiny{$\begin{array}{|c|}\hline
                              \\ \\
                             C_k \\
                              \\  \\ \hline
                           \end{array}$}};
\draw (6,0) node (21){\tiny{$\begin{array}{|c|}\hline
                              \\ \\
                             C_k \\
                              \\ \\  \hline
                           \end{array}$}};
\path[edge, line width=0.5pt] (-0.35, -1)--(-0.35, -1.5)--(6.35, -1.5)--(6.35, -1)--(-0.35, -1)--(-0.35, -1.5);
\draw (0,-1.25) node (a0) {0};
\draw (1,-1.25) node (a1) {1};
\draw (2,-1.25) node (b0) {0};
\draw (3,-1.25) node (b1) {1};
\draw (4,-1.25) node (dd) {$\cdots$};
\draw (5,-1.25) node (c0) {0};
\draw (6,-1.25) node (c1) {1};
\end{tikzpicture}
\caption{Recursive construction for a graph-dependent covering array on  $\Omega_{2k}^+$ and $T_2$.\label{fig:recursiveOmega+}}
\end{center}
\end{figure}

For each $j\in [2k]$, the $j$th column of $A$ corresponds to $C_{\lceil j/2 \rceil}$ (the $\lceil j/2 \rceil$th column of the $\hbox{CA}(n; 2, \Omega_k^+, T_2)$).  Let $i$ and $j$ be the indices of two distinct columns  of $A$ such that $j= i+t \pmod{2k}$ for some $t$ such that $1\leq t \leq k$.  We must show that some row of $A$ has a zero in the $i$th column and a one in the $j$th column; if there exists such a row, then for short, we  say that \define{$A$ covers $\{(i,0), (j,1)\}$}.



Suppose  $j>i$.  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 $j<i$. Then $1\leq 2k+j-i \leq k$, and the case-analysis is similar to show that the array $A$ covers each required interaction of the form $\{(i, 0),(j, 1)\}$.

Thus, the array $A$ is a $\hbox{CA}(n+1; 2, \Omega_{2k}^+, T_2)$, and it follows that \[\hbox{CAN}(2, \Omega_{2k}^+, T_2) \leq \hbox{CAN}(2, \Omega_k^+, T_2) + 1. \qedhere\]
\end{proof}

In the following theorem, we use Proposition~\ref{prop:CANomega2kleqCANomegak+1} to give tight bounds on the binary covering array number  for circular tournaments.

\begin{theorem}\label{thm:logkCircularlogkplusone}
  For all $k\geq 2$, \[\lceil\log_2k\rceil \leq \hbox{CAN}(2, \Omega_k, T_2) \leq \hbox{CAN}(2, \Omega_{2^{\lceil\log k\rceil}}^+, T_2)  \leq \lceil\log_2k\rceil + 1.\]
\end{theorem}

\begin{proof}
 It is easy to see that $\hbox{CAN}(2, \Omega_2^+, T_2) = 2$ since $E(\Omega_2^+) = \{(0,1), (1,0)\}$ and these two arcs cannot be covered in one row whereas two rows suffice. Now, by applying Proposition~\ref{prop:CANomega2kleqCANomegak+1} iteratively, for all $L>0$, 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}<k\leq 2^L$, the covering array number $\hbox{CAN}(2, \Omega_k, T_2)$ ranges from $\lceil\log_2k\rceil$ to $\lceil\log_2k\rceil +1$, non-decreasingly as $k$ increases.
For all $L\geq 2$, for each range $2^{L-1}<k\leq 2^L$, determine the threshold value of $k$ for which $\hbox{CAN}(2, \Omega_k, T_2) = \lceil\log_2k\rceil$ and $\hbox{CAN}(2, \Omega_{k+1}, T_2) = \lceil\log_2k\rceil + 1$.
\end{problem}

Aside from a tight numerical upper bound on $\hbox{CAN}(2, O_k, T_2)$, we are interested in finding  an extremal family of $k$-tournaments.  In particular, we wish to have a structural characterization of some infinite family of $k$-tournaments, say $\{X_k\}_{k=2}^{\infty}$,  for which $\hbox{CAN}(2, O_k, T_2)\leq \hbox{CAN}(2, X_k, T_2)$ for every $k$-tournament $O_k$.

\begin{problem}\label{pro:findUBextremalFamilyTournaments}
Find and characterize an infinite family $\{X_k\}_{k=2}^{\infty}$ of $k$-tournaments for which $\hbox{CAN}(2, O_k, T_2)\leq \hbox{CAN}(2, X_k, T_2)$ for every $k$-tournament $O_k$.
\end{problem}


It was conjectured in~\cite[Conjecture~4.5.1]{Mal2016} that circular tournaments constitute an extremal family of tournaments as described in Problem~\ref{pro:findUBextremalFamilyTournaments}; however, our data for $9$-tournaments shows that this is not the case.  Adjacency matrices and other properties for the two exceptional 9-tournaments referred to in Table~\ref{tab:tournamentAnalysis} are given in Appendix~\ref{app:exceptional9s}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The authors would like to thank the anonymous referees for their valuable comments and suggestions.



\normalsize


\begin{thebibliography}{10}

\bibitem{Col2004} C.~J. Colbourn. \newblock Combinatorial aspects of covering arrays.  \newblock {\em Le Matematiche (Catania)}, 59(1-2):125--172, 2004.

\bibitem{GarKorVac1993} L. Gargano, J. K{\"o}rner, and U. Vaccaro. \newblock Sperner capacities.  \newblock {\em Graphs and Combinatorics}, 9(1):31--46, 1993.

\bibitem{GarKorVac1994} L. Gargano, J. K{\"o}rner, and U. Vaccaro. \newblock Capacities: From information theory to extremal set theory.  \newblock {\em J. Combin. Theory Ser. A}, 68(2):296--316, 1994.

\bibitem{HelNes2004} P. Hell and J. Ne{\v{s}}et{\v{r}}il. \newblock {\em Graphs and Homomorphisms},  \newblock {volume 28 of \em Oxford Lecture Series in Mathematics and its Applications}. Oxford University Press, Oxford, 2004.

\bibitem{Kat1973} G.~O.~H. Katona. \newblock Two applications (for search theory and truth functions) of
              {S}perner type theorems.  \newblock {\em Period. Math. Hungar.}, 3:19--26, 1973.

\bibitem{KleSpe1973} D.~J. Kleitman and  J. Spencer. \newblock Families of {$k$}-independent sets.  \newblock {\em Discrete Math.}, 6:255--262, 1973.

\bibitem{Mal2016} E. Maltais. \newblock {\em Graph-dependent Covering Arrays and LYM Inequalities}.  \newblock {Ph.D. thesis}. University of Ottawa, 2016.

\bibitem{McK2017} B. McKay. \newblock Combinatorial Data: Digraphs, \\ \newblock avaliable at: \url{http://users.cecs.anu.edu.au/~bdm/data/digraphs.html}.

\bibitem{MeaSte2005} K. Meagher and B. Stevens. \newblock Covering arrays on graphs.  \newblock {\em J. Combin. Theory Ser. B}, 95(1):134--151, 2005.

\bibitem{Spe1928} E. Sperner. \newblock Ein {S}atz \"uber {U}ntermengen einer endlichen {M}enge.  \newblock {\em Math. Z.}, 27(1):544--548, 1928.

\end{thebibliography}


\newpage

\appendix
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Extremal $k$-tournaments for $2\leq k\leq 9$}\label{app:tournamentData}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



Up to $k = 9$, we determined $\hbox{CAN}(2, O_k, T_2)$ for all pairwise non-isomorphic $k$-tournaments $O_k$ by using a computer search and the lists of all $k$-tournaments given in~\cite{McK2017}.  For each $k$-tournament $O_k$ with $k\leq 9$, we found that  $\hbox{CAN}(2, O_k, T_2) \in \{\lceil \log_2k\rceil, \lceil \log_2k\rceil + 1\}$.  In the following table, for each $k$ such that $2\leq k\leq 9$, we give the lower and upper bounds of Theorem~\ref{thm:boundsForCAN2TournamentT2}, denoted L.B. and U.B., respectively.  We write CAN to abbreviate the covering array number for a covering array on a given tournament column graph with alphabet graph $T_2$.  For $2\leq k\leq 9$, we give the number of $k$-tournaments with $\hbox{CAN} = n$ for each possible value of $n$ in the range $\hbox{L.B.}\leq n \leq \hbox{U.B.}$.
For some parameters, the actual tournaments are given as the upper triangle of the adjacency matrix in row order, on one line without spaces.  We refer to this representation as the \define{adjacency vector}.  For example, the 4-tournament represented by the adjacency vector $000111$ has the following adjacency matrix and graph:

\vspace*{-0.5cm}
\begin{center}
\begin{tikzpicture}[scale=1.2]
\node[white vertex] (blank) at (-3,0.5){\small $\left(
  \begin{array}{cccc}
    0 & \textbf{0} & \textbf{0} & \textbf{0} \\
    1 & 0 & \textbf{1} & \textbf{1} \\
    1 & 0 & 0 & \textbf{1} \\
    1 & 0 & 0 & 0\\
  \end{array}
\right)$};
\node[vertex](1) at (0,1){\tiny{1}};
\node[vertex](2) at (1,1){\tiny{2}};
\node[vertex](3) at (1,0){\tiny{3}};
\node[vertex](4) at (0,0){\tiny{4}};
\path[black arrow] (2)--(1); \path[black arrow] (2)--(3);\path[black arrow] (2)--(4); \path[black arrow] (4)--(1);
\path[black arrow] (3)--(1);\path[black arrow] (3)--(4);
\end{tikzpicture}
\end{center}

\vspace*{-0.75cm}
By permuting the rows and columns of its adjacency matrix, any  given tournament has several distinct adjacency vector representations.   In Table~\ref{tab:tournamentsdata}, each given adjacency vector is represented exactly as  given in the lists in~\cite{McK2017}, with the exception of the 9-tournaments;  the adjacency vectors of the given 9-tournaments have been reconfigured in order to emphasize their structure which we discuss in more detail in Appendix~\ref{app:exceptional9s}.


\vfill


\small
\begin{table}[h!]
  \centering
  \caption{Data for small tournaments.\label{tab:tournamentsdata}}

\bigskip

\bigskip

\vfill
  \begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}}  r c}
\hline
$k=3$: & number of pairwise non-isomorphic 3-tournaments: & 2 \\
       & number with $\hbox{CAN} = \hbox{L.B.} = 2$: & 1\\
       & number with $\hbox{CAN} = \hbox{U.B.} = 3$: & 1\\ \\
& adjacency vectors of 3-tournaments with $\hbox{CAN} = 3$:& 101\\  \hline \\
$k=4$: & number of pairwise non-isomorphic 4-tournaments: & 4\\
       & number with $\hbox{CAN} = \hbox{L.B.} = 2$: & 1\\
       & number with $\hbox{CAN} = \hbox{U.B.} = 3$: & 3\\ \\
& adjacency vectors of  4-tournaments with $\hbox{CAN} = 3$:  &000101\\
& &100010\\
& &100100 \\ \hline
\end{tabular*}

\end{table}

\newpage

\small
\begin{center}


\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}}  r c}
\hline
$k=5$: & number of pairwise non-isomorphic 5-tournaments: & 12\\
       & number with $\hbox{CAN} = \hbox{L.B.} = 3$: & 11\\
       & number with $\hbox{CAN} = \hbox{U.B.} = 4$: & 1\\ \\
       & adjacency vectors of  5-tournaments with $\hbox{CAN} = 4$: &  1100101110\\ \hline
$k=6$: & number of pairwise non-isomorphic 6-tournaments: & 56\\
       & number with $\hbox{CAN} = \hbox{L.B.} = 3$: & 43\\
       & number with $\hbox{CAN} = \hbox{U.B.} = 4$: & 13\\ \\
       & adjacency vectors of  6-tournaments with $\hbox{CAN} = 4$:
& 000001100101110\\
&& 000101000010001\\
&& 010001000101100\\
&& 010001000110101\\
&& 010001000111101\\
&& 100001010010001\\
&& 100001100101110\\
&& 100101001001000\\
&& 101001100010101\\
&& 101001100100110\\
&& 110001001011000\\
&& 110001001110101\\
&& 110001010110000\\
\hline
$k=7$: & number of pairwise non-isomorphic 7-tournaments: & 456\\
       & number with $\hbox{CAN} = \hbox{L.B.} = 3$: & 75\\
       & number with $\hbox{CAN} = 4$: & 381\\
       & number with $\hbox{CAN} = \hbox{U.B.} = 5$: & 0\\ \\
       & \textit{(adjacency vectors omitted)}\\ \hline
$k=8$: & number of pairwise non-isomorphic 8-tournaments: & 6880\\
       & number with $\hbox{CAN} = \hbox{L.B.} = 3$: & 43\\
       & number with $\hbox{CAN} = 4$: & 6837\\
       & number with $\hbox{CAN} = \hbox{U.B.} = 5$: & 0\\ \\
       & \textit{(adjacency vectors omitted)}\\ \hline
$k=9$: & number of pairwise non-isomorphic 9-tournaments: & 191536\\
       & number with $\hbox{CAN} = \hbox{L.B.} = 4$: & 191534\\
       & number with $\hbox{CAN} = \hbox{U.B.} = 5$: & 2\\ \\
\end{tabular*}
\begin{tabular*}{\textwidth}{l @{\extracolsep{\fill}}  r}
adjacency vectors of 9-tournaments with $\hbox{CAN} = 5$:
 & 101110001000111111000100111101110101 \\
 & 101110001000111111000100111101110010 \\ \hline
\end{tabular*}
\end{center}
\normalsize

\newpage

\subsection{Properties of exceptional 9-tournaments}\label{app:exceptional9s}

Since there are only  two exceptional 9-tournaments, we give more details about their properties here in the hope that this information may help to solve Problem~\ref{pro:findUBextremalFamilyTournaments}.

Let $X_{9a}$ and $X_{9b}$ denote the 9-tournaments with the following adjacency vectors and adjacency matrices, respectively.

\begin{center}
\small
\hbox{\textbf{a.} 101110001000111111000100111101110101\qquad\quad\textbf{b.} 101110001000111111000100111101110010}

\vspace*{0.2cm}


\tabcolsep=4pt
\begin{tabular}{|c||ccc|ccc|ccc|}
\hline
\tiny{a.}& \tiny{1} &\tiny{2} &\tiny{3} &\tiny{4} &\tiny{5} &\tiny{6} &\tiny{7} &\tiny{8} &\tiny{9}\\ \hline\hline
\tiny{1} &0 & 1 & 0 & \color{green!60!black}1 &  \color{green!60!black}1 &  \color{green!60!black}1 & \color{blue!90!black}0 & \color{blue!90!black}0 & \color{blue!90!black}0\\
\tiny{2} &0 & 0 & 1 & \color{blue!90!black}0  & \color{blue!90!black}0   &  \color{blue!90!black}0  &  \color{green!60!black}1 &  \color{green!60!black}1 &  \color{green!60!black}1\\
\tiny{3} &1 & 0 & 0 &  \color{green!60!black}1 &  \color{green!60!black}1 &  \color{green!60!black}1 & \color{blue!90!black}0 & \color{blue!90!black}0 & \color{blue!90!black}0\\ \hline
\tiny{4} &\color{green!60!black}0 & \color{blue!90!black}1  & \color{green!60!black}0 & 0 & 1 & 0 & \color{gray!80!black}0 & \color{red!90!black}1 & \color{red!90!black}1\\
\tiny{5} &\color{green!60!black}0 & \color{blue!90!black}1  & \color{green!60!black}0 & 0 & 0 & 1 &  \color{red!90!black}1 &\color{gray!80!black}0 & \color{red!90!black}1\\
\tiny{6} &\color{green!60!black}0 & \color{blue!90!black}1  & \color{green!60!black}0 & 1 & 0 & 0 & \color{red!90!black}1 & \color{red!90!black}1 &\color{gray!80!black}0 \\ \hline
\tiny{7} &\color{blue!90!black}1  & \color{green!60!black}0 & \color{blue!90!black}1 &  \color{gray!80!black}1 & \color{red!90!black}0 & \color{red!90!black}0 & 0 & 1 & 0\\
\tiny{8} &\color{blue!90!black}1  & \color{green!60!black}0 & \color{blue!90!black}1 & \color{red!90!black}0 &\color{gray!80!black}1 & \color{red!90!black}0   & 0 & 0 & 1\\
\tiny{9} &\color{blue!90!black}1  & \color{green!60!black}0 & \color{blue!90!black}1 &  \color{red!90!black}0 & \color{red!90!black}0 &\color{gray!80!black}1  & 1 & 0 & 0\\
\hline
\end{tabular}
\qquad\qquad\qquad\qquad
\tabcolsep=4pt
\begin{tabular}{|c||ccc|ccc|ccc|}
\hline
\tiny{b.}& \tiny{1} &\tiny{2} &\tiny{3} &\tiny{4} &\tiny{5} &\tiny{6} &\tiny{7} &\tiny{8} &\tiny{9}\\ \hline\hline
\tiny{1} &0 & 1 & 0 & \color{green!60!black}1 &  \color{green!60!black}1 &  \color{green!60!black}1 & \color{blue!90!black}0 & \color{blue!90!black}0 & \color{blue!90!black}0\\
\tiny{2} &0 & 0 & 1 & \color{blue!90!black}0  & \color{blue!90!black}0   &  \color{blue!90!black}0  &  \color{green!60!black}1 &  \color{green!60!black}1 &  \color{green!60!black}1\\
\tiny{3} &1 & 0 & 0 &  \color{green!60!black}1 &  \color{green!60!black}1 &  \color{green!60!black}1 & \color{blue!90!black}0 & \color{blue!90!black}0 & \color{blue!90!black}0\\ \hline
\tiny{4} &\color{green!60!black}0 & \color{blue!90!black}1  & \color{green!60!black}0 & 0 & 1 & 0 & \color{gray!80!black}0 & \color{red!90!black}1 & \color{red!90!black}1\\
\tiny{5} &\color{green!60!black}0 & \color{blue!90!black}1  & \color{green!60!black}0 & 0 & 0 & 1 &  \color{red!90!black}1 &\color{gray!80!black}0 & \color{red!90!black}1\\
\tiny{6} &\color{green!60!black}0 & \color{blue!90!black}1  & \color{green!60!black}0 & 1 & 0 & 0 & \color{red!90!black}1 & \color{red!90!black}1 &\color{gray!80!black}0 \\ \hline
\tiny{7} &\color{blue!90!black}1  & \color{green!60!black}0 & \color{blue!90!black}1 &  \color{gray!80!black}1 & \color{red!90!black}0 & \color{red!90!black}0 & 0 & 0 & 1\\
\tiny{8} &\color{blue!90!black}1  & \color{green!60!black}0 & \color{blue!90!black}1 & \color{red!90!black}0 &\color{gray!80!black}1 & \color{red!90!black}0   & 1 & 0 & 0\\
\tiny{9} &\color{blue!90!black}1  & \color{green!60!black}0 & \color{blue!90!black}1 &  \color{red!90!black}0 & \color{red!90!black}0 &\color{gray!80!black}1  & 0 & 1 & 0\\
\hline
\end{tabular}


\vspace*{0.2cm}

\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] (7)--(8); \path[black arrow] (8)--(9); \path[black arrow] (9) edge [bend right](7);
\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_{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} 
