# Testing for a difference in means of a single feature after clustering

Yiqun T. Chen
Department of Biomedical Data Science, Stanford University
and
Lucy L. Gao
Department of Statistics, University of British Columbia

###### Abstract

For many applications, it is critical to interpret and validate groups of
observations obtained via clustering. A common validation approach involves
testing differences in feature means between observations in two estimated
clusters. In this setting, classical hypothesis tests lead to an inflated Type
I error rate. To overcome this problem, we propose a new test for the
difference in means in a single feature between a pair of clusters obtained
using hierarchical or $k$-means clustering. The test based on the proposed
$p$-value controls the selective Type I error rate in finite samples and can
be efficiently computed. We further illustrate the validity and power of our
proposal in simulation and demonstrate its use on single-cell RNA-sequencing
data.

Keywords: Hypothesis testing, Unsupervised learning, Post-selection inference,
Type I Error

##  1 Introduction

Clustering algorithms, a collection of computational tools designed to group
unlabelled data, are ubiquitously applied across fields to preprocess,
visualize, and compress large data sets [15]. It is often of interest to
interpret and validate the results from clustering a data set: for instance,
in the context of single-cell RNA sequencing (scRNA-seq), researchers often
cluster cells based on their gene expression profiles, and want to interpret
the resulting clusters as categorical measures of an unobserved aspect of the
cells’ biological state, such as cell type [11, 1]. Similarly, in market
segmentation, an analyst might cluster customers according to their measurable
characteristics such as age, gender, and spending habits, and subsequently
assign each resulting cluster a descriptive label (e.g. “outdoorsy customers”)
to inform market design [18].

Here, we consider how to determine which features are significantly different
between two groups obtained via a clustering algorithm. Concretely, suppose
that we applied a clustering algorithm to divide $n$ observations into $K$
non-overlapping groups based on $q$ features. For a pair of groups and for a
feature $j\in\\{1,2,\ldots,q\\}$, we want to answer the question: “ _How can
we assess whether the population means of the $j$th feature are the same
between the two groups?_”

Answering this question yields valuable insights. First, identifying the
subset of features that appear to have different population means across
cluster pairs facilitates cluster interpretation. For instance, in scRNA-seq,
if the data suggests that the two cell clusters have different population mean
expression levels for known marker genes of specific cell subtypes (e.g.,
helper T cells and killer T cells), this supports interpreting these cell
clusters as the corresponding subtypes. Second, answers to this question could
assist in evaluating the validity and generalizability of the obtained
clusters. Given that clustering algorithms always output distinct clusters —
even when applied to observations from a single population — observing at
least one feature with population means across clusters increases our
confidence in the resulting clusters, as well as the potential for
generalizing our clustering results to new independent data sets.

To ascertain whether the population mean of each feature is the same between
groups, applying a classical test for equality of means between two
populations (e.g., the two-sample $t$-test) for each feature and cluster pair
might seem intuitive. However, such an approach ignores the fact that the null
hypothesis of equal population means of a given feature between two clusters
depends on the data used for testing, since the clusters are estimated on the
same data. This leads to a failure to control the selective Type I error rate
[9]; that is, the probability of falsely rejecting the null hypothesis, given
that we chose to test it. Furthermore, sample splitting does not provide an
adequate solution in this context, as clustering a subset of the observations
does not directly lead to cluster assignments for the remaining observations;
detailed discussion is available in Gao et al., [10], Chen and Witten, [6],
Neufeld et al., [20].

In this paper, we develop a finite-sample selective inference framework [9]
for testing for a difference in means of a single feature in two clusters,
under a multivariate Gaussian assumption. In short, to account for the fact
that the clusters are estimated using the same data used for testing, we
condition on the event that the clustering algorithm outputs a particular
partition of the observations, thereby controlling the selective Type I error
rate. In the special case of $k$-means clustering and hierarchical clustering
— two of the most popular forms of clustering — we provide an analytical
characterization of the conditioning set that enables efficient and exact
computation of our proposed $p$-value.

Our work is closely related to Gao et al., [10] and Chen and Witten, [6] and
amounts to extending their selective inference framework for testing the
difference in _vector means_ to _individual feature means_. While this
manuscript is under preparation, Hivert et al., [13] proposed a related
selective inference framework for the difference between the mean of a single
feature in two clusters. Compared to their work, our proposal (i) does not
assume that the features used for clustering are independent; and (ii)
computes the $p$-value exactly with a computationally efficient algorithm,
rather than approximating the $p$-value via Monte Carlo sampling. Methods
developed in this paper are implemented in the R package CADET (Clustering And
Differential Expression Testing) available at
https://github.com/yiqunchen/CADET. Data and code for reproducing the results
in this paper can be found at https://github.com/yiqunchen/CADET-experiments.

The rest of our paper is organized as follows. In Section 2, we review the
problem of testing for a difference in means after clustering. In Sections 3
and 4, we propose tests that control the selective Type I error rate when
testing for a difference in means after hierarchical or $k$-means clustering,
and provide a computationally-efficient approach to compute the $p$-values
corresponding to our proposal. We evaluate our proposal in a simulation study
in Section 5 and apply our proposal to real datasets in Section 6. Proofs and
additional results are relegated to the Appendix.

Throughout this paper, we will use the following notational conventions.
$I_{n}$, $0_{n}$ and $\mathds{1}\\{\cdot\\}$ denote the $n$-dimensional
identity matrix, $n$-vector of zeros, and the indicator function,
respectively. For a matrix ${A}$, ${A}_{i}$ denotes the $i$th row and $A_{ij}$
denotes the $(i,j)$th entry. For a vector $\nu\in\mathbb{R}^{n}$,
$\|\nu\|_{2}$ denotes its $\ell_{2}$ norm, and ${\Pi}_{\nu}^{\perp}$ is the
projection matrix onto the orthogonal complement of $\nu$, i.e.,
${\Pi}_{\nu}^{\perp}=I_{n}-\nu\nu^{\top}/\|\nu\|_{2}^{2}$.

##  2 Motivation

###  2.1 Model and data

Let $x\in\mathbb{R}^{n\times q}$ be a data matrix with $n$ observations of $q$
features. For $\mu\in\mathbb{R}^{n\times q}$ with unknown rows
$\mu_{i}\in\mathbb{R}^{q}$ and known, positive-definite
$\Sigma\in\mathbb{R}^{q\times q}$, we assume that $x$ is a realization of a
random matrix $X$, where rows of $X$ are independent and drawn from a
multivariate normal distribution:

$X_{i}\sim N_{q}(\mu_{i},\Sigma),\quad i=1,2,\ldots,n.$ (1)

###  2.2 Testing two pre-defined groups

Let $j\in\\{1,2,\ldots,q\\}$. For any $G\subset\\{1,2,\ldots,n\\}$, let

$\bar{\mu}_{Gj}=\sum\limits_{i\in G}\sum\limits_{j=1}^{q}\mu_{ij}/|G|,$ (2)

be the mean of the $j$th feature in the group $G$. Consider using $x$ to test
the null hypothesis that there is no difference in the mean of the $j$th
feature across two _pre-defined_ , non-overlapping groups
$G,G^{\prime}\subset\\{1,2,\ldots,n\\}$, i.e.

$H_{0j}:\bar{\mu}_{Gj}=\bar{\mu}_{G^{\prime}j}\text{ versus
}H_{1j}:\bar{\mu}_{Gj}\neq\bar{\mu}_{G^{\prime}j}.$ (3)

This is equivalent to testing $H_{0j}:[\mu^{T}\nu]_{j}=0$ versus
$H_{1j}:[\mu^{T}\nu]_{j}\neq 0$, where $\nu$ is the $n$-vector with $i$th
element given by $\mathds{1}\\{i\in G\\}/|G|-\mathds{1}\\{i\in
G^{\prime}\\}/|G^{\prime}|$. Since $G$ and $G^{\prime}$ are chosen
independently of the data used for testing, we could test $H_{0j}$ by applying
the two-sample $Z$-test, with $p$-value given by
$\mathbb{P}_{H_{0j}}\left(|[X^{T}\nu]_{j}|\geq|[x^{T}\nu]_{j}|\right)$. Under
(1), this amounts to computing
$1-2\Phi\big{(}\big{|}[\nu^{T}x]_{j}\big{|}/\left(\|\nu\|_{2}^{2}\Sigma_{jj}\right)\big{)}$,
where $\Phi(\cdot)$ is the cumulative distribution function of the standard
normal distribution.

###  2.3 What changes when the groups are estimated clusters?

Let $\mathcal{C}(\cdot)$ be a clustering algorithm that takes in a data matrix
$x$ with $n$ rows and outputs a partition of $\\{1,2,\ldots,n\\}$. Suppose
that we now want to use $x$ to test the null hypothesis that there is no
difference in the mean of the $j$th feature across two groups obtained by
applying $\mathcal{C}(\cdot)$ to $x$, i.e.

$\hat{H}_{0j}:\bar{\mu}_{\hat{G}j}=\bar{\mu}_{\hat{G}^{\prime}j}\text{ versus
}\hat{H}_{1j}:\bar{\mu}_{\hat{G}j}\neq\bar{\mu}_{\hat{G}^{\prime}j},$ (4)

where $\hat{G},\hat{G}^{\prime}\in\mathcal{C}(x)$ are a pair of estimated
clusters. This is equivalent to testing
$\hat{H}_{0j}:[\mu^{T}\hat{\nu}]_{j}=0$ versus
$\hat{H}_{1j}:[\mu^{T}\hat{\nu}]_{j}\neq 0$, where $\hat{\nu}$ is the
$n$-vector with $i$th element given by

$[\hat{\nu}]_{i}=\mathds{1}\\{i\in\hat{G}\\}/|\hat{G}|-\mathds{1}\\{i\in\hat{G}^{\prime}\\}/|\hat{G}^{\prime}|.$
(5)

The challenge is that $\hat{H}_{0j}$ is a function of the data used to test
it, because $\hat{G}$ and $\hat{G}^{\prime}$ are estimated clusters in
$\mathcal{C}(x)$. We could naively treat $\hat{G}$ and $\hat{G}^{\prime}$ as
pre-specified groups, and test $\hat{H}_{0j}$ by applying the two-sample
$Z$-test as described in Section 2.2. This would lead to the following
$p$-value:

$p_{j,\text{naive}}=\mathbb{P}_{\hat{H}_{0j}}\left(|[X^{T}\hat{\nu}]_{j}|\geq|[x^{T}\hat{\nu}]_{j}|\right)$
(6)

That is, we could compare the values of $x_{ij}$ for
$i\in\hat{G}\cup\hat{G}^{\prime}$ to the distribution of $X_{ij}$ for
$i\in\hat{G}\cup\hat{G}^{\prime}$. However, because $\mathcal{C}(X)$ is random
and dependent on $X$, the distribution of $X_{ij}$ stratified by
$\mathcal{C}(X)$ can be far from the distribution of $X_{ij}$ stratified by
$\mathcal{C}(x)$. Consequently, over repeated realizations of $X$, applying
the two-sample $Z$-test to compare the means of two estimated clusters will
lead to anti-conservative inference.

To illustrate this in an example, we simulate data from (1) with $n=150,q=10$,
and

$\displaystyle{\mu}_{i}=(1~{}0_{9})^{T}\text{ for }i\leq
50;~{}{\mu}_{i}=(0_{9}~{}1)^{T}\text{ for }i>50,$ (7)

with $\Sigma_{ij}=1\\{i=j\\}+0.4\cdot 1\\{i\neq j\\}$ so that we have two
equally sized true clusters that differ in the first and last features only.
In each simulated data set, we apply $k$-means clustering to obtain two
clusters, and test for a difference in the means of the estimated clusters for
each of the eight features. Across all of the simulated data sets, there is no
difference in the means of the estimated clusters for features 2–8 under (7);
see Figure 1(a). Nevertheless, there can be a substantial difference in the
empirical means of the estimated clusters for features 2–8; see Figure 1(b).
Thus, over 1,500 simulated data sets, and over features 2–8, the $p$-values
from the two-sample $Z$-test appear far smaller than a Uniform$(0,1)$
distribution; by contrast, the $p$-values from our proposed test (Section 3)
follow a Uniform$(0,1)$ distribution (Figure 1(c)).

Figure 1: We simulated one data set from (1) with ${\mu}$ and $\Sigma$
specified in (7). (a)  Empirical distribution of feature 2 based on the
simulated data set. (b):  We apply $k$-means clustering to obtain two clusters
and plot the empirical distribution of feature 2 stratified by the clusters.
(c):  Quantile-quantile plot of the $p$-values from the two-sample $Z$-test
applied to the estimated clusters (defined in (6)) and our proposal (defined
in (10)), aggregated over 1,500 simulated data sets and over features 2–8
(i.e., the features with no true difference in means across _any_ pairs of
estimated clusters).

##  3 Selective inference for the mean of a single feature

We will overcome the challenges discussed in Section 2.3 by developing a
selective inference framework [9] for testing the equality of the means of a
single feature between two _estimated_ clusters.

###  3.1 The “ideal” p-value

In the setting outlined in Section 2.3, we chose to test $\hat{H}_{0j}$ in (4)
using $x$ because $\hat{G},\hat{G}^{\prime}\in\mathcal{C}(x)$. Thus, Fithian
et al., [9] argues that we should apply a test that controls the _selective
Type I error rate_ at level $\alpha$, which guarantees that the proportion of
times we falsely reject a selected null hypothesis is controlled at level
$\alpha$ over repeated realizations of $X$:

$\mathbb{P}_{\hat{H}_{0j}}\left(\text{Reject }\hat{H}_{0j}\text{ at level
}\alpha\mid\text{Choose to test }\hat{H}_{0j}\right)\leq\alpha.$ (8)

This motivates the following conditional version of the two-sample $Z$-test in
(6) to test $\hat{H}_{0j}$:

$\mathbb{P}_{\hat{H}_{0j}}\left(|[X^{T}\hat{\nu}]_{j}|\geq|[x^{T}\hat{\nu}]_{j}|~{}\Big{|}~{}\mathcal{C}(X)=\mathcal{C}(x)\right),$
(9)

where we conditioned on $\\{\mathcal{C}(X)=\mathcal{C}(x)\\}$ because the
hypothesis of interest was chosen based on the clustering output. By the
probability integral transform, rejecting $\hat{H}_{0j}$ if the $p$-value in
(9) is less than $\alpha$ controls the selective Type I error rate at level
$\alpha$.

In practice, computing (9) is challenging, as (i) the conditional distribution
of $[X^{T}\hat{\nu}]_{j}$ depends on unknown parameters that are left
unspecified by $\hat{H}_{0j}$; and (ii) the conditioning set
$\\{X\in\mathbb{R}^{n\times q}:\mathcal{C}(X)=\mathcal{C}(x)\\}$ depends on
the clustering algorithm $\mathcal{C}$ and could be highly non-trivial to
characterize. In Section 3.2, we will overcome these two challenges by
modifying (9) to condition on extra information; this leads to a
computationally tractable test that controls the selective Type I error rate
when the clusters are obtained via hierarchical or $k$-means clustering.

###  3.2 Truncated Gaussian p-value

To overcome the challenges in computing (9), we condition on additional events
and compute:

$\displaystyle
p_{j,\text{selective}}=\mathbb{P}_{\hat{H}_{0j}}\Big{(}\big{|}[X^{T}\hat{\nu}]_{j}\big{|}\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\mathcal{C}(X)=\mathcal{C}(x),U(X)=U(x)\Big{)},$
(10)

where

$\displaystyle
U(x)=x-\frac{\hat{\nu}\Sigma_{j}^{T}[x^{T}\hat{\nu}]_{j}}{\|\hat{\nu}\|_{2}^{2}\Sigma_{jj}}.$
(11)

Compared to (9), we have conditioned on $\left\\{U(X)=U(x)\right\\}$. This
choice does not sacrifice control of the selective Type I error rate (see
Proposition 3 in Fithian et al., [9]). Furthermore, we can rewrite $X$ in (1)
as:

$\displaystyle X$
$\displaystyle=\left(X-\frac{\hat{\nu}\Sigma_{j}^{T}[X^{T}\hat{\nu}]_{j}}{\|\hat{\nu}\|_{2}^{2}\Sigma_{jj}}\right)+\left(\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\right)\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}[X^{T}\hat{\nu}]_{j},$
(12)

where the first term is in the conditioning set of (10) and the second term
depends on $X$ only through our test statistic $[X^{T}\hat{\nu}]_{j}$. It
turns out that the two terms on the right-hand-side of (12) are independent
under model (1). Thus, when evaluating the conditional probability in (10), we
only need to consider the randomness in $X$ coming from the _scalar-valued_
test statistic $[X^{T}\hat{\nu}]_{j}$, despite the fact that all of $X$ is
involved in the conditioning event $\\{\mathcal{C}(X)=\mathcal{C}(x)\\}$.

This intuition is formalized in the following result, which says that (i)
computing (10) involves a truncated univariate normal distribution; and (ii)
testing $\hat{H}_{0j}$ using (10) controls the selective Type I error rate.

######  Theorem 1.

Suppose that $j\in\\{1,2,\ldots,q\\}$, $x$ is a realization from (1), and
$\mathbb{F}(t;\mu,\sigma,\mathcal{S})$ denotes the cumulative distribution
function (CDF) of a $N(\mu,\sigma^{2})$ random variable truncated to the set
$\mathcal{S}$. Then, for $p_{j,selective}$ defined in (10), we have that

$\displaystyle\begin{split}p_{j,\text{selective}}=1-\mathbb{F}\left(\big{|}[\hat{\nu}^{T}x]_{j}\big{|};0,\Sigma_{jj}\|\hat{\nu}\|_{2}^{2};\mathcal{\hat{S}}_{j}\right)+\mathbb{F}\left(-\big{|}[\hat{\nu}^{T}x]_{j}\big{|};0,\Sigma_{jj}\|\hat{\nu}\|_{2}^{2};\mathcal{\hat{S}}_{j}\right),\end{split}$
(13)

where
$x^{\prime}(\phi,j)=x+(\phi-(\bar{x}_{\hat{G}j}-\bar{x}_{\hat{G^{\prime}}j}))\left(\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\right)\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T},$
and

$\hat{S}_{j}=\left\\{\phi\in\mathbb{R}:C(x)=\mathcal{C}\left(x^{\prime}(\phi,j)\right)\right\\}.$
(14)

Furthermore, the test that rejects
$\hat{H}_{0j}:\bar{\mu}_{\hat{G}j}=\bar{\mu}_{\hat{G}^{\prime}j}$ when
$p_{j,selective}\leq\alpha$ controls the selective type I error rate at level
$\alpha$, in the sense of (8).

It follows from Theorem 1 that computing the selective $p$-value in (10)
amounts to computing the truncation set in (14). The next section is dedicated
to understanding and computing this truncation set.

##  4 The truncation set

###  4.1 Intuition

The set $\hat{S}_{j}$ defined in (14) represents the values of $\phi$ for
which the clustering algorithm $\mathcal{C}$, when applied to
$x^{\prime}(\phi,j)$, yields the clustering output $C(x)$. Here,
${x}^{\prime}(\phi,j)=x+(\phi-(\bar{x}_{\hat{G}j}-\bar{x}_{\hat{G}^{\prime}j}))\left(\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\right)\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}$
can be interpreted as a perturbation to the observed data ${x}$.

Figure 2 illustrates a realization of (1) with $n=30,q=2$, and a covariance
matrix $\Sigma$ encoding moderate correlation (0.4) between any two features.
Panel (a) displays the observed data ${x}$, which corresponds to
${x}^{\prime}(\phi)$ with $\phi={x}_{1}^{T}\hat{\nu}=-3$. Here, $\hat{\nu}$
was chosen to test the difference between $\hat{G}$ (shown in blue) and
$\hat{G^{\prime}}$ (shown in rosy brown), estimated from $k$-means clustering
with $K=3$. Panels (b) and (c) of Figure 2 display ${x}^{\prime}(\phi)$ with
$\phi=0$ and $\phi=6$, respectively. In panel (b), with $\phi=0$, the blue and
rosy brown clusters are “pushed together” in the first feature, resulting in
${x}^{\prime}(\phi)_{1}^{T}\hat{\nu}=0$; that is, there is no difference in
empirical means between feature 1 (x-axis of panel (b)) of the two clusters
under consideration. By contrast, in panel (c), with $\phi=-5$, the blue and
rosy brown clusters are “pulled apart”, which results in an increased distance
between the first feature of the blue and rosy brown clusters.

When put together, panels (a)–(c) reveal that (i) $\phi$ can be interpreted as
the observed “test statistic” $x_{j}^{T}\hat{\nu}$ on $x^{\prime}(\phi)$; (ii)
varying $\phi$ only changes the values of clusters $\hat{G}$,
$\hat{G}^{\prime}$ and leaves the other clusters (e.g., the orange cluster in
Figure 2) alone; and (iii) $\phi$ moves the observed difference in all
features correlated with the feature being tested (e.g., feature 2 in Figure
2); we visualize the magnitude of the changes in Figure 2(d). In this case,
the slope of the blue line is the correlation between the two features.

Figure 2: One simulated data set generated from model (1) with
${\mu}_{i}=1\quantity{1\leq i\leq 10}[0,2.5]^{T}+1\quantity{11\leq i\leq
20}[2.5,0]^{T}+1\quantity{21\leq i\leq 30}[-2.5,-2.5]^{T}$ and
$\Sigma=0.2\cdot[1,0.4;0.4,1]$. (a): The original data ${x}$ corresponds to
$\phi=-3$. Applying $k$-means clustering with $K=3$ yields three clusters
(rosy brown, blue, and orange). Here, $\hat{\nu}$ is chosen to test for a
difference in means between $\hat{G}$ (blue) and $\hat{G}^{\prime}$ (rosy
brown). Empirical means for features 1 and 2 are displayed in dashed lines for
$G$ and $G^{\prime}$. (b): Perturbed data ${x}^{\prime}(\phi,1)$ at $\phi=0$
results in no empirical mean difference for the first feature between the blue
and rosy brown clusters. (c):  With ${x}^{\prime}(\phi,1)$ at $\phi=-5$, the
mean difference for the first feature becomes more pronounced. (d): The
empirical difference in features 1 (red line) and 2 (blue line) as a function
of $\phi$. The slope of the red line is 1 by the definition of
$x^{\prime}(\phi,j)$ and the slope of the blue line is
$\Sigma_{12}/\Sigma_{11}$, where $\Sigma$ is the covariance matrix of the
features.

###  4.2 Computing $\mathcal{\hat{S}}$ for hierarchical clustering

We first review an important result from Gao et al., [10]. For any
$w\in\mathbb{R}^{q}$, define the set

$\mathcal{S}(w)\equiv\left\\{\phi\in\mathbb{R}:\mathcal{C}\left(\left(I_{n}-\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}\right)x+\frac{\phi\hat{\nu}w^{T}}{\|\hat{\nu}\|_{2}^{2}}\right)=\mathcal{C}(x)\right\\}.$
(15)

######  Theorem 2 (Gao et al. (2023)).

Let $K>1$ and consider applying hierarchical clustering to the squared
Euclidean distance matrix and cutting the resulting dendrogram to get $K$
clusters. Then, for any realization $x$ from (1), and any
$w\in\mathbb{R}^{q}$, the set $\mathcal{S}(w)$ can be computed in at most
$\mathcal{O}(n^{2}+n\log(n))$ operations for single and average linkage,
$\mathcal{O}(n^{3}+n\log(n))$ operations for centroid linkage, and
$\mathcal{O}(n^{2}+n\log(n))$ operations for Ward linkage.

Theorem 2 is a direct generalization of results in Section 3 of Gao et al.,
[10]. In short, Section 3.2 of Gao et al., [10] shows that $\mathcal{S}(w)$ is
the intersection of $\mathcal{O}(n^{2})$ sets, where $n$ is the number of
observations. Sections 3.3 and 3.4 of Gao et al., [10] further reveal that for
average, Ward, centroid, and single linkage, each of the $\mathcal{O}(n^{2})$
intersected sets are the solution sets to a quadratic inequality in $\phi$.
Observing that we can take the intersection of the solution sets of $N$
quadratic inequalities in $\mathcal{O}(N\log N)$ operations, and carefully
analyzing the number of operations needed to compute the coefficients of the
quadratic inequalities using the squared Euclidean distance matrix, leads to
the worst-case time complexities listed in Theorem 2.

Since $\mathcal{\hat{S}}$ in (14) can be written as
$\mathcal{\hat{S}}=\mathcal{S}(\hat{\nu},\Sigma_{j}/\Sigma_{jj})$; it follows
from Theorem 2 that computing $\mathcal{\hat{S}}$ for hierarchical clustering
requires the worst-case time complexities listed in Theorem 2.

###  4.3 Extensions to $k$-means clustering

In this section, we extend the proposed $p$-value (10) to the $k$-means
clustering algorithm and outline an efficient computational recipe. Because
$k$-means clustering iteratively updates the cluster assignment [19],
characterizing $\\{X:\mathcal{C}(X)=\mathcal{C}(x)\\}$, where $\mathcal{C}$
denotes the final clusters at convergence, may require enumerating possibly an
exponential number of intermediate cluster assignments. Hence, following Chen
and Witten, [6], we condition on _all of the intermediate clusters_ in the
$k$-means clustering algorithm to arrive at this extension of the $p$-value in
(10):

$\displaystyle p_{j,\text{k-means}}$
$\displaystyle=\mathbb{P}_{{\hat{H}_{0j}}}\Bigg{(}\big{|}[X^{T}\hat{\nu}]_{j}\big{|}\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Bigg{|}~{}U(X)=U(x),\bigcap_{t=0}^{T}\bigcap_{i=1}^{n}\big{\\{}c_{i}^{(t)}(X)=c_{i}^{(t)}(x)\big{\\}}\Bigg{)},$
(16)

where $c_{i}^{(t)}(\cdot)$ is the assigned cluster of observation $i$ at the
$t$th iteration of the $k$-means algorithm, $U(\cdot)$ is defined in (11), and
$T$ is the total number of iterations run during $k$-means clustering.

As in Section 3, conditioning on additional information in (16) still
guarantees selective type I error control, and $p_{j,\text{k-means}}$ can be
computed using a univariate truncated Gaussian distribution; this is
formalized in Proposition A1 in the Appendix. Regarding computation, we can
extend the ideas in Section 3 of Chen and Witten, [6] to efficiently compute
the conditioning set in (16). The key idea is that we can recast the
computation to solving $O(nTK)$ number of quadratic inequalities in $\phi$ and
intersecting the resulting solution sets, taking
$\mathcal{O}((n+q)KT+nKT\log(nKT))$ operations in total (see details in the
Appendix).

##  5 Simulation study

###  5.1 Overview

Throughout this section, we consider testing the null hypothesis
$\hat{H}_{0j}:\bar{\mu}_{\hat{G}j}=\bar{\mu}_{\hat{G}^{\prime}j}\text{ versus
}\hat{H}_{1j}:\bar{\mu}_{\hat{G}j}\neq\bar{\mu}_{\hat{G}^{\prime}j}$, where,
unless otherwise stated, $\hat{G}$ and $\hat{G}^{\prime}$ are a randomly-
chosen pair of clusters from $k$-means or hierarchical clustering, and $j$ is
a randomly-chosen feature. We consider the following $p$-values:
$p_{j,\text{naive}}$ in (6), $p_{j,\text{k-means}}$ in (16),
$p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and $p_{j,\text{single}}$
(defined in (10) where $\mathcal{C}$ is hierarchical clustering with average,
centroid, and single linkage, respectively).

###  5.2 Selective Type I error rate

We generate data from (1) with ${\mu}_{i}=(1,0_{q-1})^{T}\text{ for }i\leq
50;~{}{\mu}_{i}=(0_{q-1}~{}1)^{T}\text{ for }i>50;\text{ and
}\Sigma_{ij}=1\\{i=j\\}+\rho\cdot 1\\{i\neq j\\}$; therefore, $\hat{H}_{0j}$
holds for any pair of estimated cluster and any feature $j=2,\ldots,q-1$. We
simulated 1,500 data sets with $q=10$ and $\rho=0,0.4,0.8$.

For each simulated data set, we apply $k$-means clustering and hierarchical
clustering with average, centroid, and single linkage to estimate three
clusters. We then compute $p_{j,\text{naive}}$ (based on the output from
$k$-means clustering), $p_{j,\text{k-means}}$, $p_{j,\text{average}}$,
$p_{j,\text{centroid}}$, and $p_{j,\text{single}}$ for a randomly-chosen pair
of clusters and a random feature between 2 and $q-1$.

Figure 3 displays the observed $p$-value quantiles versus the Uniform(0,1)
quantiles. We see that for all values of $q$ and $\rho$, (i) the naive
$p$-values in (6) are stochastically smaller than a Uniform(0,1) random
variable, suggesting that the test based on $p_{j,\text{naive}}$ leads to an
inflated Type I error rate (the number of false rejections increases as the
underlying feature correlation increases); (ii) tests based on
$p_{j,\text{k-means}}$, $p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and
$p_{j,\text{single}}$ control the selective Type I error rate in the sense of
(8).

Figure 3: Quantile-quantile plots for $p_{j,\text{naive}}$,
$p_{j,\text{k-means}}$, $p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and
$p_{j,\text{single}}$ under (1) when $\hat{H}_{0j}$ holds.

###  5.3 Conditional power and detection probability

In this section, we demonstrate that tests based on our proposed $p$-values in
Section 3 have substantial power to reject $\hat{H}_{0j}$ when it does not
hold. We generate data from (1) with three equally sized “true clusters”,
${G}_{1}=\\{1,\ldots,50\\},{G}_{2}=\\{51,\ldots,100\\},$ and
${G}_{3}=\\{101,\ldots,150\\}$:

$\displaystyle\begin{split}&{\mu}_{i}=(0_{\lfloor q/2\rfloor},-\delta_{\lceil
q/2\rceil})^{T}\text{ for }i\leq 50;\\\ &{\mu}_{i}=0_{q}\text{ for
}50<i<100;\\\ &{\mu}_{i}=(0_{\lfloor q/2\rfloor},\delta_{\lceil
q/2\rceil})^{T}\text{ for }i\geq 100;\text{ and }\\\
&\Sigma_{ij}=1\\{i=j\\}+\rho\cdot 1\\{i\neq j\\}.\end{split}$ (17)

We simulated 2,000 data sets for each combination of $q=10$, $\rho=0,0.4,0.8$,
and $\delta=3,\ldots,8$.

For each simulated data set, we computed $p_{j,\text{k-means}}$,
$p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and $p_{j,\text{single}}$ for
a randomly-chosen pair of clusters and rejected
$\hat{H}_{0j}:\bar{\mu}_{\hat{G}j}=\bar{\mu}_{\hat{G}^{\prime}j}$ if these
$p$-values were less than $\alpha=0.05$. Note that different clustering
methods may estimate different clusters in a single data set, leading to
different null hypotheses. Thus, our analysis evaluates both the _conditional
power_ of the tests and the _detection probability_ of the employed clustering
methods [10, 6, 16, 14]. We define the conditional power as the probability of
rejecting $\hat{H}_{0j}$ in (4) _given that_ $\hat{G}$ and $\hat{G}^{\prime}$
are true clusters. Given $M$ simulated data sets with true clusters
$\quantity{\mathcal{G}_{1},\ldots,\mathcal{G}_{L}}$, we estimate it as:

$\displaystyle\frac{\sum_{m=1}^{M}1\quantity{\quantity{\hat{{G}}^{(m)},\hat{{G}}^{{}^{\prime}(m)}}\subseteq\quantity{{G}_{1},\ldots,{G}_{L}},p^{(m)}\leq\alpha}}{\sum_{m=1}^{M}1\quantity{\quantity{\hat{{G}}^{(m)}_{1},\hat{{G}}^{{}^{\prime}(m)}_{2}}\subseteq\quantity{{G}_{1},\ldots,{G}_{L}}}},$
(18)

where $p^{(m)}$ and $\hat{{G}}^{(m)},\hat{{G}}^{{}^{\prime}(m)}$ denote the
$p$-value and estimated clusters under consideration for the $m$th simulated
data set. Because the quantity in (18) conditions on the event that
$\hat{{G}}_{1}$ and $\hat{{G}}_{2}$ are true clusters, we also estimate how
often that event occurs, i.e., the _detection probability_ :

$\displaystyle\sum_{m=1}^{M}1\quantity{\quantity{\hat{{G}}^{(m)}_{1},\hat{{G}}^{(m)}_{2}}\subseteq\quantity{{G}_{1},\ldots,{G}_{L}}}/M.$
(19)

Figures 4 displays the conditional power (18) for the tests based on
$p_{j,\text{k-means}}$, $p_{j,\text{average}}$, $p_{j,\text{centroid}}$, or
$p_{j,\text{single}}$. In cases where simulations did not recover the true
clusters, we’ve conventionally set the conditional power to zero. Under model
(1) with $\mu$ defined in (LABEL:eq:power_model), the conditional power
increases as a function of the difference in feature means $\delta$ across all
proposed $p$-values and feature correlation $\rho$. For a given $q$, a larger
value of $\rho$ leads to lower conditional power, especially for the test
based on $p_{j,\text{k-means}}$. Moreover, for a given value of $\delta$ and
$q$, the ordering of power for different tests depends on the correlation
between features: with independent features (left column of Figure 18), the
test based $p_{j,\text{average}}$ and $p_{j,\text{k-means}}$. By contrast,
when features are highly correlated (right column of Figure 18), the tests
based on $p_{j,\text{single}}$ and $p_{j,\text{k-means}}$ yield the highest
and the lowest power, respectively.

The observed trends are congruent with the anticipated behaviour of individual
clustering algorithms: For instance, $k$-means clustering, which uses within-
cluster-sum-of-squares, tends to underperform when features are highly
correlated. By contrast, single linkage hierarchical clustering, making use of
the minimal distance between clusters, thrives in settings with high signal-
to-noise ratio and high feature correlation. Figure 5 displays the relative
performance of cluster recovery, characterized using detection probability
(19).

Figure 4: The conditional power (18) at $\alpha=0.05$ for the tests based on
$p_{j,\text{k-means}}$, $p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and
$p_{j,\text{single}}$, under model (1) with $\mu$ defined in
(LABEL:eq:power_model); $q=10$; and $\rho=0,0.4,0.8$. Figure 5: The detection
probability (19) at $\alpha=0.05$ of the underlying clustering methods for
$p_{j,\text{k-means}}$, $p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and
$p_{j,\text{single}}$, under model (1) with $\mu$ defined in
(LABEL:eq:power_model); $q=10$; and $\rho=0,0.4,0.8$.

##  6 Applications to scRNA-seq data

In this section, we apply the proposed $p$-values to single-cell RNA-
sequencing data collected by the Tabula Sapiens Consortium [7], which measures
messenger RNA expression levels in each of 500,000 cells from 24 different
tissues and organs. These data have enabled new insights into the distinct
cell types within the human organism and created a detailed molecular
definition of these cell types. To reveal biological insights on how gene
expression levels change across cell types, biologists typically perform
clustering on the cells, and then perform a differential expression analysis,
i.e., they test for a difference in gene expression between two clusters [1,
11]. In this approach, ignoring the fact that the clusters were estimated from
the same data used for testing, e.g., applying a two-sample $Z$-test instead
of a selective test in the differential expression analysis, will inflate the
Type I error rate.

Figure 6: (a): Quantile-quantile plot of the $p$-values
$\hat{p}_{j,\text{naive}}$ and $\hat{p}_{j,\text{k-means}}$ aggregated over
features $j=1,\ldots,500$ and all pairs of estimated clusters on the “no
cluster” data set. (b): Number of rejected null hypotheses at different
nominal FDR levels using BH-procedure-adjusted $p$-values from (a).

One unique feature of the Consortium data set is that experts annotated cell
types consistently across the different tissues. We will make use of the
labelled cell types as the “ground truth” and use this information to
demonstrate that our proposed $p$-values in Section 3 yield biologically
reasonable results. As per standard pre-processing techniques [8], we first
excluded cells with low numbers or total counts of expressed genes, as well as
cells in which a large percentage of the expressed genes are mitochondrial. We
then normalized the transcripts for each cell by the total sum of counts in
that cell, followed by a $\log_{2}(x+1)$ transformation.

Figure 7: (a): Quantile-quantile plot of the $p$-values
$\hat{p}_{j,\text{naive}}$ and $\hat{p}_{j,\text{k-means}}$ aggregated over
features $j=1,\ldots,500$ and all pairs of estimated clusters on the “cluster”
data set. (b): Number of rejected null hypotheses at different nominal FDR
levels using BH-adjusted $p$-values from (a).

We applied the pre-processing pipeline separately on two sets of cells
collected from the same donor: the CD4-positive, alpha-beta T cells, and a
combined sample of four cellular types from an identical donor, namely memory
B cells, natural killer cells, macrophages, and monocytes. We considered only
the subset of 500 genes with the largest sample variance in expression levels
post-normalization.

To investigate the selective type I error rate in the absence of true
clusters, we first consider a “no cluster” data set consisting of only
CD4-positive, alpha-beta T cells after pre-processing (thus, $n=833$ and
$q=500$). We applied $k$-means clustering with $K=4$ to obtain four estimated
clusters. For each pair of estimated clusters and each feature
$j=1,\ldots,500$, we computed the $p$-values $\hat{p}_{j,\text{naive}}$ and
$\hat{p}_{j,\text{k-means}}$ (where the $\hat{p}$ emphasizes that we used the
sample covariance matrix as an estimate of $\Sigma$ in (1)). The quantile-
quantile plot of the resulting $p$-values is displayed in Figure 6(a). We
display the number of rejected hypotheses after FDR correction using the BH
procedure [3] against the nominal FDR level in Figure 6(b). In this data set,
the naive $p$-values are extremely small for all pairs of estimated clusters,
leading to hundreds of rejected null hypotheses of equal means, while our
proposed $p$-values are quite large and lead to virtually no rejections after
FDR correction. In particular, at $\alpha=0.05$ and FDR level of $0.20$, the
test based on $\hat{p}_{j,\text{naive}}$ would conclude that more than 60%
genes are “differentially expressed”, whereas our approach would suggest that
expression levels across clusters are the same for most genes. Because this
“no cluster” data set consists only of a single type of expert-annotated cell
from a single donor, we believe the conclusion based on
$\hat{p}_{j,\text{k-means}}$ aligns better with the underlying biology.

Next, we turn our attention to the “cluster” data set, which encompasses
memory B cells, natural killer cells, macrophages, and monocytes. We applied
$k$-means clustering to obtain four clusters, and subsequently estimated a
covariance matrix based on the residuals from the $k$-means fit. Notably, the
clusters derived in this manner align closely with the four distinct cell
types, with an adjusted Rand Index between the cell type annotations and
estimated cluster memberships exceeding 0.6. We then computed the $p$-values
$\hat{p}_{j,\text{naive}}$ and $\hat{p}_{j,\text{k-means}}$ across all
features and for each pair of the estimated clusters. The quantiles of these
$p$-values, as well as the number of null hypotheses rejected following FDR
adjustment, are depicted in panels (a) and (b) of Figure 7, respectively.
Notably, both sets of $p$-values on this data set are quite small, and the BH
procedure results in a comparable count of rejections for both sets of
$p$-values. Given that the clusters in this context largely correspond to
distinct cell types, our results suggest that the test employing our proposed
$p$-value has reasonable power to reject the null hypothesis when it does not
hold.

##  7 Discussion

In this work, we proposed a test for a difference in means for a single
feature between two clusters estimated from hierarchical or $k$-means
clustering, under (1). Here, we outline several future research directions.

The $p$-values introduced in Section 3 can be extended to test for a
difference in means between _groups_ of features. For instance, if we want to
test for equality in means for all features $j\in J$ between two estimated
clusters, i.e., $\hat{H}_{0J}:\bigcap_{j\in
J}\big{\\{}\bar{\mu}_{\hat{G}j}=\bar{\mu}_{\hat{G}^{\prime}j}\big{\\}}$.
Following the argument in this paper, the following $p$-value
$\mathbb{P}_{\hat{H}_{0J}}\Big{(}\big{\|}[X^{T}\hat{\nu}]_{J}\big{\|}_{2}\big{|}\geq\big{\|}[x^{T}\hat{\nu}]_{J}\big{\|}_{2}\big{|}~{}\Bigg{|}~{}\mathcal{C}(X)=\mathcal{C}(x),$
$X-\frac{\hat{\nu}\Sigma_{J}^{T}[X^{T}\hat{\nu}]_{J}}{\|\hat{\nu}\|_{2}^{2}\Sigma_{JJ}}=x-\frac{\hat{\nu}\Sigma_{J}^{T}[x^{T}\hat{\nu}]_{J}}{\|\hat{\nu}\|_{2}^{2}\Sigma_{JJ}}\Big{)}$
controls the selective Type I error rate under (1) and can be efficiently
computed. Here, $[x^{T}\hat{\nu}]_{J}\in\mathbb{R}^{|J|}$ represents the
vector subset with indices in $J$; $\Sigma_{J}\in\mathbb{R}^{q\times|J|}$ is
the submatrix in $\Sigma$ with columns in $J$; and
$\Sigma_{JJ}\in\mathbb{R}^{|J|\times|J|}$ is the submatrix in $\Sigma$ with
row and column indices in $J$.

Furthermore, our $p$-values can be used to derive selective confidence
intervals for a difference in means for feature $j$ [17, 9]. Under our setup,
computing the confidence intervals amounts to a root-finding problem, which
can be efficiently solved using bisection [5, 4]. This extension would enhance
data uncertainty evaluation: for instance, both $p$-values and confidence
intervals on differing gene expression profiles are used to guide downstream
scientific inquiries.

## Acknowledgments

We acknowledge funding from the following sources: Natural Sciences and
Engineering Research Council of Canada Discovery Grant to LG and Stanford Data
Science Fellowship to YC. This work was also partially supported by National
Institutes of Health grants (R01 EB026908, R01 GM123993, and R01 DA047869).

## References

  * Aizarani et al., [2019] Aizarani, N., Saviano, A., Mailly, L., Durand, S., Herman, J. S., Pessaux, P., Baumert, T. F., and Grün, D. (2019).  A human liver cell atlas reveals heterogeneity and epithelial progenitors.  Nature, 572(7768):199–204.
  * Aloise et al., [2009] Aloise, D., Deshpande, A., Hansen, P., and Popat, P. (2009).  NP-hardness of Euclidean sum-of-squares clustering.  Machine Learning, 75(2):245–248.
  * Benjamini and Hochberg, [1995] Benjamini, Y. and Hochberg, Y. (1995).  Controlling the false discovery rate: A practical and powerful approach to multiple testing.  Journal of the Royal Statistical Society. Series B, Statistical methodology, 57(1):289–300.
  * Chen and Bien, [2020] Chen, S. and Bien, J. (2020).  Valid inference corrected for outlier removal.  Journal of Computational and Graphical Statistics, 29(2):323–334.
  * Chen et al., [2023] Chen, Y., Jewell, S., and Witten, D. (2023).  More powerful selective inference for the graph fused lasso.  Journal of Computational and Graphical Statistics, 32(2):577–587.
  * Chen and Witten, [2022] Chen, Y. T. and Witten, D. M. (2022).  Selective inference for k-means clustering.  To appear in Journal of Machine Learning Research.
  * Consortium et al., [2022] Consortium, T. S., Jones, R. C., Karkanias, J., Krasnow, M. A., Pisco, A. O., Quake, S. R., Salzman, J., Yosef, N., Bulthaup, B., Brown, P., et al. (2022).  The tabula sapiens: A multiple-organ, single-cell transcriptomic atlas of humans.  Science, 376(6594):eabl4896.
  * Duò et al., [2018] Duò, A., Robinson, M. D., and Soneson, C. (2018).  A systematic performance evaluation of clustering methods for single-cell RNA-seq data.  F1000Research, 7:1141.
  * Fithian et al., [2014] Fithian, W., Sun, D., and Taylor, J. (2014).  Optimal inference after model selection.  arXiv preprint arXiv:1410.2597.
  * Gao et al., [2022] Gao, L. L., Bien, J., and Witten, D. (2022).  Selective inference for hierarchical clustering.  Journal of the American Statistical Association, pages 1–11.
  * Grün et al., [2015] Grün, D., Lyubimova, A., Kester, L., Wiebrands, K., Basak, O., Sasaki, N., Clevers, H., and Van Oudenaarden, A. (2015).  Single-cell messenger rna sequencing reveals rare intestinal cell types.  Nature, 525(7568):251–255.
  * Hastie et al., [2001] Hastie, Trevor., Hastie, Trevor., Tibshirani, Robert., Friedman, and H., J. (2001).  The Elements of Statistical Learning : data mining, inference, and prediction.  Springer, New York.
  * Hivert et al., [2022] Hivert, B., Agniel, D., Thiébaut, R., and Hejblum, B. P. (2022).  Post-clustering difference testing: valid inference and practical considerations.  arXiv preprint arXiv:2210.13172.
  * Hyun et al., [2021] Hyun, S., Lin, K. Z., G’Sell, M., and Tibshirani, R. J. (2021).  Post-selection inference for changepoint detection algorithms with application to copy number variation data.  Biometrics.
  * Jaeger and Banks, [2022] Jaeger, A. and Banks, D. (2022).  Cluster analysis: A modern statistical review.  Wiley Interdisciplinary Reviews: Computational Statistics, page e1597.
  * Jewell et al., [2022] Jewell, S., Fearnhead, P., and Witten, D. (2022).  Testing for a change in mean after changepoint detection.  Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(4):1082–1104.
  * Lee et al., [2016] Lee, J. D., Sun, D. L., Sun, Y., and Taylor, J. E. (2016).  Exact post-selection inference, with application to the lasso.  The Annals of Statistics, 44(3):907–927.
  * Leisch et al., [2018] Leisch, F., Dolnicar, S., and Grün, B. (2018).  Market segmentation analysis: Understanding it, doing it, and making it useful.  Springer.
  * Lloyd, [1982] Lloyd, S. (1982).  Least squares quantization in PCM.  IEEE Trans. Inf. Theory, 28(2):129–137.
  * Neufeld et al., [2022] Neufeld, A., Gao, L. L., Popp, J., Battle, A., and Witten, D. (2022).  Inference after latent variable estimation for single-cell RNA sequencing data.  Biostatistics, pages 1–18.
  * Wood, [2017] Wood, S. (2017).  Generalized Additive Models: An Introduction with R.  Chapman and Hall/CRC, 2 edition.

## Appendix

##  Appendix A Proof of Theorem 1

We now prove Theorem 1. Observe that

$\displaystyle X$
$\displaystyle=X-\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}[X^{T}\hat{\nu}]_{j}+\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}[X^{T}\hat{\nu}]_{j}$
$\displaystyle=U(X)+\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}[X^{T}\hat{\nu}]_{j},$
(20)

where $U(X)$ is defined in equation (13) of the main text.

Substituting (20) into the definition of $p_{j,\text{selective}}$ in equation
(10) of the main text yields:

$\displaystyle p_{j,\text{selective}}$
$\displaystyle=\mathbb{P}_{\hat{H}_{0j}}\Big{(}\big{|}[X^{T}\hat{\nu}]_{j}\big{|}\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\mathcal{C}\left(U(x)+\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}[X^{T}\hat{\nu}]_{j}\right)=\mathcal{C}(x),~{}U(X)=U(x)\Big{)}$
$\displaystyle=\mathbb{P}_{\hat{H}_{0j}}\Big{(}\big{|}[X^{T}\hat{\nu}]_{j}\big{|}\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\mathcal{C}\left(x^{\prime}([X^{T}\hat{\nu}]_{j},j)\right)=\mathcal{C}(x),~{}U(X)=U(x)\Big{)},$
(21)

where the second equality in (21) follows from the definition of
$x^{\prime}(\phi,j)$ in Theorem 1. For any $\phi\in\mathbb{R}$, we can rewrite
$x^{\prime}(\phi,j)$ as:

$\displaystyle
x+(\phi-(\bar{x}_{\hat{G}j}-\bar{x}_{\hat{G^{\prime}}j}))\left(\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\right)\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}$
$\displaystyle=x+(\phi-[x^{T}\hat{\nu}]_{j}])\left(\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\right)\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}$
$\displaystyle=U(x)+\left(\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\right)\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}\phi.$

To simplify (21), we will show that

$\displaystyle U(X)\perp\\!\\!\\!\perp[\hat{X}^{T}\hat{\nu}]_{j}.$ (22)

First, observe that

$\displaystyle U(X)$
$\displaystyle=X-\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}[X^{T}\hat{\nu}]_{j}$
$\displaystyle=X-\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}X+\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}X-\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}[X^{T}\hat{\nu}]_{j}$
$\displaystyle=\left(I_{n}-\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}\right)X+\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\left(X^{T}\hat{\nu}-\frac{\Sigma_{j}}{\Sigma_{jj}}[X^{T}\hat{\nu}]_{j}\right)^{T}.$

Thus, to show (22), it suffices to show that the two terms in the sum are
independent of $[\hat{X}^{T}\hat{\nu}]_{j}$; i.e.,

$\displaystyle\left(I_{n}-\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}\right)X\perp\\!\\!\\!\perp\hat{X}^{T}\hat{\nu}$
(23)

and

$\displaystyle\left(X^{T}\hat{\nu}-\frac{\Sigma_{j}}{\Sigma_{jj}}[X^{T}\hat{\nu}]_{j}\right)\perp\\!\\!\\!\perp[X^{T}\hat{\nu}]_{j}.$
(24)

We will start by showing (23). Observe that
$I_{n}-\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}$ is the orthogonal
projection matrix onto the subspace orthogonal to $\hat{\nu}$. Thus,
$\left(I_{n}-\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}\right)\hat{\nu}=0$,
and (23) follows from properties of the multivariate normal distribution.

To show (24), we will need to state and prove an intermediate result.

######  Lemma 1.

Suppose that $\left[\begin{matrix}z_{1}\\\ z_{2}\end{matrix}\right]\sim
N_{q}\left(\left[\begin{matrix}\mu_{1}\\\
\mu_{2}\end{matrix}\right],\left[\begin{matrix}\Sigma_{11}&\Sigma_{12}\\\
\Sigma_{21}&\Sigma_{22}\end{matrix}\right]\right)$, where $z_{1}$ is a
$r$-vector and $z_{2}$ is a $(q-r)$-vector, and $\Sigma_{11}$ is invertible.
Then, $z_{1}$ and $z_{2}-\Sigma_{21}\Sigma_{11}^{-1}z_{1}$ are independent.

###### Proof.

Observe that

$\left[\begin{matrix}z_{1}\\\
z_{2}-\Sigma_{21}\Sigma_{11}^{-1}z_{1}\end{matrix}\right]=\left[\begin{matrix}I_{r}&0_{r\times(q-r)}\\\
-\Sigma_{21}\Sigma_{11}^{-1}&I_{q-r}\end{matrix}\right]\left[\begin{matrix}z_{1}\\\
z_{2}\end{matrix}\right].$

Therefore, for $B=\left[\begin{matrix}I_{r}&0_{r\times(q-r)}\\\
-\Sigma_{21}\Sigma_{11}^{-1}&I_{q-r}\end{matrix}\right]$, we have

$\left[\begin{matrix}z_{1}\\\
z_{2}-\Sigma_{21}\Sigma_{11}^{-1}z_{1}\end{matrix}\right]\sim
N_{q}\left(B\left[\begin{matrix}\mu_{1}\\\
\mu_{2}\end{matrix}\right],B\left[\begin{matrix}\Sigma_{11}&\Sigma_{12}\\\
\Sigma_{21}&\Sigma_{22}\end{matrix}\right]B^{T}\right).$

Algebra yields

$B\left[\begin{matrix}\Sigma_{11}&\Sigma_{12}\\\
\Sigma_{21}&\Sigma_{22}\end{matrix}\right]B^{T}=\left[\begin{matrix}\Sigma_{11}&0_{r\times(q-r)}\\\
0_{(q-r)\times
r}&\Sigma_{22}-\Sigma_{21}\Sigma_{11}^{-1}\Sigma_{12}\end{matrix}\right].$

Thus, it follows from properties of multivariate normal distributions that
$z_{1}$ and $z_{2}-\Sigma_{21}\Sigma_{11}^{-1}z_{1}$ are independent.

∎

Since $X^{T}\hat{\nu}\sim
N_{q}(\mu^{T}\hat{\nu},\|\hat{\nu}\|_{2}^{2}\Sigma)$, it follows from Lemma 1
that

$\displaystyle[X^{T}\hat{\nu}]_{j}\perp\\!\\!\\!\perp[X^{T}\hat{\nu}]_{-j}-\frac{\Sigma_{j,-j}^{T}}{\Sigma_{jj}}[X^{T}\hat{\nu}]_{j},$
(25)

where $[X^{T}\hat{\nu}]_{-j}$ denotes the result of removing the $j$th
component from $X^{T}\hat{\nu}\in\mathbb{R}^{q}$, and $\Sigma_{j,-j}$ denotes
the result of removing the $j$th component from $\Sigma_{j}\in\mathbb{R}^{q}$.
Finally, to complete the proof of (24), note that by algebra, the $j$th entry
of the vector
$X^{T}\hat{\nu}-\frac{\Sigma_{j}}{\Sigma_{jj}}[X^{T}\hat{\nu}]_{j}$ is always
0. This implies that any random variable that is independent of the $q-1$
subvector
$[X^{T}\hat{\nu}]_{-j}-\frac{\Sigma_{j,-j}^{T}}{\Sigma_{jj}}[X^{T}\hat{\nu}]_{j}$
in (25) is also independent of the full vector; this completes the proof.

We have now shown (22). Thus, we can apply (22) to simplify (21) as:

$\displaystyle p_{j,\text{selective}}$
$\displaystyle=\mathbb{P}_{\hat{H}_{0j}}\Big{(}\big{|}[X^{T}\hat{\nu}]_{j}\big{|}\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\mathcal{C}\left(x^{\prime}([X^{T}\hat{\nu}]_{j},j)\right)=\mathcal{C}(x)\Big{)}$
$\displaystyle=\mathbb{P}_{\hat{H}_{0j}}\Big{(}\big{|}[X^{T}\hat{\nu}]_{j}\big{|}\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}[X^{T}\hat{\nu}]_{j}\in\hat{S}_{j}\Big{)},$
(26)

where the second equality follows from the definition of $\hat{S}_{j}$ in
equation (14) of the main text as
$\left\\{\phi\in\mathbb{R}:C(x)=\mathcal{C}\left(x^{\prime}(\phi,j)\right)\right\\}$.

Now, under $\hat{H}_{0j}:[\mu^{T}\hat{\nu}]_{j}=0$, $[X^{T}\hat{\nu}]_{j}\sim
N(0,\|\hat{\nu}\|_{2}^{2}\Sigma_{jj})$. Thus, defining $\phi\sim
N(0,\|\hat{\nu}\|_{2}^{2}\Sigma_{jj})$, we can rewrite (26) as:

$\displaystyle p_{j,selective}$
$\displaystyle=\mathbb{P}\Big{(}\big{|}\phi\big{|}\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\phi\in\hat{S}_{j}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\phi\geq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\phi\in\hat{S}_{j}\Big{)}+\mathbb{P}\Big{(}\phi\leq-\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\phi\in\hat{S}_{j}\Big{)}$
$\displaystyle=1-\mathbb{P}\Big{(}\phi\leq\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\phi\in\hat{S}_{j}\Big{)}+\mathbb{P}\Big{(}\phi\leq-\big{|}[x^{T}\hat{\nu}]_{j}\big{|}~{}\Big{|}~{}\phi\in\hat{S}_{j}\Big{)}$
$\displaystyle=1-\mathbb{F}\left(\big{|}[\hat{\nu}^{T}x]_{j}\big{|};0,\Sigma_{jj}\|\hat{\nu}\|_{2}^{2};\mathcal{\hat{S}}_{j}\right)+\mathbb{F}\left(-\big{|}[\hat{\nu}^{T}x]_{j}\big{|};0,\Sigma_{jj}\|\hat{\nu}\|_{2}^{2};\mathcal{\hat{S}}_{j}\right),$
(27)

where $\mathbb{F}(t;\mu,\sigma,\mathcal{S})$ denotes the cumulative
distribution function (CDF) of a $N(\mu,\sigma^{2})$ random variable truncated
to the set $\mathcal{S}$. This is equation (13) in the main text.

We will now prove that rejecting $\hat{H}_{0j}$ based on
$p_{j,\text{selective}}\leq\alpha$ controls the selective type I error rate in
the sense of (8). First, recall that we decided to test
$\hat{H}_{0j}:[\mu^{T}\hat{\nu}]_{j}=0$ because
$\mathcal{C}(X)=\mathcal{C}(x)$. Thus, we need to show:

$\displaystyle\mathbb{P}_{\hat{H}_{0j}}\left(\text{Reject }\hat{H}_{0j}\text{
at level
}\alpha\mid\mathcal{C}(X)=\mathcal{C}(x)\right)\leq\alpha,~{}~{}~{}\text{for
all }\alpha\in(0,1).$ (28)

Define the function

$\displaystyle
p(t)=\mathbb{P}\Big{(}\big{|}\phi\big{|}\geq\big{|}t\big{|}~{}\Big{|}~{}\phi\in\hat{S}_{j}\Big{)}$
(29)

Then, observe that the following holds for any $\alpha\in(0,1)$:

$\displaystyle\mathbb{P}_{\hat{H}_{0j}}\left(\text{Reject }\hat{H}_{0j}\text{
at level }\alpha\mid\mathcal{C}(X)=\mathcal{C}(x),U(X)=U(x)\right)$
$\displaystyle=\mathbb{P}(p(\phi)\leq\alpha\mid\phi\in\hat{S}_{j})$
$\displaystyle=\alpha,$ (30)

where the first equality follows from (27), and the second equality follows
from the probability integral transform theorem. Therefore, we have that

$\displaystyle\mathbb{P}_{\hat{H}_{0j}}\left(\text{Reject }\hat{H}_{0j}\text{
at level }\alpha\mid\mathcal{C}(X)=\mathcal{C}(x)\right)$
$\displaystyle=\mathbb{E}_{\hat{H}_{0j}}\left[\mathbb{P}_{\hat{H}_{0j}}\left(\text{Reject
}\hat{H}_{0j}\text{ at level
}\alpha\mid\mathcal{C}(X)=\mathcal{C}(x),U(X)=U(x)\right)\mid\mathcal{C}(X)=\mathcal{C}(x)\right]$
$\displaystyle=\mathbb{E}_{\hat{H}_{0j}}[\alpha\mid\mathcal{C}(X)=\mathcal{C}(x)]$
$\displaystyle=\alpha,$

where the first equality follows from the tower property of conditional
expectation, and the second equality follows from (30). That is, equation (28)
holds with equality.

##  Appendix B Additional details for the extensions to $k$-means clustering
in Section 4.3

In this section, we provide more details on the extensions of proposals in
Section 3 of the main text to $k$-means clustering.

###  B.1 A brief overview of the $k$-means algorithm

We briefly review the $k$-means clustering algorithm in this section. For a
set of samples $x_{1},\ldots,x_{n}\in\mathbb{R}^{q}$ and a positive integer
$K$, $k$-means clustering partitions the $n$ samples into disjoint subsets
$\hat{\mathcal{C}}_{1},\ldots,\hat{\mathcal{C}}_{K}$ by solving the following
optimization problem [2, 19]:

$\displaystyle\begin{split}&\underset{\mathcal{C}_{1},\ldots,\mathcal{C}_{K}}{\text{minimize}}\;\Bigg{\\{}\sum_{k=1}^{K}\sum_{i\in\mathcal{C}_{k}}\bigg{\|}x_{i}-\sum_{i\in\mathcal{C}_{k}}x_{i}/|\mathcal{C}_{k}|\bigg{\|}_{2}^{2}\Bigg{\\}}\\\
&\text{subject
to}\;\bigcup_{k=1}^{K}\mathcal{C}_{k}=\\{1,\ldots,n\\},\mathcal{C}_{k}\cap\mathcal{C}_{k^{\prime}}=\emptyset,\forall
k\neq k^{\prime}.\end{split}$ (31)

It is not typically possible to solve for the global optimum in
(LABEL:eq:k_means_objective) [2]; one of the most popular approaches is
Lloyd’s algorithm [19], given in Algorithm 1. In Lloyd’s algorithm, we first
sample $K$ out of $n$ observations as initial centroids (step 1 in Algorithm
1), followed by assigning each observation to its closest centroid (step 2).
Next, we iterate between steps 1 and 2 until the cluster assignments stop
changing, and the algorithm is guaranteed to converge to a local optimum [12].

Input: Data $x_{1},\ldots,x_{n}\in\mathbb{R}^{q}$, number of output clusters
$K$, maximum iteration $T$, random seed $s$.

Output: Cluster assignments $(c_{1}^{(t)},\ldots,c_{n}^{(t)})$.

1 1\. Initialize the centroids $(m_{1}^{(1)},\ldots,m_{K}^{(1)})$ by sampling
$K$ observations from $x_{1},\ldots,x_{n}$ without replacement, using the
random seed $s$.

2 2\. Compute assignments $c_{i}^{(1)}\leftarrow\underset{1\leq k\leq
K}{\text{argmin}}\left\|x_{i}-m_{k}^{(1)}\right\|_{2}^{2},\,i=1,\ldots,n.$

3 3\. Initialize $t=1$.

4 while  _$t\leq T$_ do

5 a. Update centroids:
$m_{k}^{(t+1)}\leftarrow(\sum_{i:c_{i}^{(t)}=k}x_{i})/\sum_{i=1}^{n}\mathds{1}\\{c_{i}^{(t)}=k\\},\,k=1,\ldots,K.$

6 b. Update assignment: $c_{i}^{(t+1)}\leftarrow\underset{1\leq k\leq
K}{\text{argmin}}\left\|x_{i}-m_{k}^{(t+1)}\right\|_{2}^{2},\,i=1,\ldots,n.$

7 c. if $c_{i}^{(t+1)}=c_{i}^{(t)}$ _for all_ $1\leq i\leq n$

8 break

9 else

10 $t\leftarrow t+1.$

11

12return _$(c_{1}^{(t)},\ldots,c_{n}^{(t)})$_.

Algorithm 1 Lloyd’s algorithm for $k$-means clustering [19]

###  B.2 Characterization and efficient computation of $p_{j,\text{k-means}}$

Theorem 3 below is a direct extension of Theorem 1 (stated in Section 3.2 of
the main text and proven in Appendix A) to the case of $k$-means clustering.
Recalling
$U(x)=x-\frac{\hat{\nu}\Sigma_{j}^{T}[x^{T}\hat{\nu}]_{j}}{\|\hat{\nu}\|_{2}^{2}\Sigma_{jj}}$,
we first rewrite $p_{j,\text{k-means}}$:

$\displaystyle p_{j,\text{k-means}}$
$\displaystyle=\mathbb{P}_{{\hat{H}_{0j}}}\Bigg{(}\big{|}[X^{T}\hat{\nu}]_{j}\big{|}\geq\big{|}[X^{T}\hat{\nu}]_{j}\big{|}~{}\Bigg{|}~{}U(X)=U(x),\bigcap_{t=0}^{T}\bigcap_{i=1}^{n}\big{\\{}c_{i}^{(t)}(X)=c_{i}^{(t)}(x)\big{\\}}\Bigg{)}.$

######  Theorem 3.

Suppose that $x$ is a realization from (1), i.e., each row $x_{i}$ is drawn
independently from $N_{q}(\mu_{i},\Sigma),\,i=1,2,\ldots,n,$ and
$\mathbb{F}(t;\mu,\sigma,\mathcal{S})$ denotes the cumulative distribution
function (CDF) of a $N(\mu,\sigma^{2})$ random variable truncated to the set
$\mathcal{S}$. If
$\hat{H}_{0j}:\bar{\mu}_{\hat{G}j}=\bar{\mu}_{\hat{G}^{\prime}j}$ holds for a
given $j\in\\{1,2,\ldots,q\\}$, then we have that

$\displaystyle p_{j,\text{k-means}}$
$\displaystyle=1-\mathbb{F}\left(\big{|}[\hat{\nu}^{T}x]_{j}\big{|};0,\Sigma_{jj}\|\nu\|_{2}^{2};\mathcal{S}_{j}\Big{(}x;\bigcap_{t=1}^{T}C^{(t)}(x)\Big{)}\right)+\mathbb{F}\left(-\big{|}[\hat{\nu}^{T}x]_{j}\big{|};0,\Sigma_{jj}\|\hat{\nu}\|_{2}^{2};\mathcal{S}_{j}\Big{(}x;\bigcap_{t=1}^{T}C^{(t)}(x)\Big{)}\right).$
(32)

Here, $C^{(t)}(x)=(c_{1}^{(t)},\ldots,c_{n}^{(1)})$ is the estimated cluster
at the $t$th iteration of the $k$-means algorithm, and

$\mathcal{S}_{j}\Big{(}x;\bigcap_{t=1}^{T}C^{(t)}(x)\Big{)}=\left\\{\phi\in\mathbb{R}:\bigcap_{t=1}^{T}\left\\{{C}^{(t)}\left(x+(\phi-(\bar{x}_{\hat{G}j}-\bar{x}_{\hat{G}^{\prime}j}))\left(\frac{\hat{\nu}}{\|\hat{\nu}\|_{2}^{2}}\right)\left(\frac{\Sigma_{j}}{\Sigma_{jj}}\right)^{T}\right)={C}^{(t)}(x)\right\\}\right\\}.$
(33)

Furthermore, rejecting $\hat{H}_{0j}$ whenever
$p_{\text{k-means},j}\leq\alpha$ controls the selective type I error rate at
level $\alpha$.

###### Proof.

The proof of Theorem 3 follows directly from the proof of Theorem 1 in Section
1 of the Appendix by replacing the clustering output $\mathcal{C}(\cdot)$ with
$\bigcap_{t=1}^{T}C^{(t)}(\cdot)$. ∎

It follows from Theorem 3 that computing the $p$-value $p_{j,\text{k-means}}$
reduces to characterizing the set
$\mathcal{S}_{j}\Big{(}x;\bigcap_{t=1}^{T}C^{(t)}(x)\Big{)}$ in (33). It turns
out we could directly leverage the results in Chen and Witten, [6] (reproduced
below as Lemma 1), which tests for a difference in the means for the entire
vector, to arrive at a computationally-efficient recipe.

######  Corollary 1 (Chen and Witten (2023)).

For any $w\in\mathbb{R}^{q}$, define the set

$\mathcal{S}\Big{(}w;\bigcap_{t=1}^{T}C^{(t)}(x)\Big{)}=\left\\{\phi\in\mathbb{R}:\bigcap_{t=1}^{T}\left\\{{C}^{(t)}\left(\left(I-\frac{\hat{\nu}\hat{\nu}^{T}}{\|\hat{\nu}\|_{2}^{2}}\right)x+\frac{\phi\hat{\nu}w^{T}}{\|\hat{\nu}\|_{2}^{2}}\right)={C}^{(t)}(x)\right\\}\right\\}.$
(34)

Suppose that we apply the $k$-means clustering algorithm (Algorithm 1) to a
matrix ${x}\in\mathbb{R}^{n\times q}$, to obtain $K$ clusters in at most $T$
steps. Then, the set $\mathcal{S}\Big{(}w;\bigcap_{t=1}^{T}C^{(t)}(x)\Big{)}$
defined in (34) can be computed in
$\mathcal{O}\big{(}nKT(n+q)+nKT\log(nKT)\big{)}$ operations.

###### Proof.

Corollary 1 follows from the observation Proposition 5 in Chen and Witten, [6]
proves the special case of
$\mathcal{S}\Big{(}w;\bigcap_{t=1}^{T}C^{(t)}(x)\Big{)}$ with
$w=\nu^{T}x/\|\hat{\nu}^{T}x\|_{2}$. However, no special properties of the
vector $\hat{\nu}^{T}x/\|\hat{\nu}^{T}x\|_{2}$ was used in the proof, and
replacing $\hat{\nu}^{T}x/\|\hat{\nu}^{T}x\|_{2}$ with
$\Sigma_{j}/\Sigma_{jj}$ everywhere in their proof yields the desired result.
∎

##  Appendix C Additional simulation results

In Section 5.3, we compared the conditional power of the tests based on
$p_{j,\text{k-means}}$, $p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and
$p_{j,\text{single}}$ under model (1).

Here, we consider a different notion of power that does not condition on the
estimated clusters $\hat{G}$ and $\hat{G}^{\prime}$ being true clusters. In
this case, comparing the power of the tests requires a bit of care, because
the “effect size”, $\Big{|}[\mu^{T}\hat{\nu}]_{j}\Big{|}$ may differ across
simulated data sets from the same data-generating distribution, as the
estimated clusters and the corresponding contrast vector $\hat{\mu}$ might
vary across simulated data sets. As a result, we consider the power of the
tests _as a function of $\Big{|}[\mu^{T}\hat{\nu}]_{j}\Big{|}$_. We fit a
regression spline using the gam function in the R package mgcv [21] to obtain
a smooth estimate of power on the same simulated data sets from Section 5.3.

The results are in Figure 8. The power of the tests that reject
$\hat{H}_{0j}:\bar{\mu}_{\hat{G}j}=\bar{\mu}_{\hat{G}^{\prime}j}$ when
$p_{j,\text{k-means}}$, $p_{j,\text{average}}$, $p_{j,\text{centroid}}$, or
$p_{j,\text{single}}$ is less than $\alpha=0.05$ increases as
$\Big{|}[\mu^{T}\hat{\nu}]_{j}\Big{|}$ increases. For a given value of
$\Big{|}[\mu^{T}\hat{\nu}]_{j}\Big{|}$, the power of different tests depends
on the correlation among features. When data have low to moderate
correlations, the tests based on $p_{j,\text{average}}$ and
$p_{j,\text{centroid}}$ generally have higher power than the tests based on
$p_{j,\text{k-means}}$ and $p_{j,\text{single}}$. When the correlation among
features is high (e.g., $\rho=0.8$), the test based on $p_{j,\text{single}}$
has the highest power, followed by those based on $p_{j,\text{average}}$ and
$p_{j,\text{centroid}}$; the test based on $p_{j,\text{k-means}}$ has the
lowest power.

Figure 8: We fit a regression spline on the simulated data sets from Section
5.3 to display the power of the tests based on $p_{j,\text{k-means}}$,
$p_{j,\text{average}}$, $p_{j,\text{centroid}}$, and $p_{j,\text{single}}$.


$Id:espcrc1.tex,v1.22004/02/2411:22:11speppingExp$ Interval colorings of
complete balanced multipartite graphsPetros A. Petrosyan

# Interval colorings of complete balanced multipartite graphs

Petros A. Petrosyan email<EMAIL_ADDRESS>ysu.am, yahoo.com}
Institute for Informatics and Automation Problems,
National Academy of Sciences, 0014, Armenia  Department of Informatics and
Applied Mathematics,
Yerevan State University, 0025, Armenia

###### Abstract

A graph $G$ is called a complete $k$-partite ($k\geq 2$) graph if its vertices
can be partitioned into $k$ independent sets $V_{1},\ldots,V_{k}$ such that
each vertex in $V_{i}$ is adjacent to all the other vertices in $V_{j}$ for
$1\leq i<j\leq k$. A complete $k$-partite graph $G$ is a complete balanced
$k$-partite graph if $|V_{1}|=|V_{2}|=\cdots=|V_{k}|$. An edge-coloring of a
graph $G$ with colors $1,\ldots,t$ is an interval $t$-coloring if all colors
are used, and the colors of edges incident to each vertex of $G$ are distinct
and form an interval of integers. A graph $G$ is interval colorable if $G$ has
an interval $t$-coloring for some positive integer $t$. In this paper we show
that a complete balanced $k$-partite graph $G$ with $n$ vertices in each part
is interval colorable if and only if $nk$ is even. We also prove that if $nk$
is even and $(k-1)n\leq t\leq\left(\frac{3}{2}k-1\right)n-1$, then a complete
balanced $k$-partite graph $G$ admits an interval $t$-coloring. Moreover, if
$k=p2^{q}$, where $p$ is odd and $q\in\mathbb{N}$, then a complete balanced
$k$-partite graph $G$ has an interval $t$-coloring for each positive integer
$t$ satisfying $(k-1)n\leq t\leq\left(2k-p-q\right)n-1$.

Keywords: edge-coloring, interval coloring, complete multipartite graph,
complete graph, complete bipartite graph

##  1 Introduction

Throughout this paper all graphs are finite, undirected, and have no loops or
multiple edges. Let $V(G)$ and $E(G)$ denote the sets of vertices and edges of
$G$, respectively. For $F\subseteq E(G)$, the subgraph obtained by deleting
the edges of $F$ from $G$ is denoted by $G-F$. The maximum degree of $G$ is
denoted by $\Delta(G)$. The terms and concepts that we do not define can be
found in [19].

An edge-coloring of a graph $G$ is a mapping
$\alpha:E(G)\rightarrow\mathbb{N}$. A proper edge-coloring of a graph $G$ is
an edge-coloring $\alpha$ of $G$ such that $\alpha(e)\neq\alpha(e^{\prime})$
for any pair of adjacent edges $e,e^{\prime}\in E(G)$. The edge-chromatic
number $\chi^{\prime}(G)$ of $G$ is the least number of colors needed for a
proper edge-coloring of $G$. Clearly, $\chi^{\prime}(G)\geq\Delta(G)$ for
every graph $G$. On the other hand, the well-known theorem of Vizing [16]
states that the edge-chromatic number of any graph $G$ is either $\Delta(G)$
or $\Delta(G)+1$. One of the most important, interesting and long-standing
problem in this field is the problem of determining the exact value of the
edge-chromatic number of graphs. There are many results in this direction, in
particular, the exact value of the edge-chromatic number is known for
bipartite graphs [13], complete graphs [4, 18], complete multipartite graphs
[9, 14], split graphs with odd maximum degree [5], outerplanar graphs [7],
planar graphs $G$ with $\Delta(G)\geq 7$ [17, 20].

A graph $G$ is a complete $k$-partite ($k\geq 2$) graph if its vertices can be
partitioned into $k$ independent sets $V_{1},\ldots,V_{k}$ such that each
vertex in $V_{i}$ is adjacent to all the other vertices in $V_{j}$ for $1\leq
i<j\leq k$. A complete $k$-partite graph $G$ is a complete balanced
$k$-partite graph if $|V_{1}|=|V_{2}|=\cdots=|V_{k}|$. Clearly, if $G$ is a
complete balanced $k$-partite graph with $n$ vertices in each part, then
$\Delta(G)=(k-1)n$. Note that the complete graph $K_{n}$ and the complete
balanced bipartite graph $K_{n,n}$ are special cases of the complete balanced
$k$-partite graph. In [14], Laskar and Hare proved the following:

###### Theorem 1

If $G$ is a complete balanced $k$-partite graph with $n$ vertices in each
part, then

$\chi^{\prime}(G)=\left\\{\begin{tabular}[]{ll}$(k-1)n$,&if $nk$ is even,\\\
$(k-1)n+1$,&if $nk$ is odd.\\\ \end{tabular}\right.$

A more general result was obtained by Hoffman and Rodger [9]. Before we
formulate this result we need a definition of the overfull graph. A graph $G$
is overfull if $|E(G)|>\left\lfloor\frac{|V(G)|}{2}\right\rfloor\Delta(G)$.
Clearly, if $G$ is overfull, then $\chi^{\prime}(G)=\Delta(G)+1$.

###### Theorem 2

If $G$ is a complete $k$-partite graph, then

$\chi^{\prime}(G)=\left\\{\begin{tabular}[]{ll}$\Delta(G)$,&if $G$ is not
overfull,\\\ $\Delta(G)+1$,&if $G$ is overfull.\\\ \end{tabular}\right.$

An edge-coloring of a graph $G$ with colors $1,\ldots,t$ is an interval
$t$-coloring if all colors are used, and the colors of edges incident to each
vertex of $G$ are distinct and form an interval of integers. A graph $G$ is
interval colorable if $G$ has an interval $t$-coloring for some positive
integer $t$. For an interval colorable graph $G$, the least and the greatest
values of $t$ for which $G$ has an interval $t$-coloring are denoted by $w(G)$
and $W(G)$, respectively. The concept of interval edge-coloring was introduced
by Asratian and Kamalian [1]. In [1, 2], they proved the following:

###### Theorem 3

If $G$ is a regular graph, then

(1)

$G$ is interval colorable if and only if $\chi^{\prime}(G)=\Delta(G)$.

(2)

If $G$ is interval colorable and $w(G)\leq t\leq W(G)$, then $G$ has an
interval $t$-coloring.

In [10], Kamalian investigated interval colorings of complete bipartite graphs
and trees. In particular, he proved the following:

###### Theorem 4

For any $r,s\in\mathbb{N}$, the complete bipartite graph $K_{r,s}$ is interval
colorable, and

(1)

$w\left(K_{r,s}\right)=r+s-\gcd(r,s)$,

(2)

$W\left(K_{r,s}\right)=r+s-1$,

(3)

if $w\left(K_{r,s}\right)\leq t\leq W\left(K_{r,s}\right)$, then $K_{r,s}$ has
an interval $t$-coloring.

Later, Kamalian [11] obtained an upper bound on $W(G)$ for an interval
colorable graph $G$ depending on the number of vertices of $G$.

###### Theorem 5

If $G$ is a connected interval colorable graph, then $W(G)\leq 2|V(G)|-3$.

Clearly, this bound is sharp for the complete graph $K_{2}$, but if $G\neq
K_{2}$, then this upper bound can be improved to $2\left|V(G)\right|-4$ [8].
For an $r$-regular graph $G$, Kamalian and Petrosyan [12] showed that if $G$
with at least $2r+2$ vertices admits an interval $t$-coloring, then $t\leq
2\left|V(G)\right|-5$. For a planar graph $G$, Axenovich [3] showed that if
$G$ has an interval $t$-coloring, then $t\leq\frac{11}{6}\left|V(G)\right|$.
In [15], Petrosyan investigated interval colorings of complete graphs and
$n$-dimensional cubes. First note that $K_{2n+1}$ is not interval colorable,
but $K_{2n}$ is interval colorable and $w(K_{2n})=2n-1$ for any
$n\in\mathbb{N}$. For $W(K_{2n})$, Petrosyan [15] proved the following:

###### Theorem 6

If $n=p2^{q}$, where $p$ is odd and $q$ is nonnegative, then
$W\left(K_{2n}\right)\geq 4n-2-p-q$.

In this paper we investigate interval colorings of complete balanced
$k$-partite graphs. In particular, we generalize Theorem 6 for complete
balanced $k$-partite graphs. Also, we discuss some other corollaries of our
result.

##  2 Results

If $\alpha$ is a proper edge-coloring of $G$ and $v\in V(G)$, then
$S\left(v,\alpha\right)$ denotes the set of colors appearing on edges incident
to $v$.

Let $[t]$ denote the set of the first $t$ natural numbers. Let $\left\lfloor
a\right\rfloor$ denote the largest integer less than or equal to $a$. For two
positive integers $a$ and $b$ with $a\leq b$, the set
$\left\\{a,\ldots,b\right\\}$ is denoted by $[a,b]$ and called an interval.
For an interval $[a,b]$ and a nonnegative number $p$, the notation
$[a,b]\oplus p$ means: $[a+p,b+p]$.

We also need the following lemma.

###### Lemma 7

If $K_{n,n}$ is a complete balanced bipartite graph with a bipartition
$(U,V)$, where $U=\\{u_{1},\ldots,u_{n}\\}$ and $V=\\{v_{1},\ldots,v_{n}\\}$,
then $K_{n,n}$ has an interval $(2n-1)$-coloring $\alpha$ such that
$S(u_{i},\alpha)=S(v_{i},\alpha)=[i,i+n-1]$ for $1\leq i\leq n$

  * Proof.

Let $(U,V)$ be a bipartition of $K_{n,n}$, where $U=\\{u_{1},\ldots,u_{n}\\}$
and $V=\\{v_{1},\ldots,v_{n}\\}$. Define a coloring $\alpha$ of the edges of
$K_{n,n}$ as follows: for each edge $u_{i}v_{j}\in E(K_{n,n})$, let
$\alpha(u_{i}v_{j})=i+j-1$, where $1\leq i\leq n,1\leq j\leq n$. Clearly
$\alpha$ is an interval $(2n-1)$-coloring of $K_{n,n}$ and
$S(u_{i},\alpha)=S(v_{i},\alpha)=[i,i+n-1]$ for $1\leq i\leq n$. $\square$

Let $G$ be a complete balanced $k$-partite graph with $n$ vertices in each
part. By Theorems 1 and 3, we have that $G$ is interval colorable if and only
if $nk$ is even. Moreover, if $nk$ is even, then $w(G)=\Delta(G)=(k-1)n$. On
the other hand, by Theorem 5, we obtain $W(G)\leq 2nk-3$ whenever $nk$ is
even. Now we derive a lower bound for $W(G)$.

###### Theorem 8

If $G$ is a complete balanced $k$-partite graph with $n$ vertices in each part
and $nk$ is even, then $W(G)\geq\left(\frac{3}{2}k-1\right)n-1$.

  * Proof.

We distinguish our proof into two cases.

Case 1: $k$ is even.

Let $V(G)=\left\\{v^{(i)}_{j}\colon\,1\leq i\leq k,1\leq j\leq n\right\\}$ and

$E(G)=\left\\{v^{(i)}_{p}v^{(j)}_{q}\colon\,1\leq i<j\leq k,1\leq p\leq
n,1\leq q\leq n\right\\}$.

Define an edge-coloring $\alpha$ of the graph $G$.

For each edge $v^{(i)}_{p}v^{(j)}_{q}\in E(G)$ with $1\leq i<j\leq k$ and
$p=1,\ldots,n$, $q=1,\ldots,n$, define a color
$\alpha\left(v^{(i)}_{p}v^{(j)}_{q}\right)$ as follows:

for $i=1,\ldots,\left\lfloor\frac{k}{4}\right\rfloor$,
$j=2,\ldots,\frac{k}{2}$, $i+j\leq\frac{k}{2}+1$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-3\right)n+p+q-1$;

for $i=2,\ldots,\frac{k}{2}-1$,
$j=\left\lfloor\frac{k}{4}\right\rfloor+2,\ldots,\frac{k}{2}$,
$i+j\geq\frac{k}{2}+2$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j+\frac{k}{2}-4\right)n+p+q-1$;

for $i=3,\ldots,\frac{k}{2}$, $j=\frac{k}{2}+1,\dots,k-2$,
$j-i\leq\frac{k}{2}-2$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(\frac{k}{2}+j-i-1\right)n+p+q-1$;

for $i=1,\ldots,\frac{k}{2}$, $j=\frac{k}{2}+1,\ldots,k$,
$j-i\geq\frac{k}{2}$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(j-i-1\right)n+p+q-1$;

for $i=2,\ldots,1+\left\lfloor\frac{k-2}{4}\right\rfloor$,
$j=\frac{k}{2}+1,\dots,\frac{k}{2}+\left\lfloor\frac{k-2}{4}\right\rfloor$,
$j-i=\frac{k}{2}-1$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(2i-3\right)n+p+q-1$;

for $i=\left\lfloor\frac{k-2}{4}\right\rfloor+2,\ldots,\frac{k}{2}$,
$j=\frac{k}{2}+1+\left\lfloor\frac{k-2}{4}\right\rfloor,\ldots,k-1$,
$j-i=\frac{k}{2}-1$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-3\right)n+p+q-1$;

for
$i=\frac{k}{2}+1,\dots,\frac{k}{2}+\left\lfloor\frac{k}{4}\right\rfloor-1$,
$j=\frac{k}{2}+2,\ldots,k-2$, $i+j\leq\frac{3}{2}k-1$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-k-1\right)n+p+q-1$;

for $i=\frac{k}{2}+1,\ldots,k-1$,
$j=\frac{k}{2}+\left\lfloor\frac{k}{4}\right\rfloor+1,\dots,k$,
$i+j\geq\frac{3}{2}k$, let

$\alpha\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-\frac{k}{2}-2\right)n+p+q-1$.

Let us prove that $\alpha$ is an interval
$\left(\left(\frac{3}{2}k-1\right)n-1\right)$-coloring of the graph $G$.

First we show that for each $t\in\left[\left(\frac{3}{2}k-1\right)n-1\right]$,
there is an edge $e\in E(G)$ with $\alpha(e)=t$.

Consider the vertices
$v_{1}^{(1)},\ldots,v_{n}^{(1)},v_{1}^{(k)},\ldots,v_{n}^{(k)}$. Now, by Lemma
7 and the definition of $\alpha$, for $1\leq j\leq n$,

$S\left(v_{j}^{(1)},\alpha\right)=\bigcup_{l=1}^{k-1}\left([j,j+n-1]\oplus(l-1)n\right)$
and
$S\left(v_{j}^{(k)},\alpha\right)=\bigcup_{l=\frac{k}{2}}^{\frac{3}{2}k-2}\left([j,j+n-1]\oplus(l-1)n\right)$.

Let $\overline{C}$ and $\overline{\overline{C}}$ be the subsets of colors
appear on edges incident to the vertices $v_{1}^{(1)},\ldots,v_{n}^{(1)}$ and
$v_{1}^{(k)},\ldots,v_{n}^{(k)}$ in the coloring $\alpha$, respectively, that
is:

$\overline{C}=\bigcup_{j=1}^{n}S\left(v_{j}^{(1)},\alpha\right)$ and
$\overline{\overline{C}}=\bigcup_{j=1}^{n}S\left(v_{j}^{(k)},\alpha\right)$.

It is straightforward to check that
$\overline{C}\cup\overline{\overline{C}}=\left[\left(\frac{3}{2}k-1\right)n-1\right]$,
so for each $t\in\left[\left(\frac{3}{2}k-1\right)n-1\right]$, there is an
edge $e\in E(G)$ with $\alpha(e)=t$.

Next we show that the edges incident to any vertex of $G$ are colored by
$(k-1)n$ consecutive colors.

Let $v_{j}^{(i)}\in V(G)$, where $1\leq i\leq k$, $1\leq j\leq n$.

Subcase 1.1. $1\leq i\leq 2$, $1\leq j\leq n$.

By Lemma 7 and the definition of $\alpha$, we have

$S\left(v_{j}^{(1)},\alpha\right)=S\left(v_{j}^{(2)},\alpha\right)=\bigcup_{l=1}^{k-1}\left([j,j+n-1]\oplus(l-1)n\right)=\left[j,j+(k-1)n-1\right]$.

Subcase 1.2. $3\leq i\leq\frac{k}{2}$, $1\leq j\leq n$.

By Lemma 7 and the definition of $\alpha$, we have

$S\left(v_{j}^{(i)},\alpha\right)=\bigcup_{l=i-1}^{k-3+i}\left([j,j+n-1]\oplus(l-1)n\right)=\left[j+(i-2)n,j+(k-3+i)n-1\right]$.

Subcase 1.3. $\frac{k}{2}+1\leq i\leq k-2$, $1\leq j\leq n$.

By Lemma 7 and the definition of $\alpha$, we have

$S\left(v_{j}^{(i)},\alpha\right)=\bigcup_{l=i-\frac{k}{2}+1}^{\frac{k}{2}-1+i}\left([j,j+n-1]\oplus(l-1)n\right)=\left[j+\left(i-\frac{k}{2}\right)n,j+\left(\frac{k}{2}-1+i\right)n-1\right]$.

Subcase 1.4. $k-1\leq i\leq k,1\leq j\leq n$.

By Lemma 7 and the definition of $\alpha$, we have

$S\left(v_{j}^{(k-1)},\alpha\right)=S\left(v_{j}^{(k)},\alpha\right)=\bigcup_{l=\frac{k}{2}}^{\frac{3}{2}k-2}\left([j,j+n-1]\oplus(l-1)n\right)=\left[j+\left(\frac{k}{2}-1\right)n,j+\left(\frac{3k}{2}-2\right)n-1\right]$.

This shows that $\alpha$ is an interval
$\left(\left(\frac{3}{2}k-1\right)n-1\right)$-coloring of $G$; thus
$W(G)\geq\left(\frac{3}{2}k-1\right)n-1$ for even $k\geq 2$.

Case 2: $n$ is even.

Let $n=2m$, $m\in\mathbb{N}$. Let
$U_{i}=\left\\{v_{1}^{(i)},\ldots,v_{m}^{(i)},v_{1}^{(k+i)},\ldots,v_{m}^{(k+i)}\right\\}$
($1\leq i\leq k$) be the $k$ independent sets of vertices of $G$. For
$i=1,\ldots,2k$, define the set $V_{i}$ as follows:
$V_{i}=\left\\{v_{1}^{(i)},\ldots,v_{m}^{(i)}\right\\}$. Clearly,
$V(G)=\bigcup_{i=1}^{2k}V_{i}$. For $1\leq i<j\leq 2k$, define $(V_{i},V_{j})$
as the set of all edges between $V_{i}$ and $V_{j}$. It is easy to see that
for $1\leq i<j\leq 2k$, $\left|(V_{i},V_{j})\right|=m^{2}$ except for
$\left|(V_{i},V_{k+i})\right|=0$ whenever $i=1,\ldots,k$. If we consider the
sets $V_{i}$ as the vertices and the sets $(V_{i},V_{j})$ as the edges, then
we obtain that $G$ is isomorphic to the graph $K_{2k}-F$, where $F$ is a
perfect matching. Now we define an edge-coloring $\beta$ of the graph $G$.

For each edge $v^{(i)}_{p}v^{(j)}_{q}\in E(G)$ with $1\leq i<j\leq 2k$ and
$p=1,\ldots,m$, $q=1,\ldots,m$, define a color
$\beta\left(v^{(i)}_{p}v^{(j)}_{q}\right)$ as follows:

for $i=1,\ldots,\left\lfloor\frac{k}{2}\right\rfloor$, $j=2,\ldots,k$,
$i+j\leq k+1$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-3\right)m+p+q-1$;

for $i=2,\ldots,k-1$, $j=\left\lfloor\frac{k}{2}\right\rfloor+2,\ldots,k$,
$i+j\geq k+2$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j+k-5\right)m+p+q-1$;

for $i=3,\ldots,k$, $j=k+1,\dots,2k-2$, $j-i\leq k-2$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(k+j-i-2\right)m+p+q-1$;

for $i=1,\ldots,k-1$, $j=k+2,\ldots,2k$, $j-i\geq k+1$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(j-i-2\right)m+p+q-1$;

for $i=2,\ldots,1+\left\lfloor\frac{k-1}{2}\right\rfloor$,
$j=k+1,\dots,k+\left\lfloor\frac{k-1}{2}\right\rfloor$, $j-i=k-1$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(2i-3\right)m+p+q-1$;

for $i=\left\lfloor\frac{k-1}{2}\right\rfloor+2,\ldots,k$,
$j=k+1+\left\lfloor\frac{k-1}{2}\right\rfloor,\ldots,2k-1$, $j-i=k-1$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-4\right)m+p+q-1$;

for $i=k+1,\dots,k+\left\lfloor\frac{k}{2}\right\rfloor-1$,
$j=k+2,\ldots,2k-2$, $i+j\leq 3k-1$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-2k-1\right)m+p+q-1$;

for $i=k+1,\ldots,2k-1$,
$j=k+\left\lfloor\frac{k}{2}\right\rfloor+1,\dots,2k$, $i+j\geq 3k$, let

$\beta\left(v_{p}^{(i)}v_{q}^{(j)}\right)=\left(i+j-k-3\right)m+p+q-1$.

Let us prove that $\beta$ is an interval
$\left(\left(\frac{3}{2}k-1\right)n-1\right)$-coloring of the graph $G$.

First we show that for each $t\in\left[\left(\frac{3}{2}k-1\right)n-1\right]$,
there is an edge $e\in E(G)$ with $\beta(e)=t$.

Consider the vertices
$v_{1}^{(1)},\ldots,v_{m}^{(1)},v_{1}^{(2k)},\ldots,v_{m}^{(2k)}$. Now, by
Lemma 7 and the definition of $\beta$, for $1\leq j\leq m$,

$S\left(v_{j}^{(1)},\beta\right)=\bigcup_{l=1}^{2k-2}\left([j,j+m-1]\oplus(l-1)m\right)$
and
$S\left(v_{j}^{(2k)},\beta\right)=\bigcup_{l=k}^{3k-3}\left([j,j+m-1]\oplus(l-1)m\right)$.

Let $\tilde{C}$ and $\tilde{\tilde{C}}$ be the subsets of colors appear on
edges incident to the vertices $v_{1}^{(1)},\ldots,v_{m}^{(1)}$ and
$v_{1}^{(2k)},\ldots,v_{m}^{(2k)}$ in the coloring $\beta$, respectively, that
is:

$\tilde{C}=\bigcup_{j=1}^{m}S\left(v_{j}^{(1)},\beta\right)$ and
$\tilde{\tilde{C}}=\bigcup_{j=1}^{m}S\left(v_{j}^{(2k)},\beta\right)$.

It is straightforward to check that
$\tilde{C}\cup\tilde{\tilde{C}}=\left[\left(\frac{3}{2}k-1\right)n-1\right]$,
so for each $t\in\left[\left(\frac{3}{2}k-1\right)n-1\right]$, there is an
edge $e\in E(G)$ with $\beta(e)=t$.

Next we show that the edges incident to any vertex of $G$ are colored by
$(k-1)n$ consecutive colors.

Let $v_{j}^{(i)}\in V(G)$, where $1\leq i\leq 2k$, $1\leq j\leq m$.

Subcase 2.1. $1\leq i\leq 2$, $1\leq j\leq m$.

By Lemma 7 and the definition of $\beta$, we have

$S\left(v_{j}^{(1)},\beta\right)=S\left(v_{j}^{(2)},\beta\right)=\bigcup_{l=1}^{2k-2}\left([j,j+m-1]\oplus(l-1)m\right)=\left[j,j+(2k-2)m-1\right]$.

Subcase 2.2. $3\leq i\leq k$, $1\leq j\leq m$.

By Lemma 7 and the definition of $\beta$, we have

$S\left(v_{j}^{(i)},\beta\right)=\bigcup_{l=i-1}^{2k-4+i}\left([j,j+m-1]\oplus(l-1)m\right)=\left[j+(i-2)m,j+(2k-4+i)m-1\right]$.

Subcase 2.3. $k+1\leq i\leq 2k-2$, $1\leq j\leq m$.

By Lemma 7 and the definition of $\beta$, we have

$S\left(v_{j}^{(i)},\beta\right)=\bigcup_{l=i-k+1}^{k-2+i}\left([j,j+m-1]\oplus(l-1)m\right)=\left[j+(i-k)m,j+(k-2+i)m-1\right]$.

Subcase 2.4. $2k-1\leq i\leq 2k,1\leq j\leq m$.

By Lemma 7 and the definition of $\beta$, we have

$S\left(v_{j}^{(2k-1)},\beta\right)=S\left(v_{j}^{(2k)},\beta\right)=\bigcup_{l=k}^{3k-3}\left([j,j+m-1]\oplus(l-1)m\right)=\left[j+(k-1)m,j+(3k-3)m-1\right]$.

This shows that $\beta$ is an interval
$\left(\left(\frac{3}{2}k-1\right)n-1\right)$-coloring of $G$; thus
$W(G)\geq\left(\frac{3}{2}k-1\right)n-1$ for even $n\geq 2$. $\square$

From Theorems 3(1) and 8, and taking into account that a complete balanced
$k$-partite graph $G$ with $n$ vertices in each part is overfull when $nk$ is
odd, we have:

###### Corollary 9

If $G$ is a complete balanced $k$-partite graph with $n$ vertices in each
part, then $\chi^{\prime}(G)=(k-1)n$ if and only if $nk$ is even.

From Theorems 3(2) and 8, we have:

###### Corollary 10

Let $G$ be a complete balanced $k$-partite graph with $n$ vertices in each
part and $nk$ is even. If $(k-1)n\leq t\leq\left(\frac{3}{2}k-1\right)n-1$,
then $G$ has an interval $t$-coloring.

Also, note that the proof of the case 2 implies that if a graph $G$ with $n$
vertices is $(n-2)$-regular, then $\chi^{\prime}(G)=n-2$.

The next theorem improves the lower bound in Theorem 8 for complete balanced
$k$-partite graphs with even $k$.

###### Theorem 11

Let $G$ be a complete balanced $k$-partite graph with $n$ vertices in each
part. If $k=p2^{q}$, where $p$ is odd and $q\in\mathbb{N}$, then
$W(G)\geq(2k-p-q)n-1$.

  * Proof.

Let $V(G)=\left\\{v^{(i)}_{j}\colon\,1\leq i\leq k,1\leq j\leq n\right\\}$ and
$V(K_{k})=\\{u_{1},\ldots,u_{k}\\}$. Also, let
$E(G)=\left\\{v^{(i)}_{r}v^{(j)}_{s}\colon\,1\leq i<j\leq k,1\leq r\leq
n,1\leq s\leq n\right\\}$ and $E(K_{k})=\\{u_{i}u_{j}\colon\,1\leq i<j\leq
k\\}$.

Since $k=p2^{q}$, where $p$ is odd and $q\in\mathbb{N}$, by Theorem 6, there
exists an interval $(2k-1-p-q)$-coloring $\alpha$ of $K_{k}$. Now we define an
edge-coloring $\beta$ of the graph $G$.

For each edge $v^{(i)}_{r}v^{(j)}_{s}\in E(G)$ with $1\leq i<j\leq k$ and
$r=1,\ldots,n$, $s=1,\ldots,n$, define a color
$\beta\left(v^{(i)}_{r}v^{(j)}_{s}\right)$ as follows:

$\beta\left(v^{(i)}_{r}v^{(j)}_{s}\right)=\left(\alpha\left(u_{i}u_{j}\right)-1\right)n+r+s-1$.

By Lemma 7 and the definition of $\beta$, and taking into account that $\max
S\left(u_{i},\alpha\right)-\min S\left(u_{i},\alpha\right)=k-2$ for
$i=1,\ldots,k$, we have

$\displaystyle S\left(v_{j}^{(i)},\beta\right)$ $\displaystyle=$
$\displaystyle\bigcup_{l=\min S(u_{i},\alpha)}^{\max
S(u_{i},\alpha)}\left([j,j+n-1]\oplus(l-1)n\right)=$ $\displaystyle=$
$\displaystyle[j+\left(\min S(u_{i},\alpha)-1\right)n,j+\max
S(u_{i},\alpha)n-1]$

for $i=1,\ldots,k$ and $j=1,\ldots,n$, and

$\displaystyle\bigcup_{i=1}^{k}\bigcup_{j=1}^{n}S\left(v_{j}^{(i)},\beta\right)$
$\displaystyle=$ $\displaystyle[(2k-p-q)n-1].$

This shows that $\beta$ is an interval $((2k-p-q)n-1)$-coloring of the graph
$G$; thus $W(G)\geq(2k-p-q)n-1$. $\square$

From Theorems 3(2) and 11, we have:

###### Corollary 12

Let $G$ be a complete balanced $k$-partite graph with $n$ vertices in each
part and $k=p2^{q}$, where $p$ is odd and $q\in\mathbb{N}$. If $(k-1)n\leq
t\leq(2k-p-q)n-1$, then $G$ has an interval $t$-coloring.

##  3 Problems

In the previous section we obtained some results on interval colorings of
complete balanced multipartite graphs, but very small is known about interval
colorings of complete unbalanced multipartite graphs. In fact, there are only
two results on interval colorings of complete unbalanced multipartite graphs.
Let $n_{1}\leq\cdots\leq n_{k}$ be positive integers. The complete
multipartite graph $K_{n_{1},\ldots,n_{k}}$ is a complete $k$-partite graph
for which $|V_{i}|=n_{i}$, $i=1,\ldots,k$. The first result is Theorem 4 which
gives all possible values of the number of colors in interval colorings of
$K_{n_{1},n_{2}}$. The second result was obtained by Feng and Huang [6]. In
[6], they proved that the complete $3$-partite graph $K_{1,1,n}$ is interval
colorable if and only if $n$ is even. Now we would like to formulate some
problems on interval colorings of complete multipartite graphs:

###### Problem 1

Characterize all interval colorable complete multipartite graphs.

###### Problem 2

Find the exact values of $w(G)$ and $W(G)$ for interval colorable complete
multipartite graphs G.

###### Problem 3

Find the exact value of $W\left(K_{n,\ldots,n}\right)$ for interval colorable
complete balanced $k$-partite graphs $K_{n,\ldots,n}$.

Note that even a special case of Problem 3 is open: the problem of determining
the exact value of $W(K_{2n})$ for complete graph $K_{2n}$.

## References

  * [1] A.S. Asratian and R.R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math. 5 (1987), 25-34 (in Russian).
  * [2] A.S. Asratian and R.R. Kamalian, Investigation on interval edge-colorings of graphs, J. Combin. Theory Ser. B 62 (1994), 34-43.
  * [3] M.A. Axenovich, On interval colorings of planar graphs, Congr. Numer. 159 (2002), 77-94.
  * [4] M. Behzad, G. Chartrand and J. K. Cooper, Jr., The colour numbers of complete graphs, J. London Math. Soc. 42 (1967), 226-228.
  * [5] B.-L. Chen, H.-L. Fu and M. T. Ko, Total chromatic number and chromatic index of split graphs, J. Combin. Math. Combin. Comput. 17 (1995), 137-146.
  * [6] Y. Feng and Q. Huang, Consecutive edge-coloring of the generalized $\theta$-graph, Discrete Appl. Math. 155 (2007), 2321-2327.
  * [7] S. Fiorini, On the chromatic index of outerplanar graphs, J. Combin. Theory Ser. B 18 (1975), 35-38.
  * [8] K. Giaro, M. Kubale and M. Malafiejski, Consecutive colorings of the edges of general graphs, Discrete Math. 236 (2001), 131-143.
  * [9] D.G. Hoffman and C.A. Rodger, The chromatic index of complete multipartite graphs, J. Graph Theory 16 (1992), 159-163.
  * [10] R.R. Kamalian, Interval colorings of complete bipartite graphs and trees, preprint, Comp. Cen. of Acad. Sci. of Armenian SSR, Erevan, 1989 (in Russian).
  * [11] R.R. Kamalian, Interval edge colorings of graphs, Doctoral Thesis, Novosibirsk, 1990.
  * [12] R.R. Kamalian and P.A. Petrosyan, A note on interval edge-colorings of graphs, Math. Probl. of Comp. Sci. 36 (2012), 13-16.
  * [13] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math. Ann. 77 (1916), 453-465.
  * [14] R. Laskar and W. Hare, Chromatic numbers for certain graphs, J. London Math. Soc. (2), 4 (1972), 489-492.
  * [15] P.A. Petrosyan, Interval edge-colorings of complete graphs and $n$-dimensional cubes, Discrete Math. 310 (2010), 1580-1587.
  * [16] V.G. Vizing, On an estimate of the chromatic class of a $p$-graph, Diskret. Analiz 3 (1964), 25-30 (in Russian).
  * [17] V.G. Vizing, Critical graphs with a given chromatic class, Diskret. Analiz 5 (1965), 9-17 (in Russian).
  * [18] V.G. Vizing, The chromatic class of a multigraph, Kibernetika 3 (1965), 29-39 (in Russian).
  * [19] D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001.
  * [20] L. Zhang, Every planar graph with maximum degree 7 is of class 1, Graphs and Combin. 16 (2000), 467-495.