11institutetext: Technical University of Munich, Germany 22institutetext:
Helmholtz AI and Helmholtz Center Munich, Germany 33institutetext: Klinikum
rechts der Isar, Technical University of Munich, Germany 44institutetext:
King’s College London, UK **footnotetext: Contributed equally as senior
authors.

# Diffusion Models for Unsupervised Anomaly Detection in Fetal Brain
Ultrasound

Hanna Mykula 11 Lisa Gasser 33 Silvia Lobmaier 33 Julia A. Schnabel 1 2 41 2 4
Veronika Zimmer∗ 11 Cosmin I. Bercea∗ 1 21 2

###### Abstract

Ultrasonography is an essential tool in mid-pregnancy for assessing fetal
development, appreciated for its non-invasive and real-time imaging
capabilities. Yet, the interpretation of ultrasound images is often
complicated by acoustic shadows, speckle noise, and other artifacts that
obscure crucial diagnostic details. To address these challenges, our study
presents a novel unsupervised anomaly detection framework specifically
designed for fetal ultrasound imaging. This framework incorporates gestational
age filtering, precise identification of fetal standard planes, and targeted
segmentation of brain regions to enhance diagnostic accuracy. Furthermore, we
introduce the use of denoising diffusion probabilistic models in this context,
marking a significant innovation in detecting previously unrecognized
anomalies. We rigorously evaluated the framework using various diffusion-based
anomaly detection methods, noise types, and noise levels. Notably, AutoDDPM
emerged as the most effective, achieving an area under the precision-recall
curve of 79.8% in detecting anomalies. This advancement holds promise for
improving the tools available for nuanced and effective prenatal diagnostics.

Figure 1: Workflow for screening and monitoring fetal brain anomalies in
ultrasound images during pregnancy. Diffusion models generate pseudo-healthy
synthesis to effectively identify potential developmental anomalies.

###### Keywords:

Fetal Ultrasound Screening Medical Imaging

##  1 Introduction

Ultrasonography (US) is an indispensable tool in prenatal care, widely used
for monitoring fetal development due to its safety, real-time imaging
capabilities, and cost-effectiveness [18]. Particularly, the mid-pregnancy US
scan at around 22 weeks is crucial for assessing fetal growth and identifying
potential anomalies, including those affecting the brain. However,
interpreting US images remains challenging due to artifacts such as acoustic
shadows, speckle noise, and motion blurring. These issues arise from the
complex interactions between US waves and biological tissues, which can
obscure critical diagnostic details and complicate both manual and automated
analyses [16].

The application of deep learning (DL) in fetal US image analysis has shown
significant promise, enhancing the ability of clinicians to detect anomalies
[11]. However, supervised DL methods face considerable challenges due to the
anatomical diversity and the imbalance between healthy and anomalous samples
[17, 26]. Given these limitations, unsupervised anomaly detection (UAD)
emerges as a viable alternative. UAD methods train exclusively on healthy
samples, establishing a baseline for normality without the need for labeled
anomaly data. Even though this approach offers better generalization across
various pathologies [22], it remains largely unexplored for fetal brain US.

In this study, we propose a novel UAD framework aimed at detecting brain
anomalies in fetal US images. Our framework incorporates several innovative
techniques to enhance the quality and consistency of the US scans.
Specifically, we filter by gestational age, detect and localize standard
planes using SonoNet [2], and remove background noise to focus on the brain
region. Furthermore, we pioneer the application of denoising diffusion
probabilistic models (DDPM) in this context. DDPMs have shown exceptional
performance in capturing complex distributions and generating high-fidelity
images, making them suitable for identifying previously unseen anomalies in
fetal US scans [12].

We thoroughly evaluated our framework using various diffusion-based UAD
methods, noise types, and noise levels to understand their performance and
robustness. Among these, AutoDDPM [4] demonstrated superior performance,
achieving an area under the precision-recall curve of 79.8% in anomaly
detection.

##  2 Related work

This section reviews existing research on anomaly detection (AD) in brain
imaging, focusing on two main areas: AD methods for brain MRI and AD methods
for fetal US. This overview establishes the context for our novel approach
using diffusion-based methods for fetal brain US anomaly detection.

Anomaly Detection in Brain MRI. Magnetic resonance imaging (MRI) is vital for
detecting brain abnormalities, providing detailed tissue contrasts and
revealing various pathological changes [15]. Traditional AD methods in brain
MRI include Autoencoders [5, 9, 28] and Generative Adversarial Networks [20,
1], which learn the distribution of healthy anatomy by compressing and
decompressing image data. Recently, diffusion models have demonstrated
superior performance by offering better mode coverage and sample quality.
Denoising diffusion probabilistic models (DDPMs) iteratively learn the data
distribution through noising and denoising processes, showing significant
success in brain MRI applications [3, 23, 4]. However, their application to
fetal brain US remains unexplored.

Anomaly Detection in Fetal Images. There has been significant focus on other
fetal organs, particularly the heart, for detecting anomalies in fetal
imaging. In heart imaging, Chotzoglou et al. [10] proposed an unsupervised
approach for detecting Hypoplastic Left Heart Syndrome from fetal US images.
Research on AD for fetal brain imaging has also seen notable contributions.
FOAC-NET, a supervised convolutional neural network (CNN) architecture, has
been developed for detecting fetal organ anomalies in MRI [14]. In fetal brain
US, H. N. Xie et al. [25] developed a CNN-based system to classify US images
into normal and abnormal categories, achieving high accuracy. However,
unsupervised anomaly detection remains largely unexplored in fetal brain US.

##  3 Methods

###  3.1 Background

Denoising Diffusion Probabilistic Models (DDPMs) use a forward diffusion
process, $q(x_{t}|x_{t-1})$, to incrementally corrupt data from a target
distribution, $q(x_{0})$, to a normal distribution. A reverse process,
$p(x_{t-1}|x_{t})$, generates samples by transforming noise back to
$q(x_{0})$. The forward process is defined as:

$q(x_{t}|x_{t-1})=\mathcal{N}(x_{t}|x_{t-1},\sqrt{1-\beta_{t}},\beta_{t}I),$
(1)

with a variance schedule, $\beta_{t}\in(0,1)$, increasing linearly from
$\beta_{1}=10^{-4}$ to $\beta_{T}=0.02$ [13]. The reverse generative model,
with parameters $\theta$, begins with $x_{T}\sim\mathcal{N}(0,I)$ and proceeds
from $T$ to $1$:

$p_{\theta}(x_{t-1}|x_{t})=\mathcal{N}(x_{t-1}|\mu_{\theta}(x_{t},t),\tilde{\beta}_{t}I),$
(2)

where
$\tilde{\beta}_{t}=\frac{1-\bar{\alpha}_{t-1}}{1-\bar{\alpha}_{t}}\beta_{t}$,
$\alpha_{t}=1-\beta_{t}$ and $\bar{\alpha}_{t}=\prod_{i=0}^{t}\alpha_{i}$. A
U-Net [19] is used to learn the noise $\epsilon_{\theta}(x_{t},t)$ and
approximate $\mu_{\theta}$. The loss function, $\mathcal{L}_{t}$, targeting
the marginal likelihood $p_{\theta}(x_{0})$, is:

$\mathcal{L}_{t}=D_{KL}(q(x_{t-1}|x_{t},x_{0})||p_{\theta}(x_{t-1}|x_{t})),$
(3)

where $D_{KL}$ is the Kullback-Leibler divergence. We use Ho et al.’s
simplified objective [13]:

$\mathcal{L}_{s}=\mathbb{E}_{x_{0}\sim
q(x_{0}),\epsilon\sim\mathcal{N}(0,I)}\left[\left\|\epsilon-\epsilon_{\theta}(x_{t},t)\right\|^{2}\right].$
(4)

AnoDDPM [24] leverages DDPMs with either Gaussian or Simplex noise for anomaly
detection segmentation. A more recent method proposes a conditional diffusion
model to produce more accurate pseudo-healthy counterfactuals, known as
AutoDDPM [4].

###  3.2 Fetal Brain UAD Framework

Selecting US data from the initial dataset requires meticulous attention to
ensure the high quality of the training, validation, and testing data. This
selection process must meet specific criteria, such as the correct gestational
age, the transventricular plane view, and the visibility of key brain
structures. To diminish the noise inherent in US images, segmentation into
brain and background is necessary. Manually performing this selection process
can be extremely time-consuming. Therefore, we propose a semi-automatic data
preprocessing pipeline (see Fig. 2) that aids in the data curation process,
thereby enhancing the quality of the data in the training dataset. Following
the construction of the final training, validation, and testing datasets using
our semi-automatic pipeline, we train DDPMs to remove artificially added noise
and reconstruct pseudo-healthy images. The modular inference setup of our
method allows us to test different inference strategies, including AnoDDPM and
AutoDDPM, with various noise types such as Simplex and Gaussian.

Figure 2: Overview of the proposed framework for detecting brain anomalies in
fetal ultrasound scans. The process includes: (1) detecting standard fetal
planes (green boxes indicate correct detections, red boxes incorrect) using
SonoNet [2]; (2) segmenting and cropping brain regions from these planes [21,
7]; (3) performing a final quality check by a human expert; (4) using the
curated dataset to train and evaluate diffusion-based anomaly detection
methods; and (5) applying diffusion-based models for anomaly detection through
iterative noising and denoising.

####  3.2.1 Standard Plane Detection.

We utilize SonoNet [2] to automatically select images with the correct
transventricular plane view of the fetal brain. SonoNet is designed for the
real-time detection of fetal standard scan planes in US images and classifies
images into one of 13 standard plane categories, including the brain view at
the posterior horn of the ventricle (Brain (tv.)). The core of the method is a
CNN inspired by the VGG16 architecture. For our experiment, we employed
SonoNet-32, equipped with 32 kernels, achieving an F1-Score of 0.798 in plane
classification. SonoNet also provides a confidence score for its predictions,
enabling a more rigorous selection of candidate images. We eliminate all
images that are not labeled as "Brain (tv.)" or have a corresponding
confidence score lower than 0.9.

####  3.2.2 Brain Segmentation.

In the second step of our pipeline, we segment and crop all the images to
eliminate background noise. We use a probabilistic deep learning approach with
a U-Net segmentation network to mask the head from US images. Although in [21,
7] ellipses are fitted to the segmented contours for biometric measurements,
we only utilize the segmentation model. A manual review is performed to verify
the quality of the data that has been automatically selected and preprocessed.

####  3.2.3 Diffusion-based Anomaly Detection.

The final step in our methodology involves the use of DDPMs for anomaly
detection. The inference phase of our method is modular, allowing the use of
different strategies for anomaly detection. We explore the use of both AnoDDPM
and AutoDDPM methods.

By comparing the performance of AnoDDPM [24] and AutoDDPM [4] with different
types and levels of noise, we aim to evaluate the effectiveness of different
diffusion-based methods for fetal brain US anomaly detection.

##  4 Experiments and Results

###  4.1 Experimental Setup

Datasets. For our experiments, we utilized data from both public [8] and
private clinical datasets. The clinical dataset comprised 234 control
patients, from which only those within a gestational age range of 19 to 22+6
weeks were selected for inclusion. Consequently, our final dataset for
training, validation, and testing included 76 patients from the clinical
dataset and 19 from the public dataset, totaling 252 images. For the
evaluation of the downstream task, we chose 8 anomalous and 5 healthy control
patients from the private clinical dataset, yielding 18 and 12 images,
respectively. We adjusted the input pixel values to fall within the range of
(0, 1) for Gaussian noise and $(-1,1)$ for Simplex noise. We normalized the
images to the 98th percentile, resized them to a resolution of $128\times
128$, and applied rotations and horizontal and vertical flips as data
augmentation.

Evaluation Metrics. To evaluate the performance on healthy scans, we utilized
several metrics, including mean absolute error (MAE) as a measure of
reconstruction error, structural similarity index (SSIM), and learned
perceptual image patch similarity (LPIPS) [27] for reconstruction accuracy.
For anomaly detection performance, we assessed the algorithm’s ability to
correctly classify images as either healthy or anomalous using true positives,
true negatives, false positives, and false negatives. We calculated the Area
Under the Precision-Recall Curve (AUPRC) and the Area Under the Receiver
Operating Characteristic (AUROC) curve to provide a comprehensive view of the
algorithm’s classification performance.

###  4.2 Anomaly Detection Performance

Table 1: Anomaly detection performance. Best results are shown in bold and secondbest are underlined. Method | Healthy | Pathological
---|---|---
SSIM $\uparrow$ | LPIPS $\downarrow$ | AURPC $\uparrow$ | AUROC $\uparrow$
AnoDDPM [24] with Simplex(t=50) | 0.81±0.05 | 0.26±0.05 | 78.9 | 70.8
AnoDDPM [13] with Gaussian(t=250) | 0.88±0.01 | 0.05±0.01 | 73.0 | 63.8
AnoDDPM [13] with Gaussian(t=300) | 0.87±0.02 | 0.05±0.01 | 73.5 | 57.4
AutoDDPM [4] with Gaussian(t=300) | 0.88 $\pm$ 0.02 | 0.05 $\pm$ 0.02 | 79.8 | 66.6

(a) Healthy

(b) Pathology

Figure 3: Anomaly detection performance. From left to right we show the
original image, the generated reconstruction, and the anomaly map.

We assessed the performance of AnoDDPM employing both Gaussian and Simplex
Noise, alongside AutoDDPM, as detailed in [4]. The evaluation focused on
various noise levels ($t={50,100,150,200,250,300}$), analyzing the model’s
robustness under different conditions.

The classification outcomes are succinctly summarized in Table 1, with the
most effective noise variations and types for both AnoDDPM and AutoDDPM
highlighted. Corresponding visual results are depicted in Fig. 3. For a
thorough examination of all noise levels and types, including metrics on
reconstruction errors and accuracy, readers are directed to the supplementary
materials, which provide an extensive overview of all conducted experiments.

Influence of Noise Type and Levels. We evaluated AnoDDPM using Gaussian and
Simplex noise at various noise levels, as summarized in Tables 2 and 3 in the
supplementary materials. While Gaussian noise at a level of $t=50$ yields the
best performance in terms of reconstruction for healthy images (MAE of 0.013,
SSIM of 0.898), it demonstrates limitations in anomaly detection with modest
scores (67.5 AUPRC and 43.5 AUROC). This reflects a typical challenge in
medical imaging: achieving minimal alteration in input images often
compromises the effectiveness of anomaly detection. In contrast, higher noise
levels ($t\geq 250$) show improved anomaly detection results, reaching up to
73 AUPRC and 63.8 AUROC, despite the compromise in image quality metrics. This
observation aligns with the ’noise paradox’ discussed in.[4], illustrating the
complex trade-off between achieving optimal reconstruction of healthy images
and effective anomaly detection in pathological cases. This paradox can also
be observed in Fig.4, where higher noise levels enable the detection of the
pathology but introduce false positive detections.

At a noise level of $t=50$, AnoDDPM with Simplex noise achieves its most
effective reconstruction capabilities for healthy images, recording MAE values
of 0.034 and SSIM scores of 0.808. These significantly lag behind the results
obtained with Gaussian noise, highlighting a substantial disparity in
denoising effectiveness. As noise levels increase, both MAE and SSIM metrics
for Simplex noise exhibit gradual deterioration, e.g., for $t=300$, the MAE
increases to 0.045, while SSIM scores decrease to 0.741. In terms of anomaly
detection capabilities, Simplex noise at $t=50$ delivers the most impressive
results, achieving an AUPRC of 78.9 and an AUROC of 70.8. These figures are
the highest among all configurations and noise types tested, underscoring the
superior ability of Simplex noise to detect anomalies under specific
conditions, despite its lower reconstruction performance.

Figure 4: AutoDDPM [4] performance on pathology under multiple noise levels
$t$.

Figure 3 illustrates that Gaussian noise models achieve high-quality
reconstructions and effectively highlight anomalies in fetal brain US images.
In contrast, Simplex noise introduces noticeable noise artifacts on both
healthy and pathological scans, though it remains effective in anomaly
detection.

Influence of Anomaly Maps. We analyzed the impact of different anomaly maps —
MAE, LPIPS [6], and their combination (MAE*LPIPS) — on anomaly detection
performance. Detailed results are shown in Table 4 and Figures 1 and 2 in the
supplementary materials. The combined anomaly maps yield the best performance
overall, proving to be more precise in balancing the identification of
pathological regions and reducing false positive detections.

##  5 Discussion

Our study into the automatic anomaly detection pipeline for fetal brain US
using DDPMs demonstrates effective pseudo-healthy synthesis and precise
anomaly localization. Notably, newer diffusion models such as AutoDDPM [4]
show significant promise in enhancing these capabilities. However, the
performance of Simplex noise raises specific concerns; its interaction with
the inherent noise characteristic of US images suggests it may not be ideally
suited for these applications. This behavior necessitates further analysis to
fully understand and mitigate adverse effects caused by this type of
artificial noise.

Although the results are promising and the dataset was large enough for the
models to be able to capture the underlying normative distribution, the
statistical validation of these findings requires more extensive datasets.
This project is part of an ongoing initiative within the clinic, with
continuous efforts to collect more US images to enrich our dataset.
Additionally, assessing the clinical utility of this automated screening for
pathologies is vital. Evaluating how well our pipeline supports operators and
sonographers in detecting and diagnosing conditions will help determine the
practical benefits of integrating this technology into everyday clinical
practice.

Future research directions will focus on evaluating our pipeline on US video
data to simulate real clinical environments more accurately. This includes
capturing the dynamic aspects of fetal movements and variations in US probe
positioning, which can significantly impact image quality and diagnostic
accuracy. Moreover, expanding the diversity of the dataset with images from
different US machines and settings will help improve the generalizability and
robustness of the proposed methods.

##  6 Conclusion

In this work, we introduced a novel framework to enable fetal brain anomaly
detection on US scans. We designed the framework to automatically reduce the
noise and randomness inherent in the US images, allowing models to learn the
normative distribution effectively. For the first time, we applied diffusion-
based models to automatically processed fetal brain US scans and evaluated
their performance under different noise types and levels. Our results indicate
that diffusion models, particularly AutoDDPM, hold significant potential for
improving the accuracy and reliability of fetal brain anomaly detection in
clinical settings.

## References

  * [1] Akcay, S., Atapour-Abarghouei, A., Breckon, T.P.: Ganomaly: Semi-supervised anomaly detection via adversarial training. In: Computer Vision–ACCV 2018: 14th Asian Conference on Computer Vision, Perth, Australia, December 2–6, 2018, Revised Selected Papers, Part III 14. pp. 622–637. Springer (2019)
  * [2] Baumgartner, C.F., Kamnitsas, K., Matthew, J., Fletcher, T.P., Smith, S., Koch, L.M., Kainz, B., Rueckert, D.: Sononet: Real-time detection and localisation of fetal standard scan planes in freehand ultrasound (2017)
  * [3] Behrendt, F., Bhattacharya, D., Krüger, J., Opfer, R., Schlaefer, A.: Patched diffusion models for unsupervised anomaly detection in brain mri. International Conference on Medical Imaging with Deep Learning (2023)
  * [4] Bercea, C.I., Neumayr, M., Rueckert, D., Schnabel, J.A.: Mask, stitch, and re-sample: Enhancing robustness and generalizability in anomaly detection through automatic diffusion models (2023)
  * [5] Bercea, C.I., Rueckert, D., Schnabel, J.A.: What do aes learn? challenging common assumptions in unsupervised anomaly detection. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 304–314. Springer (2023)
  * [6] Bercea, C.I., Wiestler, B., Rueckert, D., Schnabel, J.A.: Generalizing unsupervised anomaly detection: towards unbiased pathology screening. In: Medical Imaging with Deep Learning (2023)
  * [7] Budd, S., Sinclair, M., Khanal, B., Matthew, J., Lloyd, D., Gomez, A., Toussaint, N., Robinson, E.C., Kainz, B.: Confident head circumference measurement from ultrasound with real-time feedback for sonographers. In: Shen, D., Liu, T., Peters, T.M., Staib, L.H., Essert, C., Zhou, S., Yap, P.T., Khan, A. (eds.) Medical Image Computing and Computer Assisted Intervention – MICCAI 2019. pp. 683–691. Springer International Publishing, Cham (2019)
  * [8] Burgos-Artizzu, X.P., Coronado-Gutierrez, D., Valenzuela-Alcaraz, B., Bonet-Carne, E., Eixarch, E., Crispi, F., Gratacós, E.: FETAL_PLANES_DB: Common maternal-fetal ultrasound images (Jun 2020). https://doi.org/10.5281/zenodo.3904280, https://doi.org/10.5281/zenodo.3904280
  * [9] Chen, X., You, S., Tezcan, K.C., Konukoglu, E.: Unsupervised lesion detection via image restoration with a normative prior. Medical Image Analysis 64 (2020)
  * [10] Chotzoglou, E., Day, T., Tan, J., Matthew, J., Lloyd, D., Razavi, R., Simpson, J., Kainz, B., et al.: Learning normal appearance for fetal anomaly screening: Application to the unsupervised detection of hypoplastic left heart syndrome. Machine Learning for Biomedical Imaging 1(September 2021 issue), 1–25 (2021)
  * [11] Fiorentino, M.C., Villani, F.P., Di Cosmo, M., Frontoni, E., Moccia, S.: A review on deep-learning algorithms for fetal ultrasound-image analysis. Medical Image Analysis 83, 102629 (Jan 2023). https://doi.org/10.1016/j.media.2022.102629, http://dx.doi.org/10.1016/j.media.2022.102629
  * [12] Ho, J., Jain, A., Abbeel, P.: Denoising diffusion probabilistic models. CoRR abs/2006.11239 (2020), https://arxiv.org/abs/2006.11239
  * [13] Ho, J., Jain, A., Abbeel, P.: Denoising diffusion probabilistic models (2020)
  * [14] Lo, J., Lim, A., Wagner, M.W., Ertl-Wagner, B., Sussman, D.: Fetal organ anomaly classification network for identifying organ anomalies in fetal mri. Frontiers in Artificial Intelligence 5 (2022). https://doi.org/10.3389/frai.2022.832485, https://www.frontiersin.org/articles/10.3389/frai.2022.832485
  * [15] Luo, G., Xie, W., Gao, R., Zheng, T., Chen, L., Sun, H.: Unsupervised anomaly detection in brain mri: Learning abstract distribution from massive healthy brains. Computers in Biology and Medicine 154, 106610 (2023). https://doi.org/https://doi.org/10.1016/j.compbiomed.2023.106610, https://www.sciencedirect.com/science/article/pii/S0010482523000756
  * [16] Meng, L., Zhao, D., Yang, Z., Wang, B.: Automatic display of fetal brain planes and automatic measurements of fetal brain parameters by transabdominal three-dimensional ultrasound. Journal of Clinical Ultrasound 48 (07 2019). https://doi.org/10.1002/jcu.22762
  * [17] Pang, G., Shen, C., Cao, L., Hengel, A.V.D.: Deep learning for anomaly detection: A review. ACM Computing Surveys 54(2), 1–38 (Mar 2021). https://doi.org/10.1145/3439950, http://dx.doi.org/10.1145/3439950
  * [18] Reddy, U., Filly, R., Copel, J.: Prenatal imaging: Ultrasonography and magnetic resonance imaging. Obstetrics and gynecology 112, 145–57 (08 2008). https://doi.org/10.1097/01.AOG.0000318871.95090.d9
  * [19] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation (2015)
  * [20] Schlegl, T., Seeböck, P., Waldstein, S.M., Langs, G., Schmidt-Erfurth, U.: f-AnoGAN: Fast unsupervised anomaly detection with generative adversarial networks. Medical Image Analysis 54, 30–44 (2019)
  * [21] Sinclair, M., Baumgartner, C.F., Matthew, J., Bai, W., Martinez, J.C., Li, Y., Smith, S., Knight, C.L., Kainz, B., Hajnal, J., King, A.P., Rueckert, D.: Human-level performance on automatic head biometrics in fetal ultrasound using fully convolutional neural networks. In: 2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC). pp. 714–717 (2018). https://doi.org/10.1109/EMBC.2018.8512278
  * [22] Tschuchnig, M.E., Gadermayr, M.: Anomaly Detection in Medical Imaging - A Mini Review, p. 33–38. Springer Fachmedien Wiesbaden (2022). https://doi.org/10.1007/978-3-658-36295-9_5, http://dx.doi.org/10.1007/978-3-658-36295-9_5
  * [23] Wolleb, J., Bieder, F., Sandkühler, R., Cattin, P.C.: Diffusion models for medical anomaly detection. Medical Image Computing and Computer Assisted Intervention pp. 35–45 (2022)
  * [24] Wyatt, J., Leach, A., Schmon, S.M., Willcocks, C.G.: Anoddpm: Anomaly detection with denoising diffusion probabilistic models using simplex noise. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops. pp. 650–656 (06 2022)
  * [25] Xie, H.N., Wang, N., He, M., Zhang, L.H., Cai, H.M., Xian, J.B., Lin, M.F., Zheng, J., Yang, Y.Z.: Using deep-learning algorithms to classify fetal brain ultrasound images as normal or abnormal. Ultrasound in Obstetrics & Gynecology 56(4), 579–587 (2020). https://doi.org/https://doi.org/10.1002/uog.21967, https://obgyn.onlinelibrary.wiley.com/doi/abs/10.1002/uog.21967
  * [26] Zhang, H., Guo, W., Zhang, S., Lu, H., Zhao, X.: Unsupervised deep anomaly detection for medical images using an improved adversarial autoencoder. Journal of Digital Imaging 35 (01 2022). https://doi.org/10.1007/s10278-021-00558-8
  * [27] Zhang, R., Isola, P., Efros, A.A., Shechtman, E., Wang, O.: The unreasonable effectiveness of deep features as a perceptual metric (2018)
  * [28] Zimmerer, D., Isensee, F., Petersen, J., Kohl, S., Maier-Hein, K.: Unsupervised anomaly localization using variational auto-encoders (2019)


# On the structure and diameter of graph associahedra of graphs with a set of
true twins111Partially supported by Math AmSud 22-MATH-02, PIP CONICET
11220200101900CO, PIP CONICET 11220220100068CO, PICT-2020-03032, PICT
2020-00549, PICT 2020-04064, PID 80020210300068UR, PROICO 03-0723, PROIPRO
03-2923.

Ana Gargantini222e-mail<EMAIL_ADDRESS>Facultad de Ciencias
Exactas y Naturales, Universidad Nacional de Cuyo Consejo Nacional de
Investigaciones Científicas y Técnicas, Argentina  Adrián Pastine333e-mail:
<EMAIL_ADDRESS>Instituto de Matemática Aplicada San Luis (UNSL-CONICET)
Departamento de Matemática, Universidad Nacional de San Luis  Pablo
Torres444e-mail<EMAIL_ADDRESS>Consejo Nacional de Investigaciones
Científicas y Técnicas, Argentina  Depto. de Matemática, Facultad de Ciencias
Exactas, Ing. y Agrimensura, Universidad Nacional de Rosario

###### Abstract

Given a graph $G$, the graph associahedron $\mathcal{A}(G)$ is a polytope
whose 1-skeleton is the rotation graph of $G$, that is, the 1-skeleton of
$\mathcal{A}(G)$ is the graph $\mathcal{R}(G)$ whose vertices are the search
trees on $G$ and whose edges correspond to an application of a local operation
on the search trees, called rotation. The rotation distance between two search
trees on $G$ is the minimum number of rotations needed to transform one of the
trees into the other. A challenging question is what is the maximum rotation
distance between search trees on a graph, i.e. what is the combinatorial
diameter of the corresponding graph associahedron. In this paper we study the
relation between the structure of $\mathcal{R}(G)$ and $\mathcal{R}(G-S)$ for
a particular choice of $S\subseteq E(G)$. More specifically, we show that if
$W$ is a set of true twins in $G$ and $S$ is the set of edges in $G$ with both
endpoints in $W$, then $\mathcal{R}(G-S)$ is a quotient graph of
$\mathcal{R}(G)$. We also give a lower bound for
$\textnormal{diam}(\mathcal{R}(G-S))$ in terms of
$\textnormal{diam}(\mathcal{R}(G))$. As a consequence, we obtain a new lower
bound for the diameter of the graph associahedra of balanced complete
bipartite graphs that allow us to compute the exact value of
$\textnormal{diam}(\mathcal{R}(K_{2,q}))$ for $q\in\\{3,4,5,6,7,8\\}$.

##  1 Introduction

The concept of graph associahedra, as introduced by Carr and Devadoss [6],
includes and generalizes several well-known families of polytopes; when $G$ is
a path, a cycle, a complete graph or a star, then the graph associahedron
$\mathcal{A}(G)$ of $G$ is the classical associahedron, cyclohedron,
permutohedron and stellohedron, respectively.

The polytope $\mathcal{A}(G)$ encodes the combinatorial structure of certain
decompositions of the graph $G$ into smaller connected graphs. Moreover, graph
associahedra find relevance beyond generalization since they provide a tool
for the study of combinatorial structures and their geometric representation,
finding applications in various domains including optimization [17],
hierarchical visualization systems [16], random structure generation [7], and
probabilistic methods [11]. Additionally, they hold significance in algebra
and physics as specific instances of generalized permutohedra [1, 13].

The graph determined by the 1-skeleton of $\mathcal{A}(G)$ can be understood
as the rotation graph of a connected graph $G$, that is, the graph
$\mathcal{R}(G)$ whose vertices are the search trees on $G$ and whose edges
are determined by rotations on the search trees [6, 8, 12]. Due to the
diversity of its applications, the properties of the rotation graph have been
widely considered in the literature. A problem that has sparked particular
interest is determining the combinatorial diameter of the polytope
$\mathcal{A}(G)$ or, equivalently, the diameter of $\mathcal{R}(G)$, denoted
$\textnormal{diam}(\mathcal{R}(G))$. The diameter of graph associahedra of
paths [14], cycles [15] and trees [2] has been studied. In addition, in [3]
Cardinal, Pournin and Valencia-Pabon give bounds for the diameter of
associahedra of chordal graphs and trivially perfect graphs, among others.
Moreover, they give the exact value of the diameter of associahedra of split
complete graphs $\textnormal{SPK}_{p,q}$ for all $p,q\in\mathbb{N}$ and for
complete bipartite graphs $K_{p,q}$ for $p,q\in\mathbb{N}$ such that $q\geq
4p+1$. They call the latter graphs unbalanced complete bipartite graphs. They
also pose the question for the balanced case, that is for values $p,q$ such
that $\frac{p}{4}\leq q\leq 4p$. This question has not been settled to this
day and studying it even for small values of $p$ and $q$ is not an easy task.
As a matter of fact, in [5, 9] the authors proved that finding a shortest path
between vertices of $\mathcal{R}(G)$ is NP-hard. Furthermore, it is easy to
see that

$|V(\mathcal{R}(K_{p,q}))|=\sum_{k=1}^{p}\binom{p}{k}q(p+q-k-1)!+\sum_{k=1}^{q}\binom{q}{k}p(p+q-k-1)!$

and that

$2|E(\mathcal{R}(K_{p,q}))|=(p+q-1)|V(\mathcal{R}(K_{p,q}))|.$

Thus, even for the smallest value of $p$ not settled in [3], i.e. $p=2$ and
$q\leq 8$, we can get a high number of vertices and edges, as shown in Table
1.

G | $|V(\mathcal{R}(G)|$ | $|E(\mathcal{R}(G))|$
---|---|---
$K_{2,3}$ | 92 | 184
$K_{2,4}$ | 498 | 1245
$K_{2,5}$ | 3142 | 9426
$K_{2,6}$ | 22766 | 79681
$K_{2,7}$ | 186762 | 747048
$K_{2,8}$ | 1713298 | 7709841
Table 1: Number of vertices and edges in $\mathcal{R}(K_{2,q})$ for
$q\in\\{3,4,5,6,7,8\\}$.

Here we consider connected graphs $G$ with a subset of vertices $W\subseteq
V(G)$ such that for every $u,v\in W$, $u$ and $v$ are true twins. In this case
we say that $W$ is a set of true twins (recall that for a vertex $x\in V(G)$,
the closed neighbourhood of $x$ is $N[x]=\\{w\in V(G)\mid xw\in
E(G)\\}\cup\\{x\\}$ and that $u,v\in V(G)$ are true twins if $N[u]=N[v]$). In
Section 2 we present the fundamental notions regarding graph associahedra and
rotation graphs, and present preliminary results that are used throughout the
text. In Section 3 we show that if $S$ is the set of edges in the subgraph
$G[W]$ of $G$ induced by $W$, then $\mathcal{R}(G-S)$ is a quotient graph of
$\mathcal{R}(G)$, where $G-S$ denotes the graph obtained from $G$ by removing
all the edges in $G$. Furthermore, we derive that

$\textnormal{diam}(\mathcal{R}(G))-\binom{|W|}{2}\leq\textnormal{diam}(\mathcal{R}(G-S)).$

In Section 4 we use this lower bound to compute the exact value of the
complete bipartite graph $K_{2,q}$ for $q=3,4,5,6,7$.

##  2 Graph associahedra and rotation graphs

For a connected graph $G$, the definition of the graph associahedron
$\mathcal{A}(G)$ of $G$ is given in [6] in terms of tubings of $G$. A tube $t$
in $G$ is a subset $t\subseteq V(G)$ that induces a connected subgraph of $G$.
Two tubes, $t$ and $t^{\prime}$, are nested whenever $t\subseteq t^{\prime}$
(or $t^{\prime}\subseteq t$) and they are non-adjacent whenever $t\cup
t^{\prime}$ induces a disconnected subgraph of $G$. A tubing $\mathcal{T}$ on
$G$ is a collection of tubes in $G$ such that every pair of tubes in
$\mathcal{T}$ are either nested or non-adjacent. $\mathcal{A}(G)$ is the
convex polytope whose face poset is isomorphic to the set of tubings of $G$
ordered by inclusion [6]. Since inclusionwise maximal tubings of $G$ (vertices
of the polytope) correspond to search trees on $G$ and flips in a maximal
tubing correspond to rotations on search trees [2], then the 1-skeleton of
$\mathcal{A}(G)$ has an interpretation as the rotation graph $\mathcal{R}(G)$
of $G$.

We describe $\mathcal{R}(G)$ directly in terms of search trees on $G$ and
rotations. A search tree $T$ on $G$ is a rooted tree with vertex set $V(G)$
defined recursively as follows. The root of $T$ is a vertex $r\in V(G)$ and
the children of $r$ are the roots of search trees on each connected component
of $G-r$ [3].

Notice that a search tree $T$ on $G$ can be obtained by succesively deleting
the vertices of $G$ following an elimination order given by a permutation of
$V(G)$. For this reason the search trees on $G$ are also known as elimination
trees. Notice that different eliminations orders may result in the same
elimination tree. Figure 1 shows three search trees on the split complete
graph $\textnormal{SPK}_{3,3}$. $R$ and $S$ are determined by unique
elimination orders $y_{1},y_{2},y_{3},x_{1},x_{2},x_{3}$ and
$y_{1},y_{2},y_{3},x_{1},x_{3},x_{2}$ respectively. On the other hand, $T$ is
determined by two elimination orders, $x_{1},y_{1},x_{2},x_{3},y_{2},y_{3}$
and $x_{1},y_{1},x_{2},x_{3},y_{3},y_{2}$.

$x_{1}$$x_{2}$$x_{3}$$y_{1}$$y_{2}$$y_{3}$$\textnormal{SPK}_{3,3}$

$y_{1}$$y_{2}$$y_{3}$$x_{1}$$x_{2}$$x_{3}$$R$

$y_{1}$$y_{2}$$y_{3}$$x_{1}$$x_{3}$$x_{2}$$S$

$x_{1}$$y_{1}$$x_{2}$$x_{3}$$y_{2}$$y_{3}$$T$

Figure 1: Three search trees on $\textnormal{SPK}_{3,3}$.

If $T$ is a rooted tree and $c\in V(T)$, we denote $T|c$ the subtree of $T$
rooted in $c$. If $p$ is the parent of $c$ in $T$, we say that $T|c$ is a
subtree of $p$.

A search tree $T$ on $G$ can be locally modified by the operation of rotation
as follows. Given $u,v\in V(T)$ such that $v$ is a child of $u$ in $T$, the
rotation of $u$ and $v$ (or $uv$-rotation) in $T$ produces a search tree
$T^{\prime}$ on $G$ where

  1. (i)

$u$ is a child of $v$, and $v$ a child of $p$, where $p$ is the parent of $u$
in $T$;

  2. (ii)

for every subtree $S$ of $u$ in $T$, if $S\neq T|v$ then $S$ is a subtree of
$u$ in $T^{\prime}$;

  3. (iii)

for every subtree $S$ of $v$ in $T$, if $u$ is adjacent to a vertex of $S$ in
$G$, then $S$ is a subtree of $u$ in $T^{\prime}$; otherwise, $S$ is a subtree
of $v$ in $T^{\prime}$.

In Figure 1, $R$ and $S$ differ by an $x_{2}x_{3}$-rotation.

As mentioned, for a connected graph $G$ the rotation graph $\mathcal{R}(G)$ of
$G$ is the graph whose vertex set is the set of all the search trees on $G$
and where two search trees are adjacent if they differ by one rotation. Figure
2 shows the rotation graph of the complete graph $K_{4}$ ($1$-skeleton of the
permutohedron on $4$ vertices) and the rotation graph of the complete split
graph $\textnormal{SPK}_{2,2}$. In this figure we denote
$a_{1}a_{2}a_{3}a_{4}$ to the search tree that is a path with consecutive
vertices $a_{1},a_{2},a_{3},a_{4}$ rooted at $a_{1}$. In addition, $U$ is the
search tree on $\textnormal{SPK}_{2,2}$ that consists in a path 1,2, rooted at
1 and with 2 adjacent to the leaves 3 and 4. Similarly, $V$ is the search tree
on $\textnormal{SPK}_{2,2}$ that consists in a path 2,1, rooted at 2 and with
1 adjacent to the leaves 3 and 4. Figure 3 depicts the search trees $U$ and
$V$.

$1$$3$$2$$4$$K_{4}$

$1$$3$$2$$4$$\textnormal{SPK}_{2,2}$

321423142341324134213412431243214231243124134213412341321432142313423142312413241234213421431243
(a) $\mathcal{R}(K_{4})$

32142314234132413421341243124321423124312413421341234132143214231342314231241324$U$$V$
(b) $\mathcal{R}(\textnormal{SPK}_{2,2})$

Figure 2: Rotation graphs.

By definition of $\mathcal{R}(G)$, when referring to a search tree $T$ on $G$,
we often write $T\in V(\mathcal{R}(G))$. Also, a sequence of rotations that
transform a search tree $T$ on $G$ into another $T^{\prime}$ determines a
$TT^{\prime}$-walk in $\mathcal{R}(G)$, that is, a sequence of vertices
$T=T_{0},T_{1},\ldots,T_{k}=T^{\prime}$ in $\mathcal{R}(G)$ such that two
consecutive are adjacent. Similarly, a $TT^{\prime}$-path in $\mathcal{R}(G)$
is a $TT^{\prime}$-walk with distinct vertices. The rotation distance between
search trees $T,T^{\prime}$ on $G$ is the minimum number of rotations required
to transform $T$ into $T^{\prime}$, that is, the distance
$\textnormal{d}_{R(G)}(T,T^{\prime})$ in $\mathcal{R}(G)$ between $T$ and
$T^{\prime}$.

If $T\in V(\mathcal{R}(G))$, a branch in $T$ is a path in $T$ from the root to
a leaf of $T$. If $u,v$ are two vertices such that $u$ belongs to the path in
$T$ from the root to $v$, then $u$ is an ancestor of $v$ and $v$ is a
descendant of $u$. If $T,T^{\prime}\in V(\mathcal{R}(G))$ and $u,v\in V(G)$
are vertices such that $u$ is an ancestor of $v$ in $T$ and a descendant of
$v$ in $T^{\prime}$, then we say that $u,v$ have different relative order in
$T$ and $T^{\prime}$. If $u$ is an ancestor (alternatively descendant) of $v$
in both $T$ and $T^{\prime}$, then we say that $u,v$ have the same relative
order in $T$ and $T^{\prime}$.

Next, we present a proposition regarding the relation between adjacency in a
graph $G$ and properties of sequences of rotations in $\mathcal{R}(G)$ that
will be useful in the subsequent discussions.

######  Proposition 2.1.

Let $G$ be a connected graph and $u,v\in V(G)$.

  1. (a)

$u$ and $v$ are adjacent in $G$ if and only if for every $T\in
V(\mathcal{R}(G))$, $u$ and $v$ are in the same branch in $T$.

  2. (b)

Suppose $u$ and $v$ are adjacent in $G$ and let $T,T^{\prime}\in
V(\mathcal{R}(G))$. Then, $u$ and $v$ have different relative order in $T$ and
$T^{\prime}$ if and only if any sequence of rotations that transforms $T$ into
$T^{\prime}$ has an odd number of $uv$-rotations.

  3. (c)

If $u$ and $v$ are true twins in $G$ and $T,T^{\prime}\in V(\mathcal{R}(G))$,
then every minimum length $TT^{\prime}$-path in $\mathcal{R}(G)$ has exactly
one edge determined by an $uv$-rotation if $u$ and $v$ have different relative
orders in $T$ and in $T^{\prime}$, and no edge determined by $uv$-rotations if
$u$ and $v$ have the same relative order in $T$ and in $T^{\prime}$.

###### Proof.

($a$) Let $T$ be a search tree on $G$. Suppose that $|V(G)|=n$ and $T$ is
obtained following an elimination order $v_{1},v_{2},\ldots,v_{n}$ of its
vertices. Let $i,j\in\mathbb{N}$ such that $u=v_{i}$ and $v=v_{j}$. Assume
$i\leq j$. If $u$ and $v$ are adjacent in $G$, they are in the same connected
component of $G-\\{v_{1},\ldots,v_{i-1}\\}$. Let $C$ be the connected
component of $v$ in $G-\\{v_{1},\ldots,v_{i-1},u\\}$. Then $T[C]$ is a subtree
of $u$ in $T$ that contains $v$. Hence $v$ is a descendant of $u$.
Analogously, if $i\geq j$, $u$ is a descendant of $v$. Therefore $u$ and $v$
are in the same branch in $T$.

Conversely, if $u$ and $v$ are not adjacent in $G$, then in the search tree
obtained eliminating $u$ and $v$ in the last two steps, $u$ and $v$ are both
leaves. Hence, they are not in the same branch in $T$.

($b$) The result is a direct consequence of ($a$).

($c$) Let $T,T^{\prime}\in V(\mathcal{R}(G))$ and $A$ a minimum lenght
$TT^{\prime}$-path in $\mathcal{R}(G)$. Suppose $A$ has vertices
$T=T_{0},\ldots,T_{k}=T^{\prime}$ and that $T_{i}T_{i+1}$ are adjacent for
$i\in\\{0,\ldots,k-1\\}$.

Let $u,v\in V(G)$ be true twins in $G$ and assume two or more edges in $A$
correspond to $uv$-rotations. Let $i,j\in\\{0,\ldots,n-1\\}$ be indices such
that $i+1<j$, and that $T_{i},T_{i+1}$ and $T_{j}T_{j+1}$ are edges determined
by two of these rotations.

Consider $\rho:V(G)\rightarrow V(G)$ the function defined by $\rho(u)=v$,
$\rho(v)=u$ and $\rho(x)=x$ for every $x\in V(G)-\\{u,v\\}$. Notice that since
$u$ and $v$ are true twins in $G$, then $\rho$ is an isomorphism.
Additionally, for every $T\in V(\mathcal{R}(G))$, we denote by
$\rho^{\ast}(T)$ the rooted tree with vertex set $V(G)$ and edge set
$\\{\rho(x)\rho(y)\mid xy\in E(T)\\}$. Since $\rho$ is a graph isomorphism,
$\rho^{\ast}(T)$ is a search tree on $G$. Further notice that
$T_{i}=\rho^{\ast}(T_{i+1})$ and $T_{j+1}=\rho^{\ast}(T_{j})$.

We have that the search trees

$T=T_{0},\ldots,T_{i-1},\rho^{\ast}(T_{i+1}),\ldots,\rho^{\ast}(T_{j}),T_{j+2},\ldots,T_{k}=T^{\prime}$

form a $TT^{\prime}$-walk with exactly two edges (determined by
$uv$-rotations) less than $A$. This is absurd since $A$ has minimum length.

Therefore, $A$ has at most one edge corresponding to a $uv$-rotation. By item
(b), there is exactly one $uv$-rotation if $u$ and $v$ have different relative
order in $T$ and $T^{\prime}$, and zero otherwise. ∎

######  Remark 2.2.

The proof of item $(c)$ gives a procedure applicable to a $TT^{\prime}$-path
$A$ in $\mathcal{R}(G)$, that allows to choose two edges determined by
$uv$-rotations and to construct a new $TT^{\prime}$-walk without those
particular edges.

##  3 Associahedra of graphs with a set of true twins

Let $G$ be a connected graph and suppose $G$ has a set of true twins
$W\subseteq V(G)$. In this section we prove that $\mathcal{R}(G-S)$ is a
quotient graph of $\mathcal{R}(G)$, where $S=E(G[W])$. Recall that an
equivalence relation $\sim$ (or a partition) on $V(G)$ determines a quotient
graph $Q$ of $G$ whose vertex set is $V(Q)=V(G)/\sim$ and where two
equivalence classes $[u],[v]$ are adjacent in $Q$ if and only if $u,v$ are
adjacent in $G$. For graphs $G$ and $H$, we say that a function $q\colon
V(G)\rightarrow V(H)$ is a quotient map if for every $uv\in E(G)$,
$q(u)q(v)\in E(H)$ or $q(u)=q(v)$. Notice that if $H$ is a quotient graph of
$G$ determined by an equivalence relation $\sim$, then

$\displaystyle q:V(G)$ $\displaystyle\rightarrow V(H)=V(G)/\sim$
$\displaystyle u$ $\displaystyle\mapsto[u]$

is a quotient map. Conversely, if $q:V(G)\rightarrow V(H)$ is a quotient map
then $q(G)$ is a quotient graph determined by an equivalence relation $\sim$
given by $u\sim v\iff q(u)=q(v)$.

Thus, in order to show that $\mathcal{R}(G-S)$ is a quotient graph of
$\mathcal{R}(G)$, we define a map $\pi:V(\mathcal{R}(G))\rightarrow
V(\mathcal{R}(G-S))$ and show that it is a quotient map.

By Proposition 2.1(a), if $T$ is a search tree on $G$ then all the vertices of
$W$ are in the same branch of $T$. We distinguish some search trees according
to the disposition of the vertices of $W$ in such a branch, in the following
definition.

We say that $T\in V(\mathcal{R}(G))$ is $W$-special if there exists a unique
subset $L_{T}$ of $W$ with $|L_{T}|\geq 2$ and such that $T[L_{T}]$ is a path
with an endpoint adjacent in $T$ to a vertex $q_{T}$ of $V(G)-W$, and the
other endpoint is a leaf of $T$. In addition, we say that $TT^{\prime}\in
E(\mathcal{R}(G))$ is a $W$-special edge if $T$ and $T^{\prime}$ are
$W$-special search trees on $G$ such that $L_{T}=L_{T^{\prime}}$ and the
adjacency is determined by a rotation of a pair of vertices from $L_{T}$.

In Figure 1, $W=\\{x_{1},x_{2},x_{3}\\}$ is a set of true twins in
$\textnormal{SPK}_{3,3}$, the search trees $R$ and $S$ on $G$ are $W$-special
and $T$ is not $W$-special. In addition, $L_{R}=L_{S}=W$, $q_{R}=q_{S}=y_{3}$,
$R$ and $S$ are adjacent in $\mathcal{R}(G)$ and $RS$ is a $W$-special edge.

Let $S=E(G[W])$ and let $\pi\colon V(\mathcal{R}(G))\rightarrow
V(\mathcal{R}(G-S))$ be the map defined by

$\pi(T)=\begin{cases}T_{\land},\quad\textnormal{ if $T$ is a $W$-special
search tree,}\\\ T,\quad\textnormal{ otherwise}.\end{cases}$

where $T_{\land}$ is the search tree on $G-S$ such that
$T-L_{T}=T_{\land}-L_{T}$ and all vertices from $L_{T}$ are leaves in
$T_{\land}$ with common parent $q_{T}$. Observe that $T_{\land}$ can be
obtained following the elimination order that determines $T$.

Figure 3 shows search trees $U_{1}$, $U_{2}$, $V_{1}$, $V_{2}$ on $K_{4}$ such
that $\pi(U_{1})=\pi(U_{2})$ and $\pi(V_{1})=\pi(V_{2})$.

$1$$2$$4$$3$$U_{2}$$1$$2$$3$$4$$U_{1}$$\pi$$\pi$$1$$2$$3$$4$$U$$1$$2$$4$$3$$V_{2}$$1$$2$$3$$4$$V_{1}$$\pi$$\pi$$1$$2$$3$$4$$V$
Figure 3: Four search trees on $K_{4}$, and their images through $\pi$ on
$\textnormal{SPK}_{2,2}$.

######  Proposition 3.1.

Let $G$ be a connected graph and $W\subseteq V(G)$ a set of true twins. Then
$\mathcal{R}(G-S)$ is a quotient graph of $\mathcal{R}(G)$, where $S=E(G[W])$.

###### Proof.

We show that the function $\pi$ previously defined is a quotient map, i.e.
that for every $TT^{\prime}\in E(\mathcal{R}(G))$, $\pi(T)\pi(T^{\prime})\in
E(\mathcal{R}(G-S))$ or $\pi(T)=\pi(T^{\prime})$.

Let $TT^{\prime}\in E(\mathcal{R}(G))$. Suppose $T$ is a $W$-special search
tree.

Assume first that $T^{\prime}$ is also a $W$-special search tree with
$L_{T}=L_{T^{\prime}}$ and $q_{T}=q_{T^{\prime}}$. If $T$ and $T^{\prime}$
differ by a rotation that involves two vertices of $L_{T}$, then
$\pi(T)=T_{\land}=T^{\prime}_{\land}=\pi(T^{\prime})$. If $T$ and $T^{\prime}$
differ by a rotation of two vertices that are not in $L_{T}$, then $\pi(T)$
and $\pi(T^{\prime})$ differ by the rotation of the same pair and therefore
they are adjacent in $\mathcal{R}(G-S)$.

Now, if $T^{\prime}$ is a $W$-special search tree such that $L_{T}\neq
L_{T^{\prime}}$, or if $T^{\prime}$ is not $W$-special, then $T$ and
$T^{\prime}$ differ by a rotation that involves $q_{T}$, and moreover $\pi(T)$
and $\pi(T^{\prime})$ differ by the rotation of the same pair of vertices.
Thus, $\pi(T)$ and $\pi(T^{\prime})$ are adjacent in $\mathcal{R}(G-S)$.

Finally, if $T$ and $T^{\prime}$ are not $W$-special, then $\pi(T)=T$ and
$\pi(T^{\prime})=T^{\prime}$ differ by one rotation and therefore they are
adjacent in $\mathcal{R}(G-S)$.

Hence, $\pi$ is a quotient map. ∎

In the following remark we state a particular property of the map $\pi$.

######  Remark 3.2.

Let $G$ be a connected graph, $W\subseteq V(G)$ a set of true twins and
$S=E(G[W])$. Let $\widetilde{T}\in V(\mathcal{R}(G-S))$. If there exists
$L\subseteq W$ such that $|L|\geq 2$ and every $l\in L$ is a leaf of
$\widetilde{T}$ with a common parent $q\in V(G)-W$, then the subgraph of
$\mathcal{R}(G)$ induced by $\pi^{-1}(\widetilde{T})$ is isomorphic to
$\mathcal{R}(K_{|L|})$. Otherwise, $\pi^{-1}(\widetilde{T})$ has a single
element.

Notice that $\mathcal{R}(G-S)$ is isomorphic to the graph obtained from
$\mathcal{R}(G)$ after applying several edge contractions of $W$-special
edges. In addition, if $T,T^{\prime}\in V(\mathcal{R}(G))$, from Proposition
2.1 we known that in any minimum $TT^{\prime}$-path there are at most
$\binom{|W|}{2}$ $W$-special edges. Combining this fact and previous remark we
can set the following result.

######  Lemma 3.3.

Let $G$ be a connected graph, $W\subseteq V(G)$ a set of true twins such that
$|W|\geq 2$ and $S=E(G[W])$. Let $T,T^{\prime}\in V(\mathcal{R}(G))$ and
$\widetilde{A}$ a $\pi(T)\pi(T^{\prime})$-path in $\mathcal{R}(G-S)$. Then,
there exists a $TT^{\prime}$-path $A$ in $\mathcal{R}(G)$ such that

$\textnormal{len}(A)\leq\textnormal{len}(\widetilde{A})+\binom{|W|}{2}.$

###### Proof.

Assume first that $\pi(T)\neq\pi(T^{\prime})$ and let $\widetilde{A}$ be a
$\pi(T)\pi(T^{\prime})$-path in $\mathcal{R}(G-S)$. Suppose that
$\widetilde{A}$ consists in a sequence of vertices
$\pi(T)=\widetilde{T}_{0},\widetilde{T}_{1},\ldots,\widetilde{T}_{n}=\pi(T^{\prime})$
for some $n\geq 1$ and that for $i\in\\{0,\ldots,n-1\\}$,
$\widetilde{T}_{i+1}$ is obtained from $\widetilde{T}_{i}$ by a
$u_{i}v_{i}$-rotation, for some $u_{i},v_{i}\in V(G)$ adjacent vertices in
$\widetilde{T}_{i}$.

For every $i\in\\{0,\ldots,n-1\\}$, let $T_{i}\in\pi^{-1}(\widetilde{T}_{i})$
such that $u_{i}$ and $v_{i}$ are adjacent in $T_{i}$. By making an
$u_{i}v_{i}$-rotation on $T_{i}$ we obtain
$T^{\prime}_{i+1}\in\pi^{-1}(\widetilde{T}_{i+1})$. Let $B_{i+1}$ a (possibly
trivial) $T^{\prime}_{i+1}T_{i+1}$-path in the subgraph of $\mathcal{R}(G)$
induced by $\pi^{-1}(\widetilde{T}_{i+1})$ (recall that such a path exists by
Remark 3.2).

The concatenation of the paths $B_{i}$ (whose edges are $W$-special edges) and
the $u_{i}v_{i}$-rotations for $i\in\\{0,\ldots,n-1\\}$ give a
$TT^{\prime}$-path $B$ in $\mathcal{R}(G)$. Thus, by Remark 2.2, we can
construct a path $A$ from $B$ by applying the process in item $(c)$ of
Proposition 2.1 between pairs of $uv$-rotations ($u,v\in W$) that determines
$W$-special edges. Moreover, the path $A$ has at most one more rotation for
each pair of vertices in $W$ (that correspond to $W$-special edges), and
therefore $A$ has length at most
$n+\binom{|W|}{2}=\textnormal{len}(\widetilde{A})+\binom{|W|}{2}$.

If $\pi(T)=\pi(T^{\prime})$, then $\widetilde{A}$ is a path of lenght $0$, and
by Remark 3.2 there exists a $TT^{\prime}$-path in $A$ of lenght at most
$\binom{|W|}{2}=\textnormal{diam}(\mathcal{R}(K_{|W|}))$. ∎

######  Remark 3.4.

In the previous proposition, the constructed path $A$ has the same number of
rotations that $\widetilde{A}$ plus at most one rotation between each pair of
vertices in $W$ (that corresponds to a $W$-special edge). The length of the
path $A$ is increased with respect to the length of $\widetilde{A}$ by
rotations of pairs of vertices from $W$.

######  Theorem 3.5.

Let $G$ be a connected graph and let $W\subseteq V(G)$ be a set of true twins
in $G$ such that $|W|\geq 2$. Let $S=E(G[W])$. Then

$\textnormal{diam}(\mathcal{R}(G))-\binom{|W|}{2}\leq\textnormal{diam}(\mathcal{R}(G-S)).$

###### Proof.

Let $T,T^{\prime}\in V(\mathcal{R}(G))$. Let $\widetilde{B}$ a
$\pi(T)\pi(T^{\prime})$-path in $\mathcal{R}(G-S)$ of minimum length. By Lemma
3.3, there exists $B$ a $TT^{\prime}$-path in $\mathcal{R}(G)$ such that

$\textnormal{len}(B)\leq\textnormal{len}(\widetilde{B})+\binom{|W|}{2}.$

Let $A$ be a $TT^{\prime}$-path in $\mathcal{R}(G)$ of minimum length. Then

$\displaystyle\textnormal{d}_{\mathcal{R}(G)}(T,T^{\prime})$
$\displaystyle=\textnormal{len}(A)$ $\displaystyle\leq\textnormal{len}(B)$
$\displaystyle\leq\textnormal{len}(\widetilde{B})+\binom{|W|}{2}$
$\displaystyle=\textnormal{d}_{\mathcal{R}(G-S)}(\pi(T),\pi(T^{\prime}))+\binom{|W|}{2}$
$\displaystyle\leq\textnormal{diam}(\mathcal{R}(G-S))+\binom{|W|}{2},$

and therefore

$\textnormal{diam}(\mathcal{R}(G))\leq\textnormal{diam}(\mathcal{R}(G-S))+\binom{|W|}{2}.$

∎

##  4 Application to diameter of associahedra of complete bipartite graphs

Given two positive integers $p$ and $q$, the complete split graph
$\textnormal{SPK}_{p,q}$ is the graph with vertex set $P\cup Q$, where
$P=\\{x_{1},\ldots,x_{p}\\},Q=\\{y_{1},\ldots,y_{q}\\}$, such that $P$ induces
a clique, $Q$ is an independent set and where $\\{x_{i},y_{j}\mid 1\leq i\leq
p,1\leq j\leq q\\}\subseteq E(\textnormal{SPK}{p,q})$. Note that the complete
bipartite graph $K_{p,q}$ is $\textnormal{SPK}_{p,q}-S$ where $S$ is the set
of edges with both endpoints in $P$. Since $P$ is a set of true twins in
$\textnormal{SPK}_{p,q}$, by Theorem 3.5,

$\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{p,q}))-\binom{p}{2}\leq\textnormal{diam}(\mathcal{R}(K_{p,q})).$
(1)

Cardinal et al. show in [3] that

$\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{p,q}))=\begin{dcases}2pq+\binom{p}{2}=2m-\binom{p}{2},\textnormal{
if }q\geq 4p+1\\\
pq+\left\lfloor\frac{1}{2}\binom{q}{2}\right\rfloor+\binom{p}{2},\textnormal{
otherwise.}\end{dcases}$

They also show that $\textnormal{diam}(\mathcal{R}(\textnormal{K}_{p,q}))=2pq$
if $q\geq 4p+1$, and give the following bounds for the case $\frac{p}{4}\leq
q\leq 4p$.

$\binom{q}{2}\leq\textnormal{diam}(\mathcal{R}(K_{p,q}))\leq 2pq.$ (2)

######  Remark 4.1.

  1. (a)

If $\frac{p}{4}\leq q\leq 4p$, the lower bound (1) translates as

$pq+\left\lfloor\frac{1}{2}\binom{q}{2}\right\rfloor\leq\textnormal{diam}(\mathcal{R}(K_{p,q})).$

Notice that

$pq+\left\lfloor\frac{1}{2}\binom{q}{2}\right\rfloor-\binom{q}{2}\geq
pq-\frac{1}{2}\binom{q}{2}-\frac{1}{2}\geq\frac{q^{2}}{4}-\frac{q(q-1)}{4}-\frac{1}{2}=\frac{q-2}{4}\geq
0$

since we can assume $q\geq 2$, as $\textnormal{SPK}_{p,1}$ is the complete
graph on $p+1$ vertices and $K_{p,1}$ is the split complete graph
$\textnormal{SPK}_{1,p}$, and the diameter of those graphs is known.

Thus, if $\max\\{\frac{p}{4},2\\}\leq q\leq 4p$, the lower bound given by
Theorem 3.5 is greater than or equal to the lower bound in (2).

  2. (b)

The lower bound given in Theorem 3.5 is sharp since for $p,q\in\mathbb{N}$
such that $q\geq 4p+1$,

$\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{p,q}))-\binom{p}{2}=2pq=\textnormal{diam}(K_{p,q}).$

In [3], the authors pose the question for the exact value of
$\textnormal{diam}(\mathcal{R}(K_{p,q}))$ for the balanced case, which has not
been settled to this day.

In the particular case where $p=2$, we obtain

$\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,q}))-1\leq\textnormal{diam}(\mathcal{R}(K_{2,q}))\leq\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,q})),$
(3)

where the second inequality holds since $K_{2,q}$ is a subgraph of
$\textnormal{SPK}_{2,q}$ [10].

That is, we have that

$\displaystyle 7$
$\displaystyle\leq\textnormal{diam}(\mathcal{R}(K_{2,3}))\leq 8$
$\displaystyle 11$
$\displaystyle\leq\textnormal{diam}(\mathcal{R}(K_{2,4}))\leq 12$
$\displaystyle 15$
$\displaystyle\leq\textnormal{diam}(\mathcal{R}(K_{2,5}))\leq 16$
$\displaystyle 19$
$\displaystyle\leq\textnormal{diam}(\mathcal{R}(K_{2,6}))\leq 20$
$\displaystyle 24$
$\displaystyle\leq\textnormal{diam}(\mathcal{R}(K_{2,7}))\leq 25$
$\displaystyle 30$
$\displaystyle\leq\textnormal{diam}(\mathcal{R}(K_{2,8}))\leq 31.$

We prove that

$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,3}))$ $\displaystyle=8$
$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,4}))$ $\displaystyle=11$
$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,5}))$ $\displaystyle=15$
$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,6}))$ $\displaystyle=20$
$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,7}))$ $\displaystyle=25$
$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,8}))$ $\displaystyle=30.$

Search trees on complete split graphs are called brooms, since they consist in
a path such that one of its endpoints is the root and the other is attached to
the leaves [3]. Said path is called the handle of the broom. Figure 1 shows
three brooms on $\textnormal{SPK}_{3,3}$.

First, we make some general considerations following [4]. Let $T,T^{\prime}\in
V(\mathcal{R}(K_{2,q}))$. For every $i=1,\ldots,q$, let $w_{i}$ be the number
of vertices of $P$ that are above of $y_{i}$ in $T$ and let $w^{\prime}_{i}$
be the number of vertices of $P$ that are above of $y_{i}$ in $T^{\prime}$. We
consider two $TT^{\prime}$-paths in $\mathcal{R}(K_{2,q})$. The first of them
consists in making every vertex of $Q$ in the handle of $T$ a leaf, using
exactly

$\sum_{i=1}^{q}(2-w_{i})=2q-\sum_{i=1}^{q}w_{i}$

rotations. Then rearrange the two vertices of $P$ in the handle if necessary,
using at most one rotation. Finally, take the vertices of $Q$ to their place
in $T^{\prime}$ using

$\sum_{i=1}^{q}(2-w^{\prime}_{i})=2q-\sum_{i=1}^{q}w^{\prime}_{i}$

rotations. This path has length at least

$1+4q-\sum_{i=1}^{q}w_{i}+w^{\prime}_{i}.$

The other path consists in making the vertices of $P$ leaves in $T$, using

$\sum_{i=1}^{q}w_{i}$

rotations. Analogously, it is possible to transform $T^{\prime}$ in a tree
with the vertices of $P$ as leaves, without making rotations between pairs of
vertices of $Q$, using

$\sum_{i=1}^{q}w^{\prime}_{i}$

rotations. Transforming one of these trees with the vertices of $Q$ in the
handle into the other, can be done using at most $\binom{q}{2}$ rotations.
Hence, this $TT^{\prime}$-path has length at most

$\binom{q}{2}+\sum_{i=1}^{q}w_{i}+w^{\prime}_{i}.$

Therefore,
$\textnormal{d}_{\mathcal{R}(K_{2,q})}(T,T^{\prime})\leq\min\left\\{1+4q-\Omega,\binom{q}{2}+\Omega\right\\}$,
where $\Omega=\sum_{i=1}^{q}w_{i}+w^{\prime}_{i}$. This bound is maximized
when $\Omega=2q-\frac{1}{2}\left[\binom{q}{2}-1\right]$, thus

$\textnormal{d}_{\mathcal{R}(K_{2,q})}(T,T^{\prime})\leq
2q+\frac{1}{2}\left[\binom{q}{2}+1\right].$

Now, for $q=4,5,8$ this upper bound is 11.5, 15.5, and 30.5, respectively,
yielding

$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,4}))$ $\displaystyle\leq 11$
$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,5}))$ $\displaystyle\leq 15$
$\displaystyle\textnormal{diam}(\mathcal{R}(K_{2,8}))$ $\displaystyle\leq 30.$

As in all these cases the upper bound coincides with the lower bound given in
(3), the equalities hold. For the remaining values of $q$, there exists a gap
of 1 between the lower and the upper bound. Therefore, a different strategy is
necessary to establish the exact value of the diameter.

We use the following lemma for establishing a relation between distances in
$\mathcal{R}(K_{2,q})$ and distances in $\mathcal{R}(\textnormal{SPK}_{2,q})$.

######  Lemma 4.2.

Let $G$ be a graph and $W=\\{u,v\\}\in V(G)$ such that $u$ and $v$ are true
twins. Let $T,T^{\prime}\in V(\mathcal{R}(G))$.

  1. (a)

If $\widetilde{A}$ is a $\pi(T)\pi(T^{\prime})$-path in $\mathcal{R}(G-uv)$,
there exists a $TT^{\prime}$-path $A$ in $\mathcal{R}(G)$ such that
$\textnormal{len}(\widetilde{A})\leq\textnormal{len}(A)\leq\textnormal{len}(\widetilde{A})+1$.
Additionally, if $\textnormal{len}(A)=\textnormal{len}(\widetilde{A})$, then
no edge of $A$ is a $W$-special edge, and if
$\textnormal{len}(A)=\textnormal{len}(\widetilde{A})+1$, then $A$ has exactly
one $W$-special edge.

  2. (b)

If there exists a $TT^{\prime}$-path of minimum length that has a $W$-special
edge, then

$\textnormal{d}_{\mathcal{R}(G-uv)}(\pi(T),\pi(T^{\prime}))=\textnormal{d}_{\mathcal{R}(G)}(T,T^{\prime})-1.$

Otherwise,
$\textnormal{d}_{\mathcal{R}(G-uv)}(\pi(T),\pi(T^{\prime}))=\textnormal{d}_{\mathcal{R}(G)}(T,T^{\prime})$.

###### Proof.

($a$) It is a direct consequence of Lemma 3.3 and Remark 3.4.

($b$) Let $T,T^{\prime}\in V(\mathcal{R}(G))$ and let $A$ be a minimum length
$TT^{\prime}$-path. If $A$ has consecutive vertices
$T_{0},T_{1},\ldots,T_{k}$, we denote $\pi(A)$ as the path in
$\mathcal{R}(G-S)$ with vertex set $\\{\pi(T_{i})\mid i\in\\{0,\ldots,k\\}\\}$
and with edges $\pi(T_{i})\pi(T_{i+1})$ for $i\in\\{0,\ldots,k-1\\}$ such that
$\pi(T_{i})\neq\pi(T_{i+1})$.

Suppose that $A$ has (exactly) one $W$-special edge. Then
$\textnormal{len}(\pi(A))=\textnormal{len}(A)-1$. Assume that there exists a
shorter $\pi(T)\pi(T^{\prime})$-path $\widetilde{A}_{0}$. We construct a path
$A_{0}$ in $\mathcal{R}(G)$, as in item ($a$), such that
$\textnormal{len}(A_{0})\leq\textnormal{len}(\widetilde{A}_{0})+1$. Hence,
$\textnormal{len}(A_{0})\leq\textnormal{len}(\widetilde{A}_{0})+1<\textnormal{len}(\pi(A))+1=\textnormal{len}(A)$.
But this is a contradiction, since $A$ had minimum length. Therefore,
$\textnormal{d}_{\mathcal{R}(G-uv)}(\pi(T),\pi(T^{\prime}))=\textnormal{len}(\pi(A))=\textnormal{len}(A)-1=\textnormal{d}_{\mathcal{R}(G)}(T,T^{\prime})-1$.

Now suppose that no $TT^{\prime}$-path of minimum length has a $W$-special
edge. We have that $\pi(A)$ is a $\pi(T)\pi(T^{\prime})$-path in
$\mathcal{R}(G-uv)$, and that, by definition of $\pi$,
$\textnormal{len}(\pi(A))=\textnormal{len}(A)$. Suppose there exists a shorter
$\pi(T)\pi(T^{\prime})$-path $\widetilde{A}_{0}$. We construct a path $A_{0}$
in $\mathcal{R}(G)$, as in item ($a$), such that
$\textnormal{len}(A_{0})\leq\textnormal{len}(\widetilde{A}_{0})+1$. Then
$\textnormal{len}(A_{0})\leq\textnormal{len}(\widetilde{A}_{0})+1<\textnormal{len}(\pi(A))+1=\textnormal{len}(A)+1$.
Hence, $\textnormal{len}(A_{0})\leq\textnormal{len}(A)$, but since $A$ is of
minimum length, $\textnormal{len}(A_{0})=\textnormal{len}(A)$. Then, by the
supposition at the beginning of the paragraph, $A_{0}$ has no $W$-special edge
and thus $\textnormal{len}(A_{0})=\textnormal{len}(\widetilde{A}_{0})$ by item
($a$), with
$\textnormal{len}(\widetilde{A}_{0})<\textnormal{len}(\pi(A))=\textnormal{len}(A)$.
This is a contradiction, since $A$ had minimum length. Therefore,
$\textnormal{d}_{\mathcal{R}(G-uv)}(\pi(T),\pi(T^{\prime}))=\textnormal{len}(\pi(A))=\textnormal{len}(A)=\textnormal{d}_{\mathcal{R}(G)}(T,T^{\prime})$.
∎

In order to compute the diameter of $\mathcal{R}(K_{2,q})$ for $q=3,6,7$, in
every case we follow a similar strategy. We give a pair of trees
$T,T^{\prime}\in V(\mathcal{R}(\textnormal{SPK}_{2,q}))$ such that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,q})}(T,T^{\prime})=\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,q}))$
and we prove that no path of minimum length between them has a
$x_{1}x_{2}$-rotation (the true twin vertices in the graph). We then apply
Lemma 4.2, to obtain that
$\textnormal{d}_{\mathcal{R}(K_{2,q})}(\pi(T),\pi(T^{\prime}))=\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,q})}(T,T^{\prime})=\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,q}))$.
This gives the lower bound
$\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,q}))\leq\textnormal{diam}(\mathcal{R}(K_{2,q}))$.
We also have, since $K_{2,q}\subseteq\textnormal{SPK}_{2,q}$, the upper bound
$\textnormal{diam}(\mathcal{R}(K_{2,q}))\leq\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,q}))$.
The equalities follow.

We prove first that $\textnormal{diam}(\mathcal{R}(K_{2,3}))=8$. Recall that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,3})}(T,T^{\prime})\leq\textnormal{diam}(\textnormal{SPK}_{2,3})=8$.
Let us see that for the search trees $T,T^{\prime}$ on
$\textnormal{SPK}_{2,3}$ shown in Figure 4,
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,3})}(T,T^{\prime})=8$.

$y_{1}$$x_{1}$$y_{2}$$x_{2}$$y_{3}$$T$

$y_{3}$$y_{2}$$x_{2}$$x_{1}$$y_{1}$$T^{\prime}$

Figure 4: Two search trees on $\textnormal{SPK}_{2,3}$.

To show that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,3})}(T,T^{\prime})\geq 8$,
consider a sequence of rotations that transforms $T$ into $T^{\prime}$. By
Proposition 2.1(b), in this sequence there must be at least one
$x_{1}x_{2}$-rotation, one $y_{1}x_{i}$-rotation and one $y_{3}x_{i}$-rotation
for $i=1,2$, since these pairs of vertices are adjacent and have different
relative order in $T$ and $T^{\prime}$. Then, this sequence has at least 5
rotations.

On the other hand, it can be the case that $y_{2}$ is a leaf of some broom in
the sequence or not. In the first case, there must be a rotation with $x_{2}$
(going down), and then rotations with $x_{1}$ and $x_{2}$ (going back up)
$T^{\prime}$. In the second case, there are rotations with $x_{1}$, $y_{1}$
and $y_{3}$ since they have different order in $T$ and $T^{\prime}$. In both
cases, at least three more rotations are needed.

Thus, if $A$ is a $TT^{\prime}$-path, then $\textnormal{len}(A)\geq 8$, which
implies
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,3})}(T,T^{\prime})\geq 8$.
Therefore
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,3})}(T,T^{\prime})=8$.
Denoting by $k$ the number of vertices of $Q$ that are leaves in any of the
brooms in the sequence, these 8 necessary rotations are listed in Table 2.

Vertices involved | Effect of rotation | No. of rotations
---|---|---
$x_{1},x_{2}$ | exchange | 1
$y_{1}$ with $x_{1},x_{2}$ |  $y_{1}$ leaf goes down | 2
$y_{3}$ with $x_{1},x_{2}$ |  $y_{3}$ leaf goes up | 2
Case $k=2$
$y_{2}$ with $y_{1},y_{3}$ |  $y_{2}$ exchange within handle | 2
$x_{1},y_{2}$ | exchange within handle | 1
Case $k=3$
$y_{2},x_{2}$ |  $y_{2}$ leaf goes down | 1
$y_{2}$ with $x_{1},x_{2}$ |  $y_{2}$ leaf goes up | 2
Table 2: Necessary rotations in a sequence that transforms $T$ into
$T^{\prime}$.

We show now that no $TT^{\prime}$-path of minimum length in
$\mathcal{R}(\textnormal{SPK}_{2,3})$ has a $x_{1}x_{2}$-rotation. This,
together with Lemma 4.2 allows to conclude that
$\textnormal{d}_{\mathcal{R}(K_{2,3})}(T,T^{\prime})=8$.

Suppose there were a minimum length path containing a $P$-special edge.

Note that $y_{3}$ is a leaf in the first tree of the sequence, before the
occurrence of this $P$-special edge, and $y_{1}$ is a leaf in a tree that is
after the special edge in the sequence. If $y_{1}$ and $y_{3}$ are not
simultaneously leaves in any tree of the sequence, then there must be a
rotation $y_{1}y_{3}$ (in the handle of a broom), not counted in Table 2. Then
this path would not be optimum. It follows that $y_{1}$ and $y_{3}$ are
simultaneously leaves in some tree of the path.

But, if $y_{3}$ is again a leaf after the special edge, that would require two
additional rotations (between the pairs $x_{1}y_{3}$, $x_{2}y_{3}$), not
counted in Table 2. Analogously, if $y_{1}$ were a leaf in some tree of the
sequence before the special edge, that would require two additional rotations.
Thus, such a sequence would not be optimal.

Therefore no $TT^{\prime}$-path in $\mathcal{R}(\textnormal{SPK}_{2,3})$ has a
$P$-special edge.

It follows that
$\textnormal{diam}(\mathcal{R}(K_{2,3}))=\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,3}))=8$.

We show now that $\textnormal{diam}(\mathcal{R}(K_{2,6}))=20$.

Consider $T,T^{\prime}$ the search trees on $\textnormal{SPK}_{2,6}$ shown in
Figure 5.

$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x_{1}$$y_{5}$$x_{2}$$y_{6}$$T$

$y_{6}$$y_{5}$$y_{4}$$y_{3}$$y_{2}$$x_{2}$$x_{1}$$y_{1}$$T^{\prime}$

Figure 5: Two search trees on $\textnormal{SPK}_{2,6}$.

Recall that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,6})}(T,T^{\prime})\leq\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,6}))=20$.

We show that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,6})}(T,T^{\prime})\geq 20$.
Consider a path in $\mathcal{R}(\textnormal{SPK}_{2,6})$ from $T$ to
$T^{\prime}$. Let $L\subseteq Q$ the set of vertices of $Q$ that are leaves in
some tree of the path. Let $k=|L|$. In this path the rotations in Table 3 are
necessary.

No. of rotations | Description
---|---
1 |  exchange $x_{1}x_{2}$
$\alpha+2(k-2)$ |  leaves go down, $\alpha=\begin{cases}1\quad\textnormal{if }y_{5}\in L\\\ 2\quad\textnormal{if }y_{5}\notin L\end{cases}$
$\binom{6-k}{2}$ |  sort vertices of $Q$ within the handle
$k(6-k)$ | leaves non-leaves rotations
$2(k-1)$ | leaves go up
$\beta$ | $\beta=\begin{cases}0\quad\textnormal{if }y_{5}\in L\\\ 1\quad\textnormal{if }y_{5}\notin L\quad(y_{5}x_{1})\end{cases}$
Table 3: Necessary rotations in a sequence that transforms $T$ into
$T^{\prime}$.

Then, the length of this path is at least

$1+\gamma+2(k-2)+\binom{6-k}{2}+k(6-k)+2(k-1),$

where $\gamma=\alpha+\beta=\begin{cases}1\quad\textnormal{if }y_{5}\in L\\\
3\quad\textnormal{if }y_{5}\notin L.\end{cases}$

Note that this expression is a concave function of $k$, reaching its minimum
value for $k=2$ or $k=6$. Evaluating in those values of $k$, we obtain 20 and
22 respectively (note that if $k=2$, $y_{5}\notin L$). It follows that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,6})}(T,T^{\prime})\geq 20$,
and therefore
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,6})}(T,T^{\prime})=20$.

Similarly to the case $q=3$, we have that if $y_{6}$ is a leaf again after the
occurrence of a $P$-special edge, (or $y_{1}$ is a leaf before) this requires
two additional rotations (with $x_{1}$ and $x_{2}$), apart from the at least
20 rotations counted in Table 3.

If a $TT^{\prime}$-path has a $P$-special edge and the vertices $y_{1}$ and
$y_{6}$ are simultaneously leaves in some tree of the sequence, then it must
be the case that $y_{6}$ is a leaf again after the special edge or that
$y_{1}$ is a leaf before the edge, making this path not optimal. If $y_{1}$
and $y_{6}$ are never leaves simultaneously, then there must be a rotation
between them, since they have different relative order in $T$ and
$T^{\prime}$, that is, there is an additional rotation, apart from those
counted in Table 3. This makes the path again non optimal. Hence, no
$TT^{\prime}$-path of minimum length in $\mathcal{R}(\textnormal{SPK}_{2,6})$
has a special edge.

It follows that
$\textnormal{diam}(\mathcal{R}(K_{2,6}))=\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,6}))=20$.

Finally, we prove that $\textnormal{diam}(\mathcal{R}(K_{2,7}))=25$.

Consider the search trees $T,T^{\prime}$ on $\textnormal{SPK}_{2,7}$ shown in
Figure 6.

$y_{7}$$y_{6}$$y_{5}$$y_{4}$$y_{3}$$x_{2}$$y_{2}$$x_{1}$$y_{1}$$T$

$y_{1}$$y_{2}$$y_{3}$$y_{4}$$y_{5}$$y_{6}$$x_{1}$$y_{7}$$x_{2}$$T^{\prime}$

Figure 6: Two search trees on $\textnormal{SPK}_{2,6}$.

Recall that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,7})}(T,T^{\prime})\leq\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,7}))=25$.

We prove that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,7})}(T,T^{\prime})\geq 25$.
Consider a path from $T$ to $T^{\prime}$ in
$\mathcal{R}(\textnormal{SPK}_{2,7})$.

Let us consider first the case where $y_{1}$ is the only vertex of $Q$ that is
a leaf in some tree of this sequence. Such a path has at least the following
rotations. One $x_{1}x_{2}$-rotation, $\binom{7}{2}$ rotations between pairs
of vertices in $Q$, two rotations of $y_{1}$ with both vertices in $P$, one of
$y_{2}$ with $x_{2}$ (that makes $y_{2}$ go up) and one of $y_{7}$ with
$x_{1}$ (where $y_{7}$ goes down). This gives a total of 26 rotations. Note
that in this case, the path is not of minimum length.

Suppose now that $L\subseteq Q$ is the set of vertices in $Q$ that are leaves
in some tree of this path, with $k=|L|\geq 2$. Then, in such a path the
rotations in Table 4 are necessary.

No. of rotations | Description
---|---
1 |  exchange $x_{1}x_{2}$
$\alpha+2(k-2)$ |  leaves go down, $\alpha=\begin{cases}1\quad\textnormal{if }y_{2}\in L\\\ 2\quad\textnormal{if }y_{2}\notin L\end{cases}$
$\delta$ |  sort vertices of $Q$ within handle, $\delta=\begin{cases}\binom{7-k}{2},\quad k\leq 5\\\ 0,\quad k=6,7\end{cases}$
$k(7-k)$ | leaves non-leaves rotations
$\beta+2(k-1)$ |  leaves go up, $\beta=\begin{cases}1\quad\textnormal{if }y_{7}\in L\\\ 2\quad\textnormal{if }y_{7}\notin L\end{cases}$
Table 4: Necessary rotations in a sequence that transforms $T$ into
$T^{\prime}$.

Hence, this path has length at least

$1+\gamma+2(k-2)+\delta+k(7-k)+2(k-1),$

where $\gamma=\alpha+\beta=\begin{cases}2\quad\textnormal{if }y_{2},y_{7}\in
L\\\ 3\quad\textnormal{if }(y_{2}\in L,y_{7}\notin L)\lor(y_{2}\notin
L,y_{7}\in L)\\\ 4\quad\textnormal{if }y_{2},y_{7}\notin L.\end{cases}$

Note that this expression is a concave function of $k$, therefore reaching its
minimum value for $k=2$ or $k=7$. Evaluating in those values of $k$ we obtain
26 or 27 and 25 respectively (note that if $k=2$, $y_{2}\notin L$ or
$y_{7}\notin L$). It follows that
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,7})}(T,T^{\prime})\geq 25$,
and therefore
$\textnormal{d}_{\mathcal{R}(\textnormal{SPK}_{2,7})}(T,T^{\prime})=25$.

According to the previous paragraphs, in a minimum length path $L=Q$. In
particular $y_{2},y_{7}\in L$.

Observe that in Table 4 only 3 rotations between $y_{2}$ and vertices in $P$
are counted (one when $y_{2}$ goes down to be a leaf and 2 when it goes up).
If there were a $P$-special edge in the path, and if $y_{2}$ were a leaf after
this edge, 5 additional rotations would be needed, between $y_{2}$ and
vertices of $P$ (1 when $x_{2}$ goes down, 2 when $y_{2}$ goes down to be a
leaf, 2 ir goes back up again). This makes the path of length at least 27, and
therefore not optimal. Hence, $y_{2}$ must be a leaf exclusively before the
special edge. Analogously, $y_{7}$ must be a leaf exclusively after the
special edge. Thus, $y_{2}$ and $y_{7}$ are not leaves simultaneously in any
tree of the path. This means that there must be at least one rotation between
them, since they have different relative order in $T$ and $T^{\prime}$, adding
one rotation to those already counted in Table 4. Therefore, a path with a
$P$-special edge is not optimal.

It follows that
$\textnormal{diam}(\mathcal{R}(K_{2,7}))=\textnormal{diam}(\mathcal{R}(\textnormal{SPK}_{2,7}))=25$.

## References

  * [1] Aguiar, M., and Ardila, F. Hopf monoids and generalized permutahedra, vol. 1437 of Mem. Am. Math. Soc. Providence, RI: American Mathematical Society (AMS), 2023.
  * [2] Cardinal, J., Langerman, S., and Pérez-Lantero, P. On the diameter of tree associahedra.  Electron. J. Comb. 25, 4 (2018), research paper p4.18, 13.
  * [3] Cardinal, J., Pournin, L., and Valencia-Pabon, M. Diameter estimates for graph associahedra.  Ann. Comb. 26, 4 (2022), 873–902.
  * [4] Cardinal, J., Pournin, L., and Valencia-Pabon, M. The rotation distance of brooms.  European Journal of Combinatorics 118 (2024), 103877.
  * [5] Cardinal, J., and Steiner, R. Shortest paths on polymatroids and hypergraphic polytopes.  arXiv preprint (2023).
  * [6] Carr, M., and Devadoss, S. L. Coxeter complexes and graph-associahedra.  Topology Appl. 153, 12 (2006), 2155–2168.
  * [7] David, J., Pournin, L., and Rakotonarivo, R. Elementary moves on lattice polytopes.  J. Comb. Theory, Ser. A 172 (2020), 30.  Id/No 105200.
  * [8] Devadoss, S. L. A realization of graph associahedra.  Discrete Math. 309, 1 (2009), 271–276.
  * [9] Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., Maezawa, S.-i., Nozaki, Y., and Okamoto, Y. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra.  In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) (Dagstuhl, Germany, 2023), vol. 261 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 82:1–82:17.
  * [10] Manneville, T., and Pilaud, V. Graph properties of graph associahedra.  Sémin. Lothar. Comb. 73 (2015), b73d, 31.
  * [11] Mohammadi, F., Uhler, C., Wang, C., and Yu, J. Generalized permutohedra from probabilistic graphical models.  SIAM J. Discrete Math. 32, 1 (2018), 64–93.
  * [12] Postnikov, A. Permutohedra, associahedra, and beyond.  Int. Math. Res. Not. 2009, 6 (2009), 1026–1106.
  * [13] Postnikov, A., Reiner, V., and Williams, L. Faces of generalized permutohedra.  Doc. Math. 13 (2008), 207–273.
  * [14] Pournin, L. The diameter of associahedra.  Adv. Math. 259 (2014), 13–42.
  * [15] Pournin, L. The asymptotic diameter of cyclohedra.  Isr. J. Math. 219, 2 (2017), 609–635.
  * [16] Sondag, M., Speckmann, B., and Verbeek, K. Stable treemaps via local moves.  IEEE Transactions on Visualization and Computer Graphics 24, 1 (2017), 729–738.
  * [17] van Kreveld, M., Löffler, M., and Silveira, R. I. Optimization for first order Delaunay triangulations.  Comput. Geom. 43, 4 (2010), 377–394.