# Universally Optimal Multivariate Crossover Designs

Shubham Niphadkar and Siuli Mukhopadhyay11footnotemark: 1 , Department of
Mathematics, Indian Institute of Technology Bombay, Mumbai 400 076,
IndiaCorresponding author; Email<EMAIL_ADDRESS>
###### Abstract

In this article, universally optimal multivariate crossover designs are
studied. The multiple response crossover design is motivated by a $3\times 3$
crossover setup, where the effect of $3$ doses of an oral drug are studied on
gene expressions related to mucosal inflammation. Subjects are assigned to
three treatment sequences and response measurements on 5 different gene
expressions are taken from each subject in each of the $3$ time periods. To
model multiple or $g$ responses, where $g>1$, in a crossover setup, a
multivariate fixed effect model with both direct and carryover treatment
effects is considered. It is assumed that there are non zero within response
correlations, while between response correlations are taken to be zero. The
information matrix corresponding to the direct effects is obtained and some
results are studied. The information matrix in the multivariate case is shown
to differ from the univariate case, particularly in the completely symmetric
property. For the $g>1$ case, with $t$ treatments and $p$ periods, for
$p=t\geq 3$, the design represented by a Type $I$ orthogonal array of strength
$2$ is proved to be universally optimal over the class of binary designs, for
the direct treatment effects.

Keywords— Binary designs, Completely symmetric, Correlated response,
Orthogonal arrays

##  1 Introduction

Often in clinical studies, we come across crossover trials that measure
multiple responses from each subject in each period. For example, consider the
blood sugar levels recorded at multiple time points in each period (Putt and
Chinchilli,  1999) or multiple gene expression profiles of subjects measured
in each period (Leaker et al.,  2017; Pareek et al.,  2023). Though these
researchers discuss methods for estimating and analyzing the multiple
responses measured in each period taking into account the various types of
correlation structures which can exist between and within responses, they do
not discuss any optimal design results for such multivariate crossover trials.
In this article, our aim is to find universally optimal design for such
multiple response crossover trials. The design represented by an orthogonal
array of Type $I$ and strength $2$ is shown to be universally optimal for the
$p=t\geq 3$ case, where $p$ and $t$ denote the number of periods and
treatments, respectively.

Crossover designs were initially developed to be used in agricultural sciences
(Cochran,  1939). Later, these designs were also used in various other fields,
such as pharmaceutical and clinical trials, and bioequivalence and biological
studies (Singh and Mukhopadhyay,  2016). Optimal crossover designs for
univariate responses in a fixed effect model setting have been studied by
numerous researchers, namely Hedayat and Afsarinejad,  (1975, 1978), Cheng and
Wu,  (1980), Kunert,  (1983, 1984), Stufken,  (1991), Kushner,  (1997, 1998),
Kunert and Martin,  (2000), Hedayat and Yang,  (2003, 2004) and Singh and
Kunert,  (2021). Whereas, crossover designs with random subject effects were
explored by Laska et al.,  (1983), Laska and Meisner,  (1985), Carriere and
Reinsel,  (1993), Carriere and Huang,  (2000) and Hedayat et al.,  (2006), to
name a few. Recently, there has been some interest in finding optimal
crossover designs for generalized linear models, see Singh and Mukhopadhyay,
(2016), Jankar et al.,  (2020), Mukhopadhyay et al.,  (2021) and Singh et al.,
(2021). For a detailed review of crossover designs, we would like to refer to
the paper by Bose and Dey,  (2013) and books by Senn,  (2002), Bose and Dey,
(2009) and Kenward and Jones,  (2014). However, all these works concentrate
only on single responses measured in each period. Till date, there has been no
work on the development of universally optimal crossover designs for the
multiple response case.

In this article, to model data from a multiple response crossover trial, we
propose a multivariate fixed effect model with both direct and carryover
effects of treatments. The underlying assumption made is that no correlation
exists between distinct responses. However, we allow for within response
correlation, accounting for homoscedastic error variances. Information matrix
for the direct effects is investigated and is shown to differ from the
univariate case by its lack of complete symmetricity property thus violating
the sufficient condition by Kiefer,  (1975). To find optimal designs we
instead resort to the more general technique proposed by Yeh,  (1986) for
determining universally optimal multiple response crossover design.

##  2 Motivating Example

For motivating multiple response crossover trials, we use a gene expression
dataset more recently considered by Pareek et al.,  (2023). In this study, a
randomized, double-blind crossover experiment involving $3$ periods and $3$
treatments was considered. This crossover trial was placebo controlled and the
goal was to study the effects of two single doses of oral drug, prednisone
($10$ mg and $25$ mg), with placebo on biomarkers of mucosal inflammation and
transcriptomics after a nasal allergen challenge. The subjects enrolled in the
study were assigned to one of the $3$ treatment sequences; $ABC$, $CAB$ and
$BCA$. Treatment $A$ was the $10$ mg dose of the drug, while $B$ and $C$ were
the placebo and $25$ mg dose of the drug, respectively. For our purpose, we
considered $5$ gene profiles recorded in the nasal allergen challenge as the
multiple outcomes.

Various tests were performed to check for correlation between and within the
$5$ responses. Tables S.1, S.2, S.3 and S.4 in the Supplementary Material S.1
show the test results. Table S.1 explores correlations between different
responses in the same period, while Table S.2 and S.3 do this for different
periods. Tables S.1, S.2 and S.3 show that there is no significant correlation
(at a level of significance $0.05$) between distinct responses measured in the
same and different time periods. In Table S.4, we investigate if there is a
presence of within response correlation, i.e., if the observations measured on
the same genes are correlated. From the results given in Table S.4, we note
that some sample correlation coefficients have significantly low p-values
(lower than $0.05$) thus implying within gene correlations.

We use the above motivating example of the genetic study and the corresponding
correlation results to frame the multivariate crossover statistical model in
the next section.

##  3 Proposed Statistical Model

We consider crossover designs with $t$ treatments, $n$ subjects and $p$
periods, where $t,p\geq 2$. Let $\varOmega_{t,n,p}$ be the class of all such
designs. We consider that for any design $d\in\varOmega_{t,n,p}$ and $g\geq
1$, there are $g$ response variables on which observations are recorded
corresponding to every subject in each period. For $1\leq k\leq g$,
corresponding to the $k^{th}$ response, let $Y_{dijk}$ represent the random
variable corresponding to the observation from the $i^{th}$ period and the
$j^{th}$ subject, where $1\leq i\leq p$ and $1\leq j\leq n$. We consider that
$Y_{dijk}$ satisfies the following model:

$\displaystyle
Y_{dijk}=\mu_{k}+\alpha_{i,k}+\beta_{j,k}+\tau_{d\left(i,j\right),k}+\rho_{d\left(i-1,j\right),k}+\epsilon_{ijk},$
(3.1)

where corresponding to the $k^{th}$ response variable, $\epsilon_{ijk}$ is the
error term with mean $0$ and variance $\sigma^{2}$, $\mu_{k}$ is the
intercept, $\alpha_{i,k}$ is the $i^{th}$ period effect, $\beta_{j,k}$ is the
$j^{th}$ subject effect and for $1\leq s\leq t$, $\tau_{s,k}$ is the direct
effect and $\rho_{s,k}$ is the first order carryover effect due to the
$s^{th}$ treatment. Here $d(i,j)$ represents the treatment allocated to the
$i^{th}$ period and the $j^{th}$ subject. We assume that the model (3.1) is a
fixed effect model. In the above model, all the effects are taken to vary
along with the response variable and no carryover effect is assumed in the
first period.

Expressing the above model equation in matrix notations, we obtain

$\bm{Y}_{dk}=\bm{X}_{dk}\bm{\theta}_{k}+\bm{\epsilon}_{k},$ (3.2)

where
$\bm{Y}_{dk}=\left(Y_{d11k},\cdots,Y_{dp1k},Y_{d12k},\cdots,Y_{dp2k},\cdots,Y_{d1nk},\cdots,Y_{dpnk}\right)^{{}^{\prime}}$,
$\bm{X}_{dk}=\begin{bmatrix}\bm{{1}}_{np}&\bm{P}&\bm{U}&\bm{T}_{d}&\bm{F}_{d}\end{bmatrix}$,
$\bm{\epsilon}_{k}=\left(\epsilon_{11k},\cdots,\epsilon_{p1k},\epsilon_{12k},\cdots,\epsilon_{p2k},\cdots,\epsilon_{1nk},\cdots,\epsilon_{pnk}\right)^{{}^{\prime}}$,
and
$\bm{\theta}_{k}=\left(\mu_{k},\bm{\alpha}_{k}^{{}^{\prime}},\bm{\beta}_{k}^{{}^{\prime}},\bm{\tau}_{k}^{{}^{\prime}},\bm{\rho}_{k}^{{}^{\prime}}\right)^{{}^{\prime}}$
is the parameter vector of length $(1+p+n+2t)$, with components: $\mu_{k}$,
$\bm{\alpha}_{k}=\left(\alpha_{1,k},\cdots,\alpha_{p,k}\right)^{{}^{\prime}}$,
$\bm{\beta}_{k}=\left(\beta_{1,k},\cdots,\beta_{n,k}\right)^{{}^{\prime}}$,
$\bm{\tau}_{k}=\left(\tau_{1,k},\cdots,\tau_{t,k}\right)^{{}^{\prime}}$ and
$\bm{\rho}_{k}=\left(\rho_{1,k},\cdots,\rho_{t,k}\right)^{{}^{\prime}}$. Here,
the period and subject effects are accounted by,
$\bm{P}=\bm{{1}}_{n}\otimes\bm{I}_{p}$,
$\bm{U}=\bm{I}_{n}\otimes\bm{{1}}_{p}$, respectively, while $\bm{T}_{d}$ is
the design matrix corresponding to treatment effects, and $\bm{F}_{d}$ is the
design matrix for carryover effects. Note that
$\bm{F}_{d}=\left(\bm{I}_{n}\otimes\bm{\psi}\right)\bm{T}_{d}$, where
$\bm{\psi}=\begin{bmatrix}\bm{{0}}^{{}^{\prime}}_{p-1\times 1}&0\\\
\bm{I}_{p-1}&\bm{{0}}_{p-1\times 1}\end{bmatrix}$. We partition $\bm{X}_{dk}$
as

$\bm{X}_{dk}=\begin{bmatrix}\bm{{1}}_{np\times
1}&\bm{X}_{1}&\bm{X}_{2}\end{bmatrix},$ (3.3)

where $\bm{X}_{1}=\begin{bmatrix}\bm{P}&\bm{U}\end{bmatrix}$ and
$\bm{X}_{2}=\begin{bmatrix}\bm{T}_{d}&\bm{F}_{d}\end{bmatrix}$. Combining the
model equations for all $g$ responses, we get

$\displaystyle\begin{bmatrix}\bm{Y}^{{}^{\prime}}_{d1}&\cdots&\bm{Y}^{{}^{\prime}}_{dg}\end{bmatrix}^{{}^{\prime}}$
$\displaystyle=\left(\bm{I}_{g}\otimes\bm{X}_{d1}\right)\begin{bmatrix}\bm{\theta}^{{}^{\prime}}_{1}&\cdots&\bm{\theta}^{{}^{\prime}}_{g}\end{bmatrix}^{{}^{\prime}}+\begin{bmatrix}\bm{\epsilon}^{{}^{\prime}}_{1}&\cdots&\bm{\epsilon}^{{}^{\prime}}_{g}\end{bmatrix}^{{}^{\prime}},$
(3.4)

where $\mathbb{E}\left(\bm{\epsilon}_{k}\right)=\bm{{0}}_{np\times 1}$. It is
assumed that (i) the observations from different subjects are uncorrelated,
and (ii) no correlations exists between distinct response variables implying,
$\mathbb{\text{Cov}}\left(\bm{\epsilon}_{k},\bm{\epsilon}_{k^{\prime}}\right)=\bm{{0}}_{np\times
np}$, for $1\leq k\neq k^{\prime}\leq g$. Under these assumptions, the
dispersion matrix of $\bm{\epsilon}_{k}$ is taken to be

$\displaystyle\mathbb{D}\left(\bm{\epsilon}_{k}\right)=\sigma^{2}\bm{\varSigma}=\sigma^{2}\left(\bm{I}_{n}\otimes\bm{V}\right),$
(3.5)

where $\sigma^{2}>0$ is an unknown constant, while $\bm{V}$ is assumed to be a
known positive definite and symmetric $p\times p$ matrix.

##  4 Information Matrix of the Direct Treatment Effects

In this section, we determine the information matrix under the model (3.4) for
the direct effects, for $g\geq 1$. We use some results for the $g=1$ case from
Bose and Dey,  (2009).

For any design $d\in\varOmega_{t,n,p}$, let $\bm{C}_{d}$ represent the
information matrix for the direct effects. Theorem 4.1 is the main result for
the information matrix in the $g\geq 1$ case.

######  Theorem 4.1.

The information matrix for the direct effects can be expressed as

$\displaystyle\bm{C}_{d}$
$\displaystyle=\bm{I}_{g}\otimes\left[\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\right],$
(4.1)

where $\bm{C}_{{d}11}=\bm{T}^{{}^{\prime}}_{d}\bm{A}^{*}\bm{T}_{d}$,
$\bm{C}_{{d}12}=\bm{C}_{{d}21}^{{}^{\prime}}=\bm{T}^{{}^{\prime}}_{d}\bm{A}^{*}\bm{F}_{d}$,
$\bm{C}_{{d}22}=\bm{F}^{{}^{\prime}}_{d}\bm{A}^{*}\bm{F}_{d}$,
$\bm{A}^{*}=\bm{H}_{n}\otimes\bm{V}^{*}$ and
$\bm{V}^{*}=\bm{V}^{-1}-\left(\bm{{1}}_{p}^{{}^{\prime}}\bm{V}^{-1}\bm{{1}}_{p}\right)^{-1}\bm{V}^{-1}\bm{{1}}_{p}\bm{{1}}_{p}^{{}^{\prime}}\bm{V}^{-1}$.
Here $\bm{H}_{n}=\bm{I}_{n}-\frac{1}{n}\bm{{1}}_{n}\bm{{1}}_{n}^{{}^{\prime}}$
and $\bm{C}^{-}_{d22}$ is a generalized inverse of of $\bm{C}_{d22}$.

###### Proof.

For details of the proof, refer to Supplementary Material S.2. ∎

######  Remark 4.1.

The information matrix $\bm{C}_{d}$ is symmetric, non-negative definite
(n.n.d.) matrix having zero row sums and column sums, and is invariant with
respect to the choice of generalized inverses involved.

###### Proof.

The proof is given in Supplementary Material S.2. ∎

##  5 Universal Optimality

For the single response case, universal optimality criterion have been
discussed by various authors including Kiefer,  (1975) and Bose and Dey,
(2009). Here, we extend the definition of universally optimal designs by
Kiefer,  (1975) to the $g>1$ setup as follows:
Let for $g>1$, $\mathcal{B}_{gt}$ be a class of $gt\times gt$ symmetric, non-
negative definite (n.n.d.) matrices having zero row sums. Suppose $\varPhi$ is
the class of functions
$\phi:\mathcal{B}_{gt}\rightarrow\left(-\infty,\infty\right]$, such that

  1. 1.

$\phi$ is matrix convex;

  2. 2.

For any matrix $\bm{A}\in\mathcal{B}_{gt}$, $\phi\left(x\bm{A}\right)$ is non-
increasing in the scalar $x\geq 0$;

  3. 3.

$\phi$ is invariant under each simultaneous permutation of rows and columns of
$\bm{A}\in\mathcal{B}_{gt}$.

Then a design $d^{*}\in\mathcal{D}$, where $\mathcal{D}$ is a subclass of
designs, is a universally optimal design for the parameters of interest over
$\mathcal{D}$, if $d^{*}$ minimizes $\phi\left(\bm{A}_{d}\right)$ over
$d\in\mathcal{D}$, where $\bm{A}_{d}$ is the information matrix for the
parameters of interest.

Note in the multivariate setup, we have $gt$ direct treatment parameters and
the information matrix $\bm{A}_{d}$ is of order $gt\times gt$. In the single
response case, for $\bm{A}_{d}\in\mathcal{B}_{t}$, the sufficient conditions
of Kiefer,  (1975) (a) complete symmetricity of the information matrix
corresponding to $d^{*}$, and (b) $d^{*}$ maximizing the trace of the
information matrix over $\mathcal{D}$, where $\mathcal{D}$ is a subclass of
designs, leads to the universal optimality of $d^{*}$ over $\mathcal{D}$.
However in the $g>1$ setup, due to the lack of complete symmetricity of the
information matrix for the direct effects (see Lemma A.1 in the Appendix A),
we are unable to use a similar sufficient condition. For our multivariate
setup, instead we resort to the use of a sufficient condition on the lines of
Yeh,  (1986) as stated in the next Lemma.

######  Lemma 5.1.

Let a design $d^{*}\in\mathcal{D}$ be such that for $d\in\mathcal{D}$, the
corresponding information matrix $\bm{A}_{d}\in\mathcal{B}_{gt}$; for any
$d\in\mathcal{D}$ and $\bm{A}_{d}\neq\bm{{0}}_{gt\times gt}$, there exists
scalars $b_{d1},\cdots,b_{d(gt)!}\geq 0$ satisfying
$\bm{A}_{d^{*}}=\sum_{\kappa=1}^{(gt)!}b_{d\kappa}\bm{P}_{\kappa}\bm{A}_{d}\bm{P}^{{}^{\prime}}_{\kappa}$,
where $g>1$ and $\bm{P}_{1}$, $\cdots$, $\bm{P}_{(gt)!}$ are all possible
distinct $gt\times gt$ permutation matrices. Then the design $d^{*}$ is
universally optimal for the parameters of interest over $\mathcal{D}$, if
$d^{*}$ maximizes $\text{tr}\left(\bm{A}_{d}\right)$ over $d\in\mathcal{D}$.

###### Proof.

The proof is on similar lines as in Yeh,  (1986). Please see Appendix A for an
outline of the proof. ∎

###  5.1 Universal Optimality of Orthogonal Array Designs

In this subsection, we consider designs with $p=t$. Our interest is to check
if the universal optimality of a design represented by an orthogonal array of
Type $I$ and strength $2$, $OA_{I}\big{(}n=\lambda t\left(t-1\right),p=t,$
$t,2\big{)}$, where $t\geq 3$ and $\lambda$ is a positive integer, holds for
the $g>1$ case. Note that in the univariate case with correlated error terms,
a design given as $OA_{I}\left(n=\lambda t\left(t-1\right),p,t,2\right)$,
where $3\leq p\leq t$ and $\lambda$ is a positive integer, is shown to be
universally optimal for the direct effects over the class of binary designs by
Kunert and Martin,  (2000).

######  Theorem 5.1.

Let $d^{*}\in\mathcal{D}$ be a design given by $OA_{I}\left(n=\lambda
t\left(t-1\right),p=t,t,2\right)$, where $\mathcal{D}$ is a class of binary
designs with $p=t$, $\lambda$ is a positive integer and $t\geq 3$. Then
$d^{*}$ is a universally optimal design for the direct effects over
$\mathcal{D}$ in the $g>1$ case.

###### Proof.

Here $d^{*}\in\mathcal{D}$ is a $OA_{I}\left(n=\lambda
t\left(t-1\right),p=t,t,2\right)$, where $\mathcal{D}$ is a class of binary
designs with $p=t$, $\lambda$ is a positive integer and $t\geq 3$. From Remark
4.1, it can be clearly seen that for $d\in\mathcal{D}$,
$\bm{C}_{d}\in\mathcal{B}_{gt}$. Also, $d^{*}$ is a universally optimal design
over $\mathcal{D}$ under the $g=1$ case (Kunert and Martin,  2000). Thus we
know that for $g=1$, $d^{*}$ maximizes
$\text{tr}\left(\bm{C}_{{d}}\right)=\text{tr}\left(\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\right)$
over $\mathcal{D}$. From Theorem 4.1, for $g>1$ and $d\in\mathcal{D}$, the
information matrix for the direct effects can be written as

$\displaystyle\bm{C}_{d}$
$\displaystyle=\bm{I}_{g}\otimes\left[\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\right].$
(5.1)

Hence for $g>1$ also, $d^{*}$ maximizes $\text{tr}\left(\bm{C}_{{d}}\right)$
over $\mathcal{D}$.

From Martin and Eccleston,  (1998) and Kunert and Martin,  (2000), we get that
for $g=1$, the information matrix $\bm{C}_{d^{*}}$ is a completely symmetric
matrix. So using Remark 1 from Yeh,  (1986), we get for $g=1$, any
$d\in\mathcal{D}$ and
$\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\neq\bm{{0}}_{t\times
t}$,

$\begin{split}\bm{C}_{d^{*}}&=\bm{C}_{{d^{*}}11}-\bm{C}_{{d^{*}}12}\bm{C}^{-}_{{d^{*}}22}\bm{C}_{{d^{*}}21}=\sum_{\upsilon=1}^{t!}c_{d\upsilon}\bm{Q}_{\upsilon}\left(\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\right)\bm{Q}^{{}^{\prime}}_{\upsilon},\end{split}$
(5.2)

where
$c_{d\upsilon}=\left[\text{tr}\left(\bm{C}_{d^{*}}\right)\right]/\left[t!\times\text{tr}\left(\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\right)\right]\geq
0$ and $\bm{Q}_{\upsilon}$’s are distinct $t\times t$ permutation matrices.

Using (5.1), it is clear that for $g>1$ and $d\in\mathcal{D}$,
$\bm{C}_{d}=\bm{{0}}_{gt\times gt}$ iff
$\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}=\bm{{0}}_{t\times
t}$. For $g>1$, any $d\in\mathcal{D}$, $\bm{C}_{d}\neq\bm{{0}}_{gt\times gt}$
and $\kappa=1,\cdots,(gt)!$, if we suppose

$\displaystyle b_{d\kappa}$ $\displaystyle=\begin{cases}c_{d\upsilon},\text{
if }\bm{P}_{\kappa}=\bm{I}_{g}\otimes\bm{Q}_{\upsilon},\text{ for some
}\upsilon,\\\ 0,\text{ otherwise},\end{cases}$ (5.3)

then using (5.1) and (5.2), we get that for $g>1$, any $d\in\mathcal{D}$ and
$\bm{C}_{d}\neq\bm{{0}}_{gt\times gt}$,

$\displaystyle\bm{C}_{d^{*}}$
$\displaystyle=\sum_{\kappa=1}^{(gt)!}b_{d\kappa}\bm{P}_{\kappa}\bm{C}_{d}\bm{P}^{{}^{\prime}}_{\kappa}.$
(5.4)

Thus from (5.4) and Lemma 5.1, we have proved $d^{*}$ is universally optimal
for the direct effects over $\mathcal{D}$ in the $g>1$ case. ∎

##  6 Illustration

In this section, we evaluate the efficiency of the $3\times 3$ binary
crossover design used in the genetic study by Leaker et al.,  (2017). As our
response variates, we take the $5$ gene profiles. Each of the $3$ treatment
sequences, $ABC$, $CAB$ and $BCA$, are applied on $6$ subjects, where
treatment $A$ denotes the $10$ mg dose of the drug, $B$ denotes the placebo
and $C$ denotes the $25$ mg dose of the drug. Let us denote the above
considered design by $d_{0}$. To study the efficiency of $d_{0}$, we consider
two different structures of the matrix $\bm{V}$ as follows:

  1. 1.

$\bm{V}=\left(1-r_{(1)}^{2}\right)^{-1}\begin{bmatrix}1&r_{(1)}&r_{(1)}^{2}\\\
r_{(1)}&1&r_{(1)}\\\ r_{(1)}^{2}&r_{(1)}&1\end{bmatrix}$, where
$-1<r_{(1)}<1$;

  2. 2.

$\bm{V}=\begin{bmatrix}1&r_{(1)}&0\\\ r_{(1)}&1&r_{(1)}\\\
0&r_{(1)}&1\end{bmatrix}$, where $-1/\sqrt{2}<r_{(1)}<1/\sqrt{2}$.

1 is a $AR(1)$ structure, and 2 is a tridiagonal structure with all diagonal
and off-diagonal elements equal. From our choices of $\bm{V}$, we note it is a
function of $r_{(1)}$ only, where $r_{(1)}$ is such that the matrix $\bm{V}$
is positive definite. Note that if $r_{(1)}=0$, then both $AR(1)$ and
tridiagonal structure reduces to a diagonal structure.

From Theorem 5.1, we know that a design $d^{*}\in\mathcal{D}$ represented by
$OA_{I}\big{(}n=\lambda t\left(t-1\right),$
$p=t,t,2\big{)}$, where $\mathcal{D}$ is a class of binary designs with $p=t$,
$\lambda$ is a positive integer and $t\geq 3$, is universally optimal for the
direct effects over $\mathcal{D}$ for the $g>1$ setup. Suppose to get a
measure of the efficiency of any binary design $d\in\mathcal{D}$ with $t$ and
$n$ same as that of $d^{*}$ we use the ratio of the traces as follows:

$\displaystyle e$
$\displaystyle=\frac{\text{tr}\left(\bm{C}_{d}\right)}{\text{tr}\left(\bm{C}_{d^{*}}\right)}.$

Values of $e$ close to $1$ shows that design, $d$, is a nearly efficient
design. Figures 1 and 2 plot $e$ under both the structures of $\bm{V}$. From
Figures 1 and 2, we see that the maximum efficiency of design $d_{0}$ is
$0.0278$ as compared to the universal optimal design $d^{*}$ for both
structures of $\bm{V}$. Thus, $d_{0}$ is not an efficient/nearly efficient
design.

Figure 1: Efficiency of $d_{0}$ when $\bm{V}$ has a $AR(1)$ structure Figure
2: Efficiency of $d_{0}$ when $\bm{V}$ has a tridiagonal structure

##  7 Conclusion and Future Direction

In this article, we investigated universal optimality for an orthogonal array
of Type $I$ and strength $2$ when $g$ responses are recorded in each period
from each subject, where $g\geq 1$. Under the multivariate fixed effect model,
the information matrix for the direct effects differed from the $g=1$ case,
particularly in terms of the completely symmetric property. For the $g>1$ case
and non-zero within response correlation, for $p=t\geq 3$, we showed a design
given as an orthogonal array of type $I$ and strength $2$ is universally
optimal for the direct effects over a class of binary designs. By following
similar techniques as employed in this article, we can also show that for
uncorrelated and homoscedastic errors, if a balanced uniform design is
universally optimal for the direct effects (carryover effects) over a subclass
of designs for $g=1$, then the universal optimality also holds over the same
subclass of designs for the $g>1$ case.

Though we did not consider that the between response correlation is measured
in the same/different periods in this article, such correlation may exist in a
multiple response crossover experiment. However, in those cases, the error
covariances will be of complex nature and it may be tedious to determine
theoretical optimal designs. As a future direction, we plan to investigate
optimality results in such correlated crossover scenarios. In the future, we
also plan to study the effect of heteroscedastic error terms on the results
for universal optimality in the $g>1$ case.

## Statements and Declarations

### Funding

The authors declare that no financial support has been received from any
funding agency, for this work.

### Competing Interests

The authors declare that there are no conflicts of interest regarding the
publication of this article.

### Ethical Conduct

This research does not involve human or animal participants.

### Authors’ Contributions

All authors contributed to the study conception and design. Material
preparation, analysis and investigation were performed by Shubham Niphadkar.
The first draft of the manuscript was written by Shubham Niphadkar and all
authors commented on previous versions of the manuscript. All authors read and
approved the final manuscript.

##  Appendix A Some Useful Proofs and Results

###### Proof of Lemma 5.1.

Here $d\in\mathcal{D}$, where $\mathcal{D}$ is a subclass of designs such that
$\bm{A}_{d}\in\mathcal{B}_{gt}$. For $g>1$, if $\bm{A}_{d}=\bm{{0}}_{gt\times
gt}$, then from condition 2, it is clear that
$\phi\left(\bm{A}_{d^{*}}\right)\leq\phi\left(\bm{A}_{d}\right)$. Now we
consider the case when for $g>1$, $\bm{A}_{d}\neq\bm{{0}}_{gt\times gt}$. Note
that for $d\in\mathcal{D}$, we have $\bm{A}_{d}\in\mathcal{B}_{gt}$. So
$\bm{A}_{d}=\bm{L}\bm{L}^{{}^{\prime}}$, where $\bm{L}=\bm{A}_{d}^{1/2}$.
Hence we get that $\text{tr}\left(\bm{A}_{d}\right)>0$. Here we have
$\bm{A}_{d^{*}}=\sum_{\kappa=1}^{(gt)!}b_{d\kappa}\bm{P}_{\kappa}\bm{A}_{d}\bm{P}^{{}^{\prime}}_{\kappa}$.
So, we get

$\displaystyle\text{tr}\left(\bm{A}_{d^{*}}\right)=b_{d}\text{tr}\left(\bm{A}_{d}\right),$
(A.1)

where $b_{d}=b_{d1}+\cdots b_{d(gt)!}$. Also, here we know that $d^{*}$
maximizes $\text{tr}\left(\bm{A}_{d}\right)$ over $\mathcal{D}$. Thus we get
that
$\text{tr}\left(\bm{A}_{d^{*}}\right)\geq\text{tr}\left(\bm{A}_{d}\right)$.
Since $\text{tr}\left(\bm{A}_{d}\right)>0$, from (A.1), we get that $b_{d}\geq
1$. Since $\bm{A}_{d}\in\mathcal{B}_{gt}$, from condition 3 we get that
$\phi\left(\bm{A}_{d}\right)=\phi\left(\bm{P}_{\kappa}\bm{A}_{d}\bm{P}^{{}^{\prime}}_{\kappa}\right)$,
for $\kappa=1,\cdots,(gt)!$. Thus using conditions 1 and 2 along with
$\bm{A}_{d^{*}}=\sum_{\kappa=1}^{(gt)!}b_{d\kappa}\bm{P}_{\kappa}\bm{A}_{d}\bm{P}^{{}^{\prime}}_{\kappa}$,
we get

$\displaystyle\phi\left(\bm{A}_{d^{*}}\right)=\phi\left(b_{d}\sum_{\kappa=1}^{(gt)!}\left(b_{d\kappa}/b_{d}\right)\bm{P}_{\kappa}\bm{A}_{d}\bm{P}^{{}^{\prime}}_{\kappa}\right)\leq\phi\left(\bm{A}_{d}\right).$

Hence using the definition of universal optimality, we get that $d^{*}$ is a
universally optimal design. ∎

######  Lemma A.1.

Let $d^{*}\in\varOmega_{t,n=\lambda t\left(t-1\right),p=t}$ be a design given
by $OA_{I}\left(n=\lambda t\left(t-1\right),p=t,t,2\right)$, where $\lambda$
is a positive integer and $t\geq 3$. Then for $g>1$, the information matrix
$\bm{C}_{d^{*}}$ is not completely symmetric.

###### Proof.

Here $d^{*}\in\varOmega_{t,n=\lambda t\left(t-1\right),p=t}$ is a design given
by $OA_{I}\left(n=\lambda t\left(t-1\right),p=t,t,2\right)$, where $\lambda$
is a positive integer and $t\geq 3$. From Theorem 4.1, for $g>1$, the
information matrix $\bm{C}_{d^{*}}$ is given as

$\displaystyle\begin{split}\bm{C}_{d^{*}}&=\bm{I}_{g}\otimes\left[\bm{C}_{{d^{*}}11}-\bm{C}_{{d^{*}}12}\bm{C}^{-}_{{d^{*}}22}\bm{C}_{{d^{*}}21}\right],\end{split}$
(A.2)

where $\bm{C}^{-}_{d^{*}22}$ is a generalized inverse of of
$\bm{C}_{d^{*}22}$. From Martin and Eccleston,  (1998) and Bose and Dey,
(2009), we get that for $g=1$,

$\displaystyle\begin{split}\bm{C}_{d^{*}}&=\bm{C}_{{d^{*}}11}-\bm{C}_{{d^{*}}12}\bm{C}^{-}_{{d^{*}}22}\bm{C}_{{d^{*}}21}=\left(\text{det}\left(\bm{E}\right)/e_{22}\right)\bm{H}_{t},\end{split}$
(A.3)

where $\bm{E}=\frac{n}{t-1}\begin{bmatrix}e_{11}&e_{12}\\\
e_{12}&e_{22}\end{bmatrix}$, $\text{det}\left(\bm{E}\right)\neq 0$,
$e_{11}=\text{tr}\left(\bm{T}^{{}^{\prime}}_{d^{*}1}\bm{V}^{*}\bm{T}_{d^{*}1}\right)$,
$e_{12}=\text{tr}\left(\bm{T}^{{}^{\prime}}_{d^{*}1}\bm{V}^{*}\bm{\psi}\bm{T}_{d^{*}1}\right)$
and
$e_{22}=\text{tr}\left(\bm{T}^{{}^{\prime}}_{d^{*}1}\bm{\psi}^{{}^{\prime}}\bm{V}^{*}\bm{\psi}\bm{T}_{d^{*}1}\right)-\frac{\left(\bm{V}^{*}\right)_{1,1}}{t}$.
Here
$\bm{H}_{t}=\bm{I}_{t}-\frac{1}{t}\bm{{1}}_{t}\bm{{1}}_{t}^{{}^{\prime}}$,
$\bm{\psi}=\begin{bmatrix}\bm{{0}}^{{}^{\prime}}_{p-1\times 1}&0\\\
\bm{I}_{p-1}&\bm{{0}}_{p-1\times 1}\end{bmatrix}$,
$\bm{V}^{*}=\bm{V}^{-1}-\left(\bm{{1}}_{p}^{{}^{\prime}}\bm{V}^{-1}\bm{{1}}_{p}\right)^{-1}\bm{V}^{-1}\bm{{1}}_{p}\bm{{1}}_{p}^{{}^{\prime}}\bm{V}^{-1}$,
and $\left(\bm{V}^{*}\right)_{1,1}$ is the element corresponding to first row
and first column of the matrix $\bm{V}^{*}$.

So using (A.2) and (A.3), it is clear that for $g>1$, the matrix
$\bm{C}_{d^{*}}$ is completely symmetric if and only if all off-diagonal
elements of $\left(\text{det}\left(\bm{E}\right)/e_{22}\right)\bm{H}_{t}$ are
$0$. We know that all off-diagonal elements of the matrix
$\bm{H}_{t}=\bm{I}_{t}-\frac{1}{t}\bm{{1}}_{t}\bm{{1}}_{t}^{{}^{\prime}}$ are
nonzero. From (A.3), for $t\geq 3$, we get that
$\text{det}\left(\bm{E}\right)\neq 0$. Hence for $g>1$ and $t\geq 3$, all off-
diagonal elements of $\bm{C}_{d^{*}}$ are nonzero. Thus for $g>1$ and $t\geq
3$, the information matrix $\bm{C}_{d^{*}}$ is not completely symmetric. ∎

## References

  * Bose and Dey, (2009) Bose, M. and Dey, A. (2009).  Optimal crossover designs.  World Scientific.
  * Bose and Dey, (2013) Bose, M. and Dey, A. (2013).  Developments in crossover designs.
  * Carriere and Huang, (2000) Carriere, K. C. and Huang, R. (2000).  Crossover designs for two-treatment clinical trials.  Journal of Statistical Planning and Inference, 87(1):125–134.
  * Carriere and Reinsel, (1993) Carriere, K. C. and Reinsel, G. C. (1993).  Optimal two-period repeated measurement designs with two or more treatments.  Biometrika, 80(4):924–929.
  * Cheng and Wu, (1980) Cheng, C.-S. and Wu, C.-F. (1980).  Balanced repeated measurements designs.  The Annals of Statistics, 8(6):1272–1283.
  * Cochran, (1939) Cochran, W. G. (1939).  Long-term agricultural experiments.  Supplement to the Journal of the Royal Statistical Society, 6(2):104–148.
  * Hedayat and Afsarinejad, (1975) Hedayat, A. and Afsarinejad, K. (1975).  Repeated measurements designs, I.  A Survey of Statistical Design and Linear Models, pages 229–242.
  * Hedayat and Afsarinejad, (1978) Hedayat, A. and Afsarinejad, K. (1978).  Repeated measurements designs, II.  The Annals of Statistics, 6(3):619–628.
  * Hedayat et al., (2006) Hedayat, A. S., Stufken, J., and Yang, M. (2006).  Optimal and efficient crossover designs when subject effects are random.  Journal of the American Statistical Association, 101(475):1031–1038.
  * Hedayat and Yang, (2003) Hedayat, A. S. and Yang, M. (2003).  Universal optimality of balanced uniform crossover designs.  The Annals of Statistics, 31(3):978–983.
  * Hedayat and Yang, (2004) Hedayat, A. S. and Yang, M. (2004).  Universal optimality for selected crossover designs.  Journal of the American Statistical Association, 99(466):461–466.
  * Jankar et al., (2020) Jankar, J., Mandal, A., and Yang, J. (2020).  Optimal crossover designs for generalized linear models.  Journal of Statistical Theory and Practice, 14(2):1–27.
  * Kenward and Jones, (2014) Kenward, M. G. and Jones, B. (2014).  Crossover trials.  Methods and applications of statistics in clinical trials: Concepts, principles, trials, and design, pages 310–319.
  * Kiefer, (1975) Kiefer, J. (1975).  Construction and optimality of generalized youden designs ii.  A Survey of Statistical Designs and Linear Models, pages 333–353.
  * Kunert, (1983) Kunert, J. (1983).  Optimal design and refinement of the linear model with applications to repeated measurements designs.  The Annals of Statistics, 11(1):247–257.
  * Kunert, (1984) Kunert, J. (1984).  Optimality of balanced uniform repeated measurements designs.  The Annals of Statistics, 12(3):1006–1017.
  * Kunert and Martin, (2000) Kunert, J. and Martin, R. J. (2000).  Optimality of type I orthogonal arrays for cross-over models with correlated errors.  Journal of Statistical Planning and Inference, 87(1):119–124.
  * Kushner, (1997) Kushner, H. B. (1997).  Optimality and efficiency of two-treatment repeated measurements designs.  Biometrika, 84(2):455–468.
  * Kushner, (1998) Kushner, H. B. (1998).  Optimal and efficient repeated-measurements designs for uncorrelated observations.  Journal of the American Statistical Association, 93(443):1176–1187.
  * Laska et al., (1983) Laska, E., Meisner, M., and Kushner, H. B. (1983).  Optimal crossover designs in the presence of carryover effects.  Biometrics, 39(4):1087–1091.
  * Laska and Meisner, (1985) Laska, E. M. and Meisner, M. (1985).  A variational approach to optimal two-treatment crossover designs: application to carryover-effect models.  Journal of the American Statistical Association, 80(391):704–710.
  * Leaker et al., (2017) Leaker, B. R., Malkov, V. A., Mogg, R., Ruddy, M. K., Nicholson, G. C., Tan, A. J., Tribouley, C., Chen, G., De Lepeleire, I., Calder, N. A., and others (2017).  The nasal mucosal late allergic reaction to grass pollen involves type 2 inflammation (IL-5 and IL-13), the inflammasome (IL-1$\beta$), and complement.  Mucosal immunology, 10(2):408–420.
  * Martin and Eccleston, (1998) Martin, R. J. and Eccleston, J. A. (1998).  Variance-balanced change-over designs for dependent observations.  Biometrika, 85(4):883–892.
  * Mukhopadhyay et al., (2021) Mukhopadhyay, S., Singh, S. P., and Singh, A. (2021).  Locally optimal binary crossover designs.  Stat Appl, 19(1):223–246.
  * Pareek et al., (2023) Pareek, S., Das, K., and Mukhopadhyay, S. (2023).  Likelihood-based missing data analysis in crossover trials.  Brazilian Journal of Probability and Statistics, 37(2):329–350.
  * Putt and Chinchilli, (1999) Putt, M. and Chinchilli, V. M. (1999).  A mixed effects model for the analysis of repeated measures cross-over studies.  Statistics in Medicine, 18(22):3037–3058.
  * Senn, (2002) Senn, S. S. (2002).  Cross-over trials in clinical research, volume 5.  John Wiley & Sons.
  * Singh and Kunert, (2021) Singh, R. and Kunert, J. (2021).  Efficient crossover designs for non-regular settings.  Metrika, 84(4):497–510.
  * Singh and Mukhopadhyay, (2016) Singh, S. P. and Mukhopadhyay, S. (2016).  Bayesian crossover designs for generalized linear models.  Computational Statistics & Data Analysis, 104:35–50.
  * Singh et al., (2021) Singh, S. P., Mukhopadhyay, S., and Raj, H. (2021).  Min–max crossover designs for two treatments binary and poisson crossover trials.  Statistics and Computing, 31(5):1–11.
  * Stufken, (1991) Stufken, J. (1991).  Some families of optimal and efficient repeated measurements designs.  Journal of Statistical Planning and Inference, 27(1):75–83.
  * Yeh, (1986) Yeh, C.-M. (1986).  Conditions for universal optimality of block designs.  Biometrika, 73(3):701–706.

## Supplementary Material

### S.1 Tables

Table S.1: Results for testing significance of within-period correlation coefficient between genes | Period 1 | Period 2 | Period 3
---|---|---|---
Pair of Variables | $r$ | p-value | $r$ | p-value | $r$ | p-value
$\left(Gene_{1},Gene_{2}\right)$ | $0.43$ | $>0.999$ | $0.65$ | $0.865$ | $0.04$ | $>0.999$
$\left(Gene_{1},Gene_{3}\right)$ | $0.37$ | $>0.999$ | $-0.44$ | $>0.999$ | $-0.22$ | $>0.999$
$\left(Gene_{1},Gene_{4}\right)$ | $0.25$ | $>0.999$ | $0.69$ | $0.551$ | $0.49$ | $>0.999$
$\left(Gene_{1},Gene_{5}\right)$ | $0.48$ | $>0.999$ | $0.11$ | $>0.999$ | $0.36$ | $>0.999$
$\left(Gene_{2},Gene_{3}\right)$ | $-0.13$ | $>0.999$ | $-0.51$ | $>0.999$ | $0.13$ | $>0.999$
$\left(Gene_{2},Gene_{4}\right)$ | $0.39$ | $>0.999$ | $0.28$ | $>0.999$ | $-0.43$ | $>0.999$
$\left(Gene_{2},Gene_{5}\right)$ | $0.65$ | $0.980$ | $0.41$ | $>0.999$ | $0.19$ | $>0.999$
$\left(Gene_{3},Gene_{4}\right)$ | $-0.37$ | $>0.999$ | $-0.55$ | $>0.999$ | $0.05$ | $>0.999$
$\left(Gene_{3},Gene_{5}\right)$ | $-0.09$ | $>0.999$ | $0.33$ | $>0.999$ | $0.28$ | $>0.999$
$\left(Gene_{4},Gene_{5}\right)$ | $0.44$ | $>0.999$ | $-0.23$ | $>0.999$ | $0.18$ | $>0.999$
Table S.2: Results for testing significance of between-period correlation coefficient between genes | (Period 1, Period 2) | (Period 1, Period 3) | (Period 2, Period 1)
---|---|---|---
Pair of Variables | $r$ | p-value | $r$ | p-value | $r$ | p-value
$\left(Gene_{1},Gene_{2}\right)$ | -0.25 | >0.999 | -0.51 | 0.891 | 0.04 | >0.999
$\left(Gene_{1},Gene_{3}\right)$ | 0.34 | >0.999 | -0.36 | >0.999 | -0.40 | >0.999
$\left(Gene_{1},Gene_{4}\right)$ | -0.14 | >0.999 | 0.15 | >0.999 | 0.37 | >0.999
$\left(Gene_{1},Gene_{5}\right)$ | 0.42 | >0.999 | -0.04 | >0.999 | 0.16 | >0.999
$\left(Gene_{2},Gene_{3}\right)$ | -0.12 | >0.999 | -0.17 | >0.999 | 0.16 | >0.999
$\left(Gene_{2},Gene_{4}\right)$ | 0.21 | >0.999 | 0.45 | >0.999 | 0.32 | >0.999
$\left(Gene_{2},Gene_{5}\right)$ | -0.01 | >0.999 | -0.07 | >0.999 | 0.22 | >0.999
$\left(Gene_{3},Gene_{4}\right)$ | -0.66 | 0.184 | -0.37 | >0.999 | -0.70 | 0.109
$\left(Gene_{3},Gene_{5}\right)$ | 0.66 | 0.185 | 0.03 | >0.999 | 0.04 | >0.999
$\left(Gene_{4},Gene_{5}\right)$ | -0.23 | >0.999 | 0.44 | >0.999 | 0.04 | >0.999
Table S.3: Results for testing significance of between-period correlation coefficient between genes | (Period 2, Period 3) | (Period 3, Period 1) | (Period 3, Period 2)
---|---|---|---
Pair of Variables | $r$ | p-value | $r$ | p-value | $r$ | p-value
$\left(Gene_{1},Gene_{2}\right)$ | 0.01 | >0.999 | -0.06 | >0.999 | -0.06 | >0.999
$\left(Gene_{1},Gene_{3}\right)$ | 0.32 | >0.999 | -0.30 | >0.999 | -0.30 | >0.999
$\left(Gene_{1},Gene_{4}\right)$ | 0.36 | >0.999 | 0.57 | 0.498 | 0.57 | 0.498
$\left(Gene_{1},Gene_{5}\right)$ | -0.05 | >0.999 | -0.53 | >0.701 | -0.53 | >0.701
$\left(Gene_{2},Gene_{3}\right)$ | 0.66 | 0.189 | -0.21 | >0.999 | -0.21 | >0.999
$\left(Gene_{2},Gene_{4}\right)$ | 0.08 | >0.999 | -0.05 | >0.999 | -0.05 | >0.999
$\left(Gene_{2},Gene_{5}\right)$ | 0.39 | >0.999 | -0.14 | >0.999 | -0.14 | >0.999
$\left(Gene_{3},Gene_{4}\right)$ | -0.45 | >0.999 | -0.14 | >0.999 | -0.14 | >0.999
$\left(Gene_{3},Gene_{5}\right)$ | -0.50 | 0.905 | 0.11 | >0.999 | 0.11 | >0.999
$\left(Gene_{4},Gene_{5}\right)$ | 0.05 | >0.999 | -0.22 | >0.999 | -0.22 | >0.999
Table S.4: Results for testing significance of between-period correlation coefficient within genes | (Period 1, Period 2) | (Period 1, Period 3) | (Period 2, Period 3)
---|---|---|---
Variable | $r$ | p-value | $r$ | p-value | $r$ | p-value
$Gene_{1}$ | -0.30 | 0.337 | -0.17 | 0.600 | 0.20 | 0.543
$Gene_{2}$ | 0.003 | 0.992 | -0.87 | 0.0002 | 0.03 | 0.916
$Gene_{3}$ | 0.30 | 0.347 | 0.35 | 0.262 | -0.46 | 0.133
$Gene_{4}$ | 0.63 | 0.272 | 0.56 | 0.058 | 0.71 | 0.009
$Gene_{5}$ | 0.09 | 0.793 | 0.07 | 0.833 | 0.05 | 0.884

### S.2 Proofs of Section 4

###### Proof of Theorem 4.1.

Let
$\bm{\xi}_{k}=\begin{bmatrix}\mu_{k}&\bm{\alpha}^{{}^{\prime}}_{k}&\bm{\beta}^{{}^{\prime}}_{k}&\bm{\rho}^{{}^{\prime}}_{k}\end{bmatrix}^{{}^{\prime}}$.
Then by rearranging the parameters, the model (3.4) can be equivalently
expressed as

$\begin{bmatrix}\bm{Y}^{{}^{\prime}}_{d1}&\cdots&\bm{Y}^{{}^{\prime}}_{dg}\end{bmatrix}^{{}^{\prime}}=\left(\bm{I}_{g}\otimes\bm{T}_{d}\right)\begin{bmatrix}\bm{\tau}^{{}^{\prime}}_{1}&\cdots&\bm{\tau}^{{}^{\prime}}_{g}\end{bmatrix}^{{}^{\prime}}+\left(\bm{I}_{g}\otimes\begin{bmatrix}\bm{{1}}_{np}&\bm{X}_{1}&\bm{F}_{d}\end{bmatrix}\right)\begin{bmatrix}\bm{\xi}_{1}^{{}^{\prime}}&\cdots&\bm{\xi}_{g}^{{}^{\prime}}\end{bmatrix}^{{}^{\prime}}\\\
+\begin{bmatrix}\bm{\epsilon}^{{}^{\prime}}_{1}&\cdots&\bm{\epsilon}^{{}^{\prime}}_{g}\end{bmatrix}^{{}^{\prime}}.$
(S.1)

Premultiplying the above equation by $\bm{I}_{g}\otimes\bm{\varSigma}^{-1/2}$,
we get the model as

$\begin{bmatrix}\bm{Y}^{{}^{\prime}}_{d1(new)}&\cdots&\bm{Y}^{{}^{\prime}}_{dg(new)}\end{bmatrix}^{{}^{\prime}}=\left(\bm{I}_{g}\otimes\bm{\varSigma}^{-1/2}\bm{T}_{d}\right)\begin{bmatrix}\bm{\tau}^{{}^{\prime}}_{1}&\cdots&\bm{\tau}^{{}^{\prime}}_{g}\end{bmatrix}^{{}^{\prime}}\\\
+\left(\bm{I}_{g}\otimes\bm{\varSigma}^{-1/2}\begin{bmatrix}\bm{{1}}_{np}&\bm{X}_{1}&\bm{F}_{d}\end{bmatrix}\right)\begin{bmatrix}\bm{\xi}_{1}^{{}^{\prime}}&\cdots&\bm{\xi}_{g}^{{}^{\prime}}\end{bmatrix}^{{}^{\prime}}+\begin{bmatrix}\bm{\epsilon}^{{}^{\prime}}_{1(new)}&\cdots&\bm{\epsilon}^{{}^{\prime}}_{g(new)}\end{bmatrix}^{{}^{\prime}},$
(S.2)

where $\bm{Y}_{dk(new)}=\bm{\varSigma}^{-1/2}\bm{Y}_{dk}$ and
$\bm{\epsilon}_{k(new)}=\bm{\varSigma}^{-1/2}\bm{\epsilon}_{k}$. Note that the
dispersion matrix of the vector of transformed error terms
$\begin{bmatrix}\bm{\epsilon}^{{}^{\prime}}_{1(new)}&\cdots&\bm{\epsilon}^{{}^{\prime}}_{g(new)}\end{bmatrix}^{{}^{\prime}}$
is $\sigma^{2}\bm{I}_{gnp}$. Thus using the expression of the information
matrix from Kunert,  (1983), we get that the information matrix for the direct
effects can be expressed as

$\displaystyle\bm{C}_{d}$
$\displaystyle=\left(\bm{I}_{g}\otimes\bm{T}_{d}^{{}^{\prime}}\bm{\varSigma}^{-1/2}\right)\text{pr}^{\perp}\left(\bm{I}_{g}\otimes\bm{\varSigma}^{-1/2}\begin{bmatrix}\bm{{1}}_{np}&\bm{X}_{1}&\bm{F}_{d}\end{bmatrix}\right)\left(\bm{I}_{g}\otimes\bm{\varSigma}^{-1/2}\bm{T}_{d}\right).$
(S.3)

By calculation, the above equation can be expressed as

$\displaystyle\bm{C}_{d}$
$\displaystyle=\bm{I}_{g}\otimes\left[\bm{T}_{d}^{{}^{\prime}}\bm{\varSigma}^{-1/2}\text{pr}^{\perp}\left(\bm{\varSigma}^{-1/2}\begin{bmatrix}\bm{{1}}_{np}&\bm{X}_{1}&\bm{F}_{d}\end{bmatrix}\right)\bm{\varSigma}^{-1/2}\bm{T}_{d}\right].$
(S.4)

From Bose and Dey,  (2009), we know

$\displaystyle\bm{T}_{d}^{{}^{\prime}}\bm{\varSigma}^{-1/2}\text{pr}^{\perp}\left(\bm{\varSigma}^{-1/2}\begin{bmatrix}\bm{{1}}_{np}&\bm{X}_{1}&\bm{F}_{d}\end{bmatrix}\right)\bm{\varSigma}^{-1/2}\bm{T}_{d}=\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21},$
(S.5)

where $\bm{C}_{{d}11}=\bm{T}^{{}^{\prime}}_{d}\bm{A}^{*}\bm{T}_{d}$,
$\bm{C}_{{d}12}=\bm{C}_{{d}21}^{{}^{\prime}}=\bm{T}^{{}^{\prime}}_{d}\bm{A}^{*}\bm{F}_{d}$,
$\bm{C}_{{d}22}=\bm{F}^{{}^{\prime}}_{d}\bm{A}^{*}\bm{F}_{d}$,
$\bm{A}^{*}=\bm{\varSigma}^{-1/2}\text{pr}^{\perp}\left(\bm{\varSigma}^{-1/2}\bm{X}_{1}\right)\bm{\varSigma}^{-1/2}=\bm{H}_{n}\otimes\bm{V}^{*}$
and
$\bm{V}^{*}=\bm{V}^{-1}-\left(\bm{{1}}_{p}^{{}^{\prime}}\bm{V}^{-1}\bm{{1}}_{p}\right)^{-1}\bm{V}^{-1}\bm{{1}}_{p}\bm{{1}}_{p}^{{}^{\prime}}\bm{V}^{-1}$.
Here $\bm{H}_{n}=\bm{I}_{n}-\frac{1}{n}\bm{{1}}_{n}\bm{{1}}_{n}^{{}^{\prime}}$
and $\bm{C}^{-}_{d22}$ is a generalized inverse of of $\bm{C}_{d22}$. Thus
from (S.4) and (S.5), we can prove (4.1). ∎

###### Proof of Remark 4.1.

From Bose and Dey,  (2009), we get that for $g=1$, under the model (3.4), the
information matrix for the direct effects, which is given as
$\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}$, is symmetric,
n.n.d., have row sums and column sums as zero, and is invariant with respect
to the choice of generalized inverses involved.
Thus using the expression of the information matrix given in Theorem 4.1, we
get that for $g\geq 1$, $\bm{C}_{d}$ is symmetric, n.n.d., satisfies

$\displaystyle\bm{C}_{d}\bm{{1}}_{gt}$
$\displaystyle=\left(\bm{I}_{g}\otimes\left[\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\right]\right)\bm{{1}}_{gt}=\bm{{0}}_{gt\times
1},$ $\displaystyle\bm{{1}}^{{}^{\prime}}_{gt}\bm{C}_{d}$
$\displaystyle=\bm{{1}}^{{}^{\prime}}_{gt}\left(\bm{I}_{g}\otimes\left[\bm{C}_{{d}11}-\bm{C}_{{d}12}\bm{C}^{-}_{{d}22}\bm{C}_{{d}21}\right]\right)=\bm{{0}}_{1\times
gt}$

and is invariant with respect to the choice of generalized inverses involved.
∎


# On sublinear approximations for the Petersen coloring conjecture

Davide Mattiolo<EMAIL_ADDRESS>Giuseppe Mazzuoccolo  Dipartimento
di Informatica, Università degli Studi di Verona, Strada le Grazie 15, 37134
Verona, Italy<EMAIL_ADDRESS>Vahan Mkrtchyan  Gran Sasso
Science Institute, L’Aquila, 67100, Italy<EMAIL_ADDRESS>
###### Abstract

If $f:\mathbb{N}\rightarrow\mathbb{N}$ is a function, then let us say that $f$
is sublinear if

$\lim_{n\rightarrow+\infty}\frac{f(n)}{n}=0.$

If $G=(V,E)$ is a cubic graph and $c:E\rightarrow\\{1,...,k\\}$ is a proper
$k$-edge-coloring of $G$, then an edge $e=uv$ of $G$ is poor (rich) in $c$, if
the edges incident to $u$ and $v$ are colored with three (five) colors. An
edge is abnormal if it is neither rich nor poor. The Petersen coloring
conjecture of Jaeger states that any bridgeless cubic graph admits a proper
5-edge-coloring $c$, such that there is no an abnormal edge of $G$ with
respect to $c$. For a proper 5-edge-coloring $c$ of $G$, let $N_{G}(c)$ be the
set of abnormal edges of $G$ with respect to $c$. In this paper we show that
(a) The Petersen coloring conjecture is equivalent to the statement that there
is a sublinear function $f:\mathbb{N}\rightarrow\mathbb{N}$, such that all
bridgeless cubic graphs admit a proper 5-edge-coloring $c$ with
$|N_{G}(c)|\leq f(|V|)$; (b) for $k=2,3,4$, the statement that there is a
sublinear function $f:\mathbb{N}\rightarrow\mathbb{N}$, such that all
(cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring
$c$ with $|N_{G}(c)|\leq f(|V|)$ is equivalent to the statement that all
(cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring
$c$ with $|N_{G}(c)|\leq 2k+1$.

###### keywords:

Cubic graph , Petersen coloring conjecture , normal edge-coloring , abnormal
edge

††journal: Sample Journallabel2label2footnotetext: Partially supported by
Fondazione Cariverona, program “Ricerca Scientifica di Eccellenza 2018”,
project “Reducing complexity in algebra, logic, combinatorics - REDCOM”.

##  1 Introduction

The Petersen Coloring Conjecture in graph theory asserts that the edges of
every bridgeless cubic graph $G$ can be colored with edges of the Petersen
graph $P$ as colors, such that adjacent edges of $G$ receive as colors
adjacent edges of $P$. The conjecture is considered hard to prove as it
implies some other classical conjectures in the field such as Cycle Double
Cover Conjecture, Berge-Fulkerson Conjecture, The Shortest Cycle Cover
Conjecture (see [2, 3, 5, 13, 15] for more details). In [5], Jaeger himself
introduced an equivalent formulation of the Petersen Coloring Conjecture. He
proved that a bridgeless cubic graph satisfies this conjecture, if and only
if, it admits a normal edge-coloring (see Definitions 1 and 2) with at most
$5$ colors. Let $\chi^{\prime}_{N}(G)$ be the minimum number of colors in a
normal edge-coloring of $G$. As usual, we refer to $\chi^{\prime}_{N}(G)$ as
the normal chromatic index of $G$. In terms of normal edge-colorings, Petersen
Coloring Conjecture amounts to saying that all bridgeless cubic graphs have
normal chromatic index at most five. The best known upper bound for
$\chi^{\prime}_{N}(G)$ in the class of all bridgeless cubic graphs is $7$ and
some authors have asked for improving this bound to six as an intermediate
step towards proving Jaeger’s conjecture. If one considers the class of all
simple cubic graphs (not necessarily bridgeless), then the situation has been
clarified here only recently. There are examples of cubic graphs with normal
chromatic index $7$ and it is shown in [9] that all simple cubic graphs admit
a normal edge-coloring with at most seven colors.

Now, let us introduce the main notions and definitions that will be used in
the paper. Graphs considered in this paper are finite and undirected. They do
not contain loops. However, they may contain parallel edges. If $G$ is a
graph, then let $V(G)$ and $E(G)$ be the set of vertices and edges of $G$,
respectively. For a vertex $v$ of $G$, let $\partial_{G}(v)$ be the set of
edges of $G$ that are incident to the vertex $v$ in $G$.

Assume that $G$ and $H$ are two cubic graphs. A mapping $\phi:E(G)\rightarrow
E(H)$, such that for each $v\in V(G)$ there is $w\in V(H)$ such that
$\phi(\partial_{G}(v))=\partial_{H}(w)$, is called an $H$-coloring of $G$. If
$G$ has an $H$-coloring, then we write $H\prec G$. It can be easily seen that
$\prec$ is a transitive relation defined on the set of cubic graphs. That is,
if $H\prec G$ and $K\prec H$, then $K\prec G$.

Let $P$ be the Petersen graph. The Petersen coloring conjecture of Jaeger
states:

######  Conjecture 1.

(Jaeger, 1988 [6]) If $G$ is a bridgeless cubic graph, then $P\prec G$.

Note that in [11] it is shown that the Petersen graph is the only 2-edge-
connected cubic graph that can color all bridgeless cubic graphs.

For a positive integer $k$ a (proper) $k$-edge-coloring of a graph $G$ is an
assignment of colors $\\{1,...,k\\}$ to edges of $G$, such that adjacent edges
receive different colors. If $c$ is an edge-coloring of $G$, then let
$S_{G,c}(v)$ be the set of colors that edges incident to the vertex $v$
receive. When it is clear which graph we are referring to, we write $S_{c}(v)$
in place of $S_{G,c}(v)$.

######  Definition 1.

Let $uv$ be an edge of a cubic graph $G$ and $c$ is an edge-coloring of $G$,
then the edge $uv$ is called poor or rich with respect to $c$, if
$|S_{c}(u)\cup S_{c}(v)|=3$ or $|S_{c}(u)\cup S_{c}(v)|=5$, respectively. An
edge that is neither poor nor rich is called abnormal.

For a cubic graph $G$ and an edge-coloring $c$ of $G$, let $N_{G}(c)$ be the
set of abnormal edges of $G$ with respect to $c$.

It can be easily seen that edge-colorings having only poor edges are $3$-edge-
colorings of $G$. On the other hand, edge-colorings having only rich edges
have been considered in the last years. They are called strong edge-colorings.
In this paper, we consider the case when all edges must be either poor or
rich.

######  Definition 2.

An edge-coloring $c$ of a cubic graph is normal, if any edge is rich or poor
with respect to $c$.

It is immediate that an edge coloring which assigns a different color to every
edge of a simple cubic graph is normal (as all edges are rich). Hence, one can
define the normal chromatic index of a simple cubic graph $G$, as the smallest
$k$, for which $G$ admits a normal $k$-edge-coloring. Let us denote it by
$\chi^{\prime}_{N}(G)$.

In [5], Jaeger proved that:

######  Proposition 1.

(Jaeger, [5]) If $G$ is a cubic graph, then $P\prec G$, if and only if $G$
admits a normal $5$-edge-coloring.

This means that Conjecture 1 can be stated as follows:

######  Conjecture 2.

For any bridgeless cubic graph $G$, $\chi^{\prime}_{N}(G)\leq 5$.

Observe that Conjecture 2 is true for $3$-edge-colorable cubic graphs. This is
so because in any $3$-edge-coloring $c$ of a cubic graph $G$ any edge $e$ is
poor, hence $c$ is a normal edge-coloring of $G$. This means that
non-$3$-edge-colorable cubic graphs are the main obstacle for Conjecture 2.
Let us note that Conjecture 2 is verified for some non-$3$-edge-colorable
bridgeless cubic graphs in [4].

In [14], the percentage of edges of a bridgeless cubic graph, which can be
made poor or rich in a 5-edge-coloring, is investigated. There it is shown
that in any bridgeless cubic graph $G$, there is a proper 5-edge-coloring such
that at least $\frac{1}{3}\cdot|E(G)|$ of edges are normal. See the papers [1,
7, 10, 12], where new results on this problem are presented. The problem
studied in [14] can be viewed as finding proper 5-edge-colorings of bridgeless
cubic graphs with some upper bounds for the number of abnormal edges. Note
that a similar approach was already considered by Kochol in [8] for many
different problems in graph theory.

The bounds for $\chi^{\prime}_{N}(G)$ presented in the above-mentioned papers
are linear in terms of the size of $G$. Thus, one may wonder whether it could
be possible to show that all bridgeless cubic graphs $G$ admit a proper
5-edge-coloring with at most $f(|V(G)|)$ abnormal edges, where $f$ is a fixed
sublinear function. In this paper, a function
$f:\mathbb{N}\rightarrow\mathbb{N}$ on positive integers is called sublinear,
if

$\lim_{n\rightarrow+\infty}\frac{f(n)}{n}=0.$

In the following section, we prove that obtaining such a result is going to be
a difficult task. Here, we would like to offer a more general conjecture:

######  Conjecture 3.

The following statements are equivalent:

  1. (a)

Petersen coloring conjecture is true;

  2. (b)

There is a sublinear function $f:\mathbb{N}\rightarrow\mathbb{N}$, such that
all bridgeless cubic graphs $G$ admit a proper 5-edge-coloring such that at
most $f(|V(G)|)$ edges of $G$ are abnormal;

  3. (c)

There is a sublinear function $g:\mathbb{N}\rightarrow\mathbb{N}$, such that
all 2-connected cubic graphs $G$ admit a proper 5-edge-coloring such that at
most $g(|V(G)|)$ edges of $G$ are abnormal;

  4. (d)

There is a sublinear function $h:\mathbb{N}\rightarrow\mathbb{N}$, such that
all 3-connected cubic graphs $G$ admit a proper 5-edge-coloring such that at
most $h(|V(G)|)$ edges of $G$ are abnormal;

  5. (e)

There is a sublinear function $k:\mathbb{N}\rightarrow\mathbb{N}$, such that
all cyclically 4-edge-connected cubic graphs $G$ admit a proper 5-edge-
coloring such that at most $k(|V(G)|)$ edges of $G$ are abnormal.

Roughly speaking, our conjecture suggests that beating the linear upper bound
for abnormal edges amounts to proving the original conjecture of Jaeger. Note
that [8] proves this statement for many well-known conjectures in graph
theory. Table 1 summarizes the results that we have obtained so far. On the
left column we give the class of cubic graphs where we assumed the sublinear
bound. In the right column we give the constant upper bound that this
sublinear bound implies in the class under consideration.

The class of cubic graphs | The constant upper bound for abnormal edges
---|---
bridgeless | $=0$
2-edge-connected | $\leq 5$
3-edge-connected | $\leq 7$
cyclically 4-edge-connected | $\leq 9$
Table 1: The classes of cubic graphs and the upper bounds for abnormal edges
that the sublinear bound implies.

If on one hand, upper bounds on the number of abnormal edges can be
investigated, on the other hand, one can also try to prove that graphs having
a proper $5$-edge-coloring with a small prescribed number of abnormal edges
admit a normal $5$-edge-coloring. In this spirit, we present some results and
questions in Section 3. In particular we prove that there is no proper
$5$-edge-coloring of a cubic graph having only one abnormal edge.

##  2 The main results

In this section we obtain our main results. Our first theorem says that
showing a sublinear bound for the number of abnormal edges with respect to the
order of a bridgeless cubic graph $G$ is as hard as proving Petersen coloring
conjecture. In other words, we establish the equivalence of statements (a) and
(b) in Conjecture 3. We observe that in this statement $G$ may not be
connected.

######  Theorem 1.

The following statements are equivalent:

  1. (a)

Conjecture 1 holds true;

  2. (b)

There exists a sublinear function $f$, such that every bridgeless cubic graph
$G$ admits a proper 5-edge-coloring $c$ with $|N_{G}(c)|\leq f(|V(G)|)$.

###### Proof.

(a) implies (b): it follows by Proposition 1 since the identically zero
function is sublinear.

(b) implies (a): it is known that it suffices to prove the Petersen coloring
conjecture for 2-connected cubic graphs. Let $G$ be such a graph. Consider a
cubic graph $H$ obtained from $t$ disjoint copies of $G$. Here $t\geq 1$. We
have $|V(H)|=t\cdot|V(G)|$. Since $f$ is sublinear, we can choose $t$ large
enough in such a way that

$\frac{f(|V(H)|)}{|V(H)|}<\frac{1}{|V(G)|}.$

By (b), we can assume that $H$ admits a proper 5-edge-coloring $c$, such that
$|N_{H}(c)|\leq f(|V(H)|)$. Hence

$|N_{H}(c)|\leq f(|V(H)|)<\frac{|V(H)|}{|V(G)|}=t.$

Thus, there is a copy of $G$ where there are no abnormal edges with respect to
$c$. Thus, in this copy $c$ gives a normal 5-edge-coloring of $G$. The proof
is complete. ∎

The proof of previous theorem could appear unsatisfactory since it uses a
disconnected graph. Mainly for this reason, we wonder if we can obtain similar
conditions under some connectivity assumptions. The answer is positive as we
show in the next three theorems.

######  Theorem 2.

The following statements are equivalent:

  1. (a)

Any 2-connected cubic graph $G$ admits a proper 5-edge-coloring $c$, such that
$|N_{G}(c)|\leq 5$.

  2. (b)

There exists a sublinear function $f$, such that every 2-connected cubic graph
$G$ admits a proper 5-edge-coloring $c$ with $|N_{G}(c)|\leq f(|V(G)|)$.

###### Proof.

(a) implies (b): as before, by Proposition 1 and since the identically five
function is sublinear.

(b) implies (a): Let $G$ be a 2-connected cubic graph and let $e$ be an edge
of $G$. Consider a cubic graph $H$ obtained from $t$ disjoint copies of $G-e$
by joining them cyclically. Here, $t\geq 1$. We have $|V(H)|=t\cdot|V(G)|$.
Since $f$ is sublinear, we can choose $t$ such that

$\frac{f(|V(H)|)}{|V(H)|}<\frac{1}{|V(G)|}.$

By (b), we can assume that $H$ admits a proper 5-edge-coloring $c$, such that
$|N_{H}(c)|\leq f(|V(H)|)$. Hence

$|N_{H}(c)|\leq f(|V(H)|)<\frac{|V(H)|}{|V(G)|}=t.$

Thus, there is a copy of $G-e$ where there are no abnormal edges with respect
to $c$. Since the endpoints of $e$ are adjacent to four edges, they see four
colors. Hence there is a color in $\\{1,...,5\\}$ that is missing in both ends
of $e$. We can color $e$ with this color. Clearly, this will give a proper
5-edge-coloring of $G$. Moreover, only $e$ and the four edges adjacent to it
might be abnormal. Thus (a) holds. The proof is complete. ∎

Now we show that we need to increase the number of abnormal edges under
stronger connectivity assumptions.

######  Theorem 3.

The following statements are equivalent:

  1. (a)

Any 3-connected cubic graph $G$ admits a proper 5-edge-coloring $c$, such that
$|N_{G}(c)|\leq 7$.

  2. (b)

There exists a sublinear function $f$, such that every 3-connected cubic graph
$G$ admits a proper 5-edge-coloring $c$ with $|N_{G}(c)|\leq f(|V(G)|)$.

###### Proof.

(a) implies (b): it follows as before by using Proposition 1 and the
identically seven function is sublinear.

(b) implies (a): let $G$ be any 3-connected cubic graph and let $v$ any of its
vertices. For a positive integer $t\geq 1$ take a 3-connected bipartite cubic
graph $B$ such that $B$ has $2t$ vertices. Consider a cubic graph $H$ obtained
from $B$ by replacing each of its vertices with a copy of $G-v$. Clearly, $H$
is 3-connected and $|V(H)|=2t\cdot(|V(G)|-1)$. Since $f$ is sublinear, we can
choose $t$ such that

$\frac{f(|V(H)|)}{|V(H)|}<\frac{1}{2(|V(G)|-1)}.$

By (b), there is a proper 5-edge-coloring $c$ of $H$, such that
$|N_{H}(c)|\leq f(|V(H)|)$. We have

$|N_{H}(c)|\leq f(|V(H)|)<\frac{|V(H)|}{2(|V(G)|-1)}=t.$

Thus, since the number of copies of $G-v$ is $t$, there is a copy, say $K$, of
$G-v$ which contains no abnormal edges with respect to $c$. We construct a
copy $G^{\prime}$ of $G$ by contracting all vertices of $H$ not in $K$ in a
unique vertex. We denote again, with a slight abuse of notation, by $v$ such a
vertex. Let $vv_{1}$, $vv_{2}$ and $vv_{3}$ be the three edges adjacent to $v$
in $G^{\prime}$. We color the edge-set of $G^{\prime}$ by assign to every edge
different from $vv_{1}$, $vv_{2}$ and $vv_{3}$ the same color that it has in
$c$. We extend the coloring to the remaining three edges of $G^{\prime}$ as
follows. We choose the color of $vv_{1}$ equal to the color of the unique edge
of $H$ incident to $v_{1}$ and not in $K$. Then we can choose the color of
$vv_{2}$ different from the color of $vv_{1}$ and from the color of the other
two edges of $K$ incident to $v_{2}$. Finally, we can choose the color of
$vv_{3}$ different from the colors of $vv_{1}$ and $vv_{2}$ and from the color
of the other two edges of $K$ incident to $v_{3}$. Clearly, this is possible
since five colors are avaiable and at most four of them are forbidden in each
step of the process. The resulting coloring will be a proper 5-edge-coloring.
Moreover, only the edges $vv_{1},vv_{2},vv_{3}$ and the four edges adjacent to
$vv_{2}$ and $vv_{3}$ might be abnormal. Thus, in this coloring there are at
most seven abnormal edges. The proof is complete. ∎

Let $G$ be a bridgeless cubic graph, and let $e_{1}=ab$ and $e_{2}=cd$ be two
independent edges of it. Take $t$ copies of $G-e_{1}-e_{2}$ and let the
vertices corresponding to $a,b,c,d$ in the $i$th copy of $G-e_{1}-e_{2}$ be
$a_{i},b_{i},c_{i},d_{i}$. Now, join them in the following way: for
$i=1,...,(t-1)$ add the edges $d_{i}a_{i+1}$ and $c_{i}b_{i+1}$. When $i=t$,
we add the edges $d_{t}a_{1}$ and $c_{t}b_{1}$ (Figure 1). Observe that the
resulting graph is cubic. We will say that it is obtained from $t$ copies of
$G-e_{1}-e_{2}$ by joining them cyclically.

Figure 1: Joining the copies of $G-e_{1}-e_{2}$ cyclically.

We prefer to omit the proof of the following technical proposition. It is
nothing but a case by case analysis.

######  Proposition 2.

Let $G$ be a cyclically 4-edge-connected cubic graph and let $e_{1}$, $e_{2}$
be two independent edges of $G$. Take $t\geq 2$ copies of $G-e_{1}-e_{2}$ and
join them cyclically to get a cubic graph $H$. Then $H$ is cyclically 4-edge-
connected.

Now, by taking a path of length three, such that its end-edges are $e_{1}$ and
$e_{2}$, we can prove the following

######  Theorem 4.

The following statements are equivalent:

  1. (a)

Any cyclically 4-edge-connected cubic graph $G$ admits a proper 5-edge-
coloring $c$, such that $|N_{G}(c)|\leq 9$.

  2. (b)

There exists a sublinear function $f$, such that every cyclically 4-edge-
connected cubic graph $G$ admits a proper 5-edge-coloring $c$ with
$|N_{G}(c)|\leq f(|V(G)|)$.

###### Proof.

(a) implies (b): as before it follows by Proposition 1 and since the
identically nine function is sublinear.

(b) implies (a): let $G$ be any cyclically 4-edge-connected cubic graph. Take
a path of length three in $G$ and let $e_{1}$, $e_{2}$ be the end-edges of
this path. Now for a positive integer $t\geq 2$, take $t$ copies of
$G-e_{1}-e_{2}$ and join them cyclically. Let $H$ be the resulting cubic
graph. Clearly, $|V(H)|=t\cdot|V(G)|$ and $H$ is cyclically 4-edge-connected
(Proposition 2). Since $f$ is sublinear, we can choose $t$ such that

$\frac{f(|V(H)|)}{|V(H)|}<\frac{1}{|V(G)|}.$

By (b), $H$ admits a proper 5-edge-coloring $c$, such that $|N_{H}(c)|\leq
f(|V(H)|)$. We have:

$|N_{H}(c)|\leq f(|V(H)|)<\frac{|V(H)|}{|V(G)|}=t.$

Thus, there is a copy of $G-e_{1}-e_{2}$, such that it contains no abnormal
edges with respect to $c$. Now, consider a 5-edge-coloring of $G$ obtained
from $c$ by taking the colors of $e_{1}$ and $e_{2}$ as the ones missing in
its end-points. Since the graph is cubic, there are four such edges. Hence we
can choose one from $\\{1,...,5\\}$. The resulting coloring is proper.
Moreover, only the edges $e_{1}$ and $e_{2}$ and the edges adjacent to them
might be abnormal. Since by our choice $e_{1}$ and $e_{2}$ are adjacent to one
edge, we have that $G$ contains at most nine abnormal edges with respect to
this coloring. The proof is complete. ∎

##  3 Related problems

In this paper, we considered the problem stated in [14], which can be re-
phrased as finding upper bounds for abnormal edges in 5-edge-colorings of
bridgeless cubic graphs. Our main goal was to investigate the case of this
problem when the upper bound for abnormal edges can be written as a sublinear
function of the size of the graph. We presented a conjecture which was
implying that obtaining such bounds is going to be as hard as proving the
Petersen coloring conjecture. In order to support our conjecture we obtained
several results that were showing that sublinear bounds imply constant bounds
for abnormal edges. As a problem for future research, one could consider the
problem of decreasing these constants. As an intermediate step towards this
goal, we would like to offer

######  Question 1.

Assume that a bridgeless cubic graph $G$ admits a proper 5-edge-coloring $c$,
such that $|N_{G}(c)|\leq 2$. Can we prove that $G$ admits a normal 5-edge-
coloring?

We put constant $2$ in Question 1 because a cubic graph $G$ with a proper
$5$-edge-coloring $c$ is such that $|N_{G}(c)|\neq 1$. The following result
shows this fact.

Figure 2: The edge-coloring $\tilde{c}$ of $P.$

######  Proposition 3.

There is no cubic graph having a proper $5$-edge-coloring with exactly one
abnormal edge.

###### Proof.

Let $G$ be a cubic graph and $c$ a proper $5$-edge-coloring with the property
that exactly one edge $e=uv\in E(G)$ is abnormal. We can assume without loss
of generality that $c(e)=1$ and that $S_{G,c}(u)=\\{1,2,3\\}$,
$S_{G,c}(v)=\\{1,2,4\\}$. Let $P$ be the Petersen graph with the edge-coloring
$\tilde{c}$ depicted in Figure 2. We denote $\phi_{c}\colon E(G-e)\to E(P)$
the map such that, for all edges $xy\in E(G-e)$,

  * 1.

if $xy$ is poor in $G$, then $\phi_{c}(xy)=x^{\prime}y^{\prime}$ is the unique
edge of $P$ such that $c(xy)=\tilde{c}(x^{\prime}y^{\prime})$ and
$S_{P,\tilde{c}}(x^{\prime})=S_{G,c}(x)=S_{G,c}(y)$;

  * 2.

if $xy$ is rich in $G$, then $\phi_{c}(xy)=x^{\prime}y^{\prime}$ is the unique
edge of $P$ such that $c(xy)=\tilde{c}(x^{\prime}y^{\prime})$,
$S_{P,\tilde{c}}(x^{\prime})=S_{G,c}(x)$ and
$S_{P,\tilde{c}}(y^{\prime})=S_{G,c}(y).$

Let $C\subset P$ be the bold cycle in Figure 2 and consider the subgraph $H$
of $G-e$ induced by $\phi^{-1}_{c}(C)$. First notice that
$\phi^{-1}_{c}(C)\cap(\partial_{G}(u)\cup\partial_{G}(v))$ consists of just
one edge, that is the edge $wu$, with $w\neq v$, such that $c(wu)=2$.
Therefore $H$ has one vertex of degree $1$. On the other hand, since the map
$\phi_{c}$ sends each edge $x_{1}x_{2}$ of $G-e$ to an edge $y_{1}y_{2}$ of
$P$ such that $S_{G,c}(x_{i})=S_{P,\tilde{c}}(y_{i})$, $i\in\\{1,2\\}$, we
have that every vertex of $V(H)\setminus\\{u\\}$ has degree $2$ in $H$.
Therefore $H$ is a graph with all vertices of degree $2$ and only one vertex
of degree $1$, that is impossible. ∎

On the other hand, we show that, for every integer $k\geq 2$, there is a cubic
graph with a proper $5$-edge-coloring having exactly $k$ abnormal edges.
Before going to the proof, let $G_{1},G_{2}$ be two cubic graphs and let
$e_{i}=x_{i}y_{i}\in E(G_{i})$, with $i\in\\{1,2\\}$. We define the _$2$ -cut
connection_ applied to the graphs $G_{1},G_{2}$ with prescribed edges
$e_{1},e_{2}$ respectively, to be the operation that produces the cubic graph
$K$ having vertex-set $V(K)=V(G_{1})\cup V(G_{2})$ and edge-set
$E(K)=(E(G_{1})\cup
E(G_{2})\cup\\{x_{1}x_{2},y_{1}y_{2}\\})\setminus\\{e_{1},e_{2}\\}$.

Figure 3: A proper $5$-edge-coloring of the $3$-cube with two abnormal edges
(bold edges).

######  Proposition 4.

For all integers $k\geq 2$, there is a cubic graph having a proper $5$-edge-
coloring with exactly $k$ abnormal edges.

###### Proof.

Figure 3 shows that the statement is true for $k=2$. Let $k\geq 3$ and $G$ be
a cubic graph with a proper $5$-edge-coloring $c$ with $k-1$ abnormal edges.
Call $e=uv$ one of the abnormal edges of $G$. Up to a permutation of colors,
we can assume that $c(e)=1$ and that $S_{G,c}(u)\cup
S_{G,c}(v)=\\{1,2,3,4\\}$. Construct the cubic graph $H$ applying a $2$-cut
connection to $G$ (with prescribed edge $e$) and a copy of $K_{4}$ (see Figure
4). The edge-coloring of $G$ can be extended to the new added part as shown in
Figure 4. This new edge-coloring has one more abnormal edge than $c$.
Therefore $H$ admits a proper $5$-edge-coloring with $k$ abnormal edges. ∎

Figure 4: Extendig an edge-coloring in such a way that the resulting one has
one more abnormal edge (abnormal edges are depicted in bold).

## References

  * [1] H. Bílková, Variants of Petersen coloring for some graph classes, Master’s thesis, Charles University, (2015)
  * [2] A. U. Celmins, On cubic graphs that do not have an edge-$3$-colouring, Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1984.
  * [3] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168–194.
  * [4] J. Hägglund, E. Steffen, Petersen-colorings and some families of snarks, Ars Mathematica Contemporanea 7 (2014), 161–173.
  * [5] F. Jaeger, On five-edge-colorings of cubic graphs and nowhere-zero flow problems, Ars Combinatoria, 20-B, (1985), 229–244.
  * [6] F. Jaeger, Nowhere-zero flow problems, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 71–95.
  * [7] L. Jin, Y. Kang, Partially normal 5-edge-colorings of cubic graphs, European J. Combin. 95 (2021), 103327.
  * [8] M. Kochol, Equivalences between hamiltonicity and flow conjectures, and the sublinear defect property, Discr. Math. 254, (2002), 221–230.
  * [9] G. Mazzuoccolo, V. V. Mkrtchyan, Normal edge-colorings of cubic graphs, J. Graph Theory 94(1), (2020), 75–91.
  * [10] G. Mazzuoccolo, V. V. Mkrtchyan, Normal $6$-edge-colorings of some bridgeless cubic graphs, Disc. Appl. Math. 277, (2020), 252–262.
  * [11] V. Mkrtchyan, A remark on the Petersen coloring conjecture of Jaeger, Australasian J. Comb. 56(2013), pp. 145–151.
  * [12] F. Pirot, J.-S. Sereni, R. Škrekovski, Variations on the Petersen colouring conjecture, Electron. J. Combin. 27(1) (2020), #P1.8
  * [13] M. Preissmann, Sur les colorations des aretes des graphes cubiques, These de $3$-eme cycle, Grenoble (1981).
  * [14] R. Šámal, New approach to Petersen coloring, Elec. Notes in Discr. Math. 38 (2011), 755–760.
  * [15] C.-Q. Zhang, Integer flows and cycle covers of graphs, Marcel Dekker, Inc., New York Basel Hong Kong, 1997.