# F0 ANALYSIS OF GHANAIAN POP SINGING REVEALS PROGRESSIVE ALIGNMENT WITH EQUAL
TEMPERAMENT OVER THE PAST THREE DECADES: A CASE STUDY

###### Abstract

Contemporary Ghanaian popular singing combines European and traditional
Ghanaian influences. We hypothesize that access to technology embedded with
equal temperament catalyzed a progressive alignment of Ghanaian singing with
equal-tempered scales over time. To test this, we study the Ghanaian singer
Daddy Lumba, whose work spans from the earliest Ghanaian electronic style in
the late 1980s to the present. Studying a singular musician as a case study
allows us to refine our analysis without over-interpreting the findings. We
curated a collection of his songs, distributed between 1989 and 2016, to
extract F0 values from isolated vocals. We used Gaussian mixture modeling
(GMM) to approximate each song’s scale and found that the pitch variance has
been decreasing over time. We also determined whether the GMM components
follow the arithmetic relationships observed in equal-tem-pered scales, and
observed that Daddy Lumba’s singing better aligns with equal temperament in
recent years. Together, results reveal the impact of exposure to equal-tem-
pered scales, resulting in lessened microtonal content in Daddy Lumba’s
singing. Our study highlights a potential vulnerability of Ghanaian musical
scales and implies a need for research that maps and archives singing styles.

##  1 Introduction

Ghanaian popular music today is the result of a long history of European
influences interacting with traditional sty-

les, employing scales with microtonal variance outside e- qual temperament.
Throughout the 20th century, Ghana featured hybrid music with complex harmony
such as Palm-Wine, Highlife and more recently, Hiplife and A-frobeats [1, 2].
These musics were influenced by traditional Ghanaian music, including European
influences such as Christian hymns, sea shanties and brass band music [1].

Traditional Ghanaian music is full of features that set it apart from the
Western European tradition. Ghanaian harmony is complex and compelling, yet
there is a lot of harmonic information to be examined on scales, pitch sets
and tuning. Kofi Agawu argues for transcriptions as a valid means of studying
African music [3] in keeping with our methods of music theory analysis. A
notable in-depth study is Ampene’s research on nwomkoro, traditional female A-
kan singing, with a leader’s call and the chorus’ harmonized response [4].
Adu-Gilmore (2017) [5] has researched Ghanaian harmony for over a decade, and
although afro- beats has become a best-selling global phenomenon, the culture
around African electronic music has been the focus of academic research but
the music theory and harmony is still under-researched. Her research has built
upon Ampene’s showing parallel harmonies and step-wise chord progressions,
creating tonal centers outside of the major and minor modes of the key,
implying lesser-used modes in European styles such as Phrygian, Lydian and
Mixolydian [5]. These harmonic tendencies continued to present-day popular
music styles such as Ghanaian hip-hop, Highlife and Afrobeats, combining
traditional Ghanaian scales with digital instruments and digital audio
workstations (DAWs) [2], which are equal-tempered. Moreover, Moelants and
colleagues claim that there is a move in African music towards “more
elaborate, equally-tempered scales,” even though African music traditionally
has differed from the chromatic, equal-tempered twelve-tone scale [6].

The international dominance of Western equal-tempered tuning and tonality
endangers traditional scales of the world. Internet music dissemination has
increased audiences’ music access globally. Ghanaians’ consumption of music
from overseas impacts Ghanaian music production and use of effects, including
autotune. Although autotune is mainly a means to tune vocals towards equal-
temperament, Cher’s 1998 hit “Believe” [7] very audibly used the autotune
effect for artistic purposes, producing an unnatural and robotic effect, later
popularized by rappers, notably T-Pain, who even created a commercial
microphone with an inbuilt autotune [8]. According to Ghanaian music producer,
Kofi “IAmBeatmeance” Boachie-Ansah, Ghanaian tracks such as Sony Achiba’s
“Sony Maba” [9] used autotune early on. Boachie-Ansah states: “This was a few
years after Cher’s “Believe,” when that song was dominating the charts. It had
a heavy rotation even here, for years […] Accra has always had a very vibrant
nightlife culture driven by a lot of dance music so some of the sensibilities
that informed those genres of music found a way of seeping into the popular
music of the time” [10].

We hypothesize that the exposure to music technology and the internet, over
the last three decades, has led to musical scales used in popular Ghanaian
singing to be more aligned with equal-tempered scales in artists such as Daddy
Lumba. This paper presents a case study with quantitative evidence of a move
over the years towards pitches that are more in tune with a discrete scale
instead of traditional Ghanaian microtonal features, while also gradually
trending towards equal temperament.

To test this hypothesis, we focus on the music of Daddy Lumba, who has been
described by Ghanaian popular music scholar John Collins as “one of the most
popular Burger Highlife artists” alongside his brothers, Nana Acheampong and
Sarkodie [1]. Daddy Lumba’s career spans from the earliest Ghanaian electronic
style, Burger Highlife in the late 1980s, to similar present-day musics such
as Ghanaian Hiplife [11]. Similar to most Ghanaian popular artists, Daddy
Lumba is notoriously reclusive and biographical information in general is
slim, mostly reliant on music entertainment websites (at times unreferenced,
with no author name included) and wikipedia. Daddy Lumba’s sings music in
popular music genres that prominently feature the use of equal-tempered
synthesizers and DAWs.

We curated a dataset of Daddy Lumba recordings to ask whether his singing
reflects features that progressively abandon traditional Ghanaian scales with
microtonal pitch variance in favor of equal temperament. We chose the dataset
of a singular musician as a case study to refine our analysis method and to
avoid over-interpreting the findings. Limiting the scope in this way allows us
to ensure specificity in the results.

By presenting empirical evidence, we argue that Ghanaians’ increased access to
equal-tempered music through internet dissemination coupled with greater
access to music technology is exponentially speeding up the threat to
traditional Ghanaian music intonation and scale variance. That is, equal-
tempered synthesizers and effects such as autotune enable a more pronounced
tendency toward equal-temperament. Far from combating these phenomena, this
case study aims to map this change and call for archiving and preserving
traditional global musics and their practice.

##  2 Related work

Although music scales have been examined over centuries, their study using
large datasets is made possible by two major advances in music information
retrieval (MIR). The first consists of audio source separation algorithms,
such as Wave-U-Net [12], recurrent neural networks [13], and spectrogram
U-Nets [14], which can be used to automatically isolate vocal or single
instrument tracks111these type of algorithms have recently been made available
in dedicated software toolboxes like Spleeter [15]. The second advancement
consists of F0 estimation algorithms that operate directly on waveform
signals, such as YIN [16, 17] and CREPE [18]. Together, these advancements
allow for the extraction of singing F0 values, and the subsequent
approximation of musical scales via statistical modeling.

Previous research has used F0 estimation methods in non-Western music
recordings. A recent study combined source-separation and F0 estimation
methods to quantitatively analyze melodic mode switching in raga performances
[19]. Additionally, the YIN algorithm has been used, on its own, to extract
the scales present in African and Turkish instrumental melodies [20, 21], as
well as Indian singing [22, 23]. These studies sought to assess whether the
scales found in digital musical recordings with real musical practice are
consistent with music theories for each of these music traditions [24]. More
recently, researchers used CREPE to compare the pitch content among human
signing, speech, and birdsongs, finding that human singing, across cultures
and countries, emphasizes integer ratio relationships between pitch content
(i.e. perfect fifths), compared to speech or birdsongs [25]. Similar analysis
(but using YIN instead of CREPE) on child and adult singing was used to study
the possible sensorimotor origins of inter-ratio relationships commonly seen
in sung pitch content [26].

These studies have been important in showing how modern MIR tools can be
applied to analyze melodic pitch content in digital recordings of music. We
have yet to find a study, however, that uses a data-driven methodology to
analyze the impact of equal temperament on Ghanaian scales. We therefore
believe that our study will be the first in the field to show such an effect.

Figure 1: Top panel: each song’s F0 histogram, column-wise. Lighter colors
indicate higher density. White dots represent the optimal GMM components
found. Bottom panel: three sample F0 histograms (normalized so that the F0
with the highest incidence is equal to 1, for visualization purposes).

##  3 Method to estimate F0 values in Daddy Lumba’s singing

Our goal is to study the changes in the scales and pitch content sung by Daddy
Lumba over the course of twenty-seven years, as captured in his discography.
To do this, we compiled a corpus of 99 songs released between 1989 and 2016
(stereo, mp3, 44.1 kHz sampling rate). Table 1 shows a summary of the most
relevant metadata in our corpus.

songs per year | song dur | song dur | total
---|---|---|---
(1989-2016) | (avg) | (std dev) | duration
3.54 | 5m42s | 1m8s | 9h23m23s
Table 1: Column 1: the average number of songs included in our dataset per year. Columns 2 and 3: the average song duration and standard deviation, respectively. Column 4: the total duration of our dataset. F0 dur. : song dur. | F0 dur. : song dur. | total F0
---|---|---
(avg.) | (std. dev.) | duration
0.22 | 0.06 | 2h5m37s
Table 2: Columns 1 and 2: the average and standard deviation of the ratio
between duration of F0 values extracted and total song duration. Column 3: the
total duration of F0 values extracted from our dataset.

Our corpus contains mastered songs, which means that vocals, instruments, and
other effects are mixed in the tracks. We use CREPE [18] to do F0 estimation
of the vocal tracks. However, CREPE was designed and tested to work on
monophonic signals (i.e. tracks with only one instrument) [18]. To isolate the
vocals from all other instruments and effects in a song, we used the pre-
trained Wave-U-Net made available by its original
authors222https://github.com/f90/Wave-U-Net-Pytorch. Using the Wave-U-Net on
each song, we obtained tracks containing only the vocals sung by Daddy Lumba
and vocal accompaniment.

Having the isolated vocal track, we can use CREPE to estimate the F0s in Daddy
Lumba’s songs. A pre-trained version of CREPE is made available by its
original authors333https://github.com/marl/crepe. Given an audio signal, this
version of CREPE estimates an F0 value, in Hz, every 10ms, and each value is
accompanied by a confidence score between 0 and 1. We used CREPE version
v0.0.7 to extract F0 values from each song’s isolated vocal track. To ensure
the quality of the F0 values we applied the following heuristic filtering
method: 1) we discarded F0 values outside the range between 80Hz and 600Hz
(the vocal range of male singing) 2) we also discarded F0 values that were
given a confidence score below 0.8 by CREPE. Finally, we converted the F0
values from Hz to cents using Eq. (1)

$F0_{cents}=1200\log_{2}\bigg{(}\frac{F0_{Hz}}{16.352_{Hz}}\bigg{)},$ (1)

where 16.352 Hz corresponds to the C0 tone that we used as reference. Table 2
gives a summary of the amount of F0 values that we were able to obtain from
the dataset using our extraction and filtering method. In total, we were able
to obtain over 2 hours of F0 values. On average, from each song we obtained
22% of its duration as F0 values.

We used these F0 values to carry out two analyses that quantify changes over
Daddy Lumba’s singing career. First, we used a Gaussian mixture model (GMM) to
approximate the scale of each song and study the variance around pitches in
the sung scale. Second, we used the GMM results to determine whether Daddy
Lumba’s singing scales reflect an equal-tempered structure.

##  4 Analysis 1: estimating song scales and variance around them over years

In this analysis we approximate each song’s scale to look at the variations in
pitch content. We observe whether this variation has changed over Daddy
Lumba’s career. Our specific research question is: has Daddy Lumba’s singing
reduced its pitch variations over the years?

###  4.1 Methodology

Figure 2: Left panel: a linear regression reveals a significant negative
relationship for the F0 GMM variance over the years. Right panel: a linear
regression reveals a significant positive relationship for the number of F0
GMM components over the years.

In general, a Gaussian mixture is a probabilistic unsupervised method that
models data as a probability distribution that is the sum of different
weighted Gaussians. Eq. (2) describes the general equation

$p(\theta)=\sum_{i=0}^{C-1}\phi_{i}\mathcal{N}(\mu_{i},\sigma_{i}),$ (2)

where $\mu_{i}$ and $\sigma_{i}$ are the $i$’th component’s mean and variance,
and each component is weighted by a scalar $\phi_{i}$.

For each song’s F0 values, we estimate the parameters of a Gaussian mixture
with “tied” covariance [27]. For the specific case of “tied” covariance, the
coefficient $\phi_{i}=1$ is used and a constant $\sigma$ is found for all
components in the GMM [28]. In other words, the data is clustered by using the
same distance criterion across the range of F0 values. We use a tied
covariance because we are assuming that the distribution of F0 values sung
around each pitch in a scale is the same (i.e. Daddy Lumba’s singing has a
characteristic variability around scale tones, independent of how high- or
low-pitched a tone is). We limited the F0 values considered for the GMM to be
an an octave around the most commonly-sung F0 value in each song.

We validate number of components $C$ in a GMM via the highest euclidean
silhouette score around each Gaussian component mean value. The silhouette
score is a heuristics based method that yields a coefficient by

$s=\frac{1}{N}\sum_{i=0}^{N-1}\frac{b_{i}-a_{i}}{\max(a_{i},b_{i})},$ (3)

where $a_{i}$ is the average distance between a point $i$ and the other points
in the same Gaussian component (i.e. point-wise inter-cluster distance), and
$b_{i}$ is the average distance between a point $i$ and the points in the
closest Gaussian component that $i$ is not part of. The silhouette score
ranges from -1 to 1, with values close to 1 indicating that datapoints, on
average, belong to their assigned Gaussian component, while -1 indicates that
datapoints, on average, do not belong to their assigned Gaussian component.
Since our GMM components have a “tied” covariance, the silhouette score is a
fair metric to validate components that should have similar density
properties.

We tested integer values between 4 and 15 for the possible number of
components, with 4 being the lowest number of pitch classes that we considered
to be reasonable for a singing scale, and 15 the maximum within an octave. The
GMM with the number of components that maximized the silhouette score was
selected to model a song’s scale.

###  4.2 Results: singing scales approximated via GMM

The top panel of figure 1 shows a matrix where columns are song histograms of
F0 values, chronologically ordered from left to right. White dots are the mean
of each component in the song’s F0 GMM. On average, the silhouette score
associated with each song’s F0 GMM was 0.72 (lowest was 0.62 and highest was
0.87). The GMM components (i.e. the white dots) are an approximation of each
song’s scale based on our GMM approach. The bottom panel of Figure 1 shows
three example F0 histograms, normalized so that the highest peak of each is
equal to 1 (for visualization purposes). Note how the spread around peaks is
visually smaller for the years 2016 and 2001 compared to 1989. With that said,
we should be mindful that our dataset has a limited number of data points from
2015 onwards. We believe that less data starting at that point is not a big
problem since, as shown in the top panel of Figure 1, Daddy Lumba’s singing
reflects the use of autotune.

###  4.3 Results: F0 GMM components over the years

The left panel of figure 2 shows the standard deviation associated with each
song’s F0 GMM components. A linear regression revealed a significant negative
correlation (r = -0.3839; p $<$ 0.05), indicating that, as years have
progressed, the vocals have reduced their microtonal pitch diversity,
suggesting a tendency to sing more “in tune” with the song’s scale. The right
panel of figure 2 shows the number of GMM components in each song’s F0 GMM. A
linear regression revealed a significant positive correlation (r = 0.2834; p
$<$ 0.05), indicating that, over the years, Daddy Lumba’s sings scales with
more tones per octave.

##  5 Analysis 2: Quantifying alignment with equal temperament over years

Analysis 1 resulted in a GMM for each song, with a unique number of components
and standard deviation around them, as well as a characteristic distance
between components.

###  5.1 Methodology

In a song that perfectly follows the equal-tempered scale, the distance
between any two notes $n_{i}$ and $n_{j}$ follows this rule (in units of
cents):

$|n_{i}-n_{j}|=N\times 100,$ (4)

where 100 is the shortest possible distance between two consecutive notes in a
scale, and $N\in\mathbf{Z}$ is the number of times such distance separates the
notes $n_{i}$ and $n_{j}$. 100 cents is the smallest possible distance between
equal-tem- pered notes. However, no singer is perfect and musical performances
have an error term associated, making Eq. (4):

$|n_{i}-n_{j}|=N\times 100+\epsilon,$ (5)

where $\epsilon$ is a value between 0 and 50, reflecting an error from the
perfect minimal distance of 100 cents. An $\epsilon$ closer to zero indicates
better alignment with equal-temperament.

We want to quantify to what extent Daddy Lumba’s singing reflects a scale that
is consistent with equal temperament, and whether his singing has
progressively become more equal-tempered over the years. Hence, we calculated
Eq. (5) between the F0 GMM components found in each song to get the song’s
average $\epsilon_{s}$.

###  5.2 Results: equal temperament alignment over years

A linear regression over the songs’ $\epsilon_{s}$ values revealed a
significant negative correlation (r = -0.2552; p $<$ 0.05), indicating that,
over the years, Daddy Lumba’s singing has progressively reduced the $\epsilon$
error term in Eq. (5). Figure 3 shows this regression.

The code and F0 data needed to reproduce our results and generate the figures
in this paper is openly available444https://github.com/iranroman/AFRINUM.

Figure 3: A linear regression of how error $\epsilon_{s}$ associated with
deviations from equal temperament has been reducing over the years, indicating
alignment with an equal-tempered scale

##  6 Discussion

We are interested in examining the microtonal nuances in Ghanaian singing and
its associated musical scales. This initial study analyzes Daddy Lumba’s work
over time because he has an influential catalog of work spanning from early
Ghanaian electronic music called Burger Highlife in the 90s, until the present
moment.

The first analysis used GMM to approximate the singing scales in Daddy Lumba’s
songs (independent of whether they are equal-tempered or not), and looked
closely at the pitch variations. The results in the left panel of figure 2
showed that, over time, he has tended to sing closer to the discrete tones in
his pitch sets (or modes), with less microtonal variance (i.e. he sings more
“in tune” with the scale he uses in a song). The potential reasons for this
could be manifold. For instance, his personal experience and developing
artistic identity could be the driving force, as Daddy Lumba’s career has
spanned many years, and this experience could mean that, over time, the
precision of his singing has been refined to target his chosen scale. However,
over the same time-span, the pop music industry has seen an increased access
to high-quality, budget alternatives to recording studios, such as DAWs that
allow singers to iterate over potential recordings and select tracks where
their voice reflects their preferred tuning precision and scale. Editing in
DAWs is typically a lot faster, and different takes may be easier to record,
and edit [29]. These changes in technology have implications everywhere.

We also analyzed how Daddy Lumba sings in relation to equal temperament, and
exposed a gradual shift towards equal temperament over the years (see Figure
3). The reasons for this may also be linked to access to technology. First,
traditional scales may be affected by fixed pitch equal-tem- pered
instruments, such as piano, sound synthesizers, and wind instruments, as the
string instruments and voices are tuned to them. Second, electronic
instruments and software using “auto-tuned” MIDI are tuned to the equal-
tempered system. Third, music made using electronic instruments and computers
is pervasive. Fourth, the mass music distribution through the internet has
increased the speed at which equal-tempered popular music is disseminated,
consumed and absorbed. Therefore, digital instruments and effects embedded
with tonal harmony of Wes- tern-European Christian scales and equal
temperament may impact Ghanaian singing, as well as other music across the
globe with traditional scales, tuning conventions and vocal inflections.

Why do we compare Daddy Lumba’s singing against equal temperament? Because of
its history as a British colony, to study Ghanaian popular music today, Daddy
Lumba included, it is necessary to analyze it through the lens of both Western
European tonal harmony and traditional Ghanaian harmony. Critical Sonic
Practice (CSP) investigates global music by dissolving borders between music
technology, composition and theory, while including indigenous epistemologies.
Western-European Christian tonal harmony is necessary in this discussion, not
because this scale is “in tune,” but because these scale systems are a
cultural choice at the heart of the European colonizing force of music [30].

##  7 Conclusion

This study aims to catalyze a scientific discourse about how global access to
music technology has influenced Gha- naian music, popular and traditional, as
well as other global genres, including the global north, where traditional
styles, like flamenco in Spain or Rímur in Iceland, feature microtonal
inflections that cannot be defined by the equal-tempered system [31, 32].
Evolution in music formats, such as vinyl to tape dubbing, already increased
access to broader genres; whereas internet dissemination increased access to
equal-tempered music from abroad, and gives Ghanaians more access to global
markets that picked equal temperament as an unofficial standard. Furthermore,
recent advances in technology, such as cheaper (and free) DAWs, virtual studio
technology (aka VST), and the prevalence of autotune increase the ubiquity of
equal temperament. Changes in music scales and temperament are inevitable and
MIR is an essential tool in mapping this change.

The findings in this study align with the mission of CSP, which includes
decolonizing datasets, and departing from norms of tuning that are often
overlooked, taken for granted, or even unknown. In doing so, we recognize that
current algorithms are often trained with datasets that reflect majoritian
musics. The specificity of this paper as a case study, which closely examines
one artist, signifies that we can more easily understand the culturally-
relevant nuances of a given artist’s corpus. This allows us to foresee
potential errors in cultural bias or expectation. Therefore, we are fine-
tuning necessary steps in research design that are culturally sensitive to the
dataset, before continuing to move forward toward our future work with larger
datasets encompassing entire genres, music traditions, or geographical
regions.

To reiterate, this paper demonstrates a research design for detecting
microtonal variance over time in the music of one artist, rather than a
comprehensive study of Ghanaian harmony. That said, the findings point towards
more research into Ghanaian modes and tonalities, as well as the changes
affected by technologies.

##  8 Future Research

We will expand our work by analyzing other artists in the same genre. We also
aim to research and expand the timeline to encompass releases before 1989,
hoping to better map and describe traditional scales and influences. Future
works using MIR could involve an in-depth study of Ghanaian scales and modes
in the same dataset or others to expand the archive of Ghanaian popular and
traditional musics. These could be cross-referenced with expert listening
panels to verify the empirical data. This research will be augmented by
interviews with artists, ensuring culturally specific context for the broader
study in order to investigate the reason behind this phenomenon. The work
presented here lays the groundwork for the empirical, data-driven archiving of
traditional and local modes and tonalities. With these goals in mind, this
study has broader implications in the decolonization of music research
requiring archiving of tonal systems from all over the world for cultural
preservation.

## References

  * [1] J. Collins, “Contemporary ghanaian popular music,” in _Hip Hop Africa: New African Music in a Globalizing World._ , E. Charry, Ed. Indiana UP, 2012, pp. 211–231.
  * [2] L. Adu-Gilmore, “Studio improv as compositional process through case studies of ghanaian hiplife and afrobeats,” _Critical Studies in Improvisation/Études critiques en improvisation_ , vol. 10, no. 2, 2015.
  * [3] K. Agawu, _Representing African music: Postcolonial notes, queries, positions_. Routledge, 2014.
  * [4] K. Ampene and A. Scharfenberger, _Female Song Tradition and the Akan of Ghana: The Creative Process in Nnwonkoro (SOAS Musicology Series)_. Aldershot: Ashgate, 2005.
  * [5] L. Adu-Gilmore _et al._ , “Music production in accra: Ghanaian hiplife, akan and highlife harmony and african-american minimalist hip-hop in two case studies,” 2017.
  * [6] D. Moelants, O. Cornelis, and M. Leman, “Exploring african tone scales,” in _10th International Society for Music Information Retrieval Conference (ISMIR-2009)_. International Society for music Information Retrieval, 2009, pp. 489–494.
  * [7] B. Higgins, S. McLennan, P. Barry, S. Torch, M. Gray, and T. Powell, “Believe [recorded by cher],” _On Believe [CD, track 1). United States: Warner Brothers_ , 1998.
  * [8] T. Dean and T. Brice, “How geophysics ruined music,” _Preview_ , vol. 2022, no. 217, pp. 43–47, 2022.
  * [9] S. Achiba, “Sony maba [recorded by achiba],” 2001.
  * [10] K. Boachie-Ansah, “personal communication with kofi boachie-ansah,” 2023.
  * [11] E. Charry, “The birth of ghanaian hiplife: Urban style, black thought, proverbial speech,” in _Hip Hop Africa: New African Music in a Globalizing World._ , E. Charry, Ed. Indiana UP, 2012, pp. 29–36.
  * [12] D. Stoller, S. Ewert, and S. Dixon, “Wave-u-net: A multi-scale neural network for end-to-end audio source separation,” _arXiv preprint arXiv:1806.03185_ , 2018.
  * [13] P.-S. Huang, M. Kim, M. Hasegawa-Johnson, and P. Smaragdis, “Singing-voice separation from monaural recordings using deep recurrent neural networks.” in _ISMIR_ , 2014, pp. 477–482.
  * [14] A. Jansson, E. Humphrey, N. Montecchio, R. Bittner, A. Kumar, and T. Weyde, “Singing voice separation with deep u-net convolutional networks,” in _18th International Society for Music Information Retrieval Conference_ , 2017, pp. 23–27.
  * [15] R. Hennequin, A. Khlif, F. Voituret, and M. Moussallam, “Spleeter: a fast and efficient music source separation tool with pre-trained models,” _Journal of Open Source Software_ , vol. 5, no. 50, p. 2154, 2020.
  * [16] A. De Cheveigné and H. Kawahara, “Yin, a fundamental frequency estimator for speech and music,” _The Journal of the Acoustical Society of America_ , vol. 111, no. 4, pp. 1917–1930, 2002.
  * [17] M. Mauch and S. Dixon, “pyin: A fundamental frequency estimator using probabilistic threshold distributions,” in _2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2014, pp. 659–663.
  * [18] J. W. Kim, J. Salamon, P. Li, and J. P. Bello, “Crepe: A convolutional representation for pitch estimation,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 161–165.
  * [19] N. Shikarpur, A. Keskar, and P. Rao, “Computational analysis of melodic mode switching in raga performance,” in _22th International Society for Music Information Retrieval Conference_ , 2021, pp. 657–664.
  * [20] J. Six and O. Cornelis, “Tarsos: a platform to explore pitch scales in non-western and western music,” in _12th International society for music information retrieval conference (ISMIR-2011)_. University of Miami, Frost School of Music, 2011, pp. 169–174.
  * [21] B. Bozkurt, R. Ayangil, and A. Holzapfel, “Computational analysis of turkish makam music: Review of state-of-the-art and challenges,” _Journal of New Music Research_ , vol. 43, no. 1, pp. 3–23, 2014.
  * [22] J. Serra, G. K. Koduri, M. Miron, and X. Serra, “Assessing the tuning of sung indian classical music.” in _ISMIR_. Florida, 2011, pp. 157–162.
  * [23] G. K. Koduri, S. Gulati, P. Rao, and X. Serra, “Rāga recognition based on pitch distribution methods,” _Journal of New Music Research_ , vol. 41, no. 4, pp. 337–350, 2012.
  * [24] G. Tzanetakis, “Computational ethnomusicology: a music information retrieval perspective.” in _ICMC_ , 2014, pp. 112–117.
  * [25] J. Kuroyanagi, S. Sato, M.-J. Ho, G. Chiba, J. Six, P. Pfordresher, A. Tierney, S. Fujii, and P. Savage, “Automatic comparison of human music, speech, and bird song suggests uniqueness of human scales,” in _9th Folk Music Analysis Conference_ , 2019, pp. 35–40.
  * [26] S. Sato, J. Six, P. Pfordresher, S. Fujii, and P. Savage, “Automatic comparison of global children’s and adult songs supports a sensorimotor hypothesis for the origin of musical scales,” in _9th Folk Music Analysis Conference_ , 2019, pp. 41–46.
  * [27] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg _et al._ , “Scikit-learn: Machine learning in python,” _the Journal of machine Learning research_ , vol. 12, pp. 2825–2830, 2011.
  * [28] D. A. Reynolds, “Gaussian mixture models.” _Encyclopedia of biometrics_ , vol. 741, no. 659-663, 2009.
  * [29] A. P. Bell, _Dawn of the DAW: The studio as musical instrument_. Oxford University Press, 2018.
  * [30] L. Adu-Gilmore, “Embodied listening: Grassroots governance in electronic dance music venues in accra (ghana),” in _Electronic Cities_. Springer, 2021, pp. 243–260.
  * [31] E. Gómez and J. Bonada, “Automatic melodic transcription of flamenco singing,” in _Fourth Conference on Interdisciplinary Musicology (CIM08)_ , 2008.
  * [32] Á. H. Ingólfsson, _Jón Leifs and the musical invention of Iceland_. Indiana University Press, 2019\.


# Glauber dynamics for the hard-core model
on bounded-degree $H$-free graphs

Mark Jerrum  School of Mathematical Sciences, Queen Mary, University of
London, Mile End Road, London E1 4NS<EMAIL_ADDRESS>
###### Abstract.

The hard-core model has as its configurations the independent sets of some
graph instance $G$. The probability distribution on independent sets is
controlled by a ‘fugacity’ $\lambda>0$, with higher $\lambda$ leading to
denser configurations. We investigate the mixing time of Glauber (single-site)
dynamics for the hard-core model on restricted classes of bounded-degree
graphs in which a particular graph $H$ is excluded as an induced subgraph. If
$H$ is a subdivided claw then, for all $\lambda$, the mixing time is $O(n\log
n)$, where $n$ is the order of $G$. This extends a result of Chen and Gu for
claw-free graphs. When $H$ is a path, the set of possible instances is finite.
For all other $H$, the mixing time is exponential in $n$ for sufficiently
large $\lambda$, depending on $H$ and the maximum degree of $G$.

##  1\. Introduction

The complete bipartite graph $K_{3,1}$ is known as a claw. A graph is said to
be claw-free if it does not contain a claw as an induced subgraph. The hard-
core model is specified by a graph $G$ and a fugacity $\lambda>0$. These
inputs define a probability distribution on independent sets of a graph, the
so-called hard-core distribution. Higher values of $\lambda$ favour larger
independent sets, leading to denser configurations. (Precise definitions will
be given presently.)

Glauber dynamics defines an ergodic Markov chain on independent sets in a
graph, whose stationary distribution is the hard-core distribution. We are
interested in analysing the mixing time (time to near stationarity) of Glauber
dynamics. With increasing fugacity $\lambda$ the density of configurations
increases and we expect the mixing time to increase too. For most graph
classes, for example graphs of bounded degree, which have been extensively
studied [9, 19, 21], there is a critical $\lambda$ above which the mixing time
becomes exponential in the size of the graph. However, in his PhD thesis,
Matthews [18] showed that, for any fixed $\lambda$, however large, the mixing
time of Glauber dynamics on a claw-free graph $G$ is polynomial in $n=|V(G)|$.

Recently, Chen and Gu [7] showed (amongst other things) that, with the
additional assumption that $G$ has bounded degree $\Delta$, the mixing time of
Glauber dynamics on claw-free graphs is in fact $O(n\log n)$. The constant
implicit in the O-notation depends on $\lambda$ and $\Delta$. We call this
mixing ‘optimal’, since $O(n\log n)$ time is necessary for Glauber dynamics to
visit every vertex in $G$, by the coupon-collector argument. The intuition
that $O(n\log n)$ is optimal can be formalised, though doing so is
surprisingly challenging [14]. Prior to Chen and Gu’s work, optimal mixing for
matchings in bounded-degree graphs — a related result — had been shown by
Chen, Liu and Vigoda [8].

It is natural to wonder whether excluding graphs other than the claw can lead
to optimal mixing time for all $\lambda$. There is an extensive literature on
independent sets in graph families that exclude a fixed connected graph $H$ as
an induced subgraph. (From now on we restrict attention to connected $H$.) In
this work, subdivided claws play a crucial role [1, 10]. A subdivided claw is
obtained from a claw by subdividing the three edges by arbitrary number of
intermediate vertices. Alternatively, a subdivided claw is a tree with a
single vertex of degree 3, with all other vertices having degree 1 or 2. For
$1\leq i\leq j\leq k$, we write $S_{i,j,k}$ for the subdivided claw whose
leaves are at distance $i$, $j$ and $k$ from the degree-3 vertex. The smaller
subdivided claws have special names: $S_{1,1,1}$ (as we have seen) is the
claw, $S_{1,1,2}$ the fork, $S_{1,2,2}$ is the E, and $S_{1.2.3}$ is the skew
star. See Figure 1.

Figure 1. The claw, the fork, the E and the skew star.

It soon becomes apparent that the interesting cases for us are when the
excluded graph $H$ is a subdivided claw. Informally, the reason is this: if
$H$ is not a subdivided claw or a path, then it contains either a vertex of
degree greater than 3, or a cycle, or two vertices of degree 3 connected by a
path. We can exclude the first case by working with instance graphs $G$ with
maximum degree 3, and the other two cases by working with graphs whose edges
have been ‘stretched’ or subdivided by sufficiently many vertices. This
intuition is formalised in Section 6. Note that excluding a path in a bounded-
degree graph leads to a finite graph class. The (fairly routine) conclusion is
that Glauber dynamics mixes in exponential time for sufficiently large
$\lambda$ (depending on $\Delta$ and $H$ but not on $n=|V(G)|$) when $H$ is
not a subdivided claw or a path.

Our main result, Theorem 16, asserts that bounded-degree graphs that exclude
any subdivided claw support optimal mixing, yielding a dichotomy between
optimal versus exponential time mixing. There is a formal similarity between
this dichotomy and that of Abrishami, Chudnovsky, Dibek, Cemil and Rzażewski
[1], who studied the problem of finding the largest independent set in a
bounded-degree $H$-free graph. The current result is technically not as
difficult. This is to be expected: the algorithm, for finding a largest
independent set in a claw-free graph is quite involved, whereas that for
sampling an independent set is quite simple: simulate Glauber dynamics for
$O(n\log n)$ steps.

Note that the restriction to bounded-degree graphs is crucial. General fork-
free graphs include the complete bipartite graphs of arbitrary sizes, which
certainly do not support optimal or even polynomial-time mixing. Additional
restrictions other than bounded degree can lead to polynomial-time algorithms;
for example, Dyer, Jerrum and Müller treat the case of fork-free, odd-hold
free graphs (equivalent to fork-free perfect graphs) [12].

##  2\. Preliminaries

Suppose $G$ is a graph and $\lambda>0$ a ‘fugacity’. A set $I\subseteq V(G)$
is an _independent set_ in $G$ if no edge in $E(G)$ has both endpoints in $I$.
The _weight_ $\mathrm{wt}(I)$ of independent set $I$ is simply
$\mathrm{wt}(I)=\lambda^{|I|}$. Denote by $\mathcal{I}_{G}$ the set of all
independent sets in $G$. The _hard-core distribution_ $\mu_{G,\lambda}$
assigns probability $\mu_{G,\lambda}(I)=\mathrm{wt}(I)/Z(G,\lambda)$ to each
$I\in\mathcal{I}_{G}$, where $Z(G,\lambda)$ is the _partition function_.

$Z(G,\lambda)=\sum_{I\in\mathcal{I}_{G}}\mathrm{wt}(I).$

We think of $\mu_{G,\lambda}$ being a distribution on $2^{V(G)}$ with support
$\mathcal{I}_{G}$. For a vertex $v$ in $G$ we write $\mu_{G,\lambda}^{(v,0)}$
(respectively $\mu_{G,\lambda}^{(v,1)}$) for the distribution on independent
sets obtained from $\mu_{G,\lambda}$ by conditioning on $v$ being excluded
(respectively included) in the independent set.

Glauber dynamics defines a Markov chain on the independent sets of $G$. It is
presented in Figure 2, where $\Gamma_{G}(v)$ is used to denote the set of
neighbours of $v$ in $G$. This Markov chain is ergodic, and converges to the
hard-core distribution on independent sets of $G$.

  * •

Let the current state (independent set) be $I$.

  * •

Select a vertex $v\in V(G)$ uniformly at random.

  * •

If $\Gamma_{G}(v)\cap I=\emptyset$ then:

    * –

with probability $\lambda/(1+\lambda)$, set $I^{\prime}\leftarrow
I\cup\\{v\\}$;

    * –

with the remaining probability set $I^{\prime}\leftarrow I\setminus\\{v\\}$;.

  * •

else: set $I^{\prime}\leftarrow I$.

  * •

The new state is $I^{\prime}$.

Figure 2. Glauber dynamics for the hard-core model.

Denoting the $t$-step transition probabilities of this Markov chain by
$P^{t}(\cdot,\cdot)$, convergence to stationarity may be measured by total
variation distance (i.e, one half of the $\ell_{1}$ distance) at time $t$,
i.e.,

$d(t)=\max_{I\in\mathcal{I}_{G}}\big{\\{}d_{\mathrm{TV}}(P^{t}(I,\,\cdot\,),\mu_{G,\lambda})\big{\\}}.$

Then the _mixing time_ of the Markov chain is defined to be
$t_{\mathrm{mix}}=\min\\{t:d(t)\leq\frac{1}{4}\\}$. The constant $\frac{1}{4}$
is arbitrary, subject to lying in the interval $(0,\frac{1}{2})$. It is
standard [16, §4.5] that convergence to stationary is exponential, when time
is measured in units of $t_{\mathrm{mix}}$, specifically,
$d(\ell\,t_{\mathrm{mix}})\leq 2^{-\ell}$, for all $\ell\in\mathbb{N}$. The
central question is then: is $t_{\mathrm{mix}}$ bounded by a polynomial in
$n=|V(G)|$ and, more particularly, whether $t_{\mathrm{mix}}=O(n\log n)$ (with
the constant of proportionality being a function of $\lambda$ and $\Delta$).

For a short while we change perspective very slightly and view independent
sets in $G$ as spin configurations in $\\{0,1\\}^{V(G)}$. Naturally, the
independent set $I\in\mathcal{I}_{G}$ corresponds to the spin configuration
$\sigma$, where

$\sigma(v)=\begin{cases}0,&\text{if $v\notin I$};\\\ 1,&\text{if $v\in
I$}.\end{cases}$

Let $\beta_{G,\lambda}$ be the product distribution of independent Bernoulli
random variables, with success probability $p=\lambda/(1+\lambda)$ living on
the vertices of $G$. The following simple fact will be important in what
follows.

######  Lemma 1.

The distribution $\beta_{G,\lambda}$ stochastically dominates the distribution
$\mu_{G,\lambda}$. That is, there is a coupling of random variables, $\sigma$
and $\sigma^{\prime}$, distributed as $\mu_{G,\lambda}$ and
$\beta_{G,\lambda}$, respectively, such that $\sigma\leq\sigma^{\prime}$ in
the product order on $\\{0,1\\}^{V(G)}$.

###### Proof.

A simple way to see this is by monotone coupling of Markov chains [13,
§3.10.3]. Modify the Markov chain from Figure 2 by removing the test
$\Gamma_{G}(v)\cap I=\emptyset$ and the ‘else’ part of the conditional
statement. Thus the probabilistic update is done whatever the state of the
vertices adjacent to $v$. This modified process clearly converges to the
product distribution $\beta_{G,\lambda}$. Now run the modified process
starting from the all-1 configuration in parallel with Glauber dynamics
starting from the all-0 configuration. Use the same random choice of vertex
$v$ at each step, and optimally couple the updates. It is easy to see that the
first process remains above the second in the product order. The upper process
converges to $\beta_{G,\lambda}$ and the lower to $\mu_{G,\lambda}$. ∎

######  Corollary 2.

Let $G$ be a graph of maximum degree $\Delta$, and $v$ be a vertex of $G$. If
$I$ is sampled from $\mu_{G,\lambda}$ then

$\frac{\lambda}{(1+\lambda)^{\Delta+1}}\leq\Pr(v\in
I)\leq\frac{\lambda}{1+\lambda}.$

###### Proof.

The upper bound is immediate from Lemma 1. For the lower bound, note that
$\Pr(I\cap\Gamma(v)=\emptyset)\geq 1/(1+\lambda)^{\Delta}$, and that $\Pr(v\in
I\mid I\cap\Gamma(v)=\emptyset)\geq\lambda/(1+\lambda)$, again from Lemma 1. ∎

Suppose $\mu$ and $\mu^{\prime}$ are probability distributions on
$\\{0,1\\}^{V(G)}$. The Wasserstein (or Kantorovich-Rubinstein) distance
between $\mu$ and $\mu^{\prime}$ (specialised to this application) is defined
to be

$W_{1}(\mu,\mu^{\prime})=\inf_{\sigma\sim\mu,\sigma^{\prime}\sim\mu^{\prime}}d_{\mathrm{H}}(\sigma,\sigma^{\prime}),$

where $d_{\mathrm{H}}$ denotes Hamming distance, and the infimum is over all
couplings of random variables $\sigma,\sigma^{\prime}$ with the appropriate
distributions.

For a graph $G$ and vertex $v\in V(G)$ let $\mu_{G,\lambda}^{(v,0)}$
(respectively, $\mu_{G,\lambda}^{(v,1)}$) denote the hard-core distribution on
$G$ conditioned on vertex $v$ being excluded from (respectively, included in)
the independent set. We will be using the powerful spectral independence
machinery of Anari, Liu, Oveis Gharan and Vinzant [4] as sharpened by Cryan,
Guo and Mousa [11] and Chen, Liu and Vigoda [8]. However, we can ease our task
by using Chen and Gu’s packaging of the machinery for situations such as ours.
Indeed, to show optimal mixing we just need to construct a coupling that
achieves bounded Wasserstein distance
$W_{1}\big{(}\mu_{G,\lambda}^{(v,0)},\mu_{G,\lambda}^{(v,1)}\big{)}$.

######  Corollary 3.

Let $\mathcal{G}$ be a hereditary class of graphs with degree bound $\Delta$,
and $\lambda$ be positive. Suppose there exists $\eta$ such that for all
$G\in\mathcal{G}$ and all $v\in V(G)$ we have
$W_{1}(\mu_{G,\lambda}^{(v,0)},\mu_{G,\lambda}^{(v,1)})\leq\eta$, where
$\mu_{G,\lambda}$ is the hard-core distribution with fugacity $\lambda$ on
$V(G)$. Then the mixing time of Glauber dynamics for the hard-core model on
$G\in\mathcal{G}$ is bounded above by $O(n\log n)$, where $n=|V(G)|$. The
constant implicit in the $O$-notation depends on $\lambda$, $\Delta$ and
$\eta$.

###### Proof.

This follows from [7, Thm 9 and Lemma 10],111The quoted results are stated for
edge-based configurations rather than vertex-based, but this is inessential.
which builds on earlier work, such as [8]. In order to make the correspondence
we need to discuss briefly the notion of ‘pinning’. The distributions
$\mu_{G,\lambda}^{(v,0)}$ and $\mu_{G,\lambda}^{(v,1)}$ are examples of
distributions obtained by pinning, in this instance by pinning vertex $v$ to 0
and 1, respectively. More generally, we may consider pinning a set of
vertices, say $\Lambda\subset V(G)$, to values given by
$\tau:\Lambda\to\\{0,1\\}$, resulting in a marginal distribution
$\mu_{G,\lambda}^{(\Lambda,\tau)}$ on $V(G)\setminus\Lambda$. Lemma 10 of [7]
quantifies over pairs of pinnings $(\Lambda,\tau)$ and
$(\Lambda,\tau^{\prime})$ where $\tau$ and $\tau^{\prime}$ differ at exactly
one point. However, the hard-core distribution has a pleasant property:
pinning a vertex $v$ to 0 is equivalent to removing $v$ from the graph, while
pinning $v$ to 1 is equivalent to removing $v$ and all its neighbours. So, in
the case of the hard-core model we need only quantify over single vertex
pinnings, since we are restricting attention to graph classes which are closed
under taking induced subgraphs.

From our premisses, Lemma 10 of [7] tells us that that $\mu_{G,\lambda}$ is
‘$\eta$-spectrally bounded’. For our purposes we don’t need to define this
concept as we are merely going to feed this information about
$\mu_{G,\lambda}$ into Theorem 9 of [7]. The remaining premiss required for
this theorem is that $\mu_{G,\lambda}$ is ‘$b$-marginally bounded’. This just
means that $\Pr(\sigma(v)=1)$ is bounded away from both 0 and 1 by a margin
$b$. But this is exactly what is guaranteed by Corollary 2, with
$b=\min\\{\lambda/(1+\lambda)^{\Delta+1},1/(1+\lambda)\\}$. ∎

##  3\. $S_{1,1,t}$-free graphs (claw-free and upwards)

Suppose $\Delta\geq 3$ is a degree bound and $H$ a fixed graph. Let $G$ be an
$H$-free connected graph of maximum degree $\Delta$. Chen and Gu [7, Thm 4]
show optimal mixing of Glauber dynamics for the hard-core model on $G$, for
any given fugacity $\lambda$, when the excluded graph $H$ is the claw. In
fact, optimal mixing also holds for $H=S_{1,1,t}$ with $t\geq 2$, for a rather
dull reason. Define

$\mathop{\mathrm{vol}}(\Delta,t)=1+\Delta\frac{(\Delta-1)^{t}-1}{\Delta-2},$

and note that $\mathop{\mathrm{vol}}(\Delta,t)$ bounds the number of vertices
in a radius-$t$ ball around any vertex of a graph of maximum degree $\Delta$.

######  Lemma 4.

Suppose that $G$ is a connected graph of maximum degree $\Delta$, and that
$t\geq 2$. If $|V(G)|>\mathop{\mathrm{vol}}(\Delta,t+1)$ and $G$ contains an
induced claw, then $G$ contains an induced $S_{1,1,t}$.

###### Proof.

Let $G$ be as in the statement and suppose $\\{v,a,b,c\\}\subseteq V(G)$
induces a claw centred at $v$. As $\mathop{\mathrm{vol}}(\Delta,t+1)$ is an
upper bound on the number of vertices of $G$ within distance $t+1$ of $v$,
there must exist a vertex $w$ at distance $t+2$ from $v$. Consider a minimum
length path from $\\{v,a,b,c\\}$ to $w$, which clearly has length at least
$t+1$. Let this path be $P=(w_{0},w_{1},\ldots,w_{s})$, where
$w_{0}\in\\{v,a,b,c\\}$, $w_{s}=w$ and $s\geq t+1$. Consider the graph induced
by the vertex set $U=\\{v,a,b,c,w_{1},w_{2},\ldots,w_{s}\\}$. By minimality of
$P$, the graph $G[U]$ contains edges
$\\{\\{v,a\\},\\{v,b\\},\\{v,c\\},\\{w_{1},w_{2}\\},\\{w_{2},w_{3}\\},\ldots,\\{w_{s-1},w_{s}\\}\\}$
together with some non-empty subset $A$ of
$\\{\\{v,w_{1}\\},\\{a,w_{1}\\},\\{b,w_{1}\\},\\{c,w_{1}\\}\\}$. The 15
possibilities for $A$ fall into four cases, up to symmetry:

  * •

$A=\\{\\{v,w_{1}\\}\\}$: the set $\\{v,a,b,w_{1},\ldots,w_{s-1}\\}$ induces
$S_{1,1,t}$;

  * •

$A=\\{\\{a,w_{1}\\}\\}$: the set $\\{v,b,c,a,w_{1},\ldots,w_{s-2}\\}$ induces
$S_{1,1,t}$;

  * •

$A=\\{\\{v,w_{1}\\},\\{a,w_{1}\\}\\}$: the set
$\\{v,b,c,w_{1},\ldots,w_{s-1}\\}$ induces $S_{1,1,t}$;

  * •

$A\supseteq\\{\\{a,w_{1}\\},\\{b,w_{1}\\}\\}$: the set
$\\{w_{1},a,b,w_{2},\ldots,w_{s}\\}$ induces $S_{1,1,t}$.

The cases are exhaustive, completing the proof. ∎

######  Corollary 5.

Restricted to connected graphs of maximum degree $\Delta$, the class of
$S_{1,1,t}$-free graphs is a finite variation of the class of claw-free
graphs, for any $t\geq 2$.

######  Corollary 6.

For any $\Delta\geq 3$ any $t\geq 1$ and any $\lambda>0$, Glauber dynamics for
the hard-core model at fugacity $\lambda$ has mixing time $O(n\log n)$ on the
class of $S_{1,1,t}$-free graphs of maximum degree $\Delta$.

###### Proof.

This is immediate from [7, Thm 4] and Corollary 5. ∎

##  4\. $S_{1,2,t}$-free graphs (E-free and upwards)

Before heading off to larger graph classes it is instructive to go back to a
precursor of [7]. Van den Berg and Brouwer [20] construct an explicit coupling
for matchings in a bounded-degree graph that (in modern terms) bounds spectral
independence. This almost immediately gives optimal mixing of Glauber dynamics
for the monomer-dimer model at all temperatures. (Of course, van den Berg and
Brouwer did not have the spectral independence technology, so they were only
able to deduce low-degree polynomial mixing time.) Their method extends easily
to independent sets in claw-free graphs (though this was not stated in their
paper). In this section, we rederive the result of Chen and Gu, as the proof
will provide a base from which we may progress to large subdivided claws.

  * •

Let $R$ is a random ‘red’ independent set from $\mu_{G,\lambda}^{(v,1)}$

  * •

Let $B$ be a random ‘blue’ independent set from $\mu_{G,\lambda}^{(v,0)}$,
with $B$ independent of $R$.

  * •

Consider the subgraph $G[R\cup B]$ of $G$ induced by the union of the two
independent sets. Let $C\subseteq V(G)$ be the connected component of $G[R\cup
Y]$ containing $v$. We refer to $C$ as a cluster.

  * •

Modify the blue independent set by setting $B\leftarrow(B\cap
C)\cup(R\setminus C)$. Thus, $B$ is made to agree with $B$ inside $C$ and with
$R$ outside. The independent set $R$ remains unchanged.

  * •

$(R,B)$ is the required coupling.

Figure 3. The coupling of van den Berg and Brouwer. Here, $G$ is a graph,
$v\in V(G)$ and $\lambda>0$.

The coupling of van den Berg and Brouwer, translated to independent sets, is
given in Figure 3.

######  Lemma 7.

Let $G$ be a connected claw-free graph of maximum degree $\Delta$, $v\in
V(G)$, and $\lambda>0$. Then the coupling of Figure 3 is correct: $R$ is a
sample from $\mu_{G,\lambda}^{(v,1)}$ and $B$ is a sample from
$\mu_{G,\lambda}^{(v,0)}$,

###### Proof.

Since the independent set $R$ was never modified, it is clearly a sample from
$\mu_{G,\lambda}^{(v,1)}$.

For $B$, we argue as follows. Think of the pair $R,B$ being selected as
follows. First we select the cluster $C\subseteq V(G)$, as if it had been
formed from a pair of independent sets $R,B$ as above. Since $G[C]$ is a
connected bipartite graph, and $v\in R$, we can reconstruct the portion of $R$
and $B$ lying within $C$. Denote by

$\partial C=\\{w\in V(G)\setminus C:\\{w,u\\}\in E(G)\text{ for some }u\in
C\\}$

the boundary of $C$. A subset $R_{\mathrm{ext}}\subseteq V(G)\setminus C$
extends $R_{\mathrm{int}}=R\cap C$ to an independent set
$R=R_{\mathrm{int}}\cup R_{\mathrm{ext}}$ on the whole of $V(G)$ if and only
if $R_{\mathrm{ext}}$ is an independent set of the graph
$G[V(G)\setminus(C\cup\partial C)]$. (A vertex in $R_{\mathrm{ext}}$ certainly
cannot be adjacent to a red vertex in the cluster $C$, and it cannot be
adjacent to a blue vertex by maximality of $C$.) Exactly the same is true of
extensions $B_{\mathrm{ext}}$ of $B_{\mathrm{int}}=B\cap C$. In short, the set
of possible extensions to $B_{\mathrm{int}}$ and $R_{\mathrm{int}}$ are
identical. Informally, $R_{\mathrm{ext}}$ is equally valid as an extension of
$B_{\mathrm{int}}$ as $B_{\mathrm{ext}}$ is. Thus $B=B_{\mathrm{int}}\cup
R_{\mathrm{ext}}$ is a true sample from $\mu_{G,\lambda}^{(v,0)}$. ∎

Algorithm 1 Growing a red-blue cluster by Breadth-First Search (BFS).

$\textsf{Cluster BFS}(v)$

$L_{0}\leftarrow\\{v\\}$

$U\leftarrow V(G)\setminus\\{v\\}$ // the set of unprocessed vertices

$d\leftarrow 0$ // current depth of search

while $L_{d}\not=\emptyset$ do

$N\leftarrow U\cap\partial L_{d}$ // $\partial L_{d}=\\{u\in V(G)\setminus
L_{d}:\\{u,w\\}\in E(G)\text{ for some }w\in L_{d}\\}$

if $d$ is even then

reveal the blue vertices within $N$, and set $L_{d+1}\leftarrow N\cap B$

else

reveal the red vertices within $N$, and set $L_{d+1}\leftarrow N\cap R$

end if

$U\leftarrow U\setminus N$

$d\leftarrow d+1$

end while

$d\leftarrow d-1$ // The red-blue cluster containing $v$ is $C=L_{0}\cup
L_{1}\cup\cdots\cup L_{d}$

Using this coupling we can rederive the result of Chen and Gu.

######  Corollary 8.

Suppose that $\Delta\geq 3$ and $\lambda>0$. If $G$ is a claw-free graph of
maximum degree $\Delta$ and $v\in V(G)$, then
$W_{1}(\mu_{G,\lambda}^{(v,0)},\mu_{G,\lambda}^{(v,1)})=O(1)$.

###### Proof.

The claimed bound on $W_{1}$ is evidenced by the coupling just analysed. As
$|R\oplus B|=|C|$, we just have to demonstrate that $|C|$ is small in
expectation. Note that $G[C]$ is bipartite. It is straightforward to see that
a connected bipartite claw-free graph can have no vertices of degree 3 or
greater, so is either a path or a cycle. As paths and cycles are one-
dimensional structures, we do not expect them to propagate far, and this is
indeed the case. Imagine that we reveal the colours of vertices in a breadth-
first fashion, starting with $v$ at time 0. The breadth-first search is
presented as Algorithm 1. This is a little heavy for current purposes, but its
generality will be useful later. As the cluster is either a path or a cycle,
we have $|L_{j}|\leq 2$ for all levels $j$. Since the hard core distribution
is dominated by the product of independent Bernoullli distributions (Lemma 1),
on each iteration, with probability at least $p=(1/(\lambda+1))^{2\Delta}$,
the breadth-first search will halt. So
$\mathop{\mathbb{E\hbox{}}}|C|=\mathop{\mathbb{E\hbox{}}}[|R\oplus B|]$ is
bounded above by the expectation of a random variable having a geometric
distribution with success probability $(\lambda+1)^{-2\Delta}$, which is
$(\lambda+1)^{2\Delta}$. ∎

Then, by Corollary 3 we obtain:

######  Corollary 9.

For any $\Delta\geq 3$ and $\lambda>0$, Glauber dynamics at fugacity $\lambda$
has optimal (i.e., $O(n\log n)$) mixing time on the class of claw-free graphs
of maximum degree $\Delta$.

Let’s make some modest steps towards excluding larger subdivided claws.222The
remainder of the section is not essential to the technical development of the
main result, Theorem 16, relating to general subdivided claws. However, it
contains some contextual material on graphs with excluded subdivided claws,
and also motivates the approach taken in Section 5. Fork-free graphs were
characterised by Alekseev [2]. See also Bencs [6]. A connected bipartite fork-
free graph is either a path, a cycle, or a complete bipartite graph minus a
(possibly empty) matching. Since the last of these can have size at most
$2(\Delta+1)$, the argument just given in the Proof of Lemma 7 for claw-free
graphs carries over to fork-free graphs, as the expected size of a cluster is
still constant. However, as we already saw in Corollary 5, this generalisation
is illusory.

$\vdots$$\vdots$$\vdots$$\dots$$\dots$ Figure 4. An (infinite family of)
E-free but not fork-free graph(s).

The first interesting case beyond claw free is E-free (i.e.,
$S_{1,2,2}$-free). Figure 4 illustrates an infinite family of E-free graphs
which are not claw free. Indeed, by iterating the basic building block either
horizontally or vertically, or both, we can appreciate that the family
includes graphs that contain induced copies of $S_{1,1,t}$ for arbitrarily
large $t$. (An instance of a fork is picked out in red in Figure 4.) So, by
excluding E, we have escaped from the constraints of Corollary 5 into new,
apparently interesting families of graphs.

It is worth recording the fact that there is no analogue of Corollary 5 for
the sequence of $S_{1,2,t}$-free graph classes. For example, suppose we
construct a graph $G$ as a disjoint union of an E together with a path of
arbitrary length, with endpoints $a$ and $b$, and then add edges from $a$ to
all vertices in the E. We claim that $G$ is skew-star-free (i.e.,
$S_{1,2,3}$-free). Suppose to the contrary that $G$ contains an induced skew-
star. This induced graph would have to include vertex $a$ together with at
least one edge $e$ from the E. But the endpoints of $e$ together with $a$
induce a triangle, which is a contradiction. So there are infinitely many
skew-star free graphs of degree at most 7 that are not E-free.

At this point we skip the class of E-free graphs and proceed directly to the
larger class of skew-star-free graphs as these have been analysed in detail by
Lozin [17] in his ‘Decomposition Theorem’. He showed that a connected
bipartite skew-star-free graph is of one of four kinds. Three of these are of
bounded size, while the fourth is composed of blow-ups of paths and cycles. (A
blow-up of a graph $H$ is obtained by replacing each vertex of $H$ by an
independent set, and each edge by a complete bipartite graph connecting the
corresponding independent sets.) As the unbounded components are still
‘linear’, we continue to have spectral independence and optimal mixing of
Glauber dynamics. The only change to the proof of Corollary 8 lies in the
analysis of the level sets $L_{i}$ generated by the breadth-first search: we
now have $|L_{i}|\leq 2(\Delta-1)$ rather than $|L_{j}|\leq 2$.

######  Corollary 10.

Suppose that $\Delta\geq 3$ and $\lambda>0$. If $G$ is a skew-star-free graph
of maximum degree $\Delta$ and $v\in V(G)$, then
$W_{1}(\mu_{G,\lambda}^{(v,0)},\mu_{G,\lambda}^{(v,1)})=O(1)$.

######  Corollary 11.

For any $\Delta\geq 3$ and $\lambda>0$, Glauber dynamics at fugacity $\lambda$
has optimal (i.e., $O(n\log n)$) mixing time on the class of skew-star-free
(and hence E-free) graphs of maximum degree $\Delta$.

As we saw earlier, there is no direct analogue of Lemma 4 with $S_{1,2,2}$
replacing $S_{1,1,1}$, and $S_{1,2,t}$ replacing $S_{1,1,t}$. But if we add
the condition of bipartiteness we do have:

######  Lemma 12.

Suppose that $G$ is a connected bipartite graph of maximum degree $\Delta$,
and that $t\geq 3$. If $|V(G)|>\mathop{\mathrm{vol}}(\Delta,t+2)$ and $G$
contains an induced $S_{1,2,2}$, then $G$ contains an induced $S_{1,2,t}$.

This may be proved in a similar way to Lemma 4, but we omit the proof as it is
not on the direct line to the main result.

######  Corollary 13.

For any $\Delta\geq 3$, $\lambda>0$ and $t\geq 2$, Glauber dynamics at
fugacity $\lambda$ has optimal (i.e., $O(n\log n)$) mixing time on the class
of $S_{1,2,t}$-free graphs of maximum degree $\Delta$.

###### Sketch proof.

The cluster containing $v$ is either of bounded size or is the blow-up of a
path or cycle. The layers $L_{i}$ created by the breadth-first search of
Algorithm 1 are of bounded size, so the depth of the search is again bounded
by a geometric random variable. ∎

We have seen that in the case of $S_{1,1,t}$-free graphs and $S_{1,2,t}$-free
graphs the cluster generated by Algorithm 1 is either of bounded size, or is
‘linear’ (in this case a blow-up of either a path or a cycle). We may suspect
that this remains true for graphs excluding larger subdivided stars. While
this is morally true, it is difficult to provide a suitable definition of
‘linear’ that meshes with the coupling argument. We therefore slightly change
our approach.

##  5\. $S_{2,2,2}$-free graphs and beyond

Instead of trying to analyse the structure of bounded-degree bipartite graphs
excluding a large subdivided claw, we will analyse the BFS procedure of
Algorithm 1 directly. Recall the layers $L_{i}$ that are produced by the
search. The key observation is that these layers do not grow large.

######  Lemma 14.

If $G$ is $S_{t,t,t}$-free then $|L_{i}|\leq
2\mathop{\mathrm{vol}}(\Delta,2t)$, for all $i\in\mathbb{N}$ for which $L_{i}$
is defined.

###### Proof.

Suppose to the contrary that $|L_{i}|>2\mathop{\mathrm{vol}}(\Delta,2t)$.
Choose vertices $a,b,c\in L_{i}$ with the property that $d_{G}(a,b)$,
$d_{G}(a,c)$ and $d_{G}(b,c)$ are all greater than $2t$. This is always
possible: select $a$ arbitrarily, and eliminate from consideration the at most
$\mathop{\mathrm{vol}}(\Delta,2t)$ vertices in $L_{i}$ that are within
distance $2t$ from $a$; choose $b$ from the remaining vertices and eliminate
the vertices in $L_{i}$ that are within distance $2t$ from $b$; at least one
choice for $c$ remains.

Now orient all edges away from $v$, so that each edge goes from level $L_{j}$
to $L_{j+1}$ for some $j$. Choose a minimum cardinality directed Steiner tree
$T$ connecting $v$ (as root) to all of $a,b,c$. Consider the graph
$T^{\prime}$ induced by $V(T)$. Suppose that $T^{\prime}$ has some edge not in
$E(T)$, say $e=\\{u_{j},u_{j+1}\\}$ where $u_{j}\in L_{j}$ and $u_{j+1}\in
L_{j+1}$. (Recall that $T^{\prime}$ is bipartite, so there are no edges within
a layer; also the levels were constructed by breadth-first search, so no edges
of $T^{\prime}$ skip a layer.)

First assume that $T$ has a single vertex $w$ such that either $w\not=v$ and
$\deg(w)=4$ or $w=v$ and $\deg(w)=3$. Note that all vertices of $T$ other than
$v,w,a,b,c$ have degree 2. By adding $e$ to $E(T)$ and removing the edges of
$T$ lying between $w$ and $u_{j+1}$ we obtain a smaller tree, contradicting
minimality of $T$. (Notice that we must remove at least two edges.) By choice
of $a,b,c$ we know that $d_{T}(w,a),d_{T}(w,b),d_{T}(w,c)\geq t+1$, so $G$
contains an induced $S_{t,t,t}$. (Note that we are measuring graph distances
within the tree $T$ here.)

Next assume that $T$ has two vertices $w$ and $w^{\prime}$, with $w^{\prime}$
in a higher numbered level than $w$, and such that either (i) $w\not=v$ and
and $\deg(w)=\deg(w^{\prime})=3$ or (ii) $w=v$ and $\deg(w)=2$ and
$\deg(w^{\prime})=3$. Note that all vertices of $T$ other that
$v,w,w^{\prime},a,b,c$ have degree 2. Suppose, without loss of generality,
that $a$ and $b$ are descendants of $w^{\prime}$. With two exceptions, we may
add $e$ to $E(T)$ and remove all the edges between $u_{j+1}$ and $w$, or
$w^{\prime}$ as appropriate, to obtain a smaller tree, contradicting
minimality of $T$. Those exceptions occur when $w^{\prime}\in L_{j}$, i.e.,
$u_{j}$ is in the same level as $w^{\prime}$. In that case, one edge is added
and one removed and the size of the tree remains unchanged. There are two
candidate vertices for $u_{j+1}$; these are the vertices in $L_{j+1}\cap
V(T)$, say $x$ and $y$, that are adjacent to $w^{\prime}$. Let $x$
(respectively, $y$) be the vertex on the path in $T$ from $w^{\prime}$ to $a$
(respectively $b$). To summarise: The graph induced by $V(T)$ is tree $T$,
with the possible addition of one or two of the edges $\\{u_{j},x\\}$ and
$\\{u_{j},y\\}$. (Refer to Figure 5.)

$v$$w$$w^{\prime}$$u_{j}$$x$$y$$a$$b$$c$$L_{0}$$\uparrow$$L_{j}$$\uparrow$$L_{j+1}$$\uparrow$$L_{i}$$\uparrow$
Figure 5. The two exceptional edges (shown red, dotted). The solid lines are
edges and the dot-dashed lines are paths.

By choice of $a,b,c$ we know that $d_{T}(w^{\prime},a),d_{T}(w^{\prime},b)\geq
t+1$. In the case that neither of the exceptional edges in present, we have an
induced $S_{t,t,t}$ with its centre at $w^{\prime}$ and with the path from
$w^{\prime}$ to $c$ routing via $w$. In the case of one exceptional edge, say
$\\{u_{j},x\\}$, we have an induced $S_{t,t,t}$ with its centre at $x$ and
with the path from $x$ to $b$ routing via $w^{\prime}$, and the path from $x$
to $c$ routing via $u_{j}$. In the case of two exceptional edges, we have an
induced $S_{t,t,t}$ with its centre at $u_{j}$ and with the path from $u_{j}$
to $a$ routing via $x$, and the path from $u_{j}$ to $b$ routing via $y$.

As the above cases are exhaustive, we obtain a contradiction to $G$ being
$S_{t,t,t}$-free. ∎

######  Corollary 15.

Suppose that $\Delta\geq 3$, $\lambda>0$ and $t\geq 2$. If $G$ is a
$S_{t,t,t}$-free graph of maximum degree $\Delta$ and $v\in V(G)$, then
$W_{1}(\mu_{G,\lambda}^{(v,0)},\mu_{G,\lambda}^{(v,1)})=O(1)$.

###### Proof.

The levels of the breadth-first search remain bounded. There is a constant
probability of the search terminating at each iteration. ∎

######  Theorem 16.

For any $\Delta\geq 3$, $\lambda>0$ and $t\geq 2$, Glauber dynamics at
fugacity $\lambda$ has optimal (i.e., $O(n\log n)$) mixing time on the class
of $S_{t,t,t}$-free graphs of maximum degree $\Delta$.

###### Proof.

Follows immediately using Corollary 3. ∎

Naturally, the theorem also covers $S_{i,j,k}$-free graphs by taking
$t=\max\\{i,j,k\\}$.

##  6\. Exponential-time mixing of $H$-free graphs
when $H$ is neither a path nor a subdivided claw

To complete the dichotomy, it only remains to show:

######  Theorem 17.

Let $H$ be a connected graph that is not a subdivided claw or a path. There
exists a fugacity $\lambda$ and an infinite family $\mathcal{G}$ of $H$-free
graphs of maximum degree 3 such that Glauber dynamics for the hard-core
distribution on these graphs has exponential mixing time on $\mathcal{G}$.

###### Proof.

Let $\alpha>0$ be sufficiently small. Given $n$, let $G$ be a cubic bipartite
graph on $n+n$ vertices that is a $1+\alpha$ expander for sets up to size
$\frac{2}{3}n$. Such graphs exists by a lemma due to Bassalygo [5]; see Alon
[3, Lemma 4.1]. Let $V_{L}\cup V_{R}=V(G)$ be the bipartition of the vertex
set of $G$. Let $\ell$ be a number and let $G^{*}$ denote the
$(2\ell+1)$-stretch of $G$; that is, $G^{*}$ is obtained from $G$ by
subdividing each edge by $2\ell$ new vertices. Fix $\ell$ sufficiently large
that $G^{*}$ contains no induced $H$. Let $V_{L}$ and $V_{R}$ continue to
denote the vertices in $G^{*}$ that are inherited from $G$.

Let $\mathcal{I}_{<}\cup\mathcal{I}_{=}\cup\mathcal{I}_{>}=\mathcal{I}_{G}$ be
the partition of the independent sets $\mathcal{I}_{G}$ of $G$ given by:

$\mathcal{I}_{\circ}=\\{I\in\mathcal{I}:|I\cap V_{L}|\circ|I\cap V_{R}|\\},$

where $\circ\in\\{<,=,>\\}$. Note that, to pass from any independent set in
$\mathcal{I}_{<}$ to any independent set in $\mathcal{I}_{>}$, Glauber
dynamics must pass through an independent set in $\mathcal{I}_{=}$. To show an
exponential lower bound on mixing time it is enough to verify that
$\mathrm{wt}(\mathcal{I}_{=})\leq
e^{-cn}\min\\{\mathrm{wt}(\mathcal{I}_{<}),\mathrm{wt}(\mathcal{I}_{>})\\}$
for some $c>0$.333Here, we have extended $\mathrm{wt}(\cdot)$ from
configurations to sets of configurations in the obvious way. This inequality
implies that the ‘conductance’ of Glauber dynamics on $G^{*}$ is exponential
small, and hence that the mixing time is exponentially large [15, Claim 7.14].

Note that $G^{*}$ is bipartite, with a balanced bipartition, and having
$|V(G^{*})|=(6\ell+2)n$ vertices. By selecting all vertices on one side of the
bipartition we obtain an independent set of size $(3\ell+1)n$ in
$\mathcal{I}_{<}$, and by selecting all vertices in the opposite side an
independent set of the same size in $\mathcal{I}_{>}$. Just considering these
two independent sets we see that

$\mathrm{wt}(\mathcal{I}_{<}),\mathrm{wt}(\mathcal{I}_{>})\geq\lambda^{(3\ell+1)n}.$

We will show that the independent sets in $\mathcal{I}_{=}$ all have
cardinality significantly less than $(3\ell+1)n$. So if $\lambda$ is
sufficiently large, the total weight $\mathrm{wt}(\mathcal{I}_{=})$ of
independent sets in $\mathcal{I}_{=}$ will be exponentially smaller than
$\mathrm{wt}(\mathcal{I}_{<})$, even though the former are more numerous.
(‘Energy’ wins out over ‘entropy’.) So consider an independent set $I$ with
$|I\cap V_{L}|=|I\cap V_{R}|=k$. In general, each of the paths of length
$2\ell+1$ in $G^{*}$ joining a vertex $u$ in $V_{L}$ to a vertex $v$ in
$V_{R}$ is able to support an independent set of cardinality $\ell$ on its
internal vertices (the vertices that are neither in $V_{L}$ nor in $V_{R}$).
However, if $u$ and $v$ are both in $I$ then the internal vertices can only
support an independent set of size $\ell-1$.

By expansion, if $n/(2+\alpha)\leq k\leq\frac{2}{3}n$, there must be at least
$(2+\alpha)k-n$ of these deficient paths. Thus, when $0\leq
k\leq\frac{2}{3}n$, the cardinality of an independent set $I$ in $G^{*}$ with
$|I\cap V_{L}|=|I\cap V_{R}|=k$ is at most

$|I|=2k+3\ell n-\max\\{(2+\alpha)k-n,0\\}.$

The maximum of this expression is achieved at $k=n/(2+\alpha)$ where it takes
the value $(3\ell+2/(2+\alpha))n$. When $k>\frac{2}{3}n$ there is a simpler
argument. There are $3k$ edges of $G$ leaving the set $I\cap V_{L}$ and at
most $3(n-k)$ of these can be accommodated in $V_{R}\setminus I$. So there are
at least $6k-3n$ deficient paths and the cardinality of an independent set in
this range is at most $2k+3\ell n-(6k-3n)=(3\ell+3)n-4k$. This expression is
maximised at $k=\frac{2}{3}n$, at which point it evaluates to
$(3\ell+\frac{1}{3})n$. Over the whole range of $k$, the maximum cardinality
of an independent set in $\mathcal{I}_{=}$ is bounded by
$(3\ell+2/(2+\alpha))n$.

As $|V(G^{*})|=(6\ell+2)n$, the total weight of independent sets in
$\mathcal{I}_{=}$ is at most

$\mathrm{wt}(\mathcal{I}_{=})\leq
2^{(6\ell+2)n}\lambda^{(3\ell+2/(2+\alpha))n},$

and hence the ratio of $\mathrm{wt}(\mathcal{I}_{=})$ to
$\mathrm{wt}(\mathcal{I}_{<})$ is at most

$\frac{\mathrm{wt}(\mathcal{I}_{=})}{\mathrm{wt}(\mathcal{I}_{<})}\leq\big{(}2^{6\ell+2}\lambda^{2/(2+\alpha)-1}\big{)}^{n}.$

By setting $\lambda$ sufficiently large in terms of $\ell$ (which in turn is
determined by $H$) we can ensure that the above ratio is at most $2^{-n}$.
Thus, Glauber dynamics on $G^{*}$ has exponentially small conductance, and
exponentially large mixing time. ∎

######  Corollary 18.

Excluding any finite set of connected graphs that includes at least one
subdivided claw or path yields optimal mixing. Excluding any finite set of
connected graphs none of which is a subdivided claw or path retains
exponential time mixing.

###### Proof.

The positive direction is clear. For the negative direction, let $\mathcal{H}$
be the set of excluded graphs. For each $H\in\mathcal{H}$ there is a fugacity
$\lambda_{H}$ and a degree of stretching $\ell_{H}$ such that Theorem 17
yields an infinite family of graphs on which Glauber dynamics requires
exponential time for mixing. Now take $\lambda=\max_{H}\lambda_{H}$ and
$\ell=\max_{H}\ell_{H}$. ∎

## Acknowledgements

I thank Heng Guo and Viresh Patel for useful pointers.

## References

  * [1] Tara Abrishami, Maria Chudnovsky, Cemil Dibek, and Paweł Rzażewski.  Polynomial-time algorithm for maximum independent set in bounded-degree graphs with no long induced claws.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1448–1470. [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2022.
  * [2] V. E. Alekseev.  Polynomial algorithm for finding the largest independent sets in graphs without forks.  Discrete Appl. Math., 135(1-3):3–16, 2004.  Russian translations. II.
  * [3] N. Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.  Theory of computing (Singer Island, Fla., 1984).
  * [4] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid.  Ann. of Math. (2), 199(1):259–299, 2024.
  * [5] L. A. Bassalygo.  Asymptotically optimal switching circuits.  Problemy Peredachi Informatsii, 17(3):81–88, 1981.
  * [6] Ferenc Bencs.  Graphs, Groups and Measures.  PhD thesis, Central European University, 2019.
  * [7] Zongchen Chen and Yuzhou Gu.  Fast sampling of $b$-matchings and $b$-edge covers.  In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4972–4987. SIAM, Philadelphia, PA, 2024\.
  * [8] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion.  In STOC ’21—Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537–1550. ACM, New York, [2021] ©2021.
  * [9] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Rapid mixing of Glauber dynamics up to uniqueness via contraction.  SIAM J. Comput., 52(1):196–237, 2023.
  * [10] Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé.  Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $H$-Free Graphs.  SIAM J. Comput., 53(1):47–86, 2024.
  * [11] Mary Cryan, Heng Guo, and Giorgos Mousa.  Modified log-Sobolev inequalities for strongly log-concave distributions.  Ann. Probab., 49(1):506–525, 2021.
  * [12] Martin Dyer, Mark Jerrum, Haiko Müller, and Kristina Vus̆ković.  Counting weighted independent sets beyond the permanent.  SIAM J. Discrete Math., 35(2):1503–1524, 2021.
  * [13] S. Friedli and Y. Velenik.  Statistical mechanics of lattice systems.  Cambridge University Press, Cambridge, 2018.  A concrete mathematical introduction.
  * [14] Thomas P. Hayes and Alistair Sinclair.  A general lower bound for mixing of single-site dynamics on graphs.  Ann. Appl. Probab., 17(3):931–952, 2007.
  * [15] Mark Jerrum.  Counting, sampling and integrating: algorithms and complexity.  Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 2003\.
  * [16] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.  Markov chains and mixing times.  American Mathematical Society, Providence, RI, 2009.  With a chapter by James G. Propp and David B. Wilson.
  * [17] Vadim V. Lozin.  Bipartite graphs without a skew star.  Discrete Math., 257(1):83–100, 2002.
  * [18] James Matthews.  Markov Chains for Sampling Matchings.  PhD thesis, School of Informatics, University of Edinburgh, 2008.  http://hdl.handle.net/1842/3072.
  * [19] Allan Sly.  Computational transition at the uniqueness threshold.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010, pages 287–296. IEEE Computer Soc., Los Alamitos, CA, 2010.
  * [20] J. van den Berg and R. Brouwer.  Random sampling for the monomer-dimer model on a lattice.  J. Math. Phys., 41(3):1585–1597, 2000.  Probabilistic techniques in equilibrium and nonequilibrium statistical physics.
  * [21] Dror Weitz.  Counting independent sets up to the tree threshold.  In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 140–149. ACM, New York, 2006.