# Seven Principles for Rapid-Response Data Science: Lessons Learned from
Covid-19 Forecasting

Bin<EMAIL_ADDRESS>[ Chandan<EMAIL_ADDRESS>[
Bin Yu is Professor in the Statistics Department and EECS Deparment as the
University of California, Berkeley .  Chandan Singh is a PhD Candidate in the
EECS Deparment as the University of California, Berkeley .

###### Abstract

In this article, we take a step back to distill seven principles out of our
experience in the spring of 2020, when our 12-person rapid-response team used
skills of data science and beyond to help distribute 340,000+ units of Covid
PPE. This process included tapping into domain knowledge of epidemiology and
medical logistics chains, curating a relevant data repository, developing
models for short-term county-level death forecasting in the US, and building a
website for sharing visualization (an automated AI machine). The principles
are described in the context of working with Response4Life, a then-new
nonprofit organization, to illustrate their necessity. Many of these
principles overlap with those in standard data-science teams, but an emphasis
is put on dealing with problems that require rapid response, often resembling
agile software development. The technical work from this rapid response
project resulted in a paper [1]; see also this interview for more background
[8].

Coronavirus,

Forecasting,

County-level,

Data-science,

###### keywords:

and

##  1 The decision to engage: preparedness and willingness

It was the evening of Friday, March 20, 2020, when one of the authors (Yu) saw
an email from a colleague at Berkeley engineering asking for data-science help
for a new nonprofit organization called Response4Life that aimed to distribute
PPE (personal protection equipment) to Covid hot-spots in the US. At this
time, the burgeoning epidemic was taking hold in the US, and media outlets
were crowded by reports on the huge shortage of PPEs such as masks, even for
medical doctors and healthcare workers.

Within minutes, Yu replied to the email to get connected with Response4Life.
She also knew that her group, consisting of both statistics and EECS
students/postdocs, was well-prepared to jump on this opportunity; they
collectively held a research goal of solving real-world problems, possessed
the necessary statistics/machine learning and computing skills, and had a
collaborative culture in place, all tools necessary in order to move very fast
as a team. The group had good communication channels for resolving
differences, a fair credit-sharing habit, and all members were already working
together in overlapping teams of 2-5 people.

By Saturday, several group members had been contacted, including the other
author (Singh), a PhD student from computer science. All signed up without
hesitation for a warlike two-month engagement with Response4Life. Singh, a
super-organizer, also agreed to be the deputy for the project with PI Yu. In a
few days, a team of 12 formed from other group members who joined voluntarily:
Nick Altieri (who delayed finishing his thesis), James Duncan, Raaz Dwivedi,
Karl Kumbier (former group member), Xiao Li, Robert Netzorg, Briton Park, Yan
Shuo Tan, Tiffany Tang, and Yu (Hue) Wang.

After discussing with the Response4Life team, it became clear that this was a
very unusual data-science project, with no data in hand or plans on how to
find it. Forecasts were needed to inform which hot-spot hospitals to send PPE,
but this would require first finding relevant data, developing short-term
(e.g. 5 days ahead) forecasting models, and integrating forecasts into a
Response4Life Salesforce for use. As a matter of fact, Response4Life was
founded only a week before by Rick Brennan (founder of Airtime Aviation
Holdings, LLC, engineer / entrepreneur, pilot) with mostly rotating short-term
volunteers (e.g. with availability of two weeks). Don Landwirth (angel
investor, board member of Maker Nexus, advisor and mentor to dozens of
entrepreneurs and executives) was the lead on connecting with makers and the
Salesforce logistics platform.

##  2 Effective human organization: divide and conquer

Since time was running very short, it was crucial to efficiently split up
different aspects of the project amongst various people.

Specifically, the team had two short weeks to come up with daily forecasts, at
least 5 days ahead, for each of the 7000+ hospitals in the US and put them on
the Salesforce platform for PPE distribution. With a team of 12 people, we
naturally had to divide and conquer. Subteams were formed: a data team (Tang
and Wang), a modeling team (Altieri and Li), a logistics/visualization team
(Singh and Duncan) to transport our prediction results to the Salesforce
platform/website, and a PR team (Dwivedi, Netzorg, and Tan) to help organize
many volunteers to Response4Life, scout media reports to qualitatively
validate our predictions, and call hospitals to find out whether they would be
interested in receiving PPE.

The teams were orchestrated following principles similar to agile development
[2]. Short frequent large-group meetings were held to set goals for each team
and evaluate progress. These large meetings with the entire team’s input
helped to bridge the fast pace nature of the project with the more familiar
academic environment of critique and iteration. Google Docs was used as the
primary software to organize the teams, with each team having a prioritized
list of action items that were updated as goals evolved.

Our rapid-response team also met, first daily and later a couple of times a
week, as a team and sub-teams to plan and sync-up at a very fast pace. The
authors attended daily Response4Life meetings (Yu for the 8 am leadership team
meeting and Singh for the 3 pm logistics meeting). After a couple of weeks,
the meetings became less regular, but still multiple times a week.

##  3 Gathering data and context: scraping, human contacts, and media reports

Gathering data was an immediate challenge; it turned out that web scraping,
human contacts, and monitoring media reports were all a crucial part of
gathering data.

The first challenge was deciding which quantity to model. We quickly found
from media reports Covid-19 death-count data at the county level from USAFacts
(and later NYT), but very little other information at the county level. As a
result, we decided to predict death-counts for each county. We did not want to
predict case numbers believing that (accumulated) death counts were more
reliable and relevant to hospitalization than case numbers; this was
particularly true at the beginning of the pandemic when case numbers were not
uniformly reported.

Next, these county-level predictions were translated into an actionable
hospital-level severity index. At the time, hospital-level Covid-19
information was not available, so in order to impute hospital-level counts, we
searched for information on individual hospitals through open sources,
contacts and emails.

We then use the size of each hospital (measured by the total number of
employees), to impute the death count for the hospital from each county,
(relative to the total number of hospital employees in the county). Then we
combined features such as current (imputed) death counts, predicted (imputed)
death counts, and ICU beds to assign each hospital a severity index, taking on
values low, medium, and high.

Many other static relevant datasets with information on useful factors for
predicting Covid-19 mortality were also collected, such as demographics and
health risk factors. Later on, more diverse dynamic data was added, such as
social mobility data collected from many different sources such as Google and
Apple maps, mask-wearing survey data, and safegraph social-distancing data.
This list continued to grow throughout the evolution of the pandemic to
include data such as interventions that different counties/states made to
spread gatherings. We spoke to friends and colleagues who were practicing or
studying medical doctors and researchers to understand what factors (health,
social, economic) might impact death count in addition to past death counts.
Everyone we contacted was incredibly helpful.

##  4 Data quality control: in-house data cleaning and curation

Data quality control was critical for dealing with an influx of messy data. It
was important to vet the newly incoming data and set up a pipeline to easily
adapt to unexpected changes from incurring data sources.

The data team responded quickly to any lead from the team and contacts to
scrape, clean, and curate before depositing in our repository (details in
[1]). The dynamic data such as death and case counts were curated by different
sources which used different data collection protocols, requiring cleaning for
downstream tasks such as forecasting. To efficiently gather and preprocess the
data, the data team put an automatic scraping and cleaning procedure in place
after some trial-and-error days. This procedure required a large amount of
maintenance, as the incoming data from different sources would sometimes
change without warning (e.g. including previously-missed case counts or
changing the code interface required to gather data). Since the beginning of
the project, many Ph.D. students in Yu-group teams, as well as external
volunteers, helped with the data team in terms of finding useful datasets to
be added as well as cleaning the data. Eventually, two Ph.D. students kept on
maintaining the pipeline and adding new datasets. Their skills of setting up
periodic jobs on AWS EC2 instances, data cleaning via the Python Pandas
package, and web-scraping were very handy.

Though information was desired at the hospital level, most data was available
at different levels of granularity, e.g. death-counts at the county level and
testing data at the state level. Thus, human judgement calls were made on how
best to impute between the different levels of granularity; for example, as
mentioned earlier, county-level deaths were assigned to different hospitals
proportional to each hospital’s size.

##  5 Speedy development and validation of many prediction algorithms

After a quick examination of early death-counts, it became clear that standard
epidemiological models were not yet doing a precise job at forecasting county-
level Covid-19 deaths. As a result, we turned to data-driven methods for
forecasting, that would adapt to the data at hand. With a pressing time demand
and a rapidly evolving pandemic, we decided to build on past work of one
author that weighs and combines multiple prediction schemes (with a forgetting
factor) developed successfully for audio compression at Bell Labs 20 years ago
[4]. This is due to a recognition of the similar dynamic nature in audio and
pandemic data and the proven dynamic adaptivity of the weighted combination
strategy to good predictors.

We first began by developing five extremely simple models to use as baselines
for forecasting county-level deaths. For each county, these predictors used
the past time-series of death and case counts, along with the demographic,
social, economic, and health factors from the county and its neighboring
counties. In the end, trend-following, simple and transparent linear and
exponential predictors stood out in terms of prediction performance (under
three different reasonable loss functions) on future data (which arrives every
day for 3000+ counties). The best-predicting models used only past and
neighboring county-level Covid death-counts to forecast future death-counts.

To improve upon these simple baseline models, we combined and weighted them
(with a forgetting factor) to form the CLEP predictor in our paper [1], where
CLEP stands for Combined Linear and Exponential Predictor. The weight on each
predictor was higher if the predictor did a better job fitting recent data.
These weights predictors were interpretable because they corresponded well
with the linear regime or the exponential regime that the pandemic fell in.
That is, in a linear regime of the pandemic, the linear predictor received
more weight and vice versa.

The two members of the modeling team helped to implement different predictors
in parallel. Familiarity with data analysis and python modeling packages such
as scikit-learn [3], statsmodels [5], and imodels [6] helped to develop models
quickly and effectively.

##  6 Uncertainty: measurement and empirical validation

Facing a dynamic future, it was important to assess uncertainty through a
prediction interval with a justified level of confidence.

Prediction residuals are an obvious source to use for such an interval. We
used the prediction residuals of our model to defined maximum absolute error
prediction intervals for predicted death-counts [1]. Specifically, an interval
was constructed using the maximum absolute relative error to add and subtract
from the predicted (accumulated) death count of the future 5th (or 7th or
14th) day. This construction can be seen as a form of generalized conformal
analysis [7]. With a theoretical argument, we can see that the coverage of
such intervals is around 80%; this was more or less validated by comparing
with the observed (accumulated) death counts (see [1] for details).
Additionally, these intervals require that errors are exchangeable across
different days. We restrict our interval construction to only use the previous
five days; over this time period, the residuals empirically appeared
exchangeable.

These intervals around our predictions would help inform the time needed for
physical distribution of PPE from the makers (making sure the lower bound of
the interval was larger than the last observed accumulated death count). The
possibility of evaluating our predictions and intervals with ever coming new
data every day was really the silver lining in an extremely challenging
project and gave us empirically validated confidence in what we do.

##  7 Communicating results: interactive visualizations, open-source code, and
a web interface

Quickly and effectively communicating results was extremely important in our
rapid-response setting. We did this through a combination of open-source code
and visualizations put onto our website.

From the beginning, all our work was open-source on Github, making it easy for
other groups to use our code and processed data.111https://github.com/Yu-
Group/covid19-severity-prediction. Data was saved in both raw/processed form
and updated daily, allowing other groups to make use of any subset of the data
repository they found useful. All data was placed into a common table-format
which could then be easily distributed as a csv-file (or compressed table
formats). We also stored the daily-updated forecasts numerically on github,
making them easy to access and compare against.

Moreover, we built interactive visualizations of the data, along with our
forecasts, into a website using Github Pages222https://covidseverity.com/.
These visualizations enabled much better exploration of the data, especially
for specific counties and for comparing geographic areas. Basic web skills,
such as using HTML/Javascript were crucial for quickly setting up this
website, and adding basic elements to it. For actually producing the
visualizations, various python visualization libraries such as Matplotlib and
Plotly were useful, particularly their extensions for geographical-data
visualizing. Setting up compute on AWS allowed for easily automating daily
updates to these visualizations as well as for hosting interactive
visualizations which could not be simply uploaded to a static site. The
forecasts were also integrated into the Covid-19
Atlas333https://theuscovidatlas.org/ at the University of Chicago .

Three grades of severity (high, medium, and low) based on our 5-day
predictions were put on the Salesforce platform for PPE distribution within 18
days of our engagement, with non-stop long hours every day from core team
members and people at Response4Life. There were no other county-level
prediction models available in the US until after our paper was submitted on
May 16, 2020. At the present date, we have taken down the realtime updates due
to the availability of other county-level sites and our lack of sustainable
resources for maintaining the website to deal with changing incoming data
formats.

## Conclusion

To conclude, this project was an intense and rewarding experience for everyone
on our rapid-response data-science team, especially given the fact that our
predictions helped inform the shipment of at least 349,000 face shields to
doctors and healthcare workers (14,000 through Response4Life and the rest
through Maker Nexus), at a time when they were direly needed. It would not
have been possible without the wonderful Response4Life people, our combined
skills in applied statistics, machine learning, signal processing and coding,
and awesome and timely support from friends, family, and colleagues.

[Acknowledgments] Thanks to Tiffany Tang, Hue Wang, Nick Altieri and Xiao Li
for their helpful input to the paper, as well as two referees for their
constructive comments that improved the paper. Partial support of a grant from
The Center for Information Technology Research in the Interest of Society and
the Banatao Institute (CITRIS), University of California, is gratefully
acknowledged.

## References

  * [1] [author] Altieri, NickN., Barter, Rebecca LR. L., Duncan, JamesJ., Dwivedi, RaazR., Kumbier, KarlK., Li, XiaoX., Netzorg, RobertR., Park, BritonB., Singh, ChandanC., Tan, Yan ShuoY. S., Tang, TiffanyT., Wang, YuY., Zhang, ChaoC. and Yu, BinB. (2021). Curating a COVID-19 Data Repository and Forecasting County-Level Death Counts in the United States. Harvard Data Science Review. https://hdsr.mitpress.mit.edu/pub/p6isyf0g. 10.1162/99608f92.1d4e0dae
  * [2] [author] Cockburn, AlistairA. and Highsmith, JimJ. (2001). Agile software development, the people factor. Computer 34 131–133.
  * [3] [author] Pedregosa, FabianF., Varoquaux, GaëlG., Gramfort, AlexandreA., Michel, VincentV., Thirion, BertrandB., Grisel, OlivierO., Blondel, MathieuM., Prettenhofer, PeterP., Weiss, RonR., Dubourg, VincentV. et al. (2011). Scikit-learn: Machine learning in Python. the Journal of machine Learning research 12 2825–2830.
  * [4] [author] Schuller, Gerald DTG. D., Yu, BinB., Huang, DaweiD. and Edler, BerndB. (2002). Perceptual audio coding using adaptive pre-and post-filters and lossless compression. IEEE Transactions on Speech and Audio Processing 10 379–390.
  * [5] [author] Seabold, SkipperS. and Perktold, JosefJ. (2010). Statsmodels: Econometric and statistical modeling with python. In Proceedings of the 9th Python in Science Conference 57 61\. Austin, TX.
  * [6] [author] Singh, ChandanC., Nasseri, KeyanK., Tan, Yan ShuoY. S., Tang, TiffanyT. and Yu, BinB. (2021). imodels: a python package for fitting interpretable models. Journal of Open Source Software 6 3192\. 10.21105/joss.03192
  * [7] [author] Vovk, VladimirV., Gammerman, AlexA. and Shafer, GlennG. (2005). Algorithmic learning in a random world. Springer Science & Business Media.
  * [8] [author] Yu, BinB. and Meng, Xiao-LiX.-L. (2021). An Interview with Bin Yu. Harvard Data Science Review. https://hdsr.mitpress.mit.edu/pub/5pe5xcvb.


# Distinct eigenvalues of the Transposition graph

Elena V. Konstantinova<EMAIL_ADDRESS>Artem Kravchuk
<EMAIL_ADDRESS>Sobolev Institute of Mathematics, Ak. Koptyug av. 4,
Novosibirsk 630090, Russia  Novosibirsk State University, Pirogova str. 2,
Novosibirsk, 630090, Russia  Three Gorges Mathematical Research Center, China
Three Gorges University, 8 University Avenue, Yichang 443002, Hubei Province,
China

###### Abstract

Transposition graph $T_{n}$ is defined as a Cayley graph over the symmetric
group generated by all transpositions. It is known that all eigenvalues of
$T_{n}$ are integers. Moreover, zero is its eigenvalue for any $n\geqslant 4$.
But the exact distribution of the spectrum of the graph $T_{n}$ is unknown. In
this paper we prove that integers from the interval
$[-\frac{n-4}{2},\frac{n-4}{2}]$ lie in the spectrum of $T_{n}$ if $n\geqslant
19$.

###### keywords:

Transposition graph; integral graph; spectrum;

###### MSC:

[2010] 05C25, 05E10, 05E15

††journal: arXiv

##  1 Introduction

The Transposition graph $T_{n}$ is defined as a Cayley graph over the
symmetric group $\mathrm{Sym}_{n}$ generated by all transpositions. The graph
$T_{n},n\geqslant 2$, is a connected bipartite $\binom{n}{2}$-regular graph of
order $n!$ and diameter $(n-1)$ [6]. It is an edge–transitive graph but not
distance–regular, and hence not distance–transitive graph. It was shown in [7]
that the Transposition graph is integral which means that all eigenvalues of
its adjacency matrix are integers [4]. Since $T_{n}$ is bipartite then its
spectrum $Spec(T_{n})$ is symmetric with respect to zero, where the spectrum
of a graph is defined as a multiset of distinct eigenvalues together with
their multiplicities [1].

Let $G$ be a finite group with an identity element $1_{G}$, and $S$ be its
generating set. Then a Cayley graph $\Gamma=Cay(G,S)$ is called normal if its
generating set $S$ is closed under conjugation, i. e. $S$ is the union of
conjugacy classes of $G$. The following theorem enables to compute eigenvalues
for any normal Cayley graph $\Gamma$ in terms of complex character values of
$G$.

###### Theorem 1

[9, Theorem 1] Let $G$ be a finite group with $s$ conjugacy classes and let
$\\{\chi_{1},\chi_{2},\ldots\chi_{s}\\}$ be the set of all irreducible complex
characters of $G$. Then the eigenvalues $\lambda_{i},\ i=1,2,\ldots,s$, of any
normal Cayley graph $\Gamma=Cay(G,S)$ are given by the following expression:

$\lambda_{i}=\sum_{g\in S}\frac{\chi_{i}(g)}{\chi_{i}(1_{G})},$ (1)

It was shown in [5] that the conditions of Theorem 1 hold for the
Transposition graph $T_{n}=Cay(\mathrm{Sym}_{n},T)$, where $T$ is the set of
all transpositions. Moreover, the following useful expressions were obtained.

It is well-known fact (see [8]) that there is one-to-one correspondence
between the irreducible complex characters $\chi_{i}(g)$ and
$\chi_{i}(1_{G})$, $i=1,2,\ldots,p(n)$, of the symmetric group
$\mathrm{Sym}_{n}$ and the partitions of $n$, where $p(n)$ is the number of
partitions of $n$. Let a nonincreasing sequence $(n_{1},n_{2},\ldots,n_{k}),\
k\geqslant 1$, where $\sum_{j=1}^{k}n_{j}=n$, be the integer partition ${\bf
i}=(n_{1},\dots,n_{k})\vdash n$ of $n$ corresponding to an irreducible complex
character $\chi_{i}$. Then the following expression holds:

$\frac{\chi_{i}(\tau)}{\chi_{i}(I_{n})}=\sum_{j=1}^{k}\frac{n_{j}(n_{j}-2j+1)}{n(n-1)},$
(2)

where $\tau$ is a transposition and $I_{n}$ is the identity permutation. Since
the generating set $T$ of $T_{n}$ consists of $\frac{n(n-1)}{2}$
transpositions then equations (1) and (2) give an expression for an eigenvalue
$\lambda_{\bf i}$ corresponding to the partition ${\bf i}$:

$\lambda_{\bf i}=\sum_{j=1}^{k}\frac{n_{j}(n_{j}-2j+1)}{2}.$ (3)

This formula for the eigenvalue corresponding to ${\bf i}$ is precisely the
same as the normalized character on the sum of all transpositions found in [2,
Equation (4.1)] and is a simplified version of the character of a
transposition found in [3, Lemma 7].

The following result about the spectrum of the graph $T_{n}$ is known.

###### Theorem 2

[10, Theorem 2] For any integer $k\geqslant 0$, there exists $n(k)$ such that
for any $n\geqslant n(k)$ and any $m\in\\{0,\dots,k\\}$, $m\in Spec(T_{n})$.

In the proof of this theorem $n(k)$ is chosen as $n(k)=10k+4$. It follows that
all integers from the interval $[-\frac{n-4}{10},\frac{n-4}{10}]$ lie in the
spectrum of $T_{n}$.

In this paper we improve the above result by the following theorem.

###### Theorem 3

For $n\geqslant 19$, all integers from the segment
$[-\frac{n-4}{2},\frac{n-4}{2}]$ lie in the spectrum of $T_{n}$.

The paper is organized as follows. In Section 2 we give the proof of Theorem
3. This proof relies on a few technical lemmas proved in Section 3. The
summaries of the lemmas are collected in Table 1. These lemmas mainly use (3)
to show that the given partitions correspond to the desired eigenvalues.

##  2 Proof of Theorem 3

Since $T_{n}$ is bipartite it is sufficient to prove that all integers from
the segment $[0,\frac{n-4}{2}]$ lie in the spectrum of $T_{n}$. To prove this
statement, we divide the segment $[0,\frac{n-4}{2}]$ into subsegments
$S=\bigcup_{i}s_{i}$, and specific integer numbers $A=\\{a_{0},\dots,a_{k}\\}$
depending on the parity of $n$, where $S\cup A$ contains all integers of the
interval $[0,\frac{n-4}{2}]$, as follows:

$n$ | $S$ | $A$
---|---|---
$odd$ | $\\{[1,\frac{n-3}{4}],[\frac{n+3}{4},\frac{n-1}{2}]\\}$ | $\\{0,[\frac{n-3}{4}]+1\\}$
$even$ | $\\{[2,\frac{n-4}{4}],[\frac{n+2}{2},\frac{n-4}{2}]\\}$ | $\\{0,1,[\frac{n-3}{4}]+1\\}$

Next, we show that all integers from each $s\in S$ lie in the spectrum of
$T_{n}$. For each $s$, we find a family of partitions for which by (3) it is
shown that all the integers from $s$ are elements of the spectrum of $T_{n}$.
For each integer number $a\in A$, we find a particular partition for which by
(3) the eigenvalue $a\in Spec(T_{n})$ is obtained. Thus, we show that all
integers from the segment $[0,\frac{n-4}{2}]$ lie in the spectrum of $T_{n}$,
and since $T_{n}$ is an integral graph, there are no other eigenvalues in the
interval $[0,\frac{n-4}{2}]$.

To realise the strategy above, we prove a few technical lemmas. Summary of
these lemmas are presented in Table 1 which lists $s\in S$ and $a\in A$ in the
first column. Whenever a segment is listed this means that all integers from
the segment are in the spectrum of $T_{n}$. The second column lists the
specific partitions, or families of partitions, which correspond to a given
number or a given segment. The notation $(n_{1},\dots,k\times t,\dots,n_{k})$
means that number $k$ is repeated $t$ times. The specific eigenvalues (e.g.,
$0$) correspond to the specific partitions, and the segments (e.g.,
$[1,\frac{n-3}{4}]$) correspond to the families of partitions. If we choose an
arbitrary integer value $\lambda$ from the segment from the first column and
substitute it in the expression for the family of partitions from the second
column we obtain a partition corresponding to the eigenvalue $\lambda$ of
$T_{n}$. It is worth noting that some partitions may depend not only on the
parity of $n$ but also on the remainder of $n$ divided by 4.

For each family of partitions, we prove a specific lemma to show that this
family gives the corresponding eigenvalues. A reference to this proof is given
in the corresponding column of Table 1. Each lemma has its own restrictions on
the number $n$. These constraints are given in the last column of Table 1.

Each line of Table 1 can be taken as the result of a single technical lemma.
Some of the lemmas were proved in [10]. The remaining lemmas are proved in
Section 3. Since these proofs are almost identical and a little bit cumbersome
they are moved to a separate section so that the reader can refer to them if
necessary but this would not lead away from the main line of the proof.

Thus, all that remains is to choose the minimum value $n$ for which all the
lemmas hold. It is easy to see from Table 1 that all lemmas hold for
$n\geqslant 19$ since the maximum number for which one of the lemmas does not
hold is $n=18$, namely, Lemma 9.

$\square$

Eigenvalues, $\lambda$ | Partitions | Limitations | Proof
---|---|---|---
$\ \ \ \ \ 0$ | $\left(\frac{n+1}{2},1\times\frac{n-1}{2}\right)$ |  $n$ is odd, $n\geqslant 1$ |  [10], Lemma 3
$\left(\frac{n}{2},2,1\times\frac{n-4}{2}\right)$ |  $n$ is even, $n\geqslant 4$
$[1,\frac{n-3}{4}]$ | $(\frac{n-2\lambda+1}{2},\lambda+2,2\times(\lambda-1),1\times\frac{n-4\lambda-1}{2})$ |  $n$ is odd, $n\geqslant 7$ |  [10], Lemma 5
$1$ | $\left(\frac{n-6}{2},4,4,2,1\times\frac{n-14}{2}\right)$ |  $n$ is even, $n\geqslant 14$ |  [10], Lemma 4
$[2,\frac{n-4}{4}]$ | $(\frac{n-2\lambda}{2},\lambda+2,3,2\times(\lambda-2),1\times\frac{n-4\lambda-2}{2})$ |  $n$ is even, $n\geqslant 12$ | Lemma 4
$[\frac{n+3}{4},\frac{n-1}{2}]$ | $(\lambda+1,\frac{n+3-2\lambda}{2},2\times(\frac{n-1}{2}-\lambda),1\times(\frac{4\lambda-n-3}{2})$ |  $n$ is odd, $n\geqslant 5$ | Lemma 5
$[\frac{n+2}{2},\frac{n-4}{2}]$ | $(\lambda+1,\frac{n+2-2\lambda}{2},3,2\times(\frac{n-4}{2}-\lambda),1\times(\frac{4\lambda-n-2}{2})$ |  $n$ is even, $n\geqslant 10$ | Lemma 6
$[\frac{n-3}{4}]+1$ | $(\frac{n}{4},\frac{n}{4},5,4,2\times(\frac{n-20}{4}),1)$ | $n\equiv 0\ (mod\ 4),n\geqslant 20$ | Lemma 7
$(\frac{n+3}{4},\frac{n+3}{4},4,2\times(\frac{n-13}{4}),1)$ | $n\equiv 1\ (mod\ 4),n\geqslant 13$ | Lemma 8
$(\frac{n+2}{4},\frac{n-2}{4},5,4,2\times(\frac{n-22}{4}),1,1)$ | $n\equiv 2\ (mod\ 4),n\geqslant 22$ | Lemma 9
$(\frac{n+1}{4},\frac{n+1}{4},5,3,2\times(\frac{n-19}{4}),1)$ | $n\equiv 3\ (mod\ 4),n\geqslant 19$ | Lemma 10
Table 1:  Summary of the technical lemmas.

##  3 Technical lemmas

###### Lemma 1

[10, Lemma 5] If $n\geqslant 7$ is odd then the partition
$(\frac{n-2\lambda+1}{2},\lambda+2,2\times(\lambda-1),1\times\frac{n-4\lambda-1}{2})$
corresponds to the eigenvalue $\lambda\in\mathbb{N}$, where
$1\leqslant\lambda\leqslant\frac{n-3}{4}$.

###### Lemma 2

[10, Corollary of Lemma 3 and Lemma 4] If $n\geqslant 14$ then the eigenvalues
zero and one lies in the spectrum of $T_{n}$.

###### Lemma 3

If a partition $(n_{1},n_{2},2,n_{4},\dots,n_{k}),n_{2}\geqslant 3$,
corresponds to an eigenvalue $\lambda$ then the partition
$(n_{1},n_{2},3,n_{4},\dots,n_{k})$ corresponds to the eigenvalue $\lambda$
too.

Proof. The proof follows directly from (3).

$\square$

###### Lemma 4

If $n\geqslant 12$ is even then the partition
$(\frac{n-2\lambda}{2},\lambda+2,3,2\times(\lambda-2),1\times\frac{n-4\lambda-2}{2})$
corresponds to the eigenvalue $\lambda\in\mathbb{N}$, where
$2\leqslant\lambda\leqslant\frac{n-4}{4}$.

Proof. If $\lambda\geqslant 2$ then for each partition of odd $n$ from Lemma 1
let us replace two by three at the third position. By Lemma [3, this gives the
partition of $n+1$ which corresponds to the eigenvalue $\lambda$. It is easy
to see that this results in a partition
$(\frac{n-2\lambda}{2},\lambda+2,3,2\times(\lambda-2),1\times\frac{n-4\lambda-2}{2})$
for even $n$. This partition holds when
$2\leqslant\lambda\leqslant\frac{n-4}{4}$, and the last inequality is valid
for $n\geqslant 12$.

$\square$

###### Lemma 5

If $n\geqslant 5$ and $n$ is odd then the partition
$(\lambda+1,\frac{n+3-2\lambda}{2},2\times(\frac{n-1}{2}-\lambda),1\times(\frac{4\lambda-n-3}{2}))$
corresponds to the eigenvalue $\lambda\in\mathbb{N}$, where
$\frac{n+3}{4}\leqslant\lambda\leqslant\frac{n-1}{2}$.

Proof. By (3) we have:

$\lambda_{\left(\lambda+1,\frac{n+3-2\lambda}{2},2\times(\frac{n-1}{2}-\lambda),1\times(\frac{4\lambda-n-3}{2})\right)}=$
$=\underbrace{\frac{1}{2}\lambda(\lambda+1)}_{(1)}+\underbrace{\frac{1}{2}\left(\frac{n+3-2\lambda}{2}\right)\left(\frac{n+3-2\lambda}{2}-3\right)}_{(2)}+$
$+\underbrace{\frac{1}{2}\sum\limits_{j=3}^{2+\frac{n-1}{2}-\lambda}2(2-2j+1)}_{(3)}+\underbrace{\frac{1}{2}\sum\limits_{j=3+\frac{n-1}{2}-\lambda}^{\lambda}1(1-2j+1)}_{(4)},$

where after calculations we obtain:

  1. (1)

= $\frac{1}{2}\cdot(\lambda^{2}+\lambda);$

  2. (2)

= $\frac{1}{8}\cdot(n^{2}+4\lambda^{2}-4n\lambda-12\lambda-9);$

  3. (3)

= $\frac{1}{4}\cdot(-n^{2}-4\lambda^{2}+4n\lambda-2n+4\lambda+3);$

  4. (4)

= $\frac{1}{8}\cdot(n^{2}-4n\lambda+4n-4\lambda+3).$

Finally, putting all the members of the expression together we have:

$\frac{1}{2}(\lambda^{2}+\lambda)+\frac{1}{8}(n^{2}+4\lambda^{2}-4n\lambda-12\lambda-9)+$
$+\frac{1}{4}(-n^{2}-4\lambda^{2}+4n\lambda-2n+4\lambda+3)+\frac{1}{8}(n^{2}-4n\lambda+4n-4\lambda+3)=\lambda.$

It is easy to see that this partition holds when
$\frac{n+3}{4}\leqslant\lambda\leqslant\frac{n-1}{2}$. In addition to the
limitations on $\lambda$ there is a limitation on $n$ obtained by substituting
$\lambda=\frac{n+3}{4}$ into the expression for partition which gives
$n\geqslant 5$ and completes the proof.

$\square$

###### Lemma 6

If $n\geqslant 10$ and $n$ is even then the partition
$(\lambda+1,\frac{n+2-2\lambda}{2},3,2\times(\frac{n-4}{2}-\lambda),1\times(\frac{4\lambda-n-2}{2})$
corresponds to the eigenvalue $\lambda\in\mathbb{N}$, where
$\frac{n+2}{4}\leqslant\lambda\leqslant\frac{n-4}{2}$.

Proof. From (3) we have:

$\lambda_{\left(\lambda+1,\frac{n+2-2\lambda}{2},3,2\times(\frac{n-4}{2}-\lambda),1\times(\frac{4\lambda-n-2}{2})\right)}=$

$=\underbrace{\frac{1}{2}\lambda(\lambda+1)}_{(1)}+\underbrace{\frac{1}{2}\left(\frac{n+2-2\lambda}{2}\right)\left(\frac{n+2-2\lambda}{2}-3\right)}_{(2)}+\underbrace{\frac{1}{2}3(3-6+1))}_{(3)}+$

$+\underbrace{\frac{1}{2}\sum\limits_{j=4}^{3+\frac{n-4}{2}-\lambda}2(2-2j+1)}_{(4)}+\underbrace{\frac{1}{2}\sum\limits_{j=4+\frac{n-4}{2}-\lambda}^{\lambda}(1-2j+1)}_{(5)}.$

Hence, after calculations we get:

  1. (1)

= $\frac{1}{2}\cdot(\lambda^{2}+\lambda);$

  2. (2)

= $\frac{1}{8}\cdot(n^{2}+4\lambda^{2}-4n\lambda-2n+4\lambda-8);$

  3. (3)

= $-3;$

  4. (4)

= $\frac{1}{4}\cdot(-n^{2}-4\lambda^{2}+4n\lambda+16);$

  5. (5)

= $\frac{1}{8}\cdot(n^{2}-4n\lambda+2n),$

and finally we obtain:

$\frac{1}{2}\cdot(\lambda^{2}+\lambda)+\frac{1}{8}\cdot(n^{2}+4\lambda^{2}-4n\lambda-2n+4\lambda-8)-3+$
$+\frac{1}{4}\cdot(-n^{2}-4\lambda^{2}+4n\lambda+16)+\frac{1}{8}\cdot(n^{2}-4n\lambda+2n)=\lambda.$

It is easy to see that this partition holds for any integer
$\lambda\in[\frac{n+2}{4},\frac{n-4}{2}]$. Moreover, by substituting
$\lambda=\frac{n+2}{4}$ into the partition we get $n\geqslant 10$. $\square$

###### Lemma 7

If $n\geqslant 20$ and $n\equiv 0\ ({\rm mod}\ 4)$ then the partition
$(\frac{n}{4},\frac{n}{4},5,4,2\times(\frac{n-20}{4}),1)$ corresponds to the
eigenvalue $[\frac{n-3}{4}]+1$.

Proof. Note that if $n\equiv 0\ ({\rm mod}\ 4)$ then
$[\frac{n-3}{4}]+1=\frac{n}{4}$. Substituting the partition into (3) we
immediately have:

$\lambda_{\left(\frac{n}{4},\frac{n}{4},5,4,2\times(\frac{n-20}{4}),1\right)}=$

$=\underbrace{\frac{1}{2}\frac{n}{4}\left(\frac{n}{4}-2+1\right)}_{(1)}+\underbrace{\frac{1}{2}\frac{n}{4}\left(\frac{n}{4}-4+1\right)}_{(2)}+\underbrace{\frac{1}{2}5\left(5-6+1\right)}_{(3)}+$

$+\underbrace{\frac{1}{2}4\left(4-8+1\right)}_{(4)}+\underbrace{\frac{1}{2}\sum\limits_{j=4}^{j=3+\frac{n-20}{4}}2(2-j+1)}_{(5)}+\underbrace{\frac{1}{2}\left(1-(5+\frac{n-20}{4})+1\right)}_{(6)},$

where each of the terms after calculations is given as follows:

  1. (1)

= $\frac{1}{32}\cdot(n^{2}-4n);$

  2. (2)

= $\frac{1}{32}\cdot(n^{2}-12n);$

  3. (3)

= $0;$

  4. (4)

= $-6;$

  5. (5)

= $\frac{1}{16}\cdot(-n^{2}+16n+80);$

  6. (6)

= $\frac{1}{4}\cdot(4-n),$

and finally we have:

$\frac{1}{32}(n^{2}-4n)+\frac{1}{32}(n^{2}-12n)-6+\frac{1}{16}(-n^{2}+16n+80)+\frac{1}{4}(4-n)=\frac{n}{4}$

with holding the partition for $n\geqslant 20$. $\square$

###### Lemma 8

If $n\geqslant 13$ and $n\equiv 1\ ({\rm mod}\ 4)$ then the partition
$(\frac{n+3}{4},\frac{n+3}{4},4,2\times(\frac{n-13}{4}),1)$ corresponds to the
eigenvalue $[\frac{n-3}{4}]+1$.

Proof. It is easy to see that if $n\equiv 1\ ({\rm mod}\ 4)$ then
$[\frac{n-3}{4}]+1=\frac{n-1}{4}$. A direct substitution of the partition into
(3) leads to the following expression:

$\lambda_{\left(\frac{n+3}{4},\frac{n+3}{4},4,2\times(\frac{n-13}{4}),1\right)}=$

$=\underbrace{\frac{1}{2}\left(\frac{n+3}{4}\right)\left(\frac{n+3}{4}-2+1\right)}_{(1)}+\underbrace{\frac{1}{2}\left(\frac{n+3}{4}\right)\left(\frac{n+3}{4}-4+1\right)}_{(2)}+$

$+\underbrace{\frac{1}{2}\left(4-6+1\right)}_{(3)}+\underbrace{\frac{1}{2}\sum\limits_{j=4}^{j+\frac{n-13}{4}}2(2-2j+1)}_{(4)}+\underbrace{\frac{1}{2}\left(1-2\frac{n+3}{4}+1\right)}_{(5)}.$

Further calculations give the terms $(1)=\frac{1}{32}\cdot(n^{2}+2n-3)$;
$(2)=\frac{1}{32}\cdot(n^{2}-6n-27)$; $(3)=-2$;
$(4)=-\frac{1}{16}\cdot(n^{2}-10n-39)$; and $(5)=\frac{1}{4}\cdot(1-n),$ whose
summation leads to the desired eigenvalue $\frac{n-1}{4}$. The only thing left
to notice is that the partition holds for any $n\geqslant 13$. $\square$

###### Lemma 9

If $n\geqslant 22$ and $n\equiv 2\ ({\rm mod}\ 4)$ then the partition
$(\frac{n+2}{4},\frac{n-2}{4},5,4,2\times(\frac{n-22}{4}),1,1)$ corresponds to
the eigenvalue $[\frac{n-3}{4}]+1$.

Proof. It is clear that if $n\equiv 2\ ({\rm mod}\ 4)$ then
$[\frac{n-3}{4}]+1=\frac{n-2}{4}$. By a direct substitution of the partition
into (3), we immediately have:

$\lambda_{\left(\frac{n+2}{4},\frac{n-2}{4},5,4,2\times(\frac{n-22}{4}),1,1\right)}=$

$=\underbrace{\frac{1}{2}\left(\frac{n+2}{4}\right)\left(\frac{n+2}{4}-2+1\right)}_{(1)}+\underbrace{\frac{1}{2}\left(\frac{n-2}{4}\right)\left(\frac{n-2}{4}-4+1\right)}_{(2)}+$

$\underbrace{\frac{1}{2}5\left(5-6+1\right)}_{(3)}+\underbrace{\frac{1}{2}4\left(4-8+1\right)}_{4)}+\underbrace{\frac{1}{2}\sum\limits_{j=4}^{j+\frac{n-22}{4}}2(2-2j+1)}_{(5)}+$

$+\underbrace{\frac{1}{2}\left(1-2\frac{n-2}{4}+1\right)}_{(6)}+\underbrace{\frac{1}{2}\left(1-2\frac{n+2}{4}+1\right)}_{(7)},$

whose terms after calculations are given by $(1)=\frac{1}{32}\cdot(n^{2}-4)$;
$(2)=\frac{1}{32}\cdot(n^{2}-16n+28)$; $(3)=0$; $(4)=-6$;
$(5)=-\frac{1}{16}\cdot(n^{2}-20n-44)$; $(6)=\frac{1}{4}\cdot(6-n)$; and
$(7)=\frac{1}{4}\cdot(2-n)$, and after summation we have:

$\frac{1}{32}(n^{2}-4)+\frac{1}{32}(n^{2}-16n+28)-6-\frac{1}{16}(n^{2}-20n-44)+\frac{1}{4}(6-n)+\frac{1}{4}(2-n)=\frac{n-2}{4}.$

In this case the partition holds for $n\geqslant 22$. $\square$

###### Lemma 10

If $n\geqslant 19$ and $n\equiv 3\ ({\rm mod}\ 4)$ then the partition
$(\frac{n+1}{4},\frac{n+1}{4},5,3,2\times(\frac{n-19}{4}),1)$ corresponds to
the eigenvalue $[\frac{n-3}{4}]+1$.

Proof. It is obvious that if $n\equiv 3\ ({\rm mod}\ 4)$ then
$[\frac{n-3}{4}]+1=\frac{n+1}{4}$. Using (3) we have:

$\lambda_{\left(\frac{n+1}{4},\frac{n+1}{4},5,3,2\times(\frac{n-19}{4}),1\right)}=$

$=\underbrace{\frac{1}{2}\left(\frac{n+1}{4}\right)\left(\frac{n+1}{4}-2+1\right)}_{(1)}+\underbrace{\frac{1}{2}\left(\frac{n+1}{4}\right)\left(\frac{n+1}{4}-4+1\right)}_{(2)}+\underbrace{\frac{1}{2}5\left(5-6+1\right)}_{(3)}+$

$+\underbrace{\frac{1}{2}3\left(3-8+1\right)}_{(4)}+\underbrace{\frac{1}{2}\sum\limits_{j=5}^{5+\frac{n-19}{4}}2(2-2j+1)}_{(5)}+\underbrace{\frac{1}{2}\left(1-2\frac{n+1}{4}+1\right)}_{(6)}$

with reduction to the following terms: $(1)=\frac{1}{32}\cdot(n^{2}-2n-3)$;
$(2)=\frac{1}{32}\cdot(n^{2}-10n-11)$; $(3)=0$; $(4)=-6$;
$(5)=-\frac{1}{16}\cdot(n^{2}-14n-95)$; and $(6)=\frac{1}{4}\cdot(3-n),$ whose
summation gives $\frac{n+1}{4}$, and the partition holds for $n\geqslant 19$.
$\square$

##  4 Discussions and further research

In this paper we have shown that all integers from the interval
$[-\frac{n-4}{2},\frac{n-4}{2}]$ belong to the spectrum of $T_{n}$ improving
the bounds $[-\frac{n-4}{10},\frac{n-4}{10}]$ obtained in [10]. However, the
full description of the spectrum is still unknown.

Our main goal in future research is to give the most complete description of
the spectrum of $T_{n}$ for large values of $n$. We are sure that the segment
$[-\frac{n-4}{2},\frac{n-4}{2}]$ is not the best estimate and that this
estimate can be improved by some larger segment $I(n)$ represented as follows:

$I(n)=s_{0}\cup(\cup_{k=1}^{l}s_{k})\cup\\{a_{1},\dots,a_{m}\\},$

where $s_{0}$ and $s_{1}$ are the segments considered in the proof of Theorem
3. For example, $s_{0}=[1,\frac{n-3}{4}]$ and
$s_{1}=[\frac{n+3}{4},\frac{n-1}{2}]$ if $n$ is odd. Hence, for segments
$\cup_{k=1}^{l}s_{k}$ there should be a more general description of partitions
like this:

$p(n,k,\lambda)=(n_{1}(n,k,\lambda),n_{2}(n,k,\lambda),\dots,n_{r}(n,k,\lambda)).$

It would clearly follow from such a representation that all eigenvalues from
the set $\cup_{k=1}^{l}s_{k}$ belong to the spectrum of the Transposition
graph $T_{n}$. We distinguish the segment $s_{0}$ among the other segments
since its partition has the first part depending on $\lambda$ and $n$ though
we assume the existence of a representation $p(n,k,\lambda)$ whose the first
part does not depend on $n$, i. e. $n_{1}(n,k,\lambda)=n_{1}(k,\lambda)$.

## Acknowledgements

The study by Elena V. Konstantinova was performed according to the Government
research assignment for IM SB RAS, project FWNF-2022-0017. The work of Artem
Kravchuk was supported by the Mathematical Center in Akademgorodok, under
agreement No. 075-15-2022-281 with the Ministry of Science and High Education
of the Russian Federation.

## References

  * [1] A. E. Brouwer, W. H. Haemers, _Spectra of Graphs_ , Springer, New York, 2012.
  * [2] F. Cesi, On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions, _Journal of Algebraic Combinatorics_ , 32 (2010) 155–185. https://doi.org/10.1007/s10801-009-0208-x
  * [3] P. Diaconis; M. Shahshahani, Generating a random permutation with random transpositions. _Z. Wahrsch. Verw. Gebiete_ , 57 (2) (1981) 159–179. https://doi.org/10.1007/BF00535487
  * [4] F. Harary, A. J. Schwenk, Which graphs have integral spectra? In: R. A. Bari, F. Haray (Eds.), _Graphs and Combinatorics_ , Lecture Notes in Mathematics, Vol. 406. Springer, Berlin, Heidelberg, 1974, pp. 45–51. https://doi.org/10.1007/BFb0066434
  * [5] K. Kalpakis, Y. Yesha, On the bisection Width of the Transposition network, _Networks_ , 29 (1997) 69–76.
  * [6] E. V. Konstantinova, Some problems on Cayley graphs, _Linear Algebra and its Applications_ , 429 (11-12) (2008) 2754-2769, https://doi.org/10.1016/j.laa.2008.05.010
  * [7] E. V. Konstantinova, D. V. Lytkina, Integral Cayley graphs over finite groups, _Algebra Colloquium_ , 27(1) (2020) 131–136, https://doi.org/10.1142/S1005386720000115
  * [8] B. Sagan, _The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions_ , Springer, New York, second edition, 2001.
  * [9] P.-H. Zieschang, Cayley graphs of finite groups, _Journal of Algebra_ , 118 (1988) 447–454. https://doi.org/10.1016/0021-8693(88)90033-6
  * [10] Elena V. Konstantinova, Artem Kravchuk, Spectrum of the Transposition graph, _Linear Algebra and its Applications_ , 654 (2022) (379-389). https://doi.org/10.1016/j.laa.2022.08.033