zhou]Institute of Cyber-Systems and Control, College of Control Science and
Engineering, Zhejiang University, Hangzhou, 310027, China pan]Institute of
Cyber-Systems and Control, College of Control Science and Engineering,
Zhejiang University, Hangzhou, 310027, China

# Spectrum Attention Mechanism for Time Series Classification

Shibo Zhouzhou  Yu Panpan

###### Abstract

Time series classification(TSC) has always been an important and challenging
research task. With the wide application of deep learning, more and more
researchers use deep learning models to solve TSC problems. Since time series
always contains a lot of noise, which has a negative impact on network
training, people usually filter the original data before training the network.
The existing schemes are to treat the filtering and training as two stages,
and the design of the filter requires expert experience, which increases the
design difficulty of the algorithm and is not universal. We note that the
essence of filtering is to filter out the insignificant frequency components
and highlight the important ones, which is similar to the attention mechanism.
In this paper, we propose an attention mechanism that acts on spectrum (SAM).
The network can assign appropriate weights to each frequency component to
achieve adaptive filtering. We use L1 regularization to further enhance the
frequency screening capability of SAM. We also propose a segmented-SAM (SSAM)
to avoid the loss of time domain information caused by using the spectrum of
the whole sequence. In which, a tumbling window is introduced to segment the
original data. Then SAM is applied to each segment to generate new features.
We propose a heuristic strategy to search for the appropriate number of
segments. Experimental results show that SSAM can produce better feature
representations, make the network converge faster, and improve the robustness
and classification accuracy.

###### keywords:

time series classfication, spectrum attention mechanism, deep learning,
adaptive filtering

00footnotetext: This work was supported by the National Key R&D Program of
China under Grant 2018YFB1700100.

##  1 Introduction

Time series are real-valued ordered data with the characteristics of large
data volume, high dimensionality, and high noise. The traditional TSC
algorithm requires manual feature extraction, which is complicated and not
universal[1]. With the wide application of deep learning in computer vision,
natural language processing, recommendation system, etc.[2, 3, 4], more and
more researchers use deep learning to solve TSC problems. Deep learning based
TSC model do not require manual design of features, the network can
automatically learn the internal patterns of data through training. Typical
TSC models include FCN[5], MCNN[6], InceptionTime[7], etc. However, time
series usually contain a lot of noise, which has a negative impact on the
training of the model. Before applying the algorithm, people generally filter
the original data to improve the feature representation. The existing schemes
are to treat the filtering and classifying as two stages. For example, the
effective frequency spectrum of EMG signal ranges from 0 to 4hz, digital
filters are generally applied to filter out high-frequency noise in the data
preprocessing stage[8]. For EEG and MEG time series, a high-pass filter is
generally used to remove slow drifts[9]. In the field of remote sensing
images, people usually apply the fourier smoothing algorithm to the original
normalized difference vegetation index time series (NVDI-TS) to improve the
classification accuracy[10]. In all the above cases, the filter design
requires expert experience, which undoubtedly increases the difficulty of
algorithm design.

In this paper, we propose a spectrum attention mechanism (SAM) that is
compatible with the deep learning model. It is embedded in the first layer of
the network, and the mask vector is updated through training, so as to achieve
adaptive filtering of the original data and generate the features that is more
conducive to network training. We validate the effectiveness of the scheme
through experiments on synthetic datasets and real datasets.

The paper is organized as follows: In Section 2, the problem formulation and
our methods are presented. Section 3 presents the experiments and results.
Finally, Section 4 provides the main conclusions of the paper.

##  2 Methodology

###  2.1 Frequency Domain Filtering

Our goal is to design an adaptive filtering module that is compatible with the
deep learning models, which can generate a feature representation that is more
conducive to network training. We notice that the common point of existing
schemes is the use of frequency domain filtering. That is, the frequency
domain transformation of the original data is carried out to get the spectrum,
and then the specific frequency components are filtered out according to
specific scenes. This process can be described by the formula (1).

$x_{{filtered}}^{n}=\mathcal{F}^{-1}\left(f\left(\mathcal{F}\left(x^{n}\right),{mask}\right)\right)$
(1)

Where $\mathcal{F}$ denotes the frequency domain transformation, $mask$ is a
vector of the same dimension as the input data, and $f$ represents the
operation on the spectrum, which is generally a dot product.

We should preserve the important frequency components in the spectrum and
remove the unimportant components, so the key to the problem is how to
determine a suitable mask.

###  2.2 Discrete Cosine Transformation

We use the Discrete Cosine Transform (DCT) to transform the raw data into the
frequency domain. DCT is a Fourier-related transform similar to the discrete
Fourier transform (DFT), but uses only cosine basis. DCT for a time series $X$
of length $N$ is defined as formula (2) and (3).

$\displaystyle X[k]=\sum_{n=0}^{N-1}a(k)x[n]cos\left(\frac{(2n+1)\pi
k}{2N}\right)$ (2)

$\displaystyle X[k]=\sum_{n=0}^{N-1}a(n)x[n]cos\left(\frac{(2k+1)\pi
n}{2N}\right)$ (3)

where $a(u)=\left\\{\begin{array}[]{l}\sqrt{\frac{1}{N}},u=0\\\
\sqrt{\frac{2}{N}},u=1,2,\cdots,N-1\end{array}\right.$

We choose to use DCT because it has the following advantages compared with
DFT:

  * •

DCT coefficients are real numbers as opposed to the DFT complex coefficients,
which is more suitable for gradient descent.

  * •

DCT can handle signals with trends well, while DFT suffers from the problem of
”frequency leakage” when representing simple trends.

  * •

When the successive values are highly correlated, DCT achieves better energy
concentration than DFT.

###  2.3 Spectrum Attention mechanism (SAM)

In cognitive science, due to the bottleneck of information processing
capabilities, humans selectively focus on part of the information while
ignoring the rest of the visible information. This is usually called the
attention mechanism[11]. Since frequency domain filtering is to remove
unimportant frequency components and retain or strengthen important
components, this is the same idea as the attention mechanism.

Figure 1: Spectral Attention Mechanism

We design an attention mechanism that acts on the spectrum (see Fig. 1). It
contains trainable parameters $mask$ of the same dimension as the input
signal, representing the weight of each frequency component, and the initial
value is 1. The weights are updated through training, so as to realize
adaptive filtering and generate better features. The forward propagation of
this layer is summarized in Algorithm 1.

Algorithm 1 Spectral Attention Mechanism(SAM)

Input: Univariate time series ${{x}^{n}}$
Output: $x_{filtered}^{n}$
Initialization: All-ones learnable array $mask^{n}$

1:# Transform the input series into spectral domain $s{{p}^{n}}\leftarrow
DCT({{x}^{n}})$

2:# Element-wise multiply $spectrum$ by $mask$ $masked\\_s{{p}^{n}}\leftarrow
s{{p}^{n}}\cdot mas{{k}^{n}}$

3:# Transform the $spectrum$ back into the time domain
${{x}_{filtered}}\leftarrow IDCT(masked\\_s{{p}^{n}})$

Figure 2: Three time series (left) and their corresponding spectrum (right).

SAM uses the spectrum of the entire sequence, which cannot reflect the phase
information of the original signal. As shown in Fig. 2, although the three
time series have great differences in the time domain, their spectrum is very
similar. This is because they contain the same frequency components, only the
phase of each frequency component is different. Therefore, SAM has inherent
defects in processing non-stationary signals. However, almost all signals are
non-stationary in real world. In order to retain part of the valuable phase
information, we use a tumbling window to divide the original sequence into $K$
segments of equal length, and apply SAM to each segment. The SAM output of
each segment is concatenated on the channel dimension as output features. The
main algorithm is summarized in Algorithm 2.

Algorithm 2 Segmented SAM (SSAM)

Input: ${{x}^{n}}$, number of segments $K$
Output: generated features $x_{new}^{T\times K}$

1:$T\leftarrow n//K$ # Initialize length of each segment

2:${{x}_{new}}\leftarrow zeros(T,K)$ # Initialize ${{x}_{new}}$

3:for i = 1 to $K$ do

4: # Get the ${{i}^{th}}$ segment $cur\leftarrow x[(i-1)*T:i*T]$

5: # Apply SAM to the ${{i}^{th}}$ segment $cur\\_output\leftarrow SAM(cur)$

6: # Update output ${{x}_{new}}[:,i]\leftarrow cur\\_output$

7:end for

Algorithm 3 Searching for the best number of segments

Input: training dataset, validation dataset
Output: ${K}_{best}$

1:$min\\_loss\leftarrow Inf$

2:${{K}_{best}}\leftarrow None$

3:for K = 1 to 8 do

4: Train network for 5 epochs

5: Calculate the validation loss

6: if validation loss $<$ min_loss then

7: ${{K}_{best}}\leftarrow K$

8: $min\\_loss\leftarrow validation\\_loss$

9: end if

10:end for

Since $K$ is a hyperparameter, which difficult to determine directly. We
design a heuristic search method, as shown in algorithm 3. The candidate range
of $K$ is set to 1 to 10, that is, the original data is divided into 10
segments at most. Take each $K$ value, train the model for 5 epochs, and apply
the $K$ corresponding to the minimum validation loss to the final model.

###  2.4 Architecture

Figure 3: The model architecture of SSAM-CNN.

In order to avoid the strong fitting ability of complex models to cover up the
performance of SSAM, wo present a relatively simple model. We first define the
convolution block, which consists of one-dimensional convolutional layer,
batch normalization layer[12], and activation layer. The basic convolution
block is:

$\begin{array}[]{l}y=\omega\otimes x+b\\\ s=BN(y)\\\ h={relu}(s)\end{array}$
(4)

$\otimes$ is the convolution operator. Our model is shown in Figure 3. First,
the raw data is input to SSAM for filtering to generate features more suitable
for network training. Then input into two convolution blocks to extract
features. The kernel size is {8,5}, and the channel dimension is {32,8}. After
the convolution blocks, the features are fed into a global average pooling
layer[13] instead of a fully connected layer, which largely reduces the number
of weights. The final label is produced by a softmax layer.

##  3 Experiment

In this section, experiments will be conducted on a synthetic dataset and four
widely used real datasets from UCR archive[14]. It should be noted that our
goal is to verify the effectiveness and universality of the design, so we did
not perform an overly detailed search on the hyperparameters of the model.

###  3.1 Data

Synthetic: To better understand the relationship between model performance and
the characteristics of the data, we define 3 classes: $C1$, $C2$, and $C3$ and
generate 2000 series from each as follows:

$x_{t}=\cos\left(\frac{2\pi t}{100}\right)+cos\left(\frac{2\pi
5t}{100}\right)+\omega_{t}\text{ for }x_{t}\in C_{1}$ (5)
$x_{t}=\cos\left(\frac{2\pi t}{100}\right)+cos\left(\frac{2\pi
20t}{100}\right)+\omega_{t}\text{ for }x_{t}\in C_{2}$ (6)
$x_{t}=\cos\left(\frac{2\pi t}{100}\right)+cos\left(\frac{2\pi
80t}{100}\right)+\omega_{t}\text{ for }x_{t}\in C_{3}$ (7)

where $t=1,..,100$,and $\omega_{t}$ is a gaussian noise with standard
deviation $\sigma=2$.

The most dominant frequencies for $C_{1}$ are 1 and 5, while for $C_{2}$ are 1
and 20, while for $C_{3}$ are 1 and 80. Due to the influence of noise, the
series from the three classes look similar in the time domain.
CBF: This is a shape classification datasets which contains three classes:
Cylinder, Bell and Funnel.
Control Charts (CC) : This dataset is derived from the control chart, which
contains six different control modes: normal, cyclic, increasing trend,
decreasing trend, upward shift and downward shift.
Face: This dataset originates from a face recognition problem. It consists of
four different individuals, making different facial expressions. The task is
to identify the person based on the head profile, which is represented as
“pseudo time series”.
Trace: This dataset records instrument data from a nuclear power plant for
fault detection.

The details of each dataset is summarized in Table 1.

Table 1: The characteristics of each dataset Datasets | Classes | Instances | Time Series length
---|---|---|---
Synthetic | 3 | 6000 | 100
CBF | 3 | 310 | 128
CC | 6 | 600 | 60
Face | 4 | 1120 | 350
Trace | 4 | 2000 | 275
|  |  |

###  3.2 Experimental settings

We first normalize the data, and then divide it into training dataset,
validation dataset, and test dataset at a ratio of 6:2:2. Then algorithm 3 is
applied to search for the optimal number of segments. In the training stage,
we record the validation loss in each epoch, and select the model with the
minimum validation loss as the final model. Some of the hyperparameter
configurations are shown in Table 2.

Table 2: Hyperparameters of SSAM-CNN model. | learning
---
rate
| learning
---
algorithm
| regularization
---
coefficient
epochs |  | batch
---
size
0.01 | SGD | 0.01 | 500 | 128
|  |  |  |

We select the widely used traditional TSC algorithm DTW-1NN[15] and the
representative deep learning based TSC models FCN[5] and MCNN[6] as
comparison. In order to validate the help of SSAM, we also test the base CNN
model without SSAM layer.

We visualize loss curve to discuss SSAM’s help in accelerating network
convergence. Through visulizing the learned mask and SSAM output, we discuss
the effectiveness of SSAM. We also validate that L1 regularization can make
the model generate a more sparse mask, which plays a role in frequency
component selection. At the same time, we validate that SSAM can improve the
robustness of the model to noise.

###  3.3 Results

Figure 4: The validation accuracy curve and loss curve on Synthetic dataset.

Compared to the base model, the introduction of SSAM makes the network
converge faster and the loss curve is smoother (see Figure 4). This indicates
that SSAM can map the original data into a feature representation that is more
conducive to network training.

Figure 5: Learned mask and filter output of synthetic dataset.

The learned mask is sparse and has a larger weight at three frequencies (see
Figure 5), which exactly correspond to the three target classes. Therefore,
SSAM can indeed assign appropriate weights to each frequency component,
highlighting important components and attenuating unimportant components. Due
to the influence of noise, the original time series are very similar, more
discriminative features are generated by SSAM, making the network easier to
train.

Figure 6: Classification accuracy under different intensity of white noise

We add white noise to the original data to test the noise immunity of the
model. The accuracy of the base model decreases rapidly with the increase of
noise intensity, while the accuracy of SSAM-CNN hardly decreases (see Figure
6). This is because our model is only sensitive to a few frequency components,
so it can shield most bands of white noise. Therefore, our model has good
robustness.

Table 3 shows the test accuracy of all algorithms on each dataset. The
hyperparameter $K$ obtained by algorithm3 is marked in the parentheses. From
Table 3, the accuracy of SSAM-CNN is higher than all other algorithms on four
datasets, and only slightly lower than FCN on CBF dataset. The performance of
SSAM-CNN exceeds base model on all datasets, indicating that the introducing
SSAM could improve the classification accuracy of the model. The number of
segments $K$ obtained by algorithm 3 is distributed between 1 and 3, among
which $K$ is 1 on CBF, Face and Synthetic datasets, 2 on Trace datasets, and 3
on CC datasets.

Table 3: Comparison results of the algorithms. The best result in each dataset is bolded. $K$ is marked in the parentheses. Datasets |  | DTW
---
-1NN
FCN | MCNN | base |  | SSAM
---
-CNN(K)
CBF | 91.30 | 94.60 | 80.43 | 91.30 | 93.48(1)
CC | 90.33 | 87.78 | 93.33 | 92.22 | 93.33(3)
Face | 82.14 | 91.07 | 89.88 | 83.57 | 94.64(1)
Trace | 68.33 | 93.00 | 92.33 | 86.31 | 93.73(2)
Synthetic | 63.20 | 88.30 | 93.40 | 93.09 | 99.94(1)
|  |  |  |  |
Figure 7: Learned mask and filter output of Face dataset. Figure 8: Learned
mask and filter output of CBF dataset.

Figure 7 and 8 show the learned mask and filtering results on the real
datasets CBF and Face. As can be seen from the figure, SSAM can assign
appropriate weights to each frequency component according to the
characteristics of data to generate discriminative features. And the learned
mask shows that the model pays more attention to the low frequency part of the
original data, which is in line with common sense.

Figure 9: The test accuracy of our model in different segmentation.

For CC and Trace dataset, the $K$ obtained by Algorithm 3 is not 1. This is
because the frequency difference of the original data at different phases may
be associated with the label. If the spectrum of the whole sequence is used
directly, the phase information will be lost. Therefore, Algorithm 3 gives a
$K$ that is not 1, and finally achieves a higher accuracy. In algorithm 3, we
use a heuristic strategy to search for $K$, that is, for each candidate value,
we only train the model for 5 epochs, and then decide whether to pick the
current candidate according to the validation loss. In order to verify the
effectiveness of this strategy, we apply each $K$ to the model to obtain the
test accuracy. As shown in Fig. 9, when $K$ is 2, the model achieves the
highest accuracy on the Trace dataset; When $K$ is 3, the model achieves the
highest accuracy on CC dataset. This is the same as the result obtained by the
algorithm 3, indicating that the heuristic algorithm can accurately find an
appropriate segmentation.

##  4 Conclusion

The main contribution of this paper is to prepose an attention mechanism that
acts on the spectrum. In order to avoid the complete loss of time domain
information, we also propose a segmented spectral attention mechanism, which
uses a tumbling window to segment the original sequence and apply SAM for each
segment to preserve the time domain information. We also propose a heuristic
algorithm to search for the best number of segments. The experimental results
show that the proposed SSAM is able to assign appropriate weights to each
frequency components to realize adaptive filtering, which make the model
converge faster and smoother, and more robust to noise. And the proposed
heuristic search algorithm can indeed find the most suitable segmentation and
improve the classification accuracy.

## References

  * [1] Bagnall A, Lines J, Bostrom A, Large J, Keogh E, The great time series classification bake off: A review and experimental evaluation of recent algorithmic advances, Data Mining and Knowledge Discovery, 31(3): 606-660, 2017.
  * [2] Simonyan K, Zisserman A, Very deep convolutional networks for large-scale image recognition, arXiv preprint arXiv:14091556, 2014.
  * [3] Sennrich R, Haddow B, Birch A, Neural machine translation of rare words with subword units, in Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, 2016: 1715-1725.
  * [4] Guo H, Tang R, Ye Y, Li Z, He X, Deepfm: A factorization-machine based neural network for ctr prediction, in Proceedings of the 26th International Joint Conference on Artificial Intelligence, 2017: 1725-1731.
  * [5] Wang Z, Yan W, Oates T, Time series classification from scratch with deep neural networks: A strong baseline, in 2017 International joint conference on neural networks (IJCNN), 2017: 1578-1585.
  * [6] Cui Z, Chen W, Chen Y, Multi-scale convolutional neural networks for time series classification, arXiv preprint arXiv:160306995, 2016.
  * [7] Fawaz HI, Lucas B, Forestier G, Pelletier C, Schmidt DF, Weber J, Webb GI, Idoumghar L, Muller P-A, Petitjean F, Inceptiontime: Finding alexnet for time series classification, Data Mining and Knowledge Discovery, 34(6): 1936-1962, 2020.
  * [8] Diab A, Falou O, Hassan M, Karlsson B, Marque C, Effect of filtering on the classification rate of nonlinear analysis methods applied to uterine emg signals, in 2015 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), 2015: 4182-4185.
  * [9] van Driel J, Olivers CN, Fahrenfort JJ, High-pass filtering artifacts in multivariate classification of neural time series data, BioRxiv: 530220, 2020.
  * [10] Shao Y, Lunetta RS, Wheeler B, Iiames JS, Campbell JB, An evaluation of time-series smoothing algorithms for land-cover classifications using modis-ndvi multi-temporal data, Remote Sensing of Environment, 174(258-265), 2016.
  * [11] Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser, Polosukhin I, Attention is all you need, in Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 6000-6010.
  * [12] Ioffe S, Szegedy C, Batch normalization: Accelerating deep network training by reducing internal covariate shift, in International conference on machine learning, 2015: 448-456.
  * [13] Lin M, Chen Q, Yan S, Network in network, arXiv preprint arXiv:131203762, 2013.
  * [14] Dau HA, Bagnall A, Kamgar K, Yeh C-CM, Zhu Y, Gharghabi S, Ratanamahatana CA, Keogh E, The ucr time series archive, IEEE/CAA Journal of Automatica Sinica, 6(6): 1293-1305, 2019.
  * [15] Lines J, Bagnall A, Time series classification with ensembles of elastic distance measures, Data Mining and Knowledge Discovery, 29(3): 565-592, 2014.


# Expansion properties of Whitehead moves
on cubic graphs

Laura Grave de Peralta  Research Institute in Mathematics and Physics,
UCLouvain, Chemin du Cyclotron 2, B–1348 Louvain–la–Neuve, Belgium  and
Alexander Kolpakov  Institut de Mathématiques, Université de Neuchâtel, Rue
Emile–Argand 11, CH–2000 Neuchâtel, Suisse / Switzerland

(Date: February 2023)

###### Abstract.

The present note studies the “graph of graphs” that has cubic graphs as
vertices connected by edges represented by the so–called Whitehead moves. We
study its conductance and expansion properties, and the adjacency spectrum.

##  1\. Introduction

The present note is concerned with the graph of $3$–regular, or cubic, graphs,
and associated objects, such as triangulations and pants decompositions of
surfaces. Such a “graph of graphs” $\Gamma_{n}$, represents what can be
informally described as the “deformations space” of cubic graphs on $2n$
vertices under the Whitehead moves. In particular, we shall investigate its
expansion property.

Expansion is an important notion for families of graphs: we wish to find
explicit families of graphs with good expansion properties. In particular, one
of the interests of studying expansion is because random walks converge
“quickly” to the stationary distribution and how quickly they do is controlled
by the second largest eigenvalue of the transition matrix. This notion of
_rapid mixing_ turns out to be a very useful measure of expansion for many
purposes.

We introduce the notion of _outer conductance_ because there is no standard
definition of expansion for directed non–regular multigraphs, despite them
being a natural class of objects to consider.

_Outer conductance_ captures how easy it is to escape a given subset of the
graph. Therefore, having the outer conductance tend to 0 is a way of saying
that the graphs have poor mixing and therefore cannot be “expanders” in this
sense.

Let $g$ be a cubic graph (we allow graphs with multiple edges and loops), with
set of vertices $V(g)$, and set of edges $E(g)$. Then, for an edge $e\in E(g)$
which is not a loop, there are two possible Whitehead moves $w^{(1)}_{e}$ and
$w^{(2)}_{e}$ on $e$, depicted in Figure 1, which are local transformations of
$g$. If $e\in E(g)$ is a loop, we assume that the respective Whitehead moves
have no effect on $g$.

Figure 1.  Two possible Whitehead moves performed on an edge $\varepsilon$.

Let the vertices of $\Gamma_{n}$ be all possible cubic graphs on $2n$ vertices
($n\geq 1$) up to isomorphism, where two vertices $g_{1},g_{2}\in V(\Gamma)$
are connected by a directed edge for each Whitehead move $w_{\varepsilon}$,
for $\varepsilon\in E(g_{1})$, such that $w_{\varepsilon}(g_{1})$ is
isomorphic to $g_{2}$. It is easy to see that being related by a Whitehead
move is an equivalence relation on the set of isomorphism classes of cubic
graphs on $2n$ vertices ($n\geq 1$).

Such a graph of graphs is related to moduli spaces of surface triangulations
[DP19, DP18] and pants decomposition of surfaces [RT13], although not entirely
equivalent to said objects. The definition considered here is a directed
version of the graph of graphs considered in [RT13]. Since Whitehead moves are
reversible, our graph of graphs is quasi–isometric to the one considered in
[RT13]. The graph of graphs considered in [RT13] is quasi–isometric to the
“wide” component of the thick part of the moduli space of a genus $g\geq 2$
surface. This means that $\Gamma_{n}$ describes pants decompositions of the
genus $g=n+1$ surface in which the set of separating curves contains only
sufficiently short geodesics. And so is the directed version considered here.
Similar local transformations are considered in [Hat99] and two such pants
decompositions represent adjacent vertices in $\Gamma_{n}$ if they are
connected by an $A$–move, as described in [Hat99], while an $S$–move (also
following [Hat99]) is always performed on a handle that corresponds to a loop
in the pants decomposition graph, and thus is not taken into account when
passing to $\Gamma_{n}$.

Thus, knowing the combinatorial properties of $\Gamma_{n}$ could be useful in
the study of the geometric and combinatorial properties of the former.

Here, we introduce a variation $\phi_{out}$ of the usual notion of conductance
and show that this quantity tends to $0$ for the family $\Gamma_{n}$ of cubic
graphs on $2n$ vertices.

In the present note, we show that the following statements hold.

######  Theorem A (Theorem 2.2).

Let $\Gamma_{n}$ be the graph of cubic graphs on $2n$ ($n\geq 1$) vertices
connected by Whitehead moves. Then $\phi_{out}(\Gamma_{n})\rightarrow 0$, as
$n\to\infty$.

######  Theorem B (Theorem 4.1).

Let $\Gamma_{n}$ be the graph of cubic graphs on $2n$ ($n\geq 1$) vertices.
Then the number of length $\ell$ paths in $\Gamma_{n}$ is asymptotically
$\sim\rho^{\ell}_{n}$, with $\rho_{n}$ a Perron number.

We also describe how Whitehead moves interact with graph automorphisms in
Section 5.

Finally, in Section 6 and LABEL:wm-section:open-questions, we mention some
connections and open questions related to $\Gamma_{n}$.

##  2\. Conductance and expansion

Let $G$ be a connected directed graph with vertex set $V(G)$ and edge set
$E(G)$. For a subset $S\subset V(G)$, let $d(S)$ denote the sum of vertex
out–degrees in $S$, i.e. $d(S)=\sum_{v\in S}deg_{out}(v)$, where $d_{out}(v)$
is the number of edge of the form $(v,u)$ where $v,u\in V(G)$. The boundary
$\partial(S)$ of a vertex subset $S\subset V(G)$ is defined as the number of
directed edges in $E(G)$ joining a vertex in $S$ with a vertex in
$V(G)\setminus S$, that is $\partial(S)=\\{e=(u,v)\in E(G)\ |\ u\in S\ ,v\in
S^{c}\\}$.

The outer–conductance of $S\subset V(G)$ is defined as follows:

$\phi_{out}(S)=\frac{|\partial(S)|}{\min\\{d(S),d(V(G)-S)\\}}$

and the outer–conductance of $G$ is

$\phi_{out}(G)=\min_{S\subset V(G)}\phi_{out}(S).$

This is a generalization of the notion of conductance [CG97]. Since we work
with directed graphs, the definition is adapted so that the volume is measured
with respect to the number of out–going edges. By doing so the
outer–conductance measures how hard it is to escape a subset of the graph.

As a generalisation of the notion of expander families to the case of directed
graphs with vertex degrees (both out–degree and in–degree) growing with the
number of vertices, we introduce Definition 2.1.

######  Definition 2.1.

We say that a sequence of directed graphs $G_{n}$ with out–degree and
in–degree growing with the number of vertices is an outer–expander family if
the conductance $\phi_{out}(G_{n})$ is uniformly bounded away from 0 as $n$
tends to infinity.

Now we prove our first assertion.

######  Theorem 2.2.

Let $\Gamma_{n}$ be the directed graph of cubic graphs on $2n$ ($n\geq 1$)
vertices connected by Whitehead moves. Then $\Gamma_{n}$ is connected and
$\phi_{out}(\Gamma_{n})\rightarrow 0$, as $n\to\infty$. Therefore, the family
$\\{\Gamma_{n}\\}_{n\in\mathbb{N}}$ is not a family of outer–expanders.

##  3\. Proof of Theorem 2.2

Let $\Gamma_{n}$ be the directed graph of (isomorphism classes of) cubic
graphs on $2n$ vertices ($n\geq 1$). The following two claims will imply
Theorem 2.2.

###  $\Gamma_{n}$ is connected.

This follows from [RT13]. Even simpler, by means of Whitehead moves we can
bring every cubic graph to a certain uniquely determined cubic tree.

Figure 2.  Performing a Whitehead move on the edge $\varepsilon=(v_{0},v_{1})$
that belongs to a $k$–cycle $C_{k}$ in $g\in V(\Gamma_{n})$.

Let $g$ be a cubic graph, and let $C_{k}$ be an indecomposable $k$–cycle (with
$k\geq 2$) in $g$, i.e. an induced cycle subgraph where no edge of $g$
connects any two vertices of $C_{k}$, except the edges of $C_{k}$ itself. If
we perform a Whitehead move on the edge $\varepsilon$ that belongs to a
$k$–cycle $C_{k}$, a part of which is depicted in Figure 2, we obtain a
modified graph (partly) depicted in Figure 3.

Figure 3.  A $(k-1)$–cycle $C_{k-1}$ in $\tilde{g}=w_{\varepsilon}(g)$: the
edge $\varepsilon=(v,w)$ does not belong to $C_{k-1}$.

The overall changes in the structure of $\tilde{g}=w_{\varepsilon}(g)$ as
compared to $g$ are local and amount to the following:

  * •

The $k$–cycle $C_{k}$ has been transformed into a $(k-1)$–cycle $C_{k-1}$ ;

  * •

If $v_{1}$, $w_{1}$ were part of an $l$–cycle $C_{l}$ then $C_{l}$ was
transformed into an $(l+1)$–cycle $C_{l+1}$;

  * •

Same applies to any cycle that previously contained $w_{0}$ and/or $v_{0}$.

By performing a total of $k-1$ Whitehead moves on the edges in $C_{k}$, we
reduce it to a loop, as depicted in Figure 4. Here we reduced the total amount
of $k$–cycles with $k\geq 2$ by one, although the lengths of some other cycles
could have been augmented.

Figure 4.  A $k$–cycle $C_{k}$ ($k\geq 2$) is reduced to a loop by $k-1$
consecutive Whitehead moves.

By repeating the above procedure on the remaining $k$–cycles (with $k\geq 2$)
of the resulting graph, we shall reduce it to what we call a $(n,b)$–cubic
tree, an example of which is depicted in Figure 5. Such a tree has $2n$
vertices and $b=n+1$ loops (note that $b$ is the $1$st Betty number of the
initial graph $g$, since Whitehead moves preserve the number of vertices and
edges of $g$, as well as the rank of $\pi_{1}(g)$).

Figure 5.  A $(2,3)$–cubic tree

There exists a natural isomorphism between our $(n,b)$–cubic trees with a
chosen loop (i.e. rooted $(n,b)$–cubic trees with a chosen loop
$\varepsilon^{*}$ as a root), and binary rooted trees. Namely, let us take a
rooted $(n,b)$–cubic tree $(T,\varepsilon^{*})$ and remove all the loops as
well as the edge $(v^{*},v)$ adjacent to $\varepsilon^{*}$ (with
$\varepsilon^{*}$ being a loop at vertex $v$). The result, $(\tilde{T},v^{*})$
is a binary rooted tree on $2n-1$ vertices with $n$ leaves.

As shown in Figure 6, a tree rotation can be achieved by a Whitehead move.
Thus, $(\tilde{T},v^{*})$ can be brought to the unique complete rooted binary
tree $T_{n}$ on $n$ vertices, cf. [CLRS09, §12 – §13] for more information on
binary trees and tree rebalancing. This proves that $\Gamma_{n}$ is connected.

Figure 6. A left and right rotation of a rooted binary tree (corresponding to
an $(n,b)$–cubic tree with root $\varepsilon^{*}$) realised by a Whitehead
move on edge $e$. Here $P$, $Q$ are the vertices of $\varepsilon$, and $A$,
$B$, and $C$ are the respective sub–trees

### The outer–conductance of $\Gamma_{n}$ tends to 0.

Let $B_{n}\subset V(\Gamma_{n})$ be the set of (isomorphism classes of)
connected cubic graphs on $2n$ vertices that have at least one bridge. We
shall estimate the probability $\mathbb{P}(g\in B_{n})$ asymptotically. For
this matter, notice that if $U_{n}=V(\Gamma_{n})$ is the set of unlabelled
cubic graphs (i.e. their isomorphism classes), and $L_{n}$ is the set of
labelled ones, then $\mathbb{P}(g\in U_{n}\mbox{ has a
bridge})=\mathbb{P}(g\in L_{n}\mbox{ has a bridge})+o(1)$, since
asymptotically virtually all graphs in $L_{n}$ have no non–trivial
automorphisms [Bol82], and thus $|L_{n}|\sim|U_{n}|\cdot(2n)!$, as
$n\to\infty$.

A bridge in a connected graph is an edge such that its removal produces
several connected components. A graph with a bridge is called bridged, while a
graph that has no bridges at all is called bridgeless.

A Hamiltonian circuit in a (connected) graph is a closed edge path without
self–intersection that visits each vertex once. A graph is called Hamiltonian
if it admits a Hamiltonian circuit.

It is clear that a graph that has a bridge cannot be Hamiltonian, and that
every Hamiltonian cubic graph is bridgeless.

Let $Bridged=\\{g\in L_{n}\ |\ g\mbox{ has a bridge}\\}$ and $Looped=\\{g\in
L_{n}\ |\ g\mbox{ has a loop}\\}$, and let $nH$ be the set of graphs in
$L_{n}$ that do not have a Hamiltonian circuit. Then

$\mathbb{P}(g\in Looped)\leq\mathbb{P}(g\in Bridged)\leq\mathbb{P}(g\in
Looped)+\mathbb{P}(g\notin Looped\mbox{ \& }g\in nH),$

since $Looped\subseteq Bridged$, as well as $Bridged\subseteq nH$.

By applying [JLR11, Theorem 9.5], we have that $\mathbb{P}(g\in
Looped)=1-e^{-1}+o(1)$, while [JLR11, Theorem 9.23] implies that
$\mathbb{P}(g\notin Looped\mbox{ and }g\in nH)=o(1)$, as $n\to\infty$. Thus,
$\mathbb{P}(g\in Bridged)=1-e^{-1}+o(1)$ asymptotically, as $n\to\infty$.

Together with the remarks above about the probabilities for labelled and
unlabelled graphs, we obtain that $\mathbb{P}(g\in B_{n})$, for $g\in
V(\Gamma_{n})$, satisfies $\mathbb{P}(g\in B_{n})=1-e^{-1}+o(1)$, as
$n\to\infty$. Thus, $|B_{n}|\sim(1-e^{-1})|V(\Gamma_{n})|$, and
$|V(\Gamma_{n})\setminus B_{n}|\sim e^{-1}|V(\Gamma_{n})|$.

Note that the only vertices in $B_{n}$ connected with vertices in
$V(\Gamma_{n})\setminus B_{n}$ are those $g\in B_{n}$ having a single bridge,
and the corresponding Whitehead moves have to be performed exactly on the
bridge edge of $g$.

Indeed, let $g\in V(\Gamma_{n})$ have at least one bridge and let
$\varepsilon^{*}=(u,v)$ denote one of its bridges. Then we can check
case–by–case what the result of a Whitehead move on $\varepsilon^{*}$ could
be.

For this purpose, let us introduce the following equivalence relation on the
vertices of $g$: for $v,w\in V(g)$, we write $v\sim_{g}w$ if and only if there
are two edge–disjoint paths connecting $v$ to $w$. Then we write
$[v]_{g}=\\{w\in V(g)\ s.t.\ v\sim_{g}w\\}$ for the equivalence class of $v$.

Let $\\{a,b,c,d\\}$ be the vertices adjacent to the bridge $\varepsilon^{*}\in
E(g)$, and let $\tilde{g}=w_{\varepsilon^{*}}(g)$ be the graph resulting from
a Whitehead move performed on $\varepsilon^{*}$. Then we consider the
following five possible cases.

##### 1.

$[a]_{g}=[b]_{g}=[c]_{g}=[d]_{g}$: in this case $\varepsilon^{*}$ is not a
bridge neither in $g$, nor in $\tilde{g}$, cf. Figures 8 and 8.

##### 2.

$[a]_{g}=[b]_{g}=[c]_{g}\neq[d]_{g}$: same as above, $\varepsilon^{*}$ is not
a bridge neither in $g$, nor in $\tilde{g}$, cf. Figures 10 and 10.

##### 3.

$[a]_{g}=[b]_{g}\neq[c]_{g}=[d]_{g}$: in this case, $\varepsilon^{*}$ is a
bridge in $g$, but not in $\tilde{g}$, cf. Figures 12 and 12.

##### 4.

$[a]_{g}=[b]_{g}\neq[c]_{g}$ , $[a]_{g}=[b]_{g}\neq[d]_{g}$, and
$[c]_{g}\neq[d]_{g}$: again, $\varepsilon^{*}$ is a bridge in $g$, but not in
$\tilde{g}$, cf. Figures 14 and 14.

##### 5.

$[a]_{g},[b]_{g},[c]_{g},[d]_{g}$ are all distinct: obviously,
$\varepsilon^{*}$ is a bridge in both $g$ and $\tilde{g}$, cf. Figures 16 and
16.

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 7.  Local picture inside $g$ when
$[a]_{g}=[b]_{g}=[c]_{g}=[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 8.  Local picture inside
$\tilde{g}$ when $[a]_{g}=[b]_{g}=[c]_{g}=[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 9.  Local picture inside $g$ when
$[a]_{g}=[b]_{g}=[c]_{g}\neq[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 10.  Local picture inside
$\tilde{g}$ when $[a]_{g}=[b]_{g}=[c]_{g}\neq[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 11. Local picture inside g when
$[a]_{g}=[b]_{g}\neq[c]_{g}=[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 12. Local picture inside
$\tilde{g}$ when $[a]_{g}=[b]_{g}\neq[c]_{g}=[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 13.  Local picture inside $g$ when
$[a]_{g}=[b]_{g}\neq[c]_{g}$ , $[a]_{g}=[b]_{g}\neq[d]_{g}$, and
$[c]_{g}\neq[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 14.  Local picture inside
$\tilde{g}$ when $[a]_{g}=[b]_{g}\neq[c]_{g}$ , $[a]_{g}=[b]_{g}\neq[d]_{g}$,
and $[c]_{g}\neq[d]_{g}$

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 15.  Local picture inside $g$ when
$[a]_{g},[b]_{g},[c]_{g},[d]_{g}$ are all distinct

$a$$b$$u$$v$$c$$d$$\varepsilon^{*}$ Figure 16. Local picture inside
$\tilde{g}$ when $[a]_{g},[b]_{g},[c]_{g},[d]_{g}$ are all distinct

According to the observations above, if a bridged graph $g\in B_{n}$ can be
transformed into a bridgeless one $\tilde{g}=w_{\varepsilon}(g)$, then
$\varepsilon$ is the only bridge of $g$. Every time, both Whitehead moves
either succeed or fail to bring $\tilde{g}$ outside $B_{n}$. This implies that
$|\partial(B_{n})|\leq 2|B_{n}|$. Thus the outer–conductance of the set
$B_{n}$ satisfies

$\displaystyle\phi_{out}(B_{n})$
$\displaystyle=\frac{|\partial(B_{n})|}{\min\\{d(B_{n}),d(V(\Gamma_{n})\setminus
B_{n})\\}}\leq\frac{2|B_{n}|}{6n|V(\Gamma_{n})\setminus B_{n}|}\sim$
$\displaystyle\sim\frac{2|V(\Gamma_{n})|(1-e^{-1})}{6n|V(\Gamma_{n})|e^{-1}}=\frac{e-1}{3n}\to
0,$

as $n\to\infty$. $\square$

##  4\. Adjacency spectrum

Let $A$ be a non–zero square $k\times k$ ($k\geq 2$) matrix with non–negative
integer entries. Such a matrix is called non–negative, for brevity. If all the
entries of $A$ are actually positive, then $A$ is called positive.

If there exists a permutation matrix $P$ such that $PAP^{-1}$ has
upper–triangular block form, $A$ is called reducible. Otherwise, $A$ is
irreducible.

For $i\in\\{1,\dots,k\\}$, the $i$–th period of $A$ is the least positive
integer $m$ such that the $i$–th diagonal entry of $A^{m}$ is positive. If $A$
is irreducible, then all its periods coincide, and each of them equals the
period of $A$. If the period of $A$ equals $1$, then $A$ is called aperiodic.

An aperiodic and irreducible non–negative matrix $A$ is called primitive. If
$A$ is a primitive matrix, then its spectral radius is a Perron number, as a
consequence of the Perron–Frobenius theorem [LM21]. Recall that a Perron
number is an algebraic integer $\rho>1$ such that all of its other Galois
conjugates have modulus strictly less than $\rho$. Perron numbers often appear
in dynamical context, cf. [LM21]. Another property of the spectral radius of a
primitive matrix $A$ is that this eigenvalue has multiplicity one.

Let $\Gamma$ be a directed graph, and let $A$ be its adjacency matrix defined
as follows:

$A_{uv}=\mbox{ the number of directed edges joining }u\mbox{ to }v,\mbox{ if
}u\neq v,\mbox{ and }$ $A_{vv}=\mbox{ the number of loops incident to }v.$

Then $A$ is irreducible if and only if $\Gamma$ is strongly connected, i.e.
there exists a path of directed edges in $\Gamma$ between any pair of distinct
vertices. If $\Gamma$ is strongly connected and the greatest common divisor of
its directed cycles equals $1$, then $A$ is aperiodic, and thus primitive.
Thus, in this case we can deduce that the spectral radius of $A$ is a Perron
number by considering the combinatorics of $\Gamma$.

######  Theorem 4.1.

Let $\Gamma_{n}$ be the graph of cubic graphs on $2n$ ($n\geq 1$) vertices.
Then the number of length $\ell$ paths in $\Gamma_{n}$ is asymptotically
$\sim\rho^{\ell}_{n}$, with $\rho_{n}$ a Perron number.

###  4.1. Proof of Theorem 4.1

Let $\Gamma_{n}$ be the graph of graphs on $2n$ vertices ($n\geq 1$), and let
$A_{n}=A(\Gamma_{n})$ be its adjacency matrix. We want to show that $A_{n}$ is
primitive. This would imply that its spectral radius $\rho_{n}=\rho(A_{n})$ is
a multiplicity $1$ eigenvalue with a positive eigenvector $v$, and that
$\rho_{n}$ is a Perron number. The asymptotic number of paths is then a
standard computation.

For every $n\geq 1$, there exists an $(n,b)$–cubic tree $t\in V(\Gamma_{n})$,
with $b=n+1\geq 2$ loops $\varepsilon_{1},\dots,\varepsilon_{b}$. Then,
$w_{\varepsilon_{i}}(t)=t$, for any $i=1,\dots,b$, and thus $\Gamma_{n}$ has
loops. This implies that $\Gamma_{n}$ is aperiodic111There are also edge
cycles of coprime length $\geq 2$ in the $\Gamma_{n}$ with $n\geq 3$, as can
be seen from the fact that $\Gamma_{3}$ embeds into $\Gamma_{n}$, $n\geq 4$,
and $\Gamma_{3}$ has cycles of length e.g. $2$ and $3$.

We already know that that $\Gamma_{n}$ is strongly connected, as in Theorem
2.2 we prove that $\Gamma_{n}$ is connected as a directed graph. Thus, we
obtain that $A_{n}$ is also primitive, and can now apply the Perron–Frobenius
theorem. $\square$

###  4.2. Remark on the thin neighbourhood.

It appears that $\Gamma_{n}$ is itself a relatively “thin” neighbourhood of
$B_{n}$. Indeed, we each length $k$ cycle in a graph $g\in V(\Gamma_{n})$ can
be reduced by $k-2$ Whitehead moves to a $2$–cycle, and one more Whitehead
move will create an edge incident to a loop. The standard asymptotic bound on
girth is $\mathrm{girth}(g)\lesssim 2\log_{2}n$. If $v=|V(\Gamma_{n})|$, then
$v\sim n^{n}$ [Bol82], and thus each vertex of $\Gamma_{n}$ happens to be
within $\sim\log_{2}\log_{2}v$ distance from $B_{n}$. As shown in [RT13], the
diameter of $\Gamma_{n}$ satisfies $d=\mathrm{diam}(\Gamma_{n})\sim
n\log_{2}n$, and thus each vetrex of $\Gamma_{n}$ is within $\log_{2}d$ of
$B_{n}$.

##  5\. Edge orbits and automorphisms

Below we make some remarks on how performing Whitehead moves on edges
equivalent under graph automorphisms affects the resulting graph.

######  Proposition 5.1.

Let $g$ be a trivalent graph and $e,f\in E(g)$. Suppose there exists an
automorphism $\alpha\in Aut(g)$ of $g$ such that
$\alpha(e)=f,\alpha(v_{i})=w_{i}$ and $\alpha(e_{i})=f_{i}$ for the
corresponding indices and that all the $v_{i}$’s and $w_{i}$’s are distinct
(see 18 and 18).

Then, if we perform the same Whitehead move on both sides, that is we choose
one of the following pairs of transformations:

  1. (1)

$w_{e}^{1}:(v_{1},v_{2})(v_{3},v_{4})\mapsto(v_{1},v_{3})(v_{2},v_{4})$ and
$w_{f}^{1}(g):(w_{1},w_{2})(w_{3},w_{4})\mapsto(w_{1},w_{3})(w_{2},w_{4})$; or

  2. (2)

$w_{e}^{2}:(v_{1},v_{2})(v_{3},v_{4})\mapsto(v_{1},v_{4})(v_{2},v_{3})$ and
$w_{f}^{2}:(w_{1},w_{2})(w_{3},w_{4})\mapsto(w_{1},w_{4})(w_{2},w_{3})$,

then the resulting graphs are isomorphic $w_{e}^{1}(g)\cong w_{f}^{1}(g)$ and
$w_{e}^{2}(g)\cong w_{f}^{2}(g)$.

$v_{1}$$v_{2}$$e_{1}$$e_{2}$$v_{3}$$v_{4}$$e$ Figure 17.  The neighbourhood of
$e$

$w_{1}$$w_{2}$$f_{1}$$f_{2}$$w_{3}$$w_{4}$$f$ Figure 18.  The neighbourhood of
$f$

###### Proof.

Suppose we perform a Whitehead move of type (1). Consider $g_{1}=g\setminus
St(e)$ and $g_{2}=\alpha(g)\setminus St(f)$ where $St(e)$, resp. $St(f)$, is
the star of $f$, resp. $e$ (i.e. the set of incident vertices and edges to
$e$, resp. $f$).

Then the map $\alpha$ induces $\overline{\alpha}:g_{1}\to g_{2}$ which is an
isomorphism.

Now consider $\gamma_{1}=w_{e}^{1}(g)\setminus St(e)$ and
$\gamma_{2}=w_{f}^{1}(g)\setminus St(f)$. Since a Whitehead move is a local
transformation, we have that $g_{1}=\gamma_{1}$ and $g_{2}=\gamma_{2}$. Thus,
we obtain a map $\overline{\alpha}:\gamma_{1}\to\gamma_{2}$, and this map is a
graph isomorphism.

Now we can extend $\overline{\alpha}$ to a map from $\gamma_{1}=w_{e}^{1}(g)$
to $\gamma_{2}=w_{f}^{1}(g)$ in the unique possible way, because $v_{1}$ and
$v_{3}$ have a unique common neighbour in $St_{w_{e}^{1}(g)}(e)$ and the same
applies to $w_{1},w_{3}$ in $St_{w_{f}^{1}(g)}(f)$. The same can be done for
$v_{2},v_{4}$ and $w_{2},w_{4}$. Thus, the map obtained is a graph isomorphism
between $\gamma_{1}$ and $\gamma_{2}$.

Note that exactly the same proof applies if we perform a Whitehead move of
type (2). ∎

Note also that the same proof works if, for example, $v_{1}=v_{3}$ and
$w_{1}=w_{3}$ and/or $v_{2}=v_{4}$ and $w_{2}=w_{4}$. The main point being
that multiple edges still allow extending the automorphism.

We also have a sort of converse.

######  Proposition 5.2.

Suppose $w_{e}^{k}(g)\cong w_{f}^{k}(g)$ via a map $\psi$ such that
$\psi(e^{*})=f^{*},\psi(v_{i}^{*})=w_{i}^{*}$ and $\psi(e_{i}^{*})=f_{i}^{*}$
for the corresponding indices $i$ (see Figures 20 and 20). Then, there exists
$\overline{\psi}\in Aut(g)$ such that $\overline{\psi}(e)=f$.

$v_{1}^{*}$$v_{2}^{*}$$e_{1}^{*}$$e_{2}^{*}$$v_{3}^{*}$$v_{4}^{*}$$e^{*}$
Figure 19.  The neighbourhood of $e^{*}$ in $w_{e}^{k}(g)$

$w_{1}^{*}$$w_{2}^{*}$$f_{1}^{*}$$f_{2}^{*}$$w_{3}^{*}$$w_{4}^{*}$$f^{*}$
Figure 20.  The neighbourhood of $f^{*}$ in $w_{f}^{k}(g)$

###### Proof.

Starting from the two graphs, re–apply the corresponding Whitehead moves, that
is either apply on both sides $w_{e}^{1}$ and $w_{f}^{1}$ or $w_{e}^{2}$ and
$w_{f}^{2}$ . The two graphs obtained are isomorphic, and on both sides you
retrieve $g$. Now you can apply Proposition 5.1 and thus obtain the desired
$\overline{\psi}$. ∎

######  Proposition 5.3.

Suppose $g_{1}$ and $g_{2}$ are isomorphic trivalent graphs via a map $\phi$.
Suppose $g_{1}=w_{e}^{1}(h_{1})$ and $g_{2}=w_{f}^{1}(h_{2})$. Suppose that
the map $\phi$ maps $e^{*}=w_{e}^{1}(e)$ to $f^{*}=w_{e}^{1}(f)$ and the
incident vertices $v_{i}^{*}$ to $w_{i}^{*}$ as in Figures 20 and 20. Then
$h_{1}$ and $h_{2}$ are isomorphic and there exists an isomorphism
$\psi:h_{1}\to h_{2}$ that maps $e$ onto $f$.

###### Proof.

Consider $\Gamma_{1}=g_{1}\setminus St(e^{*})$ and $\Gamma_{2}=g_{2}\setminus
St(f^{*})$. Then $\phi$ induces $\overline{\phi}:\Gamma_{1}\to\Gamma_{2}$ and
$\overline{\phi}$ is an isomorphism of graphs. Note that since a Whitehead
move is a local transformation, we have that $\Gamma_{1}=h_{1}\setminus St(e)$
and $\Gamma_{2}=h_{2}\setminus St(f)$ thus $\overline{\phi}$ can be seen as a
map from $h_{1}\setminus St(e)$ to $h_{2}\setminus St(f)$. We will now extend
$\overline{\phi}$ to an isomorphism $\psi:h_{1}\to h_{2}$.

Suppose the transformation $h_{1}\to g_{1}$ was doing (as local changes
described in $h_{1}$) $(v_{1}v_{3})(v_{2}v_{4})\to(v_{1}v_{2})(v_{3})(v_{4})$
and the transformation $h_{2}\to g_{2}$ was doing (as local changes in
$h_{2}$) $(w_{1}w_{2})(w_{3}w_{4})\to(w_{1}w_{2})(w_{3}w_{4})$.This is always
possible up to relabelling the graphs. Then $\\{e_{1}\\}=St_{h_{1}}(v_{1})\cap
St_{h_{1}}(v_{3}),\\{e_{2}\\}=St_{h_{1}}(v_{2})\cap
St_{h_{1}}(v_{4}),\\{f_{1}\\}=St_{h_{2}}(w_{1})\cap
St_{h_{2}}(w_{3}),\\{f_{2}\\}=St_{h_{2}}(w_{2})\cap St_{h_{2}}(w_{4})$ and we
define $\psi:h_{1}\to h_{2}$ as follows. We set $\psi(e_{i})=f_{i}$ and
${\left.\kern-1.2pt\psi\vphantom{\big{|}}\right|_{h_{1}\setminus
St(e)}}=\overline{\phi}$. Obviously $\psi$ is an isomorphism of graphs and it
maps $e$ to $f$ because we extend it to preserve adjacency. ∎

##  6\. Related objects

Above we consider the graph of graphs $\Gamma_{n}$ of all possible cubic
graphs on $2n$ vertices, where two vertices, $g_{1},g_{2}\in V(\Gamma_{n})$,
are connected by a directed edge for each Whitehead move $w_{\varepsilon}$,
for $\varepsilon\in E(g_{1})$, such that $w_{\varepsilon}(g_{1})$ is
isomorphic to $g_{2}$ vertices up to isomorphism.

However, there are several ways to modify this definition. Indeed, we could
modify the edges of $\Gamma_{n}$ in order to turn it into an undirected graph,
a simple graph or other types of graphs. These modifications can provide
relations between the graph of graphs and other mathematical problems. In this
section we will explore some of these connections.

####  6.0.1. Matchings on graphs

If two edges $e$, $f$ in $g\in\Gamma_{n}$ are not incident to each other, then
$w_{e}(g)$ and $w_{f}(g)$ commute. That is, if we want to apply consecutively
the two transformations, it will yield the same graph. This comes from
Whitehead moves being local transformations of the graph. Thus, if the two
local transformations are “far away” from each other, they commute. We will
call this a _simultaneous Whitehead move on the set $\\{e,f\\}$_ or
_simultaneous WM_ for short.

Thus, we can modify slightly the edges of $\Gamma_{n}$ to make it into a
simple directed graph in the following way. Say $g_{1},g_{2}\in
V(\Gamma_{n})$, are connected by an undirected edge if there exists some
Whitehead move on some set of non–incident edges of $g_{1}$ mapping $g_{1}$ to
$g_{2}$.

Then, the maximal number of edges one could choose in $g_{1}$ to perform a
simultaneous WM is the cardinality of a maximum matching in $g_{1}$. Thus,
determining the degree of $\Gamma_{n}$ as defined in this paragraph is closely
related to the number of matchings in a trivalent multigraph, though the two
quantities are not necessarily equal. Indeed, the number of maximum matchings
in $g_{1}$ yields an upper bound on the degree of $g_{1}$ in $\Gamma_{n}$.

####  6.0.2. Outer space and its spine

In [CV86], Culler and Vogtmann introduced a space $X_{n}$ on which the group
$Out(F_{n})$ acts. This space can be thought of as analogous to the
Teichmüller space of a surface with the action of the mapping class group of
the surface.

The description of $X_{n}$ is complicated, and we will not detail it here. We
will only briefly mention the relevant aspects of this object and how it could
relate to our graph of graphs.

The space $X_{n}$ is an infinite, finite–dimensional simplicial complex. A
point in a simplex in $X_{n}$ can be thought of as a metric graph (we assign
lengths to the edges of the graph) with fundamental group $F_{n}$ and some
labelling on its edges representing an element $\phi\in Out(F_{n})$ (these are
called _marked metric graphs_). Two given $k$–simplices $x_{1}$ and $x_{2}$
share a face of codimension $1$ if passing from the representative of $x_{1}$
to the one of $x_{2}$ can be obtained by quotienting an edge and re–opening
it. Thus, some simplices have open faces : the ones where collapsing an edge
would change the fundamental group on the underlying graph (that is, “killing”
a generator of $F_{n}$). Note that maximal dimension simplices correspond to
marked trivalent metric graphs.

The space $X_{n}$ admits a _spine_ $K_{n}$ which is a deformation retract of
$X_{n}$ in which we “forget” about the lengths of the edges. This spine
$K_{n}$ has the structure of a simplicial complex, in fact it can be
identified with the geometric realization of the partially ordered set of open
simplices of $X_{n}$222This is, word for word, the description given in
[Vog02]. The group $Out(F_{n})$ acts on $K_{n}$ with compact quotient.

Our graph of graphs $\Gamma_{n}$ is related to $K_{n}/Out(F_{n})$ in the
following way. First, we need to slightly modify the graph $\Gamma_{n}$: say
$g_{1},g_{2}\in V(\Gamma_{n})$ are connected by a directed edge from $g_{1}$
to $g_{2}$ for each edge $e\in g_{1}$ such that $w_{e}^{1}(g)\cong g_{2}$ or
$w_{e}^{2}(g)\cong g_{2}$. That is, we record on which edge we performed the
Whitehead move but not the type of Whitehead move.

A vertex $g\in\Gamma_{n}$ has fundamental group isomorphic to $F_{n}$ and thus
corresponds to a simplex in $K_{n}/Out(F_{n})$. In particular, since $g$ is a
cubic graph, it corresponds to a maximal simplex in $K_{n}/Out(F_{n})$. Thus,
two vertices $g_{1}$ and $g_{2}$ are adjacent in $\Gamma_{n}$ if and only if
the corresponding simplices in $K_{n}/Out(F_{n})$ share a face of codimension
$1$ (a wall).

If we set $w(g_{1},g_{2})=\min\\{\\#E(g_{1},g_{2}),\\#E(g_{2},g_{1})\\}$, then
the number $w(g_{1},g_{2})$ represents the number of walls shared by the
corresponding simplices in $K_{n}/Out(F_{n})$. Moreover, the edges chosen to
perform the Whitehead moves on indicate the edges to collapse to describe the
shared walls. Thus, our graph of graphs can be thought as encoding adjacency
between maximal simplices in $K_{n}/Out(F_{n})$ while keeping track of their
shared walls.

## Acknowledgements

Both authors were supported by the Swiss National Science Foundation project
no. PP00P2–202667. This first author is now supported by the FWO and the
F.R.S.–FNRS under the Excellence of Science (EOS) programme project ID
40007542.

## References

  * [Bol82] Béla Bollobás.  The asymptotic number of unlabelled regular graphs.  Journal of the London Mathematical Society, 2(2):201–206, 1982\.
  * [CG97] Fan RK Chung and Fan Chung Graham.  Spectral graph theory.  American Mathematical Soc., 1997.
  * [CLRS09] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [CV86] Marc Culler and Karen Vogtmann.  Moduli of graphs and automorphisms of free groups.  Inventiones mathematicae, 84(1):91–119, 1986.
  * [DP18] Valentina Disarlo and Hugo Parlier.  Simultaneous flips on triangulated surfaces.  Michigan Mathematical Journal, 67(3):451–464, 2018.
  * [DP19] Valentina Disarlo and Hugo Parlier.  The geometry of flip graphs and mapping class groups.  Transactions of the American Mathematical Society, 372(6):3809–3844, 2019.
  * [Hat99] Allen Hatcher.  Pants decompositions of surfaces.  arXiv preprint math/9906084, 1999.
  * [JLR11] Svante Janson, Tomasz Luczak, and Andrzej Rucinski.  Random graphs, volume 45.  John Wiley & Sons, 2011.
  * [LM21] Douglas Lind and Brian Marcus.  An introduction to symbolic dynamics and coding.  Cambridge university press, 2021.
  * [RT13] Kasra Rafi and Jing Tao.  The diameter of the thick part of moduli space and simultaneous whitehead moves.  Duke Mathematical Journal, 162(10):1833–1876, 2013.
  * [Vog02] Karen Vogtmann.  Automorphisms of free groups and outer space.  Geometriae Dedicata, 94:1–31, 2002.