# Mito-nuclear selection induces a trade-off between
species ecological dominance and evolutionary lifespan

Débora Princepe  Instituto de Física ‘Gleb Wataghin’, Universidade Estadual de
Campinas, Campinas, Brazil  Marcus A. M. de Aguiar  Instituto de Física ‘Gleb
Wataghin’, Universidade Estadual de Campinas, Campinas, Brazil  Joshua B.
Plotkin  Department of Biology, University of Pennsylvania, Philadelphia, PA,
USA

Mitochondrial and nuclear genomes must be co-adapted to ensure proper cellular
respiration and energy production. Mito-nuclear incompatibility reduces
individual fitness and induces hybrid infertility, suggesting a possible role
in reproductive barriers and speciation. Here we develop a birth-death model
for evolution in spatially extended populations under selection for mito-
nuclear co-adaptation. Mating is constrained by physical and genetic
proximity, and offspring inherit nuclear genomes from both parents, with
recombination. The model predicts macroscopic patterns including a community’s
long-term species diversity, its species abundance distribution, speciation
and extinction rates, as well as intra- and inter-specific genetic variation.
We explore how these long-term outcomes depend upon the microscopic parameters
of reproduction: individual fitness governed by mito-nuclear compatibility,
constraints on mating compatibility, and ecological carrying capacity. We find
that strong selection for mito-nuclear compatibility reduces the equilibrium
number of species after a radiation, increases the species’ abundances, while
simultaneously increasing both speciation and extinction rates. The negative
correlation between species diversity and diversification rates in our model
agrees with the broad empirical pattern of lower species diversity and higher
speciation/extinction rates in temperate regions, compared to the tropics. We
therefore suggest that these empirical patterns may be caused in part by
latitudinal variation in metabolic demands, and corresponding variation in
selection on mito-nuclear function.

##  1 Introduction

The origin, maintenance, and extinction of species involve diverse ecological
and evolutionary mechanisms, so that they are rarely explained by a single
hypothesis [1, 2]. Mathematical models have still been helpful in
understanding empirical patterns of biodiversity, such as species abundance
distributions [3, 4, 5] and the species-area curve [6, 7], which are well
described by both neutral and niche-based theories of community assembly [8,
9]. However, models that explain these ecological features in a community
seldom make predictions for long-term evolutionary patterns, such as
speciation rates [10] and species lifetimes [11, 12, 13], nor do they provide
a mechanistic description for the formation of species [14, 15]. Studies
describing mechanisms of speciation, on the other hand, using both genetic
[16, 17] and ecological [18, 19, 20] drivers, rarely connect these processes
to macro-evolutionary patterns [21, 22, 23, 24], whereas macro-ecological
models succeed in reproducing such patterns [25, 26] but may lack a detailed
connection with organism and population properties to explain variation in
diversification rates [27, 28]. In this context, linking micro-evolutionary
processes to macro-evolutionary patterns is key to understanding what drives
diversification [29, 30, 31, 32, 33], especially when similar evolutionary
signatures can result from different population processes [23, 22, 34].

Here we study spatially distributed populations that evolve under selection
for mating compatibility between parents as well as mito-nuclear compatibility
within individuals [35]. Genetic interactions between the mitochondrial
(mtDNA) and nuclear (nDNA) genomes is necessary for cellular respiration,
which depends on biochemically compatible proteins [36, 37]. Incompatibilities
between those genes can severely reduce individual fitness and fertility [38,
39]. Thus, mutations in the mitochondrial genome induce selection for
compatible genes in the nuclear genome, driving molecular co-evolution [40]
and ultimately promoting compensatory changes [41]. Mito-nuclear co-evolution
has been hypothesized as a driver of speciation [42, 43, 44] possibly
preceding the evolution of reproductive barriers [45, 40, 46], although its
extent in nature remains unknown [47]. The influence of the respiration
efficiency in the availability of energy in eukaryotes, which connects to
ecological traits [48] and metabolic constraints [49], suggests that mito-
nuclear interaction leaves signatures across biological scales, from cellular
metabolism to individuals and populations [37, 50, 51].

We develop an individual-based model to describe selection on mito-nuclear
compatibility and we follow the process of radiation and eventual equilibrium
towards a stationary diversity of species. We incorporate the mitochondrial
genetic material and its interaction with a portion of the nuclear genome in a
phenomenological approach [35] based on the lock-and-key principle that guides
the interaction between proteins coded by both genomes [50, 38]. Simulations
of our model record all forms of diversification events – speciation,
extinction, and hybridization – and evaluate the impact of selection on the
emergence and persistence of species. In addition, we can use the model to
reconstruct the history of an extant community, analyzing the dominance of
species throughout their evolutionary lifetime. The model reveals how mito-
nuclear selection can jointly influence species abundances and diversity in a
community as well as long-term patterns of species lifetimes.

We use the results of our model to help explain longitudinal patterns in
species diversity and speciation rates, related to a cline of environmental
harshness. Selection on mito-nuclear compatibility is expected to be stronger
in harsh, temperate environments that demand optimal metabolic function.
Whereas tropical environments, where resources are abundant and energy
efficiency is less important, present weaker selection on mito-nuclear
compatibility and function. There are well-known patterns in diversity from
tropical to temperate regions, with the former displaying high biodiversity,
old species, and low speciation and extinction rates, and the latter with
fewer species and elevated recent speciation rates [52, 53, 54, 55, 56, 57].
We hypothesize that mito-nuclear selection might play a role in forming these
patterns, as resources availability should correlate to selection on metabolic
efficiency which, in turn, governs patterns of diversity and speciation rates
in our model.

##  2 Results

###  2.1 Model for mito-nuclear interaction

We employed an agent-based model (Fig. 1, Methods) based on [6], in which
neutral processes driven by recombination and mutation change the allele
frequencies in a population. The environment is homogeneous and the population
size is kept constant at the carrying capacity. Mating is restricted by both
genetic similarity and spatial proximity, so that species emerge through
isolation by distance [22]. Here we start from the same neutral assumptions
and introduce the mito-nuclear genetic compatibility as a measure of fitness
of individuals. Simulating populations that evolve under these micro-
evolutionary dynamics, we catalogue the resulting macro-evolutionary patterns
under weak and strong mito-nuclear selection.

Following [35], each individual is described by a haploid, bi-allelic sequence
of $B$ sites that represent its nuclear genome (nDNA). To describe the mito-
nuclear interaction we also consider a shorter string of $B_{M}$ sites
representing the individual’s mitochondrial genome (mtDNA). Sexes are
separated, and sexual reproduction with non-overlapping generations occurs as
follows: during the reproduction phase, all individuals have a probability to
randomly choose a mating partner within a spatial range of radius $S$, called
the mating neighborhood. Genetic compatibility between individuals is
determined by the Hamming distance between their nDNA’s, i.e., the number of
loci bearing different alleles, and must be below the threshold of $G$ sites
for successful mating. The nuclear genome of the offspring is built from
recombination of the nuclear material of the parents, with a probability of
mutation $\mu$ per site. The mtDNA is directly inherited from the mother, with
mutation probability per site $\mu_{M}$. Starting from identical individuals,
species emerge as clusters of genetically compatible individuals, i.e., as
groups with ongoing gene flow among individuals, determined by the genetic
mating restriction $G$, but no gene flow between different groups (see Methods
Section 4.1).

Figure 1: Model of selection on mito-nuclear compatibility. a, Individuals are
randomly distributed in a square domain and carry nuclear (nDNA) and
mitochondrial (mtDNA) genomes described by binary sequences of $B$ and $B_{M}$
sites, respectively. Sexual reproduction occurs with non-overlapping
generations. Individuals look for a mating partner within a spatial range of
radius $S$, and they must be genetically compatible (within nuclear distance
$G$) to mate. Offspring are generated with recombination of the nDNA and
mutation probability $\mu$ per locus, with direct inheritance of maternal
mtDNA with mutation $\mu_{M}$. b, Mito-nuclear compatibility of an individual
is measured by the distance between its mtDNA and $B_{M}$ corresponding within
the nDNA. In the absence of mito-nuclear selection, all individuals have equal
fitness. Under selection for mito-nuclear compatibility fitness is assigned to
an individual according to its mito-nuclear distance, with strength of
selection $\sigma_{w}$, with higher fitness implying higher probability to
reproduce. c, Species are classified as groups of individuals with ongoing
gene flow, and their abundances are recorded at each generation. We register
all speciation, hybridization, and extinctions events, and record the
lifespans of all species.

We model mito-nuclear compatibility in an individual as a locus-by-locus
interaction between the mtDNA and the first $B_{M}$ sites of the nuclear
genome (the remaining $(B-B_{M})$ nuclear genes do not participate in the
interaction); the interacting pair of loci is compatible if they have the same
allele value (Fig. 1b). The mito-nuclear distance $d$ is then the fraction of
incompatible sites. Such a scheme is a phenomenological description of the
biochemical and structural compatibility between proteins coded by both
genomes necessary for the respiration process [37, 50]. In the absence of
selection, all individuals have an equal probability of reproduction, and nDNA
and mtDNA evolve independently. When mito-nuclear compatibility is under
selection, fitness $w$ is assigned to individuals accordingly to their mito-
nuclear distance, with strength expressed by a parameter $\sigma_{w}$, such
that $w=e^{-d^{2}/2\sigma_{w}^{2}}$, i.e., small $\sigma_{w}$ implies strong
selection. Individuals with higher fitness, normalized within the mating
range, have a higher probability of reproduction. We tracked all events during
the dynamics, registering speciation, hybridization, and extinctions, and
recorded the ancestry of all species.

###  2.2 Diversification rates and species richness

We simulated the evolution of populations under various strengths of
selection, $\sigma_{w}$. In the non-interacting scenario (NI), the mito-
nuclear distance is not considered for reproduction (equivalent to
$\sigma_{w}\rightarrow\infty$). Selection was simulated with $\sigma_{w}$
ranging from 0.175 (weak selection) to 0.025 (strong selection). Results are
shown for 50 independent realizations for each set of parameters. Starting
from a population of identical individuals, all simulations are characterized
by a period of rapid increase in species numbers (a radiation period),
followed by relaxation to a steady-state species richness. During the
dynamics, all diversification events were registered (Fig. 2a). The
populations were simulated for $T=2,000$ generations, a time longer than
necessary for the completion of the radiation. The equilibrium, defined by the
moment when the number of species reaches a plateau, occurred after about
$T=500$ generations in all cases (Fig. 2b). Because the population size is
nearly constant, equilibrium results from a balance between speciation,
extinction and hybridization events (compatible with the hypothesis of
ecological limits [58]). Selection had the clear effect of reducing the number
of species in equilibrium and introducing a delay in the radiation process.

Figure 2: Diversification events and species richness. a, Accumulated number
of speciation, extinction, and hybridization events over time. b, Species
richness as function of time. c, Rates of speciation (Sp), extinction (Ext),
and hybridization (Hyb) obtained from regression of a in equilibrium
($T>500$). Results are shown for varying strength of the mito-nuclear
selection $\sigma_{w}$ (smaller $\sigma_{w}$ implies stronger selection) and
in the absence of selection (NI). Solid lines represent the ensemble mean over
50 independent realizations; and the shadowed area represents one standard
deviation from the mean. Selection decreases the number of species at
equilibrium, but it increases all rates of diversification events in steady-
state, with maximum rates occurring at intermediary values of $\sigma_{w}$.

We define a speciation event, or branching, as the moment when a species
splits into two or more reproductively isolated groups. The lifetime of the
mother species is considered over at this point and the species disappears as
two (or more) sister species are born, with a positive net balance in the
number of species. Species also disappear by extinction, when the population
becomes very small and eventually does not produce descendants due to random
ecological drift and by the accumulation of mito-nuclear incompatibilities
that lead to low fitness and low fecundity; or by hybridization when two or
more species reestablish gene flow. When species hybridize, we consider that
the more abundant species persists while the other one disappears as it
merges. Linear regression of the number of events in equilibrium provided the
rates of speciation, extinction, and hybridization (Fig. 2c). In the
equilibrium, when the average number of species becomes constant, the rate at
which species are born (speciation) is equal to the rate at which species die
(extinction plus hybridization). In this regime, speciation, extinction and
hybridization rates per species increase with the strength of selection (Fig.
LABEL:fig:ratio). However, since the number of extant species decreases with
selection, the nominal rates have a maximum for intermediate values of
$\sigma_{w}$, as shown in Figure 2c. The decrease in species richness, on the
other hand, results from the radiation process, because selection decreases
the net diversification (speciation minus extinction and hybridization) during
the transient (Fig. LABEL:fig:div_rates).

###  2.3 Species abundance distributions and lifespans

Selection on mito-nuclear compatibility decreased the number of species in
equilibrium, and because the population size is fixed, this led to an increase
in the average species abundance and variance of the species abundance
distributions (SADs) (Fig. 3a). Since our simulations resulted in an average
number of species no greater than 25, we accumulated data over several
independent runs to obtain a clear signal for the expected distribution of
abundances, for each value of $\sigma_{w}$. This procedure is justified
because the lattice is much larger than the mating range and species’ range
size are smaller than the available space (see Supplementary Information,
Section LABEL:SM2).

Figure 3: Species abundances distributions (SADs) at $T=1,000$ and respective
lifespans.  a, SADs obtained from simulations. Species are binned into log2
abundance categories, following Preston [59]. Data were accumulated from 50
independent simulations with population size $M=1,300$. $\bar{N}_{s}$ is the
mean number of species. b, Respective species’ lifespans within each abundance
bin. Boxplots show the median, lower, and upper quartiles, with whiskers
extending to 1.5 times the interquartile range; all other points are plotted
as outliers. Selection increases mean species’ abundances and the variance of
the SADs, but it tends to reduce all species lifetimes. At any point of
observation, species of intermediate abundance have the longest mean
lifetimes.

We recorded species abundances in generation $T=1,000$ and found a roughly
lognormal shaped distribution of species abundances, even in the presence of
strong selection on mito-nuclear compatibility (Fig. 3a). Selection increased
both the mean species abundance and the variance: the histograms became wider
and right-shifted under strong selection (Fig. LABEL:fig:sad-skew). The SADs
are asymmetric, and, although they present a tail on the left side, low-
abundant species were infrequent because speciation occurs in our model by
fission of abundant species, producing relatively few rare species (similarly
to a stick breaking speciation model in a community with finite resources
[60]). SADs were stable during equilibrium, such that distributions taken at
any time step after $T>500$ generations were very similar (Fig. LABEL:fig:sad-
time).

The time of birth and disappearance of all species were also recorded, then
species age and remaining lifespan were known for all species present at time
$T=1,000$ (Fig. LABEL:fig:remain). The distribution of species lifespans with
species binned by same abundance class (Fig. 3b) shows that selection tended
to reduce species ages and lifetimes in all abundances classes. In all cases,
species born with intermediary relative abundance had the highest longevity
within their communities. In the absence of selection (NI), species lifetimes
were short for low-abundant species and were equally distributed between
species of intermediate or large abundance. Some of those species persisted
until the end of the simulation ($T=2,000$). Surprisingly, large species
evolving under strong selection showed drastically reduced longevity. In the
non-interacting case (no selection), the most-right filled bin (log2 abundance
class 7) had a slight reduction of lifespan, indicating that there was also a
small effect due to species abundance, although selection seems to be the
greater cause of lifespan reduction. With regards to species ages at the time
of sampling ($T=1,000$) and their remaining lifetimes, the patterns were
similar: species of intermediate abundance are the oldest and have the longest
remaining lifetimes and species’ ages of any abundance class decrease with
selection (Fig. LABEL:fig:remain).

Figure 4: Long-term evolutionary fates of species that were extant at time
$T=1,000$. The histograms depicts the fate of each species shown in Fig. 3a at
time: by branching (Branch), extinction (Ext), or hybridization (Hyb), or
persistence through time $T=2000$ (Pers), binned by log2 abundance class. The
legends indicate the percentages of total species that correspond to each
event category. Most species die by branching if they are dominant within the
community, or by extinction if they are rare. Selection for mito-nuclear
compatibility increases rates of hybridization and suppresses long-term
persistence.

Species abundances at time $T=1,000$ were also related to the distribution of
subsequent diversification events (Fig. 4), i.e., the mode of disappearance of
each species (branching, extinction, or hybridization) or whether it persisted
through generation $T=2,000$. Regardless of selection strength, most species
had two possible endings: by branching, if it was dominant within the
community, or by extinction, if it had low abundance. Remarkably, in the
absence of mito-nuclear selection, a significant portion of species persisted
through to generation $T=2,000$. Selection suppressed the persistence of
species, even when weak ($\sigma_{w}=0.175$). Selection also increased the
rate of hybridization (note that hybridization events were counted only for
low-abundant species due to our convention of considering the least abundant
species involved as dying during the fusion, whereas the more abundant species
persists with increased abundance). Notably, species belonging to the same
class of abundances had different fates, depending on whether they were under
strong, weak, or no selection. For instance, a species belonging to bin 6 in
the non-interacting scenario could persist for 1,000 generations ahead, while
a species of the same abundance was most likely to go extinct in any scenario
with selection. Whereas abundance class 7 was the largest one in simulations
without selection, more likely to speciate, but it was not dominant and more
likely to go extinct under strong selection.

Greater species abundances are expected when the number of species is smaller,
because we assume a constant population size; but it is not clear if the
macro-evolutionary patterns we observe are attributable to species abundances
per se, or to mito-nuclear selection. To tease apart these mechanisms, we
simulated populations in the absence of mito-nuclear selection, relaxing the
genetic threshold for mating compatibility (from $G=75$ to $G=220$) so that
they produced a similar number of species in steady-state as communities under
strong mito-nuclear selection (Fig. LABEL:fig:g220-abund). Species-abundance
distributions were shifted towards higher abundances as expected, but all
diversification rates were reduced, and species lifespans were significantly
longer (hence turnover was not increased), even though radiation was delayed
(Fig. LABEL:fig:g220-nsp). Therefore, we conclude that the relationship
between high speciation rate and low species diversity results directly from
the selection on mito-nuclear compatibility.

###  2.4 Genetic diversity of the populations

Figure 5: Genetic diversity within and between species. The histograms depict
the nDNA distances between pairs of individuals that belong to different
species (a), or are conspecific (b) after $T=2,000$ generations. We also show
the mean nDNA distance within each species, plotted against the species
abundance classes (c). nDNA distances between different species are much lower
under strong selection, while the nDNA distances within species are slightly
higher. The latter effect is largely due to species abundances: as shown in c,
more abundant species allow for greater intraspecific diversity, independent
of selection strength.

The analysis of genetic patterns can help to elucidate the mechanism by which
mito-nuclear selection promotes or hinders diversification. We evaluated
genetic diversity by measuring the nuclear genetic distance between pairs of
individuals at time $T=2,000$. Mito-nuclear selection drastically reduced the
genetic distances between individuals belonging to different species (Fig.
5a). In the absence of selection (NI), species were genetically well isolated
from each other, with a prominent peak around 650 loci. Increasing the
strength of selection (reducing $\sigma_{w}$) made species progressively more
similar to each other genetically. However, the effect was opposite for
conspecific individuals (Fig. 5b): under selective pressure, we observed a
slightly larger nuclear divergence within a species than in the non-selective
case. Notably for strong selection, several pairs of individuals had distances
exceeding the genetic threshold ($G=75$) required for mating. In this case,
species cohesion was kept by ongoing gene flow.

The patterns of diversity between different species were similar for the mtDNA
content (Fig. LABEL:fig:mtdnaa) and is explained by the effect of the mito-
nuclear selection on reducing both nuclear and mitochondrial substitutions.
When reproduction can only occur in individuals with high fitness (low mito-
nuclear distance), fixation of a mutation in any of the genome is hampered,
because it must be followed by a mutation in the corresponding site of the
interacting pair to maintain the mito-nuclear compatibility. As a result,
interacting sites had lower substitution rates in both the mitochondrial and
nuclear genomes (Fig. LABEL:fig:subs). Within a species, the mean nDNA
distance is positively correlated to the species’ abundance (Fig. 5c),
independent of the selection strength. As selection increased species
abundances, the effect on the population was to increase the nDNA distances
within each species. Therefore, the mito-nuclear interaction promoted the
intraspecies genetic diversity but reduced the global diversity in the
community.

Figure 6: From selection at the individual level to ecological and macro-
evolutionary patterns. The flow chart (left) summarizes the cascade of events
connecting selection on mito-nuclear compatibility within individuals to its
effects on populations, species, and evolutionary turnover. Colors represent
the scale of effects: genetic (purple), ecological (green), and evolutionary
(orange). The table (right) compares the equilibrium eco-evolutionary patterns
in populations under weak versus strong selection. These predictions are
qualitatively similar to empirical ecological and evolutionary patterns in
tropical (weak selection) versus temperate zones (strong selection).

A chain of effects connects selection on mito-nuclear genetic compatibility
within an individual to skewed species abundance distributions in a community,
shorter species lifespans, and elevated macro-evolutionary turnover (chart at
Fig. 6). Strong selection promotes the conservation of the nuclear genetic
content in the population because mutations accumulate more slowly.
Consequently, the disruption of gene flow is hindered, and the number of
species diminished. With a reduced number of species, they are naturally more
abundant and support more diversity, favoring evolutionary branching events.
Therefore, the speciation rate increases, and abundant species have reduced
lifetimes. Low-abundant (non-dominant) species are also short-lived for being
more susceptible to fluctuations in the abundance. The reduced genetic
distances between different species also promotes hybridization, with sister
species merging more easily after speciation. As a global result, communities
under mito-nuclear selection were characterized by a low number of species
with larger abundances, short species lifespans and high rates of speciation,
extinction, and hybridization, i.e., high turnover rate.

##  3 Discussion

We have investigated how micro-evolutionary processes impact ecological and
macro-evolutionary patterns in a model with selection for mito-nuclear
compatibility. Speciation, hybridization, and extinction are emergent
phenomena in our model, byproducts of changes in allele frequencies in the
populations, as well as spatial and genetic restrictions on mating. We have
shown that strong mito-nuclear selection at the individual level triggers a
succession of effects in populations and species, with low species richness in
equilibrium, reduced species lifespans, and high evolutionary turnover (Fig.
6). We investigated the mechanisms by which selection induces these effects,
and how they are correlated across scales.

The negative correlation between species diversity and speciation rates
predicted by our model has been observed empirically – in particular, across
latitudinal gradients. The number of species in a taxa typically increases
towards the tropics while showing reduced speciation rates, compared to
temperate zones [52, 53, 54, 55, 56, 57], along with increasing ages of sister
species [52, 55, 61]. The properties of populations evolved under strong mito-
nuclear selection in our model are thus broadly similar to empirical
populations in temperate zones, whereas model predictions under weak or no
mito-nuclear selection are similar to empirical patterns in the tropics (see
table in Fig. 6). These empirical patterns are likely the result of many
different ecological, evolutionary, and biogeographical processes [1, 25, 26],
or even neutral processes [62], such that there is no consensus about the
causes of the richness gradient [63, 64, 61] or even the homogeneity of
patterns [65] (ecototherms [55] versus planktonic foraminifera[66], for
instance, exhibit a positive correlation between richness and speciation
rate). We suggest that selection for mito-nuclear compatibility is a possible
mechanism that connects environmental harshness, population genetics and
species trajectories. In this way, our study helps to link macro-evolutionary
patterns of diversification and species turnover, from first principles of
mating and fitness operating within a population [27].

Temperate zones are generally regarded as harsh environments with low resource
availability [53, 54, 67], in which metabolic function is critical [49]. We
therefore assume that selection on mito-nuclear co-adaptation is stronger in
such zones. The empirical correlation between environmental harshness and the
differentiation within species [54, 53] suggests that speciation is frequent
in those regions, which is supported by the observation of young species ages
[68]. Cutter and Gray [67] scrutinized how harsh environments promote the
recurrent fragmentation of species in space, which may sequentially develop
reproductive barriers [10, 23]. Those incipient species evolve through local
adaptation and ecological speciation, and are therefore more prone to
hybridization. Our model produces similar patterns in a process driven by
stabilizing (purifying) selection, in contrast to the mechanism of ecological
speciation (based on divergent selection) – which shows that the same macro-
evolutionary pattern can result from distinct population processes.

The genetic patterns in our simulated populations reflect the primary causes
of variation in diversification rates. A negative correlation between
speciation rates and species richness based on a spatially explicit genetic
model was also obtained in [24], as a result of sexual reproduction
(independent of selection strength). In our model, by contrast, strong mito-
nuclear selection reduces the nuclear genetic distance between species (Fig.
5a), as the maintenance of mito-nuclear compatibility slows the fixation of
mutations for both nDNA and mtDNA (Fig. LABEL:fig:subs). Substitutions occur
more slowly, delaying and prolonging radiation and promoting the conservation
of genetic content in the population. Since gene flow is higher, there are
fewer species that are each more abundant and contain greater intraspecific
genetic diversity (Fig. 5b,c). Those abundant species branch more frequently,
shortening their lifetimes and resulting in a high speciation rate despite the
lower substitution rate of the nuclear alleles. Notably, the average rate of
substitutions was not positively correlated with the speciation rate[69],
which has previously been proposed to be a driver of biodiversity (revised by
[63]). The large intra-species genetic diversity in communities with low
richness in our model are similar to wider niches [70, 71] and are consistent
with predictions of the niche hypothesis (which proposes that ecological
opportunity is greater where diversity is low, leading to faster evolution at
high latitudes[69]).

Although our model reproduces the broad empirical signatures of mito-nuclear
coevolution across the genomes [72, 73], it does not produce strong signatures
of positive selection associated with the compensatory evolution of nDNA in
response to mutations in mtDNA [74, 41]. This is because we have simulated an
adaptive radiation starting from perfectly coordinated mtDNA and nDNA, so that
the majority of selection on interacting mito-nuclear sites is purifying
selection.

In contrast to rare species that are more extinction-prone, abundant species
are expected to be old and long-lived, i.e. more robust to the ecological
drift [4, 11]. However, we found that strong mito-nuclear selection reduced
species’ lifespans even though they were abundant (Fig. 3). We conclude that,
for abundant species, the intrinsic robustness to the ecological drift was
opposed by purifying selection against mito-nuclear incompatibilities that
rapidly decreased individual fitness as mutations accumulated. Frequent
speciation by species’ fission was responsible for the death of abundant
species under strong selection, which explains the relationship between their
short lifetime and the corresponding high speciation rate (also suggested by
[13]).

Genetic divergence between species is generally greater in the tropics than
temperate regions, which is usually explained by the long age of tropical
species [55]. Likewise, intraspecific divergences are generally higher in
temperate zones, associated with recent speciation rates [75, 76, 68, 53, 54].
Our results suggest that the process of accumulating intraspecific genetic
diversity may be the cause, rather than the consequence, of a species being
older or younger.

##  4 Methods

###  4.1 Model

We use an individual-based model of reproduction and eventual speciation
adapted from [6, 22], following the methodology of previous work [35]. We
consider a spatially distributed population evolving in a homogeneous
environment, in the absence of geographic barriers, and under the influence of
neutral micro-evolutionary processes – mutation and genetic drift. Resources
are finite but readily available, so that the population is always close to
the carrying capacity $M$[58]. Reproduction occurs through pairwise mating of
parents.

Derrida & Peliti [77] first demonstrated this simple model of sympatric
speciation with infinite bi-allelic genomes in the absence of natural
selection. For sexual reproduction, the only requirement for speciation to
occur is genetic compatibility, a weak form of assortative mating requiring a
threshold genetic distance $G$ between mating pairs [77, 78]. Implementation
of finite genomes [35] requires also spatial proximity of mating individuals,
which must be separated by a maximum spatial distance $S$, changing from a
sympatric to a parapatric mode of speciation [78]. We call the area of radius
$S$ around an individual its mating neighborhood. These are the minimal
conditions that guarantee the evolution of reproductive isolation [79], and
they allow us to introduce selection on mito-nuclear compatibility into the
model. Species emerge from the dynamics as groups of individuals connected by
gene flow and separated from all others by the genetic mating restriction $G$.
Not all individuals of a species need to be compatible since gene flow can be
established through intermediary individuals. In other words, species
correspond to the components of a network where individuals (nodes) are
connected if their nuclear genetic distance is less than or equal to $G$. The
model predicts patterns of biodiversity, such as species abundance
distributions (SADs) and species-area relationships [6], similar to previous
neutral models [3, 4].

In order to include mito-nuclear selection, individuals are described by a
nuclear DNA, which undergoes recombination and defines genetic compatibility
for mating, and by a mitochondrial DNA, inherited from the mother. Both
genomes are modeled as binary strings with sizes $B$ and $B_{M}$ respectively.
Sexes are separated and individuals are randomly distributed over a square
area of size $L\times L$ (see Fig. 1a) with periodic boundary conditions
(individuals can, by chance, occupy the same lattice site). Generations do not
overlap and the population is fully replaced by the offspring. Each individual
has a probability $P$ to reproduce and $Q=1-P$ of dying without leaving
offspring. For reproduction, a mating partner is randomly chosen among
genetically compatible individuals in its mating neighborhood. The nuclear
genetic distance $D_{n}$ between individuals is defined as the Hamming
distance between their nuclear genomes, and compatibility requires $D_{n}\leq
G$. If a genetically compatible mate is found within the mating neighborhood
of the ‘focal’ individual, an offspring is produced with locus by locus
recombination of the nuclear genomes, followed by mutation with probability
$\mu$ per locus. The mtDNA is inherited from the mother, with mutations with
probability $\mu_{M}$ (Fig. 1a). The offspring is placed at the site of the
focal individual or, with diffusion probability $D$, in one of $S_{D}$
randomly chosen nearest neighbor sites. Note that individuals can generate
more than one offspring: when selected as mating partner by their neighbors or
when playing the role of focal individual. If the focal individual cannot find
a compatible mate in its mating neighborhood, it expands his search area to
radius $S+1$ and then to $S+2$. If no compatible mate is found in the extended
area, or if the individual dies without reproducing (probability $Q$), another
individual is randomly selected within its original mating neighborhood to
reproduce in its place, keeping the population size constant. On rare
occasions, however, due to population fluctuations, the mating neighborhood
might be empty and no replacement can be found. In these cases, mating does
not occur and the population size decreases by one. In order to restore the
population to its carrying capacity $M$, we allow individuals to have two
offspring in the next generation if their mating neighborhoods have densities
below $60\%$ of the expected average value $M/L^{2}$. This procedure
introduces small fluctuations in population size.

We compare the neutral process, when mito-nuclear selection is absent, with
the scenario where mito-nuclear compatibility promotes fitness differences in
the population, testing different levels of selective pressure while keeping
all other parameters fixed. The mito-nuclear distance $d$ measures the
compatibility between the mtDNA and the corresponding loci of nDNA, assigned
to each individual, ranging from 0 (totally unmatched sequences) to 1 (fully
compatible sequences); for completely random sequences, the expected value of
$d$ is 0.5. The individual’s fitness $w$ depends on $d$ according to a
Gaussian function with width $\sigma_{w}$, which quantifies the selective
strength of the mito-nuclear interaction (Fig. 1b). The parameter $\sigma_{w}$
is related to the population average $\langle d\rangle$ in equilibrium (see
Fig. LABEL:fig:dmed), such as the absence of selection leads to $\langle
d\rangle\approx 0.5$ and increasing the selection diminishes $\langle
d\rangle$ towards 0. Selection over mito-nuclear compatibility changes the
probability of an individual to reproduce, i.e., it affects its fecundity. The
focal individual has its chance for reproduction modified by its fitness as
follows: first the fitness of all individuals in the population are computed
as $w(i)=e^{-d(i)^{2}/2\sigma_{w}^{2}}$; second, $Q$ for individual $i$ is
modified to $Q_{w}(i)=2Q(w_{max}-w(i))/(w_{max}-w_{min})$ where $w_{max}$ and
$w_{min}$ are the maximum and minimum fitness in the population, respectively.
Individuals with $w(i)=w_{max}$ have $Q_{w}(i)=0$ and probability of
reproducing $P_{w}=1-Q_{w}=1$. Those with $w(i)=w_{min}$ have $Q_{w}(i)=2Q$
and $P_{w}=1-2Q$. Therefore, individuals with low fitness still have a small
chance of reproducing. If the individual dies without reproducing, another one
is selected in its mating neighborhood, also according to fitness, to
reproduce in its place, keeping the total population constant. Finally, a
mating partner is selected from the compatible individuals in the mating
neighborhood, with probability proportional to their fitness.

For the analysis, we considered a standard set of parameters following
previous demonstrations of the model that explored the evolution of species
under different conditions [78, 22]. We choose a population size $M$ and a
nuclear genome length $B$ that guarantee the onset of radiation and
establishment of the equilibrium of the number of species after a few hundred
generations. The chosen parameters values were: a population of $M=1,300$
individuals randomly distributed in ($100\times 100$) lattice with reflecting
boundary conditions; the nuclear genome length is $B=1,500$, with mutation
rate $\mu=0.00025$, genetic similarity threshold $G=75=0.05B$ and mating range
$S=5$. Population density is 0.13, indicating many empty sites in the lattice;
the average number of individuals in the mating neighborhood is 10. The
mitochondrial genome length is $B_{M}=500$, with mutation rate $\mu_{M}=3\mu$.
We start from an initial condition where all individuals are identical, thus
emulating a radiation process. We also fixed $D=0.02$ and $S_{D}=20$. In this
work, we simulate the evolutionary process for $T=2,000$ generations. We fixed
$Q=0.37\approx e^{-1}$ as the neutral probability of dying without leaving
offspring (equal to the chance of not selecting one particular individual in
$M$ trials with replacement [78]). We have run 50 independent realizations of
each scenario and present the population-averaged or accumulated measurements.

###  4.2 Processes of diversification

Throughout the evolutionary dynamics, recombination and mutation change allele
frequencies in the population and, combined with the genetic and spatial
restrictions for mating, reproductively isolated species can emerge. New
species are born from an abundant one that eventually divides into smaller
clusters with disrupted gene flow. Due to the model’s stochasticity, species
abundances and species richness fluctuate randomly (ecological drift). The
number of individuals of a species can progressively diminish until no
offspring is left to the next generation, due to lack of compatible partners
in the mating neighborhood or by chance, and the species is extinct. Also,
genetically close species can merge by the reestablishment of the gene flow
due to mutations, hybridizing. Therefore we identify three classes of events
in which a species can disappear when registering the evolutionary history of
the populations: speciation or branching: when an abundant species breaks into
two or more new species. The mother species is considered dead and new species
are born, adding to the number of living species; extinction: when the number
of individuals of the species progressively diminishes until it reaches a null
abundance; and hybridization: when the descendants of individuals from two or
more different species at $T-1$ belong to the same species at the generation
$T$, reestablishing the gene flow. In this case we adopted the protocol of
maintaining the largest species and consider the smaller species dead,
absorbed by the largest one.

Branching events increase species richness, while extinction and hybridization
decrease the number of extant species, reducing biodiversity. Hybridization is
an emergent event in our model and only cause loss of diversity. In nature,
however, hybridization may increase species richness inducing the evolution of
reproductive barriers [80]. Here we emulated the loss of diversity due to
hybridization from lineage fusion, speciation reversal [81], and hybrid
breakdown [40]. We included in this category events of failed speciation
attempts (when two or more recent sister species merge back) and events of
reticulate evolution (when there are two speciation events in a row and a
species fuses with the one with the most distant ancestor)

###  4.3 Species abundances distributions

In our simulations the number of species in equilibrium ($T\geq 500$) ranged
from about 20 in the non-interacting case to about 5 for strong selection
(Fig. 2b). To generate abundance distribution plots with statistical
significance, we have run 50 independent simulations for each set of
parameters and accumulated the results. This increased the number of species
in the histograms to about 1,000 for the non-interacting case and 100 for the
case of strong selection. Section LABEL:SM2 of Supplementary Information
justifies the validity of this procedure.

To generate the species’ abundances histograms, data were binned in abundances
classes (log2). There are several methods for choosing the bins’ boundaries,
and we followed the method adopted by [3]: bins were built by using the powers
of two as the center of bins. The boundaries then come as $2^{n-1/2}$ and
$2^{n+1/2}$. Thus, bin=0 stores species with 1 individual, bin=1 counts
species with 2 individuals, bin=2 species with 3, 4, and 5 individuals, and so
on.

### Data availability

There are no empirical data associated with this study.

### Code availability

All simulations are run in Fortran. All the codes for simulations and scripts
for data treatment in Python are available in the GitHub repository at
https://github.com/deborapr/mito-nuclear-speciation.

### Acknowledgment

This work was partly supported by the São Paulo Research Foundation (FAPESP),
grants #2018/11187-8 (DP), #2019/24449-3 (DP), #2019/20271-5 (MAMA) and
#2016/01343-7 (ICTP-SAIFR). MAMA was supported by Conselho Nacional de
Pesquisas Científicas (CNPq), grant #301082/2019-7.

## References

  * 1. Hagen, O. _et al._ gen3sis: A general engine for eco-evolutionary simulations of the processes that shape Earth’s biodiversity.  _PLOS Biology_ 19, e3001340 (2021).
  * 2. Urban, M. C. _et al._ Evolutionary origins for ecological patterns in space.  _Proceedings of the National Academy of Sciences of the United States of America_ 117, 17482–17490 (2020).
  * 3. Hubbell, S. P.  _The Unified Neutral Theory of Biodiversity and Biogeography (MPB-32)_ (Princeton University Press, Princeton, 2001).
  * 4. Volkov, I., Banavar, J. R., Hubbell, S. P. & Maritan, A.  Neutral theory and relative species abundance in ecology.  _Nature_ 424, 1035–1037 (2003).
  * 5. McGill, B. J. _et al._ Species abundance distributions: moving beyond single prediction theories to integration within an ecological framework.  _Ecology Letters_ 10, 995–1015 (2007).
  * 6. de Aguiar, M. A. M., Baranger, M., Baptestini, E. M., Kaufman, L. & Bar-Yam, Y.  Global patterns of speciation and diversity.  _Nature_ 460, 384 (2009).
  * 7. O’Dwyer, J. P. & Green, J. L.  Field theory for biogeography: A spatially explicit model for predicting patterns of biodiversity.  _Ecology Letters_ 13, 87–95 (2010).
  * 8. Chisholm, R. A. & Pacala, S. W.  Niche and neutral models predict asymptotically equivalent species abundance distributions in high-diversity ecological communities.  _Proceedings of the National Academy of Sciences of the United States of America_ 107, 15821–15825 (2010).
  * 9. Mutshinda, C. M., O’Hara, R. B. & Woiwod, I. P.  What drives community dynamics?  _Proceedings of the Royal Society B: Biological Sciences_ 276, 2923–2929 (2009).
  * 10. Rosindell, J., Cornell, S. J., Hubbell, S. P. & Etienne, R. S.  Protracted speciation revitalizes the neutral theory of biodiversity.  _Ecology Letters_ 13, 716–727 (2010).
  * 11. Chisholm, R. A. & O’Dwyer, J. P.  Species ages in neutral biodiversity models.  _Theoretical Population Biology_ 93, 85–94 (2014).
  * 12. Nee, S.  The neutral theory of biodiversity: do the numbers add up?  _Functional Ecology_ 19, 173–176 (2005).
  * 13. Ricklefs, R. E.  A comment on Hubbell’s zero-sum ecological drift model.  _Oikos_ 100, 185–192 (2003).
  * 14. Etienne, R. S., Apol, M. E. F., Olff, H. & Weissing, F. J.  Modes of speciation and the neutral theory of biodiversity.  _Oikos_ 116, 241–258 (2007).
  * 15. Davies, T. J., Allen, A. P., Borda-de Água, L., Regetz, J. & Melián, C. J.  Neutral biodiversity theory can explain the imbalance of phylogenetic trees but not the tempo of their diversification.  _Evolution_ 65, 1841–1850 (2011).
  * 16. Higgs, P. G. & Derrida, B.  Stochastic models for species formation in evolving populations.  _Journal of Physics A: Mathematical and General_ 24, L985 (1991).
  * 17. Gavrilets, S., Li, H. & Vose, M. D.  Rapid parapatric speciation on holey adaptive landscapes.  _Proceedings of the Royal Society B: Biological Sciences_ 265, 1483–1489 (1998).  9807006.
  * 18. Dieckmann, U. & Doebeli, M.  On the origin of species by sympatric speciation.  _Nature_ 400, 354 (1999).
  * 19. Gavrilets, S. & Vose, A.  Dynamic patterns of adaptive radiation.  _Proceedings of the National Academy of Sciences of the United States of America_ 102, 18040–18045 (2005).
  * 20. Nosil, P.  _Ecological speciation_ (Oxford University Press, 2012).
  * 21. Gavrilets, S., Acton, R. & Gravner, J.  Dynamics of speciation and diversification in a metapopulation.  _Evolution_ 54, 1493–1501 (2000).
  * 22. Costa, C. L. N. _et al._ Signatures of Microevolutionary Processes in Phylogenetic Patterns.  _Systematic Biology_ 68, 131–144 (2018).
  * 23. Li, J., Huang, J.-P., Sukumaran, J. & Knowles, L. L.  Microevolutionary processes impact macroevolutionary patterns.  _BMC Evolutionary Biology_ 18, 123 (2018).
  * 24. Melián, C. J., Alonso, D., Allesina, S., Condit, R. S. & Etienne, R. S.  Does Sex Speed Up Evolutionary Rate and Increase Biodiversity?  _PLOS Computational Biology_ 8, e1002414 (2012).
  * 25. Rangel, T. F. _et al._ Modeling the ecology and evolution of biodiversity: Biogeographical cradles, museums, and graves.  _Science_ 361 (2018).
  * 26. Pontarp, M. _et al._ The Latitudinal Diversity Gradient: Novel Understanding through Mechanistic Eco-evolutionary Models.  _Trends in Ecology & Evolution_ 34, 211–223 (2019).
  * 27. de Alencar, L. R. V. & Quental, T. B.  Linking population-level and microevolutionary processes to understand speciation dynamics at the macroevolutionary scale.  _Ecology and Evolution_ 11, 5828–5843 (2021).
  * 28. Hurlbert, A. H. & Stegen, J. C.  When should species richness be energy limited, and how would we know?  _Ecology Letters_ 17, 401–413 (2014).
  * 29. Morlon, H.  Phylogenetic approaches for studying diversification.  _Ecology Letters_ 17, 508–525 (2014).
  * 30. Rosindell, J., Harmon, L. J. & Etienne, R. S.  Unifying ecology and macroevolution with individual-based theory.  _Ecology Letters_ 18, 472–482 (2015).
  * 31. Rosindell, J. & Harmon, L. J.  A unified model of species immigration, extinction and abundance on islands.  _Journal of Biogeography_ 40, 1107–1118 (2013).
  * 32. Etienne, R. S. & Rosindell, J.  Prolonging the past counteracts the pull of the present: Protracted speciation can explain observed slowdowns in diversification.  _Systematic Biology_ 61, 204–213 (2012).
  * 33. Rabosky, D. L. & Matute, D. R.  Macroevolutionary speciation rates are decoupled from the evolution of intrinsic reproductive isolation in Drosophila and birds.  _Proceedings of the National Academy of Sciences_ 110, 15354–15359 (2013).
  * 34. Louca, S. & Pennell, M. W.  Extant timetrees are consistent with a myriad of diversification histories.  _Nature_ 580, 502–505 (2020).
  * 35. Princepe, D. & De Aguiar, M. A. M.  Modeling Mito-nuclear Compatibility and Its Role in Species Identification.  _Systematic Biology_ 70, 133–144 (2021).
  * 36. Bar-Yaacov, D., Blumberg, A. & Mishmar, D.  Mitochondrial-nuclear co-evolution and its effects on OXPHOS activity and regulation.  _Biochimica et Biophysica Acta - Gene Regulatory Mechanisms_ 1819, 1107–1111 (2012).
  * 37. Sunnucks, P., Morales, H. E., Lamb, A. M., Pavlova, A. & Greening, C.  Integrative Approaches for Studying Mitochondrial and Nuclear Genome Co-evolution in Oxidative Phosphorylation.  _Frontiers in genetics_ 8, 25 (2017).
  * 38. Hill, G. E.  The mitonuclear compatibility species concept.  _The Auk_ 134, 393–409 (2017).
  * 39. Lima, T. G., Burton, R. S. & Willett, C. S.  Genomic scans reveal multiple mito-nuclear incompatibilities in population crosses of the copepod _Tigriopus californicus_.  _Evolution_ (2019).
  * 40. Barreto, F. S. & Burton, R. S.  Elevated oxidative damage is correlated with reduced fitness in interpopulation hybrids of a marine copepod.  _Proceedings of the Royal Society B: Biological Sciences_ 280 (2013).
  * 41. Hill, G. E.  Mitonuclear Compensatory Coevolution.  _Trends in Genetics_ 36, 403–414 (2020).
  * 42. Gershoni, M., Templeton, A. R. & Mishmar, D.  Mitochondrial bioenergetics as a major motive force of speciation.  _BioEssays_ 31, 642–650 (2009).
  * 43. Hill, G. E.  Mitonuclear coevolution as the genesis of speciation and the mitochondrial DNA barcode gap.  _Ecology and Evolution_ 6, 5831–5842 (2016).
  * 44. Tobler, M., Barts, N. & Greenway, R.  Mitochondria and the Origin of Species: Bridging Genetic and Ecological Perspectives on Speciation Processes.  _Integrative and Comparative Biology_ 59, 900–911 (2019).
  * 45. Burton, R. S. & Barreto, F. S.  A disproportionate role for mtDNA in Dobzhansky-Muller incompatibilities?  _Molecular Ecology_ 21, 4942–4957 (2012).
  * 46. Telschow, A., Gadau, J., Werren, J. H. & Kobayashi, Y.  Genetic incompatibilities between mitochondria and nuclear genes: Effect on gene flow and speciation.  _Frontiers in Genetics_ 10, 62 (2019).
  * 47. Lane, N.  Biodiversity: On the origin of bar codes.  _Nature_ 462, 272–274 (2009).
  * 48. Hill, G. E.  _Mitonuclear Ecology_ (Oxford University Press, Oxford, U.K., 2019).
  * 49. Dowling, D. K., Abiega, K. C. & Arnqvist, G.  Temperature-specific outcomes of cytoplasmic-nuclear interactions on egg-to-adult development time in seed beetles.  _Evolution_ 61, 194–201 (2007).
  * 50. Wolff, J. N., Ladoukakis, E. D., Enríquez, J. A. & Dowling, D. K.  Mitonuclear interactions: evolutionary consequences over multiple biological scales.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ 369, 20130443 (2014).
  * 51. Koch, R. E. _et al._ Integrating Mitochondrial Aerobic Metabolism into Ecology and Evolution.  _Trends in Ecology & Evolution_ 36, 321–332 (2021).
  * 52. Weir, J. T. & Schluter, D.  The latitudinal gradient in recent speciation and extinction rates of birds and mammals.  _Science_ 315, 1574–1576 (2007).
  * 53. Botero, C. A., Dor, R., McCain, C. M. & Safran, R. J.  Environmental harshness is positively correlated with intraspecific divergence in mammals and birds.  _Molecular Ecology_ 23, 259–268 (2014).
  * 54. Weir, J. T.  Environmental harshness, latitude and incipient speciation.  _Molecular Ecology_ 23, 251–253 (2014).
  * 55. Schluter, D. & Pennell, M. W.  Speciation gradients and the distribution of biodiversity.  _Nature_ 546, 48–55 (2017).
  * 56. Harvey, M. G. _et al._ The evolution of a tropical biodiversity hotspot.  _Science_ 370, 1343–1348 (2020).
  * 57. Rabosky, D. L. _et al._ An inverse latitudinal gradient in speciation rate for marine fishes.  _Nature_ 559, 392–395 (2018).
  * 58. Rabosky, D. L. & Hurlbert, A. H.  Species Richness at Continental Scales Is Dominated by Ecological Limits.  _American Naturalist_ 185, 572–583 (2015).
  * 59. Gray, J. S., Bjørgesæter, A. & Ugland, K. I.  On plotting species abundance distributions.  _Journal of Animal Ecology_ 75, 752–756 (2006).
  * 60. Sugihara, G.  Minimal Community Structure: An Explanation of Species Abundance Patterns.  _The American Naturalist_ 116, 770–787 (1980).
  * 61. Kennedy, J. D. _et al._ Into and out of the tropics: The generation of the latitudinal gradient among New World passerine birds.  _Journal of Biogeography_ 41, 1746–1757 (2014).
  * 62. Etienne, R. S. _et al._ A minimal model for the latitudinal diversity gradient suggests a dominant role for ecological limits.  _American Naturalist_ 194, E122–E133 (2019).
  * 63. Mittelbach, G. G. _et al._ Evolution and the latitudinal diversity gradient: Speciation, extinction and biogeography.  _Ecology Letters_ 10, 315–331 (2007).
  * 64. Hillebrand, H.  On the generality of the latitudinal diversity gradient.  _American Naturalist_ 163, 192–211 (2004).
  * 65. Evans, K. L. & Gaston, K. J.  Can the evolutionary-rates hypothesis explain species-energy relationships?  _Functional Ecology_ 19, 899–915 (2005).
  * 66. Allen, A. P. & Gillooly, J. F.  Assessing latitudinal gradients in speciation rates and biodiversity at the global scale.  _Ecology letters_ 9, 947–954 (2006).
  * 67. Cutter, A. D. & Gray, J. C.  Ephemeral ecological speciation and the latitudinal biodiversity gradient.  _Evolution_ 70, 2171–2185 (2016).
  * 68. Smith, B. T., Seeholzer, G. F., Harvey, M. G., Cuervo, A. M. & Brumfield, R. T.  A latitudinal phylogeographic diversity gradient in birds.  _PLOS Biology_ 15, e2001073 (2017).
  * 69. Freeman, B. G., Weeks, T., Schluter, D. & Tobias, J. A.  The latitudinal gradient in rates of evolution for bird beaks, a species interaction trait.  _Ecology Letters_ 25, 635–646 (2022).
  * 70. Vellend, M.  Species Diversity and Genetic Diversity: Parallel Processes and Correlated Patterns.  _American Naturalist_ 166, 199–215 (2005).
  * 71. Pontarp, M. & Wiens, J. J.  The origin of species richness patterns along environmental gradients: uniting explanations based on time, diversification rate and carrying capacity.  _Journal of Biogeography_ 44, 722–735 (2017).
  * 72. Zhang, F. & Broughton, R. E.  Mitochondrial-nuclear interactions: compensatory evolution or variable functional constraint among vertebrate oxidative phosphorylation genes?  _Genome biology and evolution_ 5, 1781–1791 (2013).
  * 73. Piccinini, G. _et al._ Mitonuclear Coevolution, but not Nuclear Compensation, Drives Evolution of OXPHOS Complexes in Bivalves.  _Molecular Biology and Evolution_ 38, 2597–2614 (2021).
  * 74. Barreto, F. S. _et al._ Genomic signatures of mitonuclear coevolution across populations of Tigriopus californicus.  _Nature Ecology and Evolution_ 2, 1250–1257 (2018).
  * 75. Harvey, M. G. _et al._ Positive association between population genetic differentiation and speciation rates in New World birds.  _Proceedings of the National Academy of Sciences of the United States of America_ 114, 6328–6333 (2017).
  * 76. Araújo, M. S. & Costa-Pereira, R.  Latitudinal gradients in intraspecific ecological diversity.  _Biology Letters_ 9 (2013).
  * 77. Derrida, B. & Peliti, L.  Evolution in a flat fitness landscape.  _Bulletin of Mathematical Biology_ 53, 355–382 (1991).
  * 78. de Aguiar, M. A. M.  Speciation in the Derrida-Higgs model with finite genomes and spatial populations.  _Journal of Physics A: Mathematical and Theoretical_ 50, 85602 (2017).
  * 79. Thibert-Plante, X. & Gavrilets, S.  Evolution of mate choice and the so-called magic traits in ecological speciation.  _Ecology Letters_ 16, 1004–1013 (2013).
  * 80. Seehausen, O.  Hybridization and adaptive radiation.  _Trends in Ecology and Evolution_ 19, 198–207 (2004).
  * 81. Kearns, A. M. _et al._ Genomic evidence of speciation reversal in ravens.  _Nature Communications_ 9, 906 (2018).


# A class of graphs of zero Turán density in a hypercube

Maria Axenovich Karlsruhe Institute of Technology, Karlsruhe, Germany; email:
<EMAIL_ADDRESS>
###### Abstract

A graph is cubical if it is a subgraph of a hypercube. For a cubical graph $H$
and a hypercube $Q_{n}$, ${\rm ex}(Q_{n},H)$ is the largest number of edges in
an $H$-free subgraph of $Q_{n}$. If ${\rm ex}(Q_{n},H)$ is at least a positive
proportion of the number of edges in $Q_{n}$, $H$ is said to have a positive
Turán density in a hypercube or simply a positive Turán density; otherwise it
has a zero Turán density. Determining ${\rm ex}(Q_{n},H)$ and even identifying
whether $H$ has a positive or a zero Turán density remains a widely open
question for general $H$. By relating extremal numbers in a hypercube and
certain corresponding hypergraphs, Conlon found a large class of cubical
graphs, ones having so-called partite representation, that have a zero Turán
density. He raised a question whether this gives a characterisation, i.e.,
whether a cubical graph has zero Turán density if and only if it has partite
representation. Here, we show that, as suspected by Conlon, this is not the
case. We give an example of a class of cubical graphs which have no partite
representation, but on the other hand, have a zero Turán density. In addition,
we show that any graph whose every block has partite representation has a zero
Turán density in a hypercube.

##  1 Introduction

A hypercube $Q_{n}$ with a ground set $X$ of size $n$, is a graph on a vertex
set $\\{A:A\subseteq X\\}$ and an edge set consisting of all pairs
$\\{A,B\\}$, where $A\subseteq B$ and $|A|=|B|-1$. Unless specified, $X=[n]$,
where $[n]=\\{1,\ldots,n\\}$. We often identify vertices of $Q_{n}$ with
binary vectors that are indicator vectors of respective sets. If a graph is a
subgraph of $Q_{n}$, for some $n$, it is called cubical. We denote the number
of vertices and the number of edges in a graph $H$ by $|H|$ and $||H||$,
respectively. The degree of a vertex $y$ in a graph $H$ is denoted $d(y)$ or
$d_{H}(y)$. A block in a graph is a maximal two-connected subgraph or a
bridge. We shall need the notion of layers. The $i$th vertex layer of $Q_{n}$,
denoted $V_{i}$, is the set of vertices $\binom{[n]}{i}$, $i=0,\ldots,n$. The
$i$th edge-layer $L_{i}$ of $Q_{n}$ is a graph induced by $V_{i}\cup V_{i-1}$,
$i=1,\ldots,n$.

For a graph $H$, let the extremal number of $H$ in $Q_{n}$, denoted ${\rm
ex}(Q_{n},H)$, be the largest number of edges in a subgraph $G$ of $Q_{n}$
such that there is no subgraph of $G$ isomorphic to $H$. A graph $H$ is said
to have zero Turán density in a hypercube if ${\rm ex}(Q_{n},H)=o(||Q_{n}||)$.
Otherwise, we say that $H$ has a positive Turán density in a hypercube. Note
that by using a standard double counting argument, the sequence ${\rm
ex}(Q_{n},H)/||Q_{n}||$ is non-increasing, thus the above density notions are
well-defined. When clear from context, we simply say Turán density instead of
Turán density in a hypercube. The behaviour of the function ${\rm
ex}(Q_{n},H)$ is not well understood in general and it is not even known what
graphs have positive or zero Turán density. Currently, the only known cubical
graphs of positive Turán density are those containing a $4$\- or a $6$-cycle
as a subgraph, [8, 9], and one special graph of girth $8$ [2]. Conlon [10]
observed a connection between extremal numbers in a hypercube and classical
extremal numbers for uniform hypergraphs. That permitted to determine large
specific classes of graphs, such as for example subdivisions, with zero Turán
density, see [2]. For more results on extremal numbers in a hypercube, see [5,
6, 1, 17, 16].

A graph $H$ has a $k$-partite representation $\mathcal{H}$ if for some $n$,
$H$ is isomorphic to a subgraph $H^{\prime}$ of the $k$th layer $L_{k}$ of
$Q_{n}$ such that $V(H^{\prime})\cap V_{k}$ is an edge-set of a $k$-partite
$k$-uniform hypergraph $\mathcal{H}$. The graph $H^{\prime}$ is called
representing. If $H$ has a $k$-partite representation for some $k$, we say
that $H$ has a partite representation. Here, a $k$-uniform hypergraph is
$k$-partite if the vertex set can be partitioned into $k$ parts such that each
hyperedge has exactly one vertex in each part. Here, we omit the brackets and
commas denoting sets, when clear from context, i.e., for a set $\\{1,2\\}$ we
simply write $12$. For example, if $H$ is an $8$-cycle, it has a $2$-partite
representation $\mathcal{H}$ with hyperedges $12,23,34,14$ corresponding to an
$8$-cycle with vertices $1,12,2,23,3,34,4,14,1$, in order. For a $k$-uniform
hypergraph $\mathcal{H}$, ${\rm ex}_{k}(n,\mathcal{H})$ denotes the largest
number of edges in a $k$-uniform $n$-vertex hypergraph with no subgraph
isomorphic to $\mathcal{H}$.

Using a theorem by Erdős [11], that states that ${\rm
ex}_{k}(n,\mathcal{H})=o_{n}(n^{k})$ for any $k$-partite hypergraph
$\mathcal{H}$, Conlon [10] proved that if $H$ is a graph that has partite
representation, then ${\rm ex}(Q_{n},H)=o(||Q_{n}||)$. In the same paper
Conlon [10] raised a question whether cubical graphs that have no partite
representation have positive Turán density. Here, we show that it is not the
case, i.e. having a partite representation is not a characterisation for zero
Turán density in a hypercube. For that, we construct a family of cubical
graphs that have no partite representation, but have zero Turán density. These
graphs are formed by two copies of so-called theta-graphs that we define
below.

For a graph $G$, let $G(1)$ be a $1$-subdivision of $G$, i.e., a graph
$G^{\prime}$ with a vertex set $V(G)\cup E(G)$ and an edge set
$\\{ue,ev:e=uv\in E(G)\\}$. We call the vertices from $V(G)$ in $G^{\prime}$,
the poles of $G^{\prime}$ and other vertices, the subdivision vertices. Let
$K_{s,t}$ denote a complete bipartite graph with parts of sizes $s$ and $t$,
respectively. We shall be considering the $1$-subdivision of $K_{q,2}$, $q\geq
3$. We shall call the two vertices of degree $q$ in $K_{q,2}(1)$, the main
poles. Note that $K_{q,2}(1)$ is also referred to as a theta graph with $q$
legs of length $4$. Here the legs are paths with endpoints being main poles.
We shall use a shorter notation $\Theta(q)$ for $K_{q,2}(1)$, when
appropriate. If a graph $G$ contains a subgraph isomorphic to $H$, we call
such a subgraph a copy of $H$.

Let $H(q)$ be a union of two copies of $\Theta(q)$ sharing exactly one vertex
that is a main pole of one copy and a subdivision vertex in another copy, see
Figure 1.

21345 2451453 Figure 1: A graph $H(3)$ with larger vertices being poles in the
respective copies of theta graphs as well as a nice coloring of one theta
graph

Marquardt [15] showed that $H(q)$ has no partite representation for $q=3$.
Here, we give a slightly different proof of this fact for any $q\geq 3$ and
show that $H(q)$ has a zero Turán density. In doing so, we prove a result of
an independent interest that gives a new class of cubical graphs of zero Turán
density.

######  Theorem 1.

Let $H$ be a graph whose every block has a partite representation. Then $H$
has a zero Turán density in a hypercube.

######  Theorem 2.

For any $q\geq 3$ the graph $H(q)$ is cubical, has no partite representation,
but has a zero Turán density in a hypercube.

##  2 Proofs of main results

We shall need the following lemmas. The first one gives a property of graphs
with partite representations, formulated by Marquardt [15], we include it here
for completeness. The second one is basically a result of Conlon [10], but
with a slightly different averaging argument that also gives a more precise
statement about an embedding of a graph in a layer in two different ways.
Finally, the last one is the main lemma needed for Theorem 1. If a graph $H$
has a $k$-partite representation with representing graph $H^{\prime}$, then
the vertices of $H$ corresponding to $V(H^{\prime})\cap V_{k}$ are called top
vertices with respect to this representation, all other vertices are called
bottom vertices. Note that if a graph has a $k$-partite representation, it has
a $(k+1)$-partite representation that could be seen by simply adding a new
element to every vertex of a representing graph.

######  Lemma 3.

Let $H$ and $G$ be connected graphs, each having a $k$-partite representation.
Assume that $V(H)\cap V(G)=\\{v\\}$, where $v$ that is a top vertex for both
$H$ and $G$ or a bottom vertex for both $H$ and $G$. Then $H\cup G$ has a
partite representation.

###### Proof.

Let $H^{\prime}$ and $G^{\prime}$ be copies of $H$ and $G$ that are subgraphs
of the $k$th layer in hypercubes with a ground set $X$ and $Y$, respectively,
such that $V(H^{\prime})\cap\binom{X}{k}$ and $V(H^{\prime})\cap\binom{Y}{k}$
are the edge sets of $k$-partite hypergraphs with parts $U_{1},\ldots,U_{k}$
and parts $W_{1},\ldots,W_{k}$, respectively. Let $u$ and $w$ be respective
copies of $v$ in $H^{\prime}$ and $G^{\prime}$.

Assume first that $v$ is a top vertex of $H$ and of $G$. Assume that $X\cap
Y=\emptyset$. Let $F^{\prime\prime}$ be an induced subgraph of a hypercube $Q$
with ground set $X\cup Y$ and vertex set $\\{x\cup w:x\in
V(H^{\prime})\\}\cup\\{u\cup y:y\in V(G^{\prime})\\}$. We see that
$F^{\prime\prime}$ contains a copy $F^{\prime}$ of $F$ and is contained in the
layer $2k$ of $Q$ with the vertex $u\cup w$ playing a role of $v$. Moreover
$V(F^{\prime})\cap\binom{X\cup Y}{2k}$ is an edge set of a $2k$-partite
hypergraph with parts $U_{1},\ldots,U_{k},W_{1},\ldots,W_{k}$.

Assume now that $v$ is a bottom vertex of $H$ and of $G$. Assume further that
$X\cap Y=[k-1]$ and $u=w=[k-1]$. Let $F^{\prime\prime}$ be an induced subgraph
of a hypercube $Q$ with ground set $X\cup Y$ and vertex set $V(H^{\prime})\cup
V(G^{\prime})$. We see that $F^{\prime\prime}$ contains a copy $F^{\prime}$ of
$F$ and is contained in layer $k$ of $Q$ with vertex $v^{\prime}=[k-1]$
playing a role of $v$. Moreover $V(F^{\prime})\cap\binom{X\cup Y}{k}$ is an
edge set of a $k$-partite hypergraph with parts $U_{1}\cup
W_{1},\ldots,U_{k}\cup W_{k}$. ∎

######  Lemma 4.

Let $Z$ be a connected bipartite graph with a partite representation. Then for
any $\gamma>0$ there is $n_{1}=n_{1}(\gamma,Z)$ such that for any $n>n_{1}$
the following holds. Let $L_{j}$ be the $j$th layer of $Q_{n}$, where
$n/2-n^{2/3}\leq j\leq n/2+n^{2/3}$. Let $G\subseteq L_{j}$ be a graph such
that $||G||\geq\gamma||L_{j}||$. Fix one of the two partite set of $Z$
arbitrarily and call its vertices odd. Then there is a copy of $Z$ in $G$ with
odd vertices in $V_{j}$ and there is a copy of $Z$ in $G$ with odd vertices in
$V_{j-1}$.

###### Proof.

Let $Z$ have a $k$-partite representation in a hypercube $Q_{n}$ with ground
set $[n]$, with odd vertices corresponding to $k$-element sets. We need the
following notation. For any $x\in V(Q_{n})$, let ${\rm Up}(x)$ be the up set
of $x$, i.e., ${\rm Up}(x)=\\{y\subseteq[n]:~{}x\subseteq y\\}$. Note that
${\rm Up}(x)$ induces a graph isomorphic to $Q_{m}$, for $m=n-|x|$.

To prove the first part of the lemma, for each $x\in V_{j-k}$, let
$U_{x}=U_{x,k}$ be the intersection of $G$ and the $k$th edge-layer of the
hypercube $Q$ induced by ${\rm Up}(x)$. Note that $U_{x}$ is a subgraph of
$L_{j}$, the $j$th layer of $Q_{n}$. We call a vertex $y$ of $U_{x}$ a full
vertex if it is in the $k$th vertex layer of $Q$ and has degree $k$ in
$U_{x}$, the largest possible degree. Let $u_{x}$ be the number of full
vertices in $U_{x}$. We shall argue that there is a vertex $x\in V_{j-k}$ such
that $u_{x}$ is large.

Let $t$ be the number of $k$-edge stars in $G$ with the center in $V_{j}$.
Then

$t=\sum_{y\in
V_{j}}\binom{d_{G}(y)}{k}\geq|V_{j}|\binom{\gamma||L_{j}||/|V_{j}|}{k}.$

Each such a star corresponds to a full vertex in $U_{x}$, for some $x$. Thus
$\sum_{x\in V_{j-k}}u_{x}\geq t$ and there is a vertex $x$ such that

$u_{x}\geq\frac{|V_{j}|}{|V_{j-k}|}\binom{\gamma^{\prime}||L_{j}||/|V_{j}|}{k}.$

Since $n/2-n^{2/3}\leq j\leq n/2+n^{2/3}$ and $k$ is a fixed constant, we have
that $||L_{j}||/||V_{j}||=\frac{n}{2}(1+o(1))$ and $|V_{j}|/|V_{j-k}|\geq
c^{\prime}(k)$, so

$u_{x}\geq c(k)n^{k},$

for positive constant $c(k)$ and $c^{\prime}(k)$. Consider the full vertices
in $U_{x}$. They correspond to $u_{x}$ hyperedges in a $k$-uniform hypergraph
with the vertex set $[n]-x$ of size $n-j+k=\frac{n}{2}(1+o(1))$. By a theorem
of Erdős [11], such a hypergraph contains any fixed $k$-partite $k$-uniform
hypergraph, and thus in particular the one representing $Z$. Therefore $G$
contains a copy of $Z$ with odd vertices in $V_{j}$.

To prove the second part of the Lemma, we can repeat the above argument by
considering the vertices $x$ in $V_{j+k-1}$ and their downsets. Alternatively,
we see that $L_{j}$ corresponds to $L_{j^{\prime}}$, a “symmetric” layer,
where $j^{\prime}=n+1-j$, $V_{j^{\prime}}$ corresponds to $V_{j-1}$, and
$V_{j^{\prime}-1}$ corresponds to $V_{j}$. Thus, finding a copy of $Z$ in
$L_{j^{\prime}}$ with odd vertices in $V_{j^{\prime}}$ corresponds to finding
a copy of $Z$ in $L_{j}$ with odd vertices in $V_{j-1}$. Since $j^{\prime}$
satisfies the same conditions as $j$, i.e., $n/2-n^{2/3}\leq j^{\prime}\leq
n/2+n^{2/3}$, we thus could use the first part of the Claim to obtain the
second one. ∎

######  Lemma 5.

Let $H$ be a connected bipartite graph with $\ell$ blocks, where every block
has a partite representation. Then for any $\gamma>0$ there is
$n_{0}=n_{0}(\gamma,H)$ such that for any $n>n_{0}$ the following holds. Let
$L_{j}$ be the $j$th layer of $Q_{n}$, where $n/2-n^{2/3}\leq j\leq
n/2+n^{2/3}$. Let $G\subseteq L_{j}$ be a graph with $||G||=\gamma||L_{j}||$.
Fix one of two partite sets of $H$ arbitrarily and call its vertices odd. Then
there is a copy of $H$ in $G$ with odd vertices in $V_{j}$ and there is a copy
of $H$ in $G$ with odd vertices in $V_{j-1}$.

###### Proof.

We shall prove the statement by induction on $\ell$ with the base case
$\ell=1$ directly following from Lemma 4.

If $H$ has $\ell$ blocks, $\ell\geq 2$, such that each has a $k$-partite
representation, let $H=H^{\prime}\cup H^{\prime\prime}$, where $H^{\prime}$
and $H^{\prime\prime}$ share a single vertex $v^{\prime}$, and
$H^{\prime\prime}$ is a block of $H$, i.e., a leaf block. Let $F$ be a graph
that is a union of $q>|V(H^{\prime})|$ copies $F_{1},\ldots,F_{q}$ of
$H^{\prime\prime}$ that pairwise share only a vertex corresponding to
$v^{\prime}$. Let $\gamma>0$ and $n_{0}$ be sufficiently large (we shall
specify how large later). Let $G\subseteq L_{j}$, $||G||=\gamma||L_{j}||$.

Assume first that $v^{\prime}$ is an odd vertex.

The idea of the proof is as follows. We shall first find many copies of
$H^{\prime}$ in $G$ such that a vertex corresponding to $v^{\prime}$ is in
$V_{j}$. Then we shall find a copy of $F^{*}$ of $F$ and a copy $H^{*}$ of
$H^{\prime}$ such that $V(F^{*})\cap V(H^{*})\cap V_{j}=\\{v\\}$, where $v$
plays a role of $v^{\prime}$. Finally, since $q$ is large enough, we shall
claim that there is a copy $F_{i}^{*}$ of $F_{i}$ for some $i$ such that
$V(F_{i}^{*})\cap V(H^{*})\cap V_{j-1}=\emptyset$. This will imply that
$F^{*}_{i}\cup H^{*}$ is a copy of $H$. Next we shall give the details of this
argument:

First, we shall construct sets $\tilde{V},V,$ and $V^{\prime}$, such that
$V^{\prime}\subseteq V\subseteq\tilde{V}\subseteq V_{j}$ as follows:

Consider all copies $H^{\prime}_{v}$ of $H^{\prime}$ in $G$ with a vertex
playing a role of $v^{\prime}$ being in $V_{j}$. Let $\tilde{V}\subseteq
V_{j}$ be the set of such vertices $v$. Note that
$||G[V_{j}-\tilde{V},V_{j-1}]||<\frac{1}{4}\gamma||L_{j}||$, otherwise by
induction we can find another copy $H_{w}^{\prime}$ of $H^{\prime}$ with a
vertex $w\in V_{j}-\tilde{V}$ playing a role of $v^{\prime}$, contradicting
the definition of $\tilde{V}$. Here, we assume that
$n_{0}>n_{0}(\gamma/4,H^{\prime})$. Note, that for each $v\in V$ there could
be several copies of $H^{\prime}$ with $v$ playing a role of $v^{\prime}$. We
choose one such copy $H^{\prime}_{v}$ arbitrarily. Let $V\subseteq\tilde{V}$
be a set of vertices whose degree in $G$ is at least half the average degree
of $G$, i.e. for each $y\in V$,

$d_{G}(y)\geq\frac{\gamma}{2}\frac{||L_{j}||}{|V_{j}|}.$

The total number of edges of $G$ not incident to $V$ is at most
$\frac{1}{4}\gamma||L_{j}||+\frac{1}{2}||G||=\frac{3}{4}\gamma||L_{j}||$. Thus
$||G[V,V_{j-1}]||\geq\frac{\gamma}{4}||L_{j}||$. Since all vertices from
$V_{j}$ in $L_{j}$ have the same degree,

$|V|\geq\frac{\gamma}{4}|V_{j}|.$

Let for each $v\in V$, $A_{v}\subseteq V_{j}$ and $B_{v}\subseteq V_{j-1}$ be
sets of vertices such that $V(H^{\prime}_{v})=A_{v}\cup B_{v}\cup\\{v\\}$,
$v\not\in A_{v}$. Randomly color each vertex in $V$ with red or blue
independently with equal probability, color the vertices in $V_{j}-V$ blue. We
say that a vertex $v\in V$ is good if $v$ is red and each vertex in $A_{v}$ is
blue. Then the expected number of good $v$’s is at least $|V|2^{-t}$, where
$|A_{v}|=t-1$. Thus there is a set $V^{\prime}\subseteq V$, corresponding to a
set of good $v$’s, with $|V^{\prime}|\geq|V|2^{-t}$, such that for each $v\in
V^{\prime}$, $A_{v}\cap V^{\prime}=\emptyset$.

We see that

$||G[V^{\prime},V_{j-1}]||\geq\frac{\gamma}{2}\frac{||L_{j}||}{|V_{j}|}|V^{\prime}|\geq\frac{\gamma}{2}\frac{||L_{j}||}{|V_{j}|}\frac{|V|}{2^{t}}\geq\gamma^{2}2^{-t-3}||L_{j}||.$

Consider the graph $F$ defined above. By Lemma 3 $F$ has a partite
representation. Then by Lemma 4 there is a copy $F^{*}$ of $F$ in
$G[V^{\prime}\cup V_{j-1}]$ with a vertex $v\in V$ corresponding to
$v^{\prime}$. Here, we assume that $n_{0}>n_{1}(\gamma^{2}2^{-t-3},F)$. Let
$F_{i}^{*}$ be a respective copy of $F_{i}$, for each $i\in[q]$. By
construction of $V^{\prime}$, there is a copy $H^{*}$ of $H^{\prime}$ in $G$
with all vertices except for $v$ not in $V^{\prime}$. Let $B_{v}$ be the set
of vertices of $H^{*}$ in $V_{j-1}$. We see that $V(F^{*})\cap V(H^{*})\cap
V_{j}=\\{v\\}$. Since $q>|V(H^{\prime})|>|B_{v}|$, there is $i\in[q]$, such
that $V(F^{*}_{i})\cap B_{v}\cap V_{j-1}=\emptyset$. Then $H^{*}\cup
F_{i}^{*}$ is a copy of $H$ in $G$.

The case when $v^{\prime}$ is not an odd vertex is treated similarly by first
finding many copies of $H^{\prime}$ with a vertex corresponding to
$v^{\prime}$ in $V_{j-1}$. ∎

###### Proof of Theorem 1.

Let $G^{\prime}$ be a subgraph of $Q_{n}$ such that
$||G^{\prime}||=2\gamma||Q_{n}||$, for some constant $\gamma>0$ and
sufficiently large $n$. By a standard argument, see for example Lemma 1 [4],

$\sum_{i:|i-n/2|>n^{2/3}}\binom{n}{i}=o(2^{n}).$

Since the degree of each vertex in $Q_{n}$ is $n$, the total number of edges
in $G^{\prime}$, incident to vertices in $V_{i}$’s, for $i<n/2-n^{2/3}$ or
$i>n/2+n^{2/3}$ is $o(n2^{n})=o(||Q_{n}||)=o(||G||)$. Then there is
$j\in\\{n/2-n^{2/3},n/2+n^{2/3}\\}$ such that $L_{j}$ contains at least
$\gamma||L_{i}||$ edges of $G^{\prime}$. Lemma 5 applied to $G=G^{\prime}\cap
L_{j}$ concludes the proof. ∎

###### Proof of Theorem 2.

Let $H=H(q)$ be a union of two copies $\Theta_{1}$ and $\Theta_{2}$ of
$\Theta(q)$ sharing exactly one vertex that is a main pole of $\Theta_{2}$ and
a subdivision vertex of $\Theta_{1}$.

First we need to check that $H(q)$ is cubical. Marquardt [15] gave an explicit
embedding of $H(3)$ in a hypecube. One can also use a characterisation by
Havel and Moravek [14], who proved that a graph is cubical if and only if it
has a nice edge-coloring. Here, an edge-coloring is nice if any cycle uses
each color an even number of times and each non-trivial path uses some color
an odd number of times. To construct a nice coloring of $H$, one can use nice
colorings of $\Theta_{1}$ and $\Theta_{2}$ using disjoint sets of colors.
These colorings were given in [14] and we show one in Figure 1.

Next, we shall show that $H(q)$ has no partite representation. A Hamming
distance between two binary vectors $a$ and $b$, denoted $d_{H}(a,b)$ is the
number of positions where the vectors differ. In [2] it is shown that if
$q\geq 3$ and $a,a^{\prime}$ are the main poles of a copy of $\Theta(q)$
embedded in a layer of a hypercube, then $d_{H}(a,a^{\prime})=2$. Let the main
poles of $\Theta_{1}$ and $\Theta_{2}$ be denoted
$v_{i}^{\prime},v_{i}^{\prime\prime}$, respectively, $i=1,2$. Assume that $H$
has a $k$-partite representation for some $k$, i.e.,
$V(H)\subseteq\binom{[n]}{k}\cup\binom{[n]}{k-1}$, for some $n$ and
$V(H)\cap\binom{[n]}{k}$ corresponds to the edges of a $k$-partite hypergraph,
denote it by $\mathcal{H}$. We have that
$d_{H}(v_{i}^{\prime},v_{i}^{\prime\prime})=2$, $i=1,2$. Since a main pole of
$\Theta_{1}$ and a main pole of $\Theta_{2}$ are adjacent, the main poles of
$\Theta_{1}$ are in one vertex layer and the main poles of $\Theta_{2}$ are in
another vertex layer, without loss of generality,
$v_{1}^{\prime},v_{1}^{\prime\prime}\in\binom{[n]}{k}$ and
$v_{2}^{\prime},v_{2}^{\prime\prime}\in\binom{[n]}{k-1}$. Assume further that
$v_{1}^{\prime}$ and $v_{1}^{\prime\prime}$ equal to $10$ and $01$ in the
first two positions of their binary representation and coincide on all other
positions. Consider neighbours of $v_{1}$ in $\Theta_{1}$. At least one of
these neighbours, say $w$ differs from $v_{1}^{\prime}$ in a position that is
not one of the first two ones, say in the third position. Then, restricted to
the first three position $v_{1}^{\prime}$ is $101$, $w$ is $100$, and
$v_{1}^{\prime\prime}$ is $011$. Thus, the remaining two vertices on the
$v_{1},v_{1}^{\prime}$ path, that contains $w$, must be equal to $110$ and
$010$ in these three position. All vertices of this leg are the same in
positions $4,\ldots,n$, say they are equal to $1$ on a set of positions
$A\subseteq\\{4,\ldots,n\\}$, $|A|=k-2$. Thus, we have that
$\mathcal{H}^{\prime}$ contains hyperedges $\\{1,2\\}\cup A$, $\\{2,3\\}\cup
A$, and $\\{1,3\\}\cup A$. If $\mathcal{H}$ were to be $k$-partite, $1,2,3$
and each element of $A$ would belong to distinct parts, i.e., to $k+1$ parts,
a contradiction. This shows that $H(q)$ has no partite representation.

Finally, we shall show that $H(q)$ has a zero Turán density in a hypercube.
Using Theorem 1 it is sufficient to show that $\Theta(q)$ has partite
representation. Note that $\Theta(q)=K_{2,q}(1)$, a subdivision of $K_{2,q}$.
We claim that $\mathcal{H}=K_{2,q}$ gives a $2$-partite representation of
$\Theta(q)$. Indeed, let $n=q+2$ and let $\mathcal{H}$ be a hypergraph on a
vertex set $[n]$ with the edge set $\\{ij:i\in[2],j\in[n]\setminus[2]\\}$. So,
$\mathcal{H}$ is a bipartite graph, i.e., $2$-partite $2$-uniform hypergraph.
Let the edges of $\mathcal{H}$ correspond to subdivision vertices of
$K_{2,q}(1)$. Let vertices $1$ and $2$ correspond to the main poles of
$\Theta(q)$ and vertices $2,\ldots,q$ correspond to other vertices. This
concludes the proof of Theorem 2. ∎

Conclusions  We showed that there are cubical graphs that have no partite
representation and have zero Turán density in a hypercube. On the other hand
we proved that any graph whose every block has a partite representation has a
zero Turán density in a hypercube. This leads to a followup question:

Open question  Is it true that in each cubical graph that has a zero Turán
density in a hypercube each block has a partite representation?

Acknowledgements  The research was supported in part by a DFG grant FKZ AX
93/2-1.

## References

  * [1] N. Alon, A. Krech and T. Szabó.  Turán’s theorem in the hypercube. SIAM Journal on Discrete Mathematics, 21(1) (2007), 66–72.
  * [2] M. Axenovich, R. Martin, C. Winter.  On graphs embeddable in a layer of a hypercube and their extremal numbers. ArXiv preprint 2023: arXiv:2303.15529
  * [3] M. Axenovich.  Extremal numbers for cycles in a hypercube. To appear in Discrete Applied Mathematics, ArXiv preprint 2022: arXiv:2211.12842
  * [4] M. Axenovich, J. Manske, R. Martin, Extremal functions for Q2 in a Boolean lattice, Order, Online First, 14 March 2011.
  * [5] R. Baber.  Turán densities of hypercubes. Arxiv preprint (2012) arXiv:1201.3587.
  * [6] J. Balogh, P. Hu, B. Lidický and H. Liu.  Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube. European Journal of Combinatorics 35 (2014), 75–85.
  * [7] P. Brass, H. Harborth and H. Nienborg.  On the maximum number of edges in a $C_{4}$-free subgraph of $Q_{n}$. Journal of Graph Theory 19, (1995) 17–23.
  * [8] F. Chung.  Subgraphs of a hypercube containing no small even cycles. Journal Graph Theory 16 (1992), 273–286.
  * [9] M. Conder.  Hexagon-free subgraphs of hypercubes. Journal of Graph Theory 17 (4) (1993), 477–479.
  * [10] D. Conlon.  An extremal theorem in the hypercube. Electronic Journal of Combinatorics 17 (2010), no. R111.
  * [11] P. Erdős.  On extremal problems of graphs and generalized graphs. Israel J. Math. 2 (1964) 183–190.
  * [12] Z. Füredi and L. Özkahya.  On even-cycle-free subgraphs of the hypercube. Electronic Notes in Discrete Mathematics 34 (2009), 515–517.
  * [13] Z. Füredi and L. Özkahya.  On even-cycle-free subgraphs of the hypercube. Journal of Combinatorial Theory, Series A, 118 (2011), 1816–1819.
  * [14] I. Havel and J. Morávek.  B-valuations of graphs. Czechoslovak Mathematical Journal, Vol. 22 (1972), No. 2, 338–351.
  * [15] F. Marquardt.  On the characterization of graphs with zero Turán density in the hypercube. Master thesis, Karlsruhe Institute of Technology, 2022.
  * [16] D. Offner.  Some Turán type results on the hypercube. Discrete Mathematics, 309(9) (2009), 2905–2912.
  * [17] A. Thomason and P. Wagner.  Bounding the size of square-free subgraphs of the hypercube. Discrete Math. 309 (2009), 1730–1735.
  * [18] I. Tomon.  Robust (rainbow) subdivisions and simplicial cycles. ArXiv preprint 2022: arXiv:2201.12309.