# Universal time and length scales of polar active polymer melts

Mattia Alberto Ubertini<EMAIL_ADDRESS>Current affiliation: Friedrich
Miescher Institute for Biomedical Research (FMI), Basel, Switzerland Scuola
Internazionale Superiore di Studi Avanzati (SISSA), Via Bonomea 265, 34136
Trieste, Italy  Emanuele Locatelli<EMAIL_ADDRESS>Department of
Physics and Astronomy, University of Padova, Via Marzolo 8, I-35131 Padova,
Italy and INFN, Sezione di Padova, Via Marzolo 8, I-35131 Padova, Italy
Angelo Rosa<EMAIL_ADDRESS>Scuola Internazionale Superiore di Studi Avanzati
(SISSA), Via Bonomea 265, 34136 Trieste, Italy

###### Abstract

We present an in-depth multi-scale analysis of the conformations and dynamics
of polar active polymers, comparing very dilute and very dense conditions. We
unveil characteristic length and time scales, common to both dilute and dense
systems, that recapitulate the conformational and dynamical properties of
these active polymers upon varying both the polymer size and the strength of
the activity. Specifically, we find that a correlation (or looping) length
characterises the polymer conformations and the monomer dynamics. Instead, the
dynamics of the center of mass can be fully characterised by the end-to-end
mean-square distance and by the associated relaxation time. As such, we show
that the dynamics in melts of polar active polymers are not controlled by
entanglements but only by the strength of the self-propulsion.

Active matter consists of systems whose fundamental units are able to
transduce energy into persistent movement leading to features very different
from the passive counterparts [1, 2]. Examples of such systems abound in
nature, from the macroscopic scale, such as bird flocks or fish shoals [3],
down to the sub-cellular level, the main example being the cytoskeleton [4].
Of late, significant attention has focused on a specific subset of active
matter – active polymers [5]. This interest arises from their biological
relevance, as many biological systems feature molecular motors, which serve as
prototypical examples of active matter by converting energy from chemical
reactions into motion along biological filaments, such as DNA or RNA. For
instance, DNA polymerase traverses DNA strands during replication, while
ribosomes actively synthesize proteins by sliding along RNA filaments [6].
Experimentally, anomalous diffusion of chromatin loci has been observed [7]
and showed to be caused by non-equilibrium processes related to enzymatic
activity. A further example at the micrometric scale is given by cilia and
flagella, used in mono- as well as multi-cellular organisms for transport and
locomotion [8]. Furthermore, active polymer models have been used to
rationalise the individual and collective properties of filamentous bacteria
and parasites [9, 10, 11]. On the other hand, active filamentous systems have
also attracted attention at the macro-scale, as worms [12] seem to provide an
interesting experimental system with anomalous emerging properties [13, 14,
15, 16]. In all cases, what makes active filaments interesting is that the
energy input at the monomer level changes the typical conformation of the
whole filament and influences its dynamics in a multi-scale fashion. This is
true for a single filament; however, at finite density, it reverberates on the
organisation of the entire system [17, 9, 18, 19]. Consequently, understanding
the multi-scale organisation of active polymer systems represents an important
challenge.

In this paper, we focus on polar (or tangential) active polymers, where a
self-propulsion force is applied to each monomer parallely to the local
backbone tangent. In this case, significant progress has been achieved in
characterizing dilute active linear and ring polymers [20, 21, 22, 23, 24, 25,
26]. Quite surprisingly, less work has been devoted to dense, entangled
polymer systems (melts), feature that is relevant in many contexts, as for
instance in chromatin organization [27]. In particular, the efforts were
restricted to the limit of small activity [28, 29, 30], with the recent
exception of Ref. [31] exploring the consequences of large activity for linear
viscoelasticity. Here, we investigate how activity impacts on the size, shape
and dynamics of entangled polymer chains in melt and compare them vis-à-vis
with their counterparts in dilute conditions, to highlight the main
differences and the interplay between entanglements and activity.

Specifically, we employ Langevin molecular dynamics computer simulations (for
details, see Section S1 in Supporting Information (SI)) of a well established
model for polar active polymers [21] in the presence of both, Brownian thermal
forces, mimicking the effect of the solvent, and active local tangential
forces [21] of constant norm $f_{a}$ imparted on every monomer, except the
first and the last one, of each chain in the system. In order to express the
relative strength of the activity against the thermal fluctuations, we
introduce the usual adimensional Péclet number ${\rm
Pe}\equiv{f_{a}\sigma}/{(\kappa_{B}T)}$ where $T$ is the temperature of the
environment and $\kappa_{B}$ is the Boltzmann constant. Here we choose ${\rm
Pe}=1,5,10,20$, i.e. from low to high activity regime and, for reference, we
compare these situations to the purely passive case ${\rm Pe}=0$. We consider
systems of hundreds ($250$, at least) polymer chains of, respectively,
$N=100,200,400,800$ monomers per chain at the overall monomer density
$\rho=0.85\sigma^{-3}$ ($\sigma$ is the monomer diameter) corresponding to
typical melt conditions [32]. For comparison, we simulate the same chains at
very dilute conditions. A more detailed account of the polymer systems
considered in this work (including their preparation and proper equilibration)
is provided in Sec. S1 in SI.

We characterize the folding of polymer chains across all scales employing the
mean-square internal distance for monomer pairs with contour length separation
$n$,

$\langle
R^{2}(n)\rangle\equiv\frac{1}{N-n}\sum_{n^{\prime}=1}^{N-n}\langle\left({\vec{r}}_{n^{\prime}+n}-{\vec{r}}_{n^{\prime}}\right)^{2}\rangle\,,$
(1)

where ${\vec{r}}_{n}$ ($n=1,...,N$) is the spatial position of monomer $n$ and
the brackets $\langle\cdot\rangle$ denote the ensemble average; we further
consider the corresponding (local) scaling exponent,

$\nu(n)\equiv\frac{1}{2}\,\frac{\log(\langle R^{2}(n+1)\rangle)-\log(\langle
R^{2}(n-1)\rangle)}{\log(n+1)-\log(n-1)}\,.$ (2)

For passive systems (i.e., ${\rm Pe}=0$), $\langle R^{2}(n)\rangle$ display
monotonous behavior (see corresponding panels in Fig. S1 in SI) and the
scaling exponent, although within the limits of finite-size effects, agree
with the established [33] asymptotic values $\nu_{\rm dilute}\simeq 0.6$ and
$\nu_{\rm melt}=0.5$. Conversely, the behavior of $\langle R^{2}(n)\rangle$
for active systems appears more complex (see corresponding panels in Fig. S1
in SI). At fixed ${\rm Pe}$ and $N$, we report three regimes for small,
intermediate and large $n$, with asymptotic $\nu$ (see insets) smaller than
the passive chains (we will expand on this point later). However, and most
remarkably, for the same ${\rm Pe}$, $\langle R^{2}(n)\rangle$ depends, at
intermediate contour separations, also on the total chain length $N$, a
feature completely absent in passive systems.

In order to rationalize this peculiar behavior, we look at the bond-vector
correlation function as a function of the contour length separation $n$ [23,
22, 34],

$c(n)\equiv\frac{1}{\langle{\vec{t}}^{\,2}\rangle}\frac{\sum_{n^{\prime}=1}^{N-1-n}\,\langle{\vec{t}}_{n^{\prime}+n}\cdot{\vec{t}}_{n^{\prime}}\rangle}{N-1-n}\,,$
(3)

where ${\vec{t}}_{n}\equiv{\vec{r}}_{n+1}-{\vec{r}}_{n}$ ($n=1,...,N-1$) is
the oriented bond-vector and
$\langle{\vec{t}}^{\,2}\rangle=\sum_{n^{\prime}=1}^{N-1}\,\langle{\vec{t}}_{n^{\prime}}^{\,2}\rangle/(N-1)$
is the mean-square bond length, i.e. $c(0)=1$ by construction. Since $c(n)$
and $\langle R^{2}(n)\rangle$ are related to each other via the relation
$c(n)=\frac{1}{2}\frac{{\rm d}^{2}}{{\rm d}n^{2}}\langle R^{2}(n)\rangle$,
features of $\langle c(n)\rangle$ may help understanding the observed
phenomenon. Indeed, in passive systems (see top row in Fig. S2 in SI), $c(n)$
displays a power-law decay for both dilute and melt conditions, with
characteristic exponents ($c(n)\sim n^{-0.824}$ for dilute systems and
$c(n)\sim n^{-3/2}$ for melts) in good agreement with previous results [35].
On the contrary, the distinct scaling regimes displayed by $\langle
R^{2}(n)\rangle$ for ${\rm Pe}>0$ are mirrored by the non-monotonous behavior
of $c(n)$ (second to last row in Fig. S2 in SI). Indeed, for ${\rm Pe}>0$,
$c(n)$ exhibits a distinct negative minimum, i.e. bond-vectors become anti-
correlated, at some characteristic length scale $n\equiv n_{\rm min}$.
Afterwards, correlations decay back to zero, yet with a much steeper behavior
($c(n)\sim n^{-3}$, roughly) than in passive conditions.

Figure 1:  Contour distance $n_{\rm min}$ (symbols), corresponding to the
contour length position of the minimum value of the bond-correlation function
$c(n)$ (Eq. (3)) for Péclet number ${\rm Pe}>0$, as a function of the polymer
total length $N$. Each dashed line corresponds to the best fit of the relative
data to the power-law (4), whose values for the exponent $\alpha$ are reported
in the legend (and in Table S1 in SI).  Figure 2:  (Top, main) Normalized
mean-square internal distance, $\langle R^{2}(n)\rangle/\langle R^{2}(n_{\rm
min})\rangle$, as a function of normalized contour length separation,
$n/n_{\rm min}$. (Top, insets) Local scaling exponent $\nu(n)$ (Eq. (2)) as a
function of $n/n_{\rm min}$. The dashed lines set the reference values
$\nu=0.4$ and $\nu=0.5$. (Bottom) Bond-vector correlation function $\langle
c(n)\rangle$ as a function of normalized contour length separation $n/n_{\rm
min}$. The asymptotic $\sim n^{-3}$-decay is a guide to the eye and purely
indicative. For all panels, ${\rm Pe}=20$ is fixed; symbols refer to dilute
($\triangle$) and melt ($\circ$) conditions, respectively.

The presence of the negative minimum, entailing a length scale $n_{\rm min}$,
is particularly suggestive as it implies [36, 37] that, both in dilute and
melt conditions, active polymers tend to (double)fold into looped
conformations of loop mean contour length approximately equal to $n_{\rm
min}$. We thus report such emerging length scale in Fig. 1. We notice that, in
both dilute and melt conditions, $n_{\rm min}$ decreases upon increasing
$\mathrm{Pe}$ at fixed $N$. Conversely, at fixed $\rm Pe$, $n_{\rm min}$ grows
with $N$ as a power-law. We quantify this behavior by fitting our data (see
dashed lines in Fig. 1) to the phenomenological power-law

$n_{\rm min}=n_{0}\left(\frac{N}{n_{0}}\right)^{\alpha}\,,$ (4)

where $n_{0}$ is a microscopic contour length scale that depends on $\rm Pe$
and where $0.259\leq\alpha\leq 0.36$ for dilute chains and $0.32\leq\alpha\leq
0.37$ for melts (see Table S1 in SI for the values of the fit parameters).
More importantly, we claim that $n_{\rm min}$ is the fundamental length scale
of active systems. In fact, by normalizing the mean-square internal distances
$\langle R^{2}(n)\rangle$ in terms of $\langle R^{2}(n=n_{\rm min})\rangle$
and after rescaling $n$ by $n_{\rm min}$, the distinct sets of data for each
$\rm Pe$ collapse onto one single master curve; the same happens with the
bond-correlation functions $c(n)$ (see Fig. 2 and Fig. S3 in SI). After
rescaling, $\langle R^{2}(n)\rangle$ and the associated exponent $\nu(n)$ (Eq.
(2)) reveal the following noteworthy features: (i) for $n/n_{\rm min}\lesssim
1$ both dilute and melt polymers are stiffened by the activity, i.e.
$\nu(n)>0.5$ (see insets in the panels for rescaled $\langle R^{2}(n)\rangle$
in Fig. 2 and Fig. S3 in SI). Interestingly, by fitting $\langle R^{2}(n_{\rm
min})\rangle$ with a power-law $R_{0}^{2}(N/n_{0})^{\beta}$ and using the
results of Eq. (4), one can derive the power-law exponent $\beta/\alpha$ for
$\langle R^{2}(n_{\rm min})\rangle$ as a function of $n_{\mathrm{min}}$,
resulting in $\beta/\alpha>1$ systematically (Table S1 in SI); (ii) for
$n/n_{\rm min}\simeq 1$, the activity-induced looping of the polymer results
in an unusually low value for $\nu$ as the polymer tends to become locally
more compact; (iii) finally, in the long-chain limit ($n/n_{\rm min}\gg 1$)
dilute and melt polymers exhibit the asymptotic values for $\nu(n)$,
respectively $\nu(\infty)\simeq 0.5$ and $\nu(\infty)\simeq 0.4$. Quite
interestingly, these asymptotic values appear to be independent of the
activity level already for relatively moderate activities ${\rm Pe}\geq 5$.

Figure 3:  Monomer mean-square displacement, $g_{1}$, normalized by $\langle
R^{2}(n_{\rm min})\rangle$ as a function of rescaled time $t/\tau_{\rm min}$
(lines) in comparison to normalized mean-square internal distance, $\langle
R^{2}(n)\rangle/\langle R^{2}(n_{\rm min})\rangle$, as a function of
normalized contour length separation, $n/n_{\rm min}$ (symbols). Symbols are
as in Fig. 2 and ${\rm Pe}=20$.

We further show that $n_{\rm min}$ plays an important role in the
characterization of the chain dynamics. We consider the monomer mean-square
displacement [32],

$g_{1}({\tau})\equiv\frac{1}{N}\sum_{n=1}^{N}\langle\left({\vec{r}}_{n}(t+\tau)-{\vec{r}}_{n}(t)\right)^{2}\rangle\,,$
(5)

as a function of time $\tau$; we define the time scale $\tau_{\rm min}$ as
$g_{1}(\tau_{\rm min})=\langle R^{2}(n_{\rm min})\rangle$. By expressing
$g_{1}$ and the time $\tau$ in terms of, respectively, $\langle R^{2}(n_{\rm
min})\rangle$ and $\tau_{\rm min}$, the different data superimpose perfectly
on the normalized data for $\langle R^{2}(n)\rangle$ (Fig. 3 for ${\rm Pe}=20$
and Fig. S4 in SI), namely monomers, on average, move along the contour length
of their chain. Overall, activity triggers a kind of motion where each monomer
is, on average, pulled along the polymer local shape before the chain
reorganizes into a new conformation.

Figure 4:  (Top) Mean-square displacement of the chain centre of mass per unit
time, $g_{3}(\tau)/\tau$, normalized by $\langle R_{\rm
ee}^{2}\rangle/\tau_{\rm ee}$ as a function of normalized time $\tau/\tau_{\rm
ee}$ at fixed ${\rm Pe}=20$. (Bottom, left) Chain mean-square end-to-end
distance $\langle R_{\rm ee}^{2}\rangle$ normalized by $N$ as a function of
$\rm Pe$ (symbols) and corresponding power-law best fits (lines). (Bottom,
right) Chain relaxation time $\tau_{\rm ee}$ normalized by $N$ as a function
of $\rm Pe$ (symbols) and corresponding power-law best fits (lines). Symbols
are as in Fig. 2.  Figure 5:  Long-time diffusion coefficient of the centre of
mass, $D$ (in units of monomer diffusion coefficient, see Sec. S1.2 in SI), as
a function of ${\rm Pe}$. Symbols are as in Fig. 2. Lines recapitulating the
data correspond to the analytical expression for dilute chains proposed in
[21] and a phenomenological power-law fit ($\sim{\rm Pe}^{1.20}$) for melts.
(Inset) Corresponding ratios, $D_{\rm dilute}/D_{\rm melt}$, between diffusion
coefficients in dilute and melt conditions as a function of $\rm Pe$.

Finally, the material properties of the system, such as its viscosity, are of
crucial interest for polymer melts and can be connected to the dynamics of the
center of mass of the chains [33]. We thus investigate $g_{3}({\tau})$, the
mean-square displacement of the chain centre of mass ${\vec{r}}_{\rm
CM}(t)\equiv\frac{1}{N}\sum_{n=1}^{N}{\vec{r}}_{n}(t)$, defined as

$g_{3}({\tau})\equiv\langle\left({\vec{r}}_{\rm CM}(t+\tau)-{\vec{r}}_{\rm
CM}(t)\right)^{2}\rangle\,,$ (6)

as a function of time $\tau$. Previous works [21, 34, 24, 38] on dilute polar
active polymers has shown that, with respect to passive systems, $g_{3}(\tau)$
displays a ballistic regime up to the chain relaxation time $\tau_{\rm ee}$,
defined as $g_{3}(\tau_{\rm ee})=\langle R_{\rm ee}^{2}\rangle$, $\langle
R_{\rm ee}^{2}\rangle$ being the mean-square end-to-end distance (i.e., Eq.
(1) with $n=N-1$); as such, $\tau_{\rm ee}$ is proportional to the end-to-end
correlation time, usually employed to characterize $g_{3}(\tau)$ in polar
active polymer models. At larger times an active diffusive regime ensues
$g_{3}(\tau)=6D\tau$, where the active diffusion coefficient $D$ increases
with ${\rm Pe}$ and is independent of the chain contour length $N$, in
contrast with the passive, hydrodynamic-free, predictions [33]. We observe
that such features are present also in melt conditions. Additionally, upon
normalizing $g_{3}({\tau})$ by the corresponding $\langle R_{\rm
ee}^{2}\rangle$ and $\tau$ by $\tau_{\rm ee}$, data from systems at different
values of $N$ and $\mathrm{Pe}$ strikingly collapse onto the same universal
curve that is valid for both dilute and melt systems in the ballistic and
active diffusive regime (Fig. 4 (top panel) and Fig. S5 in SI). This result is
quite remarkable for polymer melts as, according to the classical tube model
[33], for $\tau<\tau_{\rm ee}$ single-chain dynamics is expected to be sub-
diffusive, $g_{3}\sim t^{1/2}$, since motion is confined in a tube-like
region, resulting from the topological barriers (entanglements) exerted by the
surrounding chains. The absence of this regime suggests that polymer dynamics
is entirely controlled by activity, that govers $\tau_{\rm ee}$ and $\langle
R_{\rm ee}^{2}\rangle$, and entanglements become almost irrelevant for
polymers’ dynamics in melts of tangentially active polymers. In support of
this point, we highlight the scaling of $\langle R_{\rm ee}^{2}\rangle$ and
$\tau_{\rm ee}$ in melt conditions: $\langle R_{\rm ee}^{2}\rangle\propto
N/\mathrm{Pe}^{0.1}$ and $\tau_{\rm ee}\propto N/\mathrm{Pe}^{1.3}$ (Fig. 4,
bottom panels). Notice, in particular, a difference with the infinite dilution
case, where $\langle R_{\rm ee}^{2}\rangle\sim N/\mathrm{Pe}^{0.3}$ and
$\tau_{\rm ee}\propto N/\mathrm{Pe}$, as well as with passive melts where
$\tau_{\rm ee}\sim N^{3}$ [33]. As $D\propto\langle R_{\rm
ee}^{2}\rangle/\tau_{\rm ee}$, we indeed recover the scaling of $D$ as
function of $N$ and $\mathrm{Pe}$, $D\propto N^{0}\cdot\mathrm{Pe}^{1.2}$ (see
dashed line in Fig. 5). While results for dilute chains are in agreement with
the analytical predictions [21] (solid line in Fig. 5, see also the brief
recapitulation in Sec. S2.1 in SI), notice that $D$ has a steeper increase in
melt; as such although dilute chains diffuse systematically faster than in
melt, the gap between the two appears to be narrowing for growing $\rm Pe$
(see inset in Fig. 5) until the two set-up’s become substantially equivalent
at sufficiently high values of $\mathrm{Pe}$. These findings align with the
reported observations that the relaxation times $\tau_{\rm ee}$ for the two
set-up’s become increasingly close to each other as $\rm Pe$ increases (Fig.
4, bottom right panel).

To summarize, in this work we have investigated the impact of activity on the
conformational and dynamical properties of linear chains in melt conditions,
as compared to dilute active and passive melt counterparts. The multi-scale
analysis of the conformations highlighted a fundamental length scale, $n_{\rm
min}$, which governs both the conformation of the active chains as well the
dynamics of the individual monomers. The latter property highlights the
“railway motion”, typical of tangential propulsion, where monomers move along
the contour path of the backbone. Notably, we observe deviations from random
walk statistics, particularly for the formation of loops (see Figs. S1 and S2
in SI) within the chains. Moreover, the asymptotic exponent $\nu$ extracted
from $\langle R^{2}(n)\rangle$ deviates from the random walk value of
$\nu=1/2$. While the deviation is small for single chains and both predictions
are, overall, compatible with the results reported in [21], chains in the melt
deviate significantly reaching a value of $\nu\simeq 0.4$. In this respect,
some warning needs to be given on attempting to measure $\nu$ from the scaling
of the mean-square end-to-end distance $\langle R_{\rm ee}^{2}\rangle$
(namely, Eq. (1) with $n=N-1$) vs. $N$. In fact, as shown in Sec. S2.2 and the
corresponding Fig. S6 in SI and in agreement with [31], the exponent $\nu$ of
active chains appears to be $\simeq 0.5$ for both dilute and melt conditions
suggesting that active chains in melt do not remain completely self-similar
(as also pointed out by the mean-square internal distance $\langle
R^{2}(n)\rangle$ in Fig. S1 in SI [39]). At the same time, we have shown that
the (apparent) scaling $\langle R_{\rm ee}^{2}\rangle\sim N$ plays a role in
the characterization of chain dynamics. We further find that both systems
remarkably exhibit the same centre of mass dynamics (see Fig. 4) governed by
the length scale $\langle R_{\rm ee}^{2}\rangle$ and by the time scale
$\tau_{\rm ee}$. At long times, $\tau\gg\tau_{\rm ee}$, both systems diffuse
with a diffusion coefficient, $D$, which increases with ${\rm Pe}$ (see Fig.
4) and is independent on $N$. However, as mentioned, $D$ has a stronger
dependence on $\mathrm{Pe}$ in melts, possibly hinting at the emergence of
multi-chain effects that go beyond the railway motion. Taken together our
results suggest that both chain conformations and dynamics present universal
features, that are independent of whether chains are dilute or in melt
conditions. In the latter situation, in particular, the slowing effects due to
the unavoidable topological constraints (entanglements) between distinct
chains – a fundamental property of their passive counterparts – become
negligible when chains are subjected to tangential active forces. These
results align with experimental observations [14] on active worms, which
showed a decrease in system viscosity with activity, and a milder dependence
on concentration compared to passive entangled systems. Moreover, as recently
shown [31], for tangentially propelled entangled chains the plateau modulus,
$G_{0}$, that encodes the elastic response of the system [33], depends on the
active forces in the systems and is not anymore simply proportional [33] to
the mean concentration of entanglement lengths as in equilibrium conditions.

## Supporting Information

Complementary details on: polymer model, molecular dynamics computer
simulations and preparation and equilibration of polymer configurations,
single-chain diffusion and mean-square end-to-end distance. Supporting table
for scaling parameters $n_{\rm min}$ and $\langle R^{2}(n_{\rm min})\rangle$.
Additional figures on: polymer structure (internal distances and bond-vector
correlations), polymer dynamics (mean-square displacements for monomers and
chain centre of mass).

###### Acknowledgements.

This work was supported by a STSM Grant from COST Action CA17139
(eutopia.unitn.eu) funded by COST (www.cost.eu). E. Locatelli acknowledges
support from the MIUR grant Rita Levi Montalcini.

## References

  * Ramaswamy [2010] S. Ramaswamy, The mechanics and statistics of active matter, Annu. Rev. Condens. Matter Phys. 1, 323 (2010).
  * Marchetti  _et al._ [2013] M. C. Marchetti, J.-F. Joanny, S. Ramaswamy, T. B. Liverpool, J. Prost, M. Rao, and R. A. Simha, Hydrodynamics of soft active matter, Rev. Mod. Phys. 85, 1143 (2013).
  * Vicsek and Zafeiris [2012] T. Vicsek and A. Zafeiris, Collective motion, Phys. Rep. 517, 71 (2012).
  * Fletcher and Mullins [2010] D. A. Fletcher and R. D. Mullins, Cell mechanics and the cytoskeleton, Nature 463, 485 (2010).
  * Winkler and Gompper [2020] R. G. Winkler and G. Gompper, The physics of active polymers and filaments, J. Chem. Phys. 153 (2020).
  * Alberts  _et al._ [2002] B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, and P. Walter, The cytoskeleton and cell behavior, in  _Molecular Biology of the Cell. 4th edition_ (Garland science, 2002).
  * Weber  _et al._ [2012] S. C. Weber, A. J. Spakowitz, and J. A. Theriot, Nonthermal atp-dependent fluctuations contribute to the in vivo motion of chromosomal loci, Proc. Natl. Acad. Sci. USA 109, 7338 (2012).
  * Gilpin  _et al._ [2020] W. Gilpin, M. S. Bull, and M. Prakash, The multiscale physics of cilia and flagella, Nature Reviews Physics 2, 74 (2020).
  * Patra  _et al._ [2022] P. Patra, K. Beyer, A. Jaiswal, A. Battista, K. Rohr, F. Frischknecht, and U. S. Schwarz, Collective migration reveals mechanical flexibility of malaria parasites, Nature Physics 18, 586 (2022).
  * Faluweki  _et al._ [2023] M. K. Faluweki, J. Cammann, M. G. Mazza, and L. Goehring, Active spaghetti: collective organization in cyanobacteria, Physical Review Letters 131, 158303 (2023).
  * Kurjahn  _et al._ [2024] M. Kurjahn, L. Abbaspour, F. Papenfuß, P. Bittihn, R. Golestanian, B. Mahault, and S. Karpitschka, Collective self-caging of active filaments in virtual confinement, arXiv preprint arXiv:2403.03093 (2024).
  * Deblais  _et al._ [2023] A. Deblais, K. Prathyusha, R. Sinaasappel, H. Tuazon, I. Tiwari, V. P. Patil, and M. S. Bhamla, Worm blobs as entangled living polymers: from topological active matter to flexible soft robot collectives, Soft Matter 19, 7057 (2023).
  * Deblais  _et al._ [2020a] A. Deblais, A. Maggs, D. Bonn, and S. Woutersen, Phase separation by entanglement of active polymerlike worms, Phys. Rev. Lett. 124, 208006 (2020a).
  * Deblais  _et al._ [2020b] A. Deblais, S. Woutersen, and D. Bonn, Rheology of entangled active polymer-like t. tubifex worms, Phys. Rev. Lett. 124, 188002 (2020b).
  * Ozkan-Aydin  _et al._ [2021] Y. Ozkan-Aydin, D. I. Goldman, and M. S. Bhamla, Collective dynamics in entangled worm and robot blobs, Proc. Natl. Acad. Sci. USA 118, e2010542118 (2021).
  * Patil  _et al._ [2023] V. P. Patil, H. Tuazon, E. Kaufman, T. Chakrabortty, D. Qin, J. Dunkel, and M. S. Bhamla, Ultrafast reversible self-assembly of living tangled matter, Science 380, 392 (2023).
  * Smrek  _et al._ [2020] J. Smrek, I. Chubak, C. N. Likos, and K. Kremer, Active topological glass, Nature Communications 11, 26 (2020).
  * Dunajova  _et al._ [2023] Z. Dunajova, B. P. Mateu, P. Radler, K. Lim, D. Brandis, P. Velicky, J. G. Danzl, R. W. Wong, J. Elgeti, E. Hannezo, _et al._ , Chiral and nematic phases of flexible active filaments, Nature Physics 19, 1916 (2023).
  * Miranda  _et al._ [2024] J. P. Miranda, E. Locatelli, and C. Valeriani, Self-organized states from solutions of active ring polymers in bulk and under confinement, Journal of Chemical Theory and Computation 20, 1636 (2024).
  * Isele-Holder  _et al._ [2015] R. E. Isele-Holder, J. Elgeti, and G. Gompper, Self-propelled worm-like filaments: spontaneous spiral formation, structure, and dynamics, Soft Matter 11, 7181 (2015).
  * Bianco  _et al._ [2018] V. Bianco, E. Locatelli, and P. Malgaretti, Globulelike conformation and enhanced diffusion of active polymers, Phys. Rev. Lett. 121, 217802 (2018).
  * Locatelli  _et al._ [2021] E. Locatelli, V. Bianco, and P. Malgaretti, Activity-induced collapse and arrest of active polymer rings, Phys. Rev. Lett. 126, 097801 (2021).
  * Foglino  _et al._ [2019] M. Foglino, E. Locatelli, C. Brackley, D. Michieletto, C. Likos, and D. Marenduzzo, Non-equilibrium effects of molecular motors on polymers, Soft Matter 15, 5995 (2019).
  * Philipps  _et al._ [2022a] C. A. Philipps, G. Gompper, and R. G. Winkler, Tangentially driven active polar linear polymers—an analytical study, J. Chem. Phys. 157, 194904 (2022a).
  * Philipps  _et al._ [2022b] C. A. Philipps, G. Gompper, and R. G. Winkler, Dynamics of active polar ring polymers, Phys. Rev. E 105, L062501 (2022b).
  * Vatin  _et al._ [2024] M. Vatin, S. Kundu, and E. Locatelli, Conformation and dynamics of partially active linear polymers, Soft Matter 20, 1892 (2024).
  * Rosa and Everaers [2008] A. Rosa and R. Everaers, Structure and dynamics of interphase chromosomes, Plos Comput. Biol. 4, e1000153 (2008).
  * Tejedor and Ramirez [2019] A. R. Tejedor and J. Ramirez, Reptation of active entangled polymers, Macromolecules 52, 8788 (2019).
  * Tejedor and Ramirez [2020] A. R. Tejedor and J. Ramirez, Dynamics of entangled polymers subjected to reptation and drift, Soft Matter 16, 3154 (2020).
  * Tejedor  _et al._ [2023] A. R. Tejedor, R. Carracedo, and J. Ramírez, Molecular dynamics simulations of active entangled polymers reptating through a passive mesh, Polymer 268, 125677 (2023).
  * Breoni  _et al._ [2023] D. Breoni, C. Kurzthaler, B. Liebchen, H. Löwen, and S. Mandal, Giant activity-induced stress plateau in entangled polymer solutions, arXiv:2310.02929v1 (2023).
  * Kremer and Grest [1990] K. Kremer and G. S. Grest, Dynamics of entangled linear polymer melts: A molecular‐dynamics simulation, J. Chem. Phys. 92, 5057 (1990).
  * Rubinstein and Colby [2003] M. Rubinstein and R. H. Colby,  _Polymer Physics_ (Oxford University Press, New York, 2003).
  * Fazelzadeh  _et al._ [2023] M. Fazelzadeh, E. Irani, Z. Mokhtari, and S. Jabbari-Farouji, Effects of inertia on conformation and dynamics of tangentially driven active filaments, Phys. Rev. E 108, 024606 (2023).
  * Wittmer  _et al._ [2004] J. P. Wittmer, H. Meyer, J. Baschnagel, A. Johner, S. Obukhov, L. Mattioni, M. Müller, and A. N. Semenov, Long range bond-bond correlations in dense polymer solutions, Phys. Rev. Lett. 93, 147801 (2004).
  * Müller  _et al._ [2000] M. Müller, J. P. Wittmer, and M. E. Cates, Topological effects in ring polymers. ii. influence of persistence length, Phys. Rev. E 61, 4078 (2000).
  * Rosa and Everaers [2014] A. Rosa and R. Everaers, Ring polymers in the melt state: The physics of crumpling, Phys. Rev. Lett. 112, 118302 (2014).
  * Li  _et al._ [2023] J.-X. Li, S. Wu, L.-L. Hao, Q.-L. Lei, and Y.-Q. Ma, Nonequilibrium structural and dynamic behaviors of polar active polymer controlled by head activity, Physical Review Research 5, 043064 (2023).
  * [39] This should not be too surprising. An analogous situation occurs for flexible polymers that are densely packed in a spherical cavity. For increasing chain length $N$ the radius of the sphere must also increase to keep the density fixed and, trivially, $\langle R_{\rm ee}^{2}\rangle\sim N^{2/3}$. On the other hand, on length scales smaller than the radius of the sphere, the local structure of the system is no different than the one of an ordinary polymer melt, implying $\nu=1/2$.
  * [40] By this choice of the parameters the FENE bond (Eq. S2) is made stronger, in this way accidental strand-crossings between chains can be carefully avoided (see Ref. [22]).
  * Thompson  _et al._ [2022] A. P. Thompson, H. M. Aktulga, R. Berger, D. S. Bolintineanu, W. M. Brown, P. S. Crozier, P. J. in’t Veld, A. Kohlmeyer, S. G. Moore, T. D. Nguyen, _et al._ , Lammps-a flexible simulation tool for particle-based materials modeling at the atomic, meso, and continuum scales, Comput. Phys. Commun. 271, 108171 (2022).
  * Ubertini and Rosa [2021] M. A. Ubertini and A. Rosa, Computer simulations of melts of ring polymers with nonconserved topology: A dynamic monte carlo lattice model, Phys. Rev. E 104, 054503 (2021).
  * Ubertini  _et al._ [2022] M. A. Ubertini, J. Smrek, and A. Rosa, Entanglement length scale separates threading from branching of unknotted and non-concatenated ring polymers in melts, Macromolecules 55, 10723 (2022).
  * [44] Note that, only for the preparation of the initial states, we have adopted the conventional [32] Kremer-Grest values for the parameters in Eq. (S2), namely: $\epsilon=1\,\kappa_{B}T$ and $k=30\,\kappa_{B}T/\sigma^{2}$.

– Supporting Information –
Universal time and length scales of polar active polymer melts

Mattia Alberto Ubertini, Emanuele Locatelli, Angelo Rosa

###### Contents

  1. S1 Polymer model and methods
    1. S1.1 Numerical model for active polymers
    2. S1.2 Simulation details
    3. S1.3 Preparation of initial chain configurations and check for equilibration
  2. S2 More on single-chain properties
    1. S2.1 Long-time diffusion coefficient
    2. S2.2 Mean-square end-to-end distance

In this Supporting Information file, we provide more specific details on the
polymer model used (Sec. S1.1), on the compositions of the considered polymer
systems and technical details on the molecular dynamics computer simulations
(Sec. S1.2) and on the initial preparation and following equilibration of the
systems (Sec. S1.3). We conclude with a brief overview on the scaling
properties of the mean-square end-to-end distance for our polymers (Sec. S2.2)
and a short recap (Sec. S2.1) of the theory for active polymer model diffusion
first discussed in Refs. [21, 34] and used in the main text.

##  S1 Polymer model and methods

###  S1.1 Numerical model for active polymers

Chain connectivity and monomer-monomer interactions for dilute and melt linear
chains are accounted for by a suitably modified version of the classical
polymer model by Kremer and Grest [32]. Specifically, excluded volume
interactions between beads (including consecutive ones along the contour
length of the chains) are described in terms of the shifted and truncated
Lennard-Jones (LJ) potential:

$U_{\rm
LJ}(r)=\left\\{\begin{array}[]{lr}4\epsilon\left[\left(\frac{\sigma}{r}\right)^{12}-\left(\frac{\sigma}{r}\right)^{6}+\frac{1}{4}\right]&\,r\leq
r_{c}\\\ 0&\,r>r_{c}\end{array}\right.\,,$ (S1)

where $r$ denotes the spatial separation between the bead centers. By denoting
with $\kappa_{B}$ the Boltzmann constant, the energy scale is set to
$\epsilon=20\,\kappa_{B}T$ (against the standard $\epsilon=1\hskip
2.84544pt\kappa_{B}T$ [32]) where $T$ and $\sigma$ are, respectively, the
units of temperature and length in our simulation. The unit of energy is thus
taken as the thermal energy, i.e. $\kappa_{B}T=1$. Further, nearest-neighbour
monomers along the contour of the chains are connected by the finitely
extensible nonlinear elastic (FENE) potential, given by:

$U_{\rm
FENE}(r)=\left\\{\begin{array}[]{lcl}-0.5kR_{0}^{2}\ln\left(1-(r/R_{0})^{2}\right)&\
r\leq R_{0}\\\ \infty&\ r>R_{0}&\end{array}\right.\,,$ (S2)

where $k=30\epsilon/\sigma^{2}=600\,\kappa_{B}T/\sigma^{2}$ is the spring
constant and $R_{0}=1.5\sigma$ is the maximum extension of the elastic FENE
bond [40]. Finally, polymer activity is taken into account by imposing that
the $i$-th monomer of each chain of spatial coordinates $\vec{r}_{i}$ (for
$i=2,...,N-1$, with $N$ being the total number of monomers of the chain) is
subject to the active force $\vec{F}_{i}$ [21]:

$\vec{F}_{i}=f_{a}\frac{\vec{r}_{i+1}-\vec{r}_{i-1}}{|\vec{r}_{i+1}-\vec{r}_{i-1}|}\,,$
(S3)

of constant magnitude $f_{a}$ and instantaneous orientation directed along the
tangent to the polymer chain at $\vec{r}_{i}$. Notice that the first and the
last monomers of each chain are (conventionally, see [21]) excluded by the
active perturbation because those monomers have only one, instead of two,
neighbor along the chain. As described in the main paper, the relative
importance of the active forces vs. the thermal ones is quantified in term of
the so called Péclet number $\rm Pe$, defined as

${\rm Pe}\equiv\frac{f_{a}\sigma}{\kappa_{B}T}\,,$ (S4)

We consider values ${\rm Pe}=1,5,10,20$ and, for comparison, the purely
passive case ${\rm Pe}=0$.

###  S1.2 Simulation details

We consider monodisperse melts of $M$ linear polymer chains, each chain being
made of $N$ monomers. Specifically, we consider systems with compositions
$(M,N)=(1000,100)$, $(500,200)$ and $(250,400)$ (i.e., $M\times N=100,\\!000$
monomers in total) and $(M,N)=(250,800)$ (i.e., $M\times N=200,\\!000$
monomers in total). As in the original work by Kremer and Grest [32], we
maintain a fixed monomer density of $\rho=0.85\sigma^{-3}$ for all polymer
compositions.

As mentioned in the main paper, we compare simulation results for active
polymer melts to those for single self-avoiding active polymers in dilute
conditions. In the latter case we simulate the same systems as the ones of the
set-up’s described above, with deactivated inter-chain LJ (see Eq. (S1))
excluded volume interactions. This allows us to effectively simulate replicas
of linear chains in dilute conditions.

The static and kinetic properties of chains are studied using fixed-volume and
constant-temperature molecular dynamics (MD) simulations with implicit solvent
and periodic boundary conditions. MD simulations are performed by using the
LAMMPS package [41]. By introducing the MD time-unit $\tau_{\rm
MD}=\sigma\sqrt{m/\kappa_{B}T}$, we integrate the equations of motion by using
the velocity-Verlet algorithm. We set $\Delta t$, the integration time step of
the algorithm, as the following: (i) $\Delta t=0.01\,\tau_{\rm MD}$ for
passive polymers (i.e., $\rm{Pe}=0$) and (ii) $\Delta t=0.001\,\tau_{\rm MD}$
for active systems with ${\rm Pe}>0$ (in order to prevent accidental strand-
crossings, especially in the regime of high active forces). Finally, in order
to ensure the overdamped regime [34], the friction coefficient $\gamma$ is
$=20\,\tau^{-1}_{MD}$.

###  S1.3 Preparation of initial chain configurations and check for
equilibration

Preparation of melts of linear chains poses no particular technical problem.
Chains up to $N=400$ were initially arranged inside the simulation box and the
system is passively (i.e., active forces at this stage are turned off) let
towards complete equilibration (defined as after the chains have drifted from
their original positions for several times their own root-mean-square end-to-
end distance, $\sqrt{\langle R_{\rm ee}^{2}\rangle}$ (where $\langle R_{\rm
ee}^{2}\rangle$ is Eq. (1) in the main text with $n=N-1$). For the case with
$N=800$ this procedure becomes tediously long, so we have prepared first the
system on the FCC lattice and, then, let it partially equilibrate by means of
the efficient kinetic Monte Carlo algorithm used in [42, 43]. After completing
this step, we move the whole system back off-lattice again and let it evolve
by standard MD: being the system highly entangled for the polymer contour
length considered, we performed one last equilibration check by verifying that
the main structural properties of the chains are effectively independent of
the initial preparation [44].

Following this initial set-up, the polymer conformations become the starting
point for the production runs of systems in the presence of active force
(i.e., for ${\rm Pe}>0$) and, also, for their passive counterparts (${\rm
Pe}=0$). The typical production run consists of $10^{6}\,\tau_{\rm MD}$-units.

##  S2 More on single-chain properties

###  S2.1 Long-time diffusion coefficient

The long time diffusion coefficient of isolated tangentially active polymers
can be computed analytically [21, 34]. We start from the diffusion coefficient
for an Active Brownian Particle,

$D=D_{t}+\frac{\tau_{r}\,v_{a}^{2}}{2d}=D_{t}+\frac{\tau_{r}\left(F_{a}/\gamma\right)^{2}}{2d}\,,$
(S5)

where $v_{a}=f_{a}/\gamma$ is the self-propulsion velocity and
$D_{t}=\kappa_{B}T/\gamma$; $d$ is the dimensionality of the system (here,
$d=3$). For a tangentially active polymer: (i) $\gamma=N\gamma_{0}$,
$\gamma_{0}$ being the friction coefficient of a single monomer; (ii)
$F_{a}=f_{a}R_{\rm ee}/\sigma$, with $f_{a}=\frac{\kappa_{B}T}{\sigma}{\rm
Pe}$ as in Eq. (S4), $R_{\rm ee}$ being the (root mean-square) end-to-end
distance and $\sigma$ the mean bond length (Sec. S1.1); (iii)
$\tau_{r}=\tau_{\rm ee}$ corresponds to the chain relaxation time (defined in
the main text). If $f_{a}$ is sufficiently large, we can disregard the passive
contribution and write

$D=\frac{\tau_{\rm
ee}}{2d}\,\left(\frac{\mathrm{Pe}}{N}\frac{\kappa_{B}T}{\gamma_{0}}\frac{R_{\rm
ee}}{\sigma}\right)^{2}=\frac{1}{2d}\frac{\tau_{\rm
ee}D_{0}}{\sigma^{2}}\,\frac{\mathrm{Pe}^{2}}{N^{2}}\frac{R^{2}_{\rm
ee}}{\sigma^{2}}D_{0}\,.$ (S6)

We now consider what is reported in the top panel of Fig. 4 in the main text
and Fig. S5 here, i.e. $(g_{3}(\tau)/\tau)/(R_{\rm ee}^{2}/\tau_{\rm ee})$. We
focus on the long time diffusion: we have by definition that
$g_{3}(\tau)=2dD\tau$, from which $g_{3}(\tau)/\tau=2dD$. As such, the data
reported in Fig. 4 in the main text and Fig. S5 here show that

$(g_{3}(\tau)/\tau)/(R_{\rm ee}^{2}/\tau_{\rm ee})=(2dD)/(R_{\rm
ee}^{2}/\tau_{\rm ee})\simeq 1.5\,.$ (S7)

From Eq. (S6) we get

$\frac{2dD}{R_{\rm ee}^{2}/\tau_{\rm ee}}=\left(\frac{\tau_{\rm
ee}D_{0}}{\sigma^{2}}\right)^{2}\,\frac{\mathrm{Pe}^{2}}{N^{2}}=\left(\tau_{0}\frac{N}{\mathrm{Pe}}\right)^{2}\,\frac{\mathrm{Pe}^{2}}{N^{2}}=\tau_{0}^{2}\,,$
(S8)

where $D_{0}$ is the passive diffusion coefficient of a single monomer and we
have used the relation $\tau_{\rm ee}D_{0}/\sigma^{2}=\tau_{0}N/{\rm Pe}$,
shown to be valid in dilute conditions for the characteristic relaxation time
$\tau_{\rm ee}$ in Fig. 4 of the main text. As $D_{0}=\kappa_{B}T/\gamma=0.05$
in this work, from Fig. 4 we get $\tau_{0}=1.05$. As such, the analytical
prediction is $(2dD)/(R_{\rm ee}^{2}/\tau_{e})=1.1$.

###  S2.2 Mean-square end-to-end distance

Results for $\langle R_{\rm ee}^{2}\rangle$ are reported in Fig. S6. The
passive case (${\rm Pe}=0$) behaves as expected, dilute linear chains exhibit
swelling compared to chains within the melt, with their sizes scaling
differently. Specifically, the scaling exponent for dilute chains is
$\nu=0.588$ [33], while in the melt, linear chains follow random walk
statistics [33] and their sizes scale with $\nu=0.5$. Notably, in both
systems, as $\rm{Pe}$ grows, the polymers crumple, a feature already seen for
dilute active linear chains [21]. Remarkably, at high Péclet number $\simeq
10/20$, across all considered polymer lengths $N$, $\langle R_{\rm
ee}^{2}\rangle$ for both dilute and melt cases converge to similar values.
Moreover, always at high activity, the scaling of $\langle R_{\rm
ee}^{2}\rangle$ appears to align with ideal behavior, exhibiting a scaling
exponent of $\nu=0.5$ for both cases.

## Supporting Table & Figures

|  |  | Dilute |  |  | Melt
---|---|---|---|---|---|---
${\rm Pe}$ |  |  |  $n_{0}$ |  |  $\alpha$ |  |  $R_{0}^{2}$ |  |  $\beta$ |  |  $\beta/\alpha$ |  |  |  $n_{0}$ |  |  $\alpha$ |  |  $R_{0}^{2}$ |  |  $\beta$ |  |  $\beta/\alpha$
$1$ |  |  | $8.2\pm 1.7$ |  | $0.36\pm 0.02$ |  | $17.4\pm 4.1$ |  | $0.45\pm 0.02$ |  | $1.2\pm 0.1$ |  |  | $5.2\pm 1.6$ |  | $0.37\pm 0.03$ |  | $4.7\pm 1.7$ |  | $0.63\pm 0.02$ |  | $1.7\pm 0.2$
$5$ |  |  | $3.3\pm 0.2$ |  | $0.330\pm 0.007$ |  | $4.9\pm 0.4$ |  | $0.435\pm 0.006$ |  | $1.32\pm 0.05$ |  |  | $3.3\pm 0.9$ |  | $0.37\pm 0.03$ |  | $2.8\pm 1.3$ |  | $0.63\pm 0.04$ |  | $1.7\pm 0.2$
$10$ |  |  | $2.4\pm 0.2$ |  | $0.311\pm 0.008$ |  | $3.0\pm 0.3$ |  | $0.433\pm 0.008$ |  | $1.39\pm 0.06$ |  |  | $3.1\pm 0.8$ |  | $0.35\pm 0.02$ |  | $2.7\pm 1.1$ |  | $0.59\pm 0.04$ |  | $1.7\pm 0.2$
$20$ |  |  | $2.4\pm 0.1$ |  | $0.259\pm 0.005$ |  | $2.7\pm 0.1$ |  | $0.396\pm 0.006$ |  | $1.53\pm 0.05$ |  |  | $2.9\pm 0.5$ |  | $0.32\pm 0.02$ |  | $2.6\pm 0.7$ |  | $0.55\pm 0.03$ |  | $1.7\pm 0.2$

Table S1:  Fit parameters for the empirical power-laws $n_{\rm
min}=n_{0}\\!\left(\frac{N}{n_{0}}\right)^{\\!\alpha}$ and $\langle
R^{2}(n_{\rm min})\rangle=R_{0}^{2}\left(\frac{N}{n_{0}}\right)^{\\!\beta}$
(see main text for details) for dilute and melt systems and at Péclet number
$\rm Pe$. By combining these two power-laws, one get the scaling $\langle
R^{2}(n_{\rm min})\rangle\sim n_{\rm min}^{\beta/\alpha}$: the exponent
$\beta/\alpha$ has been calculated from the corresponding values for $\alpha$
and $\beta$.  Figure S1:  Mean-square internal distance, $\langle
R^{2}(n)\rangle$ (Eq. (1) in the main paper), as a function of contour length
separation, $n$, and (insets) corresponding local scaling exponents $\nu(n)$
(Eq. (2) in the main paper). Left- and right-hand-side panels are for dilute
and melt systems. The dashed lines in the insets are for reference values
$\nu=0.4$, $0.5$ and $0.6$. Increasing Péclet numbers are from top to bottom,
while different colors are for different total chain lengths $N$ (see legend).
Figure S2:  Bond-vector correlation function, $\langle c(n)\rangle$ (Eq. (3)
in the main paper), as a function of contour length separation, $n$, in log-
lin representation (main panels) and corresponding norm, $|\langle
c(n)\rangle|$, in log-log representation (insets). Panels ordering, symbols
and color code are as in Fig. S1. Power-law decays in the “${\rm
Pe}=0$”-insets correspond to the known [35] behaviors in dilute and melt
polymers. The “$\sim n^{-3}$”-decay for active (${\rm Pe}>0$) systems is for
guiding the eye and purely indicative.  $\begin{array}[]{c}{\rm Pe}=1\\\
\includegraphics[width=216.81pt]{R2-BCF-vs-n-scaling-Pe01.eps}\\\ \\\ \\\ {\rm
Pe}=5\\\ \includegraphics[width=216.81pt]{R2-BCF-vs-n-scaling-Pe05.eps}\\\ \\\
\\\ {\rm Pe}=10\\\ \includegraphics[width=216.81pt]{R2-BCF-vs-n-scaling-
Pe10.eps}\end{array}$ Figure S3:  Spatial structure of active polymer chains
of contour length $N$ (different colors are for different $N$’s, see legend)
and for Péclet numbers ${\rm Pe}=1,\,5,\,10$. Notation, symbols and color code
are as in Fig. 2 in the main paper.  $\begin{array}[]{c}{\rm Pe}=1\\\
\includegraphics[width=325.215pt]{g1-scaling-Pe01.eps}\\\ \\\ \\\ {\rm
Pe}=5\\\ \includegraphics[width=325.215pt]{g1-scaling-Pe05.eps}\\\ \\\ \\\
{\rm Pe}=10\\\ \includegraphics[width=325.215pt]{g1-scaling-
Pe10.eps}\end{array}$ Figure S4:  Monomer mean-square displacement, $g_{1}$,
normalized by $\langle R^{2}(n_{\rm min})\rangle$ as a function of rescaled
time $t/\tau_{\rm min}$ (lines) in comparison to normalized mean-square
internal distance, $\langle R^{2}(n)\rangle/\langle R^{2}(n_{\rm
min})\rangle$, as a function of normalized contour length separation,
$n/n_{\rm min}$ (symbols, same as in the corresponding panels of Fig. S3
here). Results are for Péclet numbers ${\rm Pe}=1,\,5,\,10$ (for ${\rm
Pe}=20$, see Fig. 3 in the main paper).  $\begin{array}[]{cc}{\rm Pe}=1&{\rm
Pe}=5\\\ \includegraphics[width=216.81pt]{g3-scaling-
Pe01.eps}&\includegraphics[width=216.81pt]{g3-scaling-Pe05.eps}\\\ \\\
\lx@intercol\hfil{\rm Pe}=10\hfil\lx@intercol\\\
<EMAIL_ADDRESS>Pe10.eps}\hfil\lx@intercol\end{array}$
Figure S5:  Mean-square displacement of the chain centre of mass per unit
time, $g_{3}(\tau)/\tau$, normalized by $\langle R_{\rm
ee}^{2}\rangle/\tau_{\rm ee}$ as a function of normalized time $\tau/\tau_{\rm
ee}$. Results for polymers in dilute ($\bigtriangleup$) and melt ($\circ$)
conditions, for different contour lengths $N$ (see legend) and for Péclet
numbers ${\rm Pe}=1,\,5,\,10$ (for ${\rm Pe}=20$, see top panel in Fig. 4 in
the main paper).  Figure S6:  Polymer mean-square end-to-end distance,
$\langle R_{\rm ee}^{2}\rangle$ (Eq. (1) in the main paper, with $n=N-1$), as
a function of the total chain contour length $N$ and Péclet number $\rm Pe$
(Eq. (S4)). Dashed lines are best fits to simple power-law behavior
$=b^{2}N^{2\nu}$ (see legends, for the results).


# Evolution of locally dependent random graphs

Joshua Brody1 Pat Devlin1 Aditi Dudeja2 Emmi Rivkin1

(1 Swarthmore College, Swarthmore, PA, United States
2 University of Salzburg, Salzburg, Austria

May 15, 2024 )

###### Abstract

In this paper we study $d$-dependent random graphs—introduced by Brody and
Sanchez [6]—which are the family of random graph distributions where each edge
is present with probability $p$, and each edge is independent of all but at
most $d$ other edges. For this random graph model, we analyze degree
sequences, jumbledness, connectivity, and subgraph containment. Our results
mirror those of the classical Erdős–Rényi random graph, which are recovered by
specializing our problem to $d=0$, although we show that in many regards our
setting is appreciably more nuanced. We survey what is known for this model
and conclude with a variety of open questions.

††footnotetext: AMS 2020 subject classification: 05C80, 05C40, 60C05, 68R10

##  1 Introduction

Since the seminal papers of Erdős and Rényi [9, 10], random graphs have been
among the most researched topics in discrete mathematics and theoretical
computer science. Random graphs have had a wide range of applications
including computer science, discrete math, statistical mechanics, and
modelling. By far the most well-studied random graph distribution is the
Erdős–Rényi model which is a random graph on $n$ vertices where each edge is
present independently with probability $p$. After decades of active research,
this distribution is now quite well understood—see texts [2, 4, 15]—and in
fact recent tools for understanding this model have become so sophisticated as
to render many low-level questions almost trivial [11, 18].

Although the Erdős–Rényi random graph is the most popular random graph
distribution in the literature, it is unable to model a number of important
settings where the edges depend on each other, and a wide variety of other
random graph models have been proposed over the years, see e.g., the textbook
[12] or the survey [7]. Of particular relevance for us is [1], where Alon and
Nussboim considered $k$-wise independent random graphs. In this model, each
edge is present with probability $p$, but the independence assumption is
loosened to say merely that any subset of $k$ edges is independent (with no
assumptions about larger sets). In that setting, Alon and Nussboim were able
to establish a number of results including a careful estimation of
eigenvalues. However, because the family of $k$-wise independent graph
distributions is relatively poorly behaved, their results were necessarily
weaker than those for the Erdős–Rényi graph.

Motivated by an application to number-on-the-forehead communication
complexity, Brody and Sanchez [6] introduced the locally dependent random
graph model, which is the focus of the current paper. In this model, a
$d$-dependent random graph $G_{n,p,d}$ is any random graph distribution on $n$
vertices where each edge appears with probability $p$, and each edge depends
on at most $d$ others.

Said more precisely, a _dependency graph_ for a set of random variables
$X_{1},\ldots,X_{n}$ is a graph $H=(V,E)$ where vertices correspond to the
random variables, and edges correspond to dependencies: each $X_{i}$ is
independent of all $X_{j}$ except those for which $(i,j)\in E$. Variables
$\\{X_{i}\\}$ are $d$-_locally dependent_ if there exists a dependency graph
for $\\{X_{i}\\}$ with maximum degree $d$. This notion of local dependence
coincides with that considered in both the well-known Lovász local lemma [8,
17] as well as Janson’s inequality [14]. A $d$-dependent random graph
$G_{n,p,d}$ is a random graph distribution on $n$ vertices, where each edge is
present with probability $p$ and the set of edges are $d$-locally dependent.

The family of $d$-dependent random graphs is a relatively new but natural
model, which in some sense interpolates between the Erdős–Rényi random graph
($d=0$) and every other distribution of random graphs
($d=\genfrac{(}{)}{0.0pt}{2}{n}{2}$), provided each edge appears with
probability $p$.

One of the particularly interesting aspects of this model is that because it
encompasses an entire family of distributions, it does not typically exhibit
thresholds for monotone properties in the simple way that the Erdős–Rényi
model does. For example, if $G$ is an Erdős–Rényi random graph, then viewing
$p$ as a function of $n$, we have that $\mathbb{P}(G\text{ is connected})$
tends to 0 if $p\ll\ln(n)/n$, and the probability tends to 1 if $p\gg\ln(n)/n$
(see [4] for this and much more precise results).

In the setting of $d$-dependent random graphs, it’s unreasonable to expect
such a simple result would be true since we are considering an entire family
of distributions simultaneously. That is to say, in our setting a typical
threshold result ought to have three regimes separated by distinct lower and
upper thresholds, $L(n,d)\leq U(n,d).$ Namely, (i) if $p\ll L(n,d)$, then all
$d$-dependent distributions are very unlikely to have the desired property;
(ii) if $p\gg U(n,d)$, then all distributions are very likely to have the
desired property; and (iii) for intermediate values of $p$, there are some
$d$-dependent distributions that are likely to have the property and others
that are not. The gap—if any—between (i) and (ii) would necessarily be some
function of $n$ and $d$ which (by a classical result of [5]) essentially
vanishes when $d=0$. One of the main results of this paper addresses these
lower and upper thresholds for connectivity. We discuss this further in our
conclusion section.

As an example of a related phenomenon, in [6] Brody and Sanchez initiated the
study of $d$-dependent random graphs, where their main result is the
following:

######  Proposition 1 (Theorems 1 and 3 of [6]).

Say $d/\sqrt{n}\ll p\leq 1/4$. There are positive constants $C_{1},C_{2}$ such
that for any $d$-dependent random graph $G\sim G_{n,p,d}$, with probability
tending to 1

$C_{1}\dfrac{\ln(n)}{\ln(1/p)}\leq\text{(clique number of $G$)}\leq
C_{2}\dfrac{(d+1)\ln(n)}{\ln(1/p)}.$

The upper bound follows simply by noting that the expected number of cliques
on $k$ vertices is at most ${n\choose k}p^{{k\choose 2}/(d+1)}$, since any
collection of $m$ edges must contain a subset of size at least $m/(d+1)$ whose
presence are independent events. Their lower bound was much more involved, and
it amounted to estimating the mean and variance of a related random variable
and applying Azuma’s inequality. Interestingly, this shows that when $d$ is
not too large (say $d\ll p\sqrt{n}$), the clique number of a $d$-dependent
random graph cannot be fundamentally lower than what it would be in the
Erdős–Rényi case. They also exhibit graphs with clique number roughly
$C\sqrt{d+1}\ln(n)/\ln(1/p)$. It is unknown if the upper bound in Proposition
1 can be attained.

The authors of [6] used the above to prove the immediate corresponding
inequalities regarding the chromatic number of $G_{n,p,d}$, which in turn gave
improved bounds for the multiparty pointer jumping problem, a canonical
problem in number-on-the-forehead communication complexity. They also noted
that very little can be said about the clique number of dependent random
graphs when $d=\Omega(n)$. For instance, if $p=1/2$, then the random bipartite
graph (where each $x$ and $y$ are in the same partition with probability
exactly $1/2$) would be a $2n$-dependent random graph which is always
bipartite. And its complement would be a $2n$-dependent random graph which is
the disjoint union of two cliques (at least one of which must have at least
$n/2$ vertices). Thus, the lower bound of Proposition 1 cannot be true for all
values of $d$.

### Our results

We now turn our attention to original results on $d$-dependent random graphs.
As this model is still relatively new, we focus on several of the most
fundamental questions in random graph theory: degree sequence, jumbledness,
connectivity, and subgraph containment.

Throughout, we say that an event happens almost surely to mean that it happens
with probability tending to 1 as the relevant parameter (typically $n$) tends
to infinity. We use $\ln$ to denote the natural (base $e$) logarithm.

Our first result is the fact that for many choices of parameters, almost
surely every vertex has degree very nearly $np$.

######  Theorem 2 (Degree concentration).

Say $G\sim G_{n,p,d}$ is any $d$-dependent random graph distribution. If
$p\geq(d+1)\dfrac{\ln(n)}{n}$, then almost surely, every vertex of $G$ has
degree between $np-4\sqrt{np(d+1)\ln(n)}$ and $np+4\sqrt{np(d+1)\ln(n)}$.

In fact, this can be generalized in a certain sense by arguing that with high
probability any $d$-dependent random graph exhibits a jumbledness property
that the number of edges between any two subsets of vertices is roughly what
it would be in the Erdős–Rényi setting. Jumbledness, first introduced by
Thomason [19], is a convenient graph property that in many ways allows such
graphs to be treated as Erdős–Rényi graphs [16].

######  Theorem 3 (Jumbledness).

Suppose $C\geq 10$, and $G\sim G_{n,p,d}$ is drawn from any $d$-dependent
random graph distribution. Further suppose that almost surely the maximum
degree of $G$ is at most $(C^{2}/14)np$—which would be implied if $p\geq
14/C^{2}$ or $p\geq(d+1)\ln(n)/n$. Then almost surely, all subsets of vertices
$A,B$ simultaneously satisfy

$\Big{|}e(A,B)-p|A||B|\Big{|}\leq C\sqrt{|A||B|np(d+1)},$

where $e(A,B)$ counts the number of edges of $G$ having one endpoint in $A$
and the other in $B$—with the usual convention that edges contained in $A\cap
B$ are counted twice.

In the language of pseudorandom graphs, the above result shows that the
$d$-dependent random graph is almost surely $(p,C\sqrt{np(d+1)})$-jumbled. The
next example shows that this is best possible up to the choice of $C$ and that
we must have $C\geq 1$.

######  Theorem 4 (Jumbledness example).

Suppose $np\to\infty$ and $d<0.99n$. Then there is a $d$-dependent random
graph distribution such that almost surely, there are sets $A$ and $B$ where

$e(A,B)-p|A||B|>(1-o(1))(1-p)\sqrt{1-d/n}\sqrt{|A||B|np(d+1)}.$

We now turn our attention to connectivity.

######  Theorem 5 (Connectivity).

Let $G\sim G_{n,p,d}$ be any $d$-dependent random graph distribution.

  * (i)

Suppose $f(n)$ is any function for which $f(n)\to\infty$. If
$p>(d+1)\dfrac{\ln(n)+f(n)}{n}$, then $G$ is almost surely connected.

  * (ii)

If $np\to 0$, then almost surely $G$ will not be connected.

As for the optimality of each of these bounds, we have:

######  Theorem 6 (Connectivity examples).

There are distributions with the following properties.

  * (i)

There is a $d$-dependent random graph distribution with the property that for
each fixed $\varepsilon>0$, if
$p<(1-\varepsilon)(d+1)\dfrac{\ln(n/\sqrt{d+1})}{n}$ and $d\ln(n)/n\to 0$, the
graph is almost surely not connected.

  * (ii)

There is a $d$-dependent random graph distribution (namely, the Erdős–Rényi
graph) such that for any function $f(n)\to\infty$, if
$p>\dfrac{\ln(n)+f(n)}{n}$, then the graph is almost surely connected.

Thus, item (i) of Theorem 5 is nearly best possible up to a factor of
$1/\sqrt{d+1}$ appearing in the logarithm. In fact, if $d\leq n$, then the
bounds given in item (i) of the above theorems differ by at most a
multiplicative factor of 2. As for the lower threshold, there is a gap where
it is uncertain whether or not there are any almost surely connected
$d$-dependent random graphs with $1/n\leq p\leq\ln(n)/n$. We feel that closing
this gap would be of particular interest. We discuss this general phenomenon
and related open problems in the conclusion.

Finally, we conclude with a generalization of a result of Bollobás [3]
addressing thresholds for when a $d$-dependent random graph is likely to
contain small subgraphs.

######  Theorem 7 (Subgraph containment).

Suppose $H=H_{n}$ is any sequence of graphs. For each graph $\Gamma$, let
$V(\Gamma)$ denote its vertex set, $E(\Gamma)$ its edge set, and let
$f(\Gamma)$ denote its edge cover number, i.e., the minimum number of edges in
a set $A\subseteq\Gamma$ such that every edge of $\Gamma$ shares an endpoint
with some edge of $A$. Define the quantity

$\Phi(H):=\displaystyle\sum_{\emptyset\neq\Gamma\subseteq
H}\left(\dfrac{20|V(H)|}{n}\right)^{|V(\Gamma)|}\dfrac{(d+1)^{f(\Gamma)}}{p^{|E(\Gamma)|}},$

where the sum is taken over non-empty subgraphs of $H$. Finally suppose
$d|E(H)||V(H)|/n<0.9$.

For any $d$-dependent graph distribution $G\sim G_{n,p,d}$, the probability
that $G$ contains no copies of $H$ is at most $10\Phi(H)$. In particular,
define $m(H)=\max_{\emptyset\neq\Gamma\subseteq H}|E(\Gamma)|/|V(\Gamma)|$. If
$H$ is fixed and $p(n/(d+1))^{1/m(H)}\to\infty$, then $G$ almost surely
contains a copy of $H$.

Note that if $d=0$, this recovers the result of Bollobás for the Erdős–Rényi
random graph. In that setting (when $H$ is fixed) the Erdős–Rényi random graph
almost surely has no copies of $H$ when $pn^{1/m(H)}\to 0$. As an example in
our model, when $H=K_{3}$ is a triangle, we have

$\Phi(K_{3})=C\left(\dfrac{(d+1)^{1}}{n^{2}p}+\dfrac{(d+1)^{2}}{n^{3}p^{2}}+\dfrac{(d+1)^{2}}{n^{3}p^{3}}\right).$

Thus, if $p\gg(d+1)^{2/3}/n$, then any $d$-dependent random graph will almost
surely contain a triangle.

### Outline of paper

We begin in Section 2 with common notation used throughout. Continuing in
Section 3, we provide several examples of $d$-dependent graph distributions
including a proof of Theorems 4 and 6. Next, in Section 4 we prove Theorems 2
and 3. Section 5 is devoted to a proof of Theorem 5, and we prove Theorem 7 in
Section 6. Finally, we list a variety of open questions and conjectures in the
conclusion.

##  2 Common notation and useful facts

Throughout, we use $\ln(x)$ to denote the natural log of $x$. We say an event
happens almost surely to mean that it happens with probability tending to 1 as
the relevant parameter (typically $n$) tends to infinity. Following notation
of Janson’s inequality [14], we let $d_{1}$ denote $d+1$.

As a common approximation, we use the fact that for all $x$ we have $1+x\leq
e^{x}$ and moreover if $-1/2\leq x$ we have $e^{-2x}\leq e^{x-x^{2}}\leq 1+x$.
Combining these, we have that if $x\to 0$, then $1+x=e^{x(1+o(1))}$. Moreover,
for any integers $1\leq k\leq m$, we use the fact $(m/k)^{k}\leq{m\choose
k}\leq(em/k)^{k}$ (for details on all of these, see, e.g., the first chapter
of [4]).

Let us now recall the following versions of Janson’s inequality [14]
specialized for our situation.

######  Lemma 8 (Janson).

Let $G$ be any $d$-dependent random graph, and let $A,B$ be any subsets of
vertices. Define $e(A,B)$ to be the number of edges of $G$ between $A$ and
$B$, with the usual convention that edges inside $A\cap B$ are counted twice.
Define $\mu=\mathbb{E}[e(A,B)]=|A||B|p$. For all $t>0$ we have

$\displaystyle\mathbb{P}\left(\Big{|}e(A,B)-\mu\Big{|}\geq t\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left[\dfrac{-8t^{2}}{50d_{1}(\mu+t/3)}\right],$ (1)
$\displaystyle\mathbb{P}\left(\Big{|}e(A,B)-\mu\Big{|}\geq t\right)$
$\displaystyle\leq$ $\displaystyle
2\exp\left[\dfrac{-\mu}{2d_{1}}\varphi\left(\dfrac{4t}{5\mu}\right)\right],$
(2)

where $\varphi(x)=(1+x)\ln(1+x)-x$.

###### Proof.

These inequalities are a direct application of Theorem 2.3 of [14] in the
following way. We may treat $e(A,B)$ as a sum of $|A||B|$ indicator random
variables (with edges inside $A\cap B$ appearing twice in this sum), where
each random variable has mean $p$ and each random variable depends on fewer
than $2d_{1}$ terms in the summation [multiplying by 2 to account for the fact
that some edges may have been duplicated in this sum]. ∎

##  3 Examples of $d$-dependent random graphs

Here we provide examples of two different $d$-dependent random graph
distributions and use them to prove Theorems 4 and 6. In each case, for
convenience we assume that all large numbers are integers (since the errors
associated with rounding do not change the validity of our results).

### Proof of Theorem 4: jumbledness example

###### Proof.

Partition the vertex set $V$ into sets $V=S\cup T$ where $|S|=d_{1}$. For each
$x\in T$, we fully correlate all the edges from $x$ to $S$. That is, $x$ is
adjacent to all of $S$ with probability $p$ and otherwise it is adjacent to
none of the vertices of $S$. All other edges of this graph are independent.

The key is that every vertex of $S$ has the exact same set of neighbors in
$T$. Let $B\subseteq T$ denote the vertices of $T$ that are adjacent to at
least one (and hence every) vertex of $S$. Then $|B|$ is a binomial random
variable with mean $|T|p$ and variance $|T|p(1-p)$. Applying Chebyshev’s
inequality

$\displaystyle\mathbb{P}\Big{(}|B|\leq|T|p(1-(np)^{-1/4})\Big{)}$
$\displaystyle=$
$\displaystyle\mathbb{P}\Big{(}|B|-\mathbb{E}[|B|]<-|T|p(np)^{-1/4}\Big{)}\leq\dfrac{\text{Var}(|B|)}{\Big{(}|T|p(np)^{-1/4}\Big{)}^{2}}$
$\displaystyle=$
$\displaystyle\dfrac{|T|p(1-p)}{(|T|p)^{2}/\sqrt{np}}\leq\dfrac{\sqrt{np}}{|T|p}=\dfrac{1}{(1-d_{1}/n)\sqrt{np}}\to
0.$

Thus, almost surely $|B|\geq np(1-d_{1}/n)(1-o(1))$, and as a result

$\displaystyle e(S,B)-|S||B|p$ $\displaystyle=$
$\displaystyle(1-p)|S||B|=(1-p)\sqrt{|S||B|\cdot(|S||B|)}$ $\displaystyle\geq$
$\displaystyle(1-o(1))(1-p)\sqrt{1-d/n}\sqrt{|S||B|npd_{1}},$

as we were trying to show. ∎

### Proof of Theorem 6: non-connected example

###### Proof.

Claim (ii) is a well-known result in random graphs—which also follows
immediately from Theorem 5. Here we prove claim (i) of Theorem 6. For this,
suppose $\varepsilon>0$ is fixed,
$p\leq(1-\varepsilon)\dfrac{d_{1}\ln(n/\sqrt{d_{1}})}{n}$, and
$d_{1}\ln(n)/n\to 0$, which in turn implies that $p\to 0$ as well. We will
prove that there is a $d$-dependent distribution which is almost surely not
connected.

Partition the vertex set $V$ as $V=A\cup B$ where
$|A|=\dfrac{n}{\ln(n)\sqrt{d_{1}}}$. And partition $B$ into $m\leq n/d_{1}$
sets $B_{1},B_{2},\ldots,B_{m}$ each of size $d_{1}$. For each $x\in A$ and
each $1\leq j\leq m$, we fully correlate all the edges from $x$ to $B_{j}$,
which is to say $x$ is adjacent to the entirety of $B_{j}$ with probability
$p$ (and otherwise, there are no edges between $x$ and $B_{j}$).

Now we also partition $A$ into $t=|A|/\sqrt{d_{1}}=\dfrac{n}{\ln(n)d_{1}}$
sets $A_{1},A_{2},\ldots,A_{t}$ each of size $\sqrt{d_{1}}$. For each $1\leq
i\leq j\leq t$, fully correlate all the edges between $A_{i}$ and $A_{j}$ (in
the case $i=j$, this means each $A_{i}$ is either a complete graph or an empty
graph).

Let $S\subseteq A$ denote the set of vertices in $A$ that have no edges to any
other vertices of $A$.

Claim: With high probability $|S|\geq|A|\varepsilon/2$.

Proof of this claim: For each $1\leq i\leq j\leq t$, say the ordered pair
$(i,j)$ is on iff our random graph has edges between $A_{i}$ and $A_{j}$. Each
pair is ‘on’ with probability precisely $p$, and these events are independent.
Moreover, there are precisely ${t\choose 2}+t={t+1\choose 2}$ pairs $(i,j)$
where $1\leq i\leq j\leq t$. Thus, the total number of ‘on’ pairs is a
binomial random variable with mean $p{t+1\choose 2}<(1-\varepsilon)(t+1)/2$
and variance $p(1-p){t+1\choose 2}$. So the chance that the number of ‘on’
pairs is greater than $t(1-\varepsilon/2)/2$ is at most (by Chebyshev’s
inequality) $C\varepsilon/(p{t+1\choose 2})$. And by Markov’s inequality, this
probability is also at most $C\varepsilon p{t+1\choose 2}/t$. The geometric
mean of these upper bounds is $C\varepsilon/\sqrt{t}$, and since $t\to\infty$,
at least one of these upper bounds must tend to 0. So, almost surely, there
are at most $t(1-\varepsilon/2)/2$ ‘on’ pairs, meaning there are at least
$t\varepsilon/2$ choices of $k$ where the set $A_{k}$ has no edges inside $A$.
Thus, $|S|\geq(t\varepsilon/2)\sqrt{d_{1}}=|A|\varepsilon/2$, proving the
claim.

Now for each $x\in S$, we would have that $x$ is isolated in the graph iff
there are no edges from $x$ to $B$. Then after conditioning on $S$, each
vertex of $S$ is isolated with probability exactly $(1-p)^{m}$, and these
events are independent. Because $p\to 0$, we know $(1-p)=\exp(-p(1+o(1)))$.
Thus, if $I$ denotes the total number of isolated vertices in $S$, then $I$ is
a binomial random variable with mean

$\displaystyle\mathbb{E}[I]$ $\displaystyle=$
$\displaystyle|S|(1-p)^{m}=\exp[\ln|S|-(1+o(1))pm]\geq\exp[\ln(|A|\varepsilon/2)-(1+o(1))pn/d_{1}]$
$\displaystyle\geq$
$\displaystyle\exp[\ln(n\varepsilon/(2\ln(n)\sqrt{d_{1}}))-(1+o(1))(1-\varepsilon)\ln(n/\sqrt{d_{1}})]$
$\displaystyle\geq$
$\displaystyle\dfrac{\varepsilon(n/\sqrt{d_{1}})^{\varepsilon-o(1)}}{2\ln(n)}\to\infty.$

Thus, by Chebyshev’s inequality, we have

$\mathbb{P}(I=0)\leq\dfrac{\text{Var}(I)}{(\mathbb{E}[I])^{2}}=\dfrac{(1-(1-p)^{m})}{\mathbb{E}[I]}\leq\dfrac{1}{\mathbb{E}[I]}\to
0.$

So this graph almost surely has an isolated vertex, meaning it is not
connected. ∎

##  4 Proofs of degree concentration and jumbledness

### Proof of Theorem 2: degree concentration

###### Proof.

Suppose $t=4\sqrt{d_{1}np\ln(n)}$. For each vertex $u$, consider $A=\\{u\\}$
and $B=V(G)\setminus\\{u\\}$. The degree of $u$ is thus equal to $e(A,B)$, and
we have

$\mathbb{P}\Big{(}|e(A,B)-np|\geq
t\Big{)}\leq\mathbb{P}\Big{(}|e(A,B)-(n-1)p|\geq t-p\Big{)}.$

By our choice of $t$—and the assumption that $p>d_{1}\ln(n)/n$—we see that
$t>4d_{1}\ln(n)\geq 4\ln(n)$, which means that for all sufficiently large
values of $n$, we have $t-p>t-1>3.9\sqrt{d_{1}np\ln(n)}$. Moreover, we have
$t-p<t\leq 4np$. Applying Janson’s inequality—our Lemma 8, (1)—yields

$\displaystyle\mathbb{P}\Big{(}|e(A,B)-np|\geq t\Big{)}$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\Big{(}|e(A,B)-(n-1)p|\geq
3.9\sqrt{d_{1}np\ln(n)}\Big{)}$ $\displaystyle\leq$ $\displaystyle
2\exp\left(\dfrac{-(8/50)(3.9)^{2}d_{1}np\ln(n)}{d_{1}((n-1)p+t/3)}\right)\leq
2\exp\left(\dfrac{-(8/50)(3.9)^{2}\ln(n)}{1+4/3}\right)$ $\displaystyle\leq$
$\displaystyle 2n^{-1.04}.$

Summing over the $n$ choices for the vertex $u$, we see that the expected
number of vertices whose degree is not in the desired range is at most
$2n^{-0.04}$, which tends to $0$. Thus, the probability that there is such a
vertex also tends to $0$. ∎

### Proof of Theorem 3: jumbledness

Our proof is similar to a typical proof for the Erdős–Rényi graph (e.g., Lemma
8 of [13]), with the main exception being that we rely on Janson’s inequality
in lieu of a standard Chernoff bound.

###### Proof.

For each pair of sets $(A,B)$, let us first establish some notation used
throughout. Say $|A|=a$, $|B|=b$, and define $\mu:=abp$ and
$t:=C\sqrt{abnpd_{1}}$, where $C\geq 10$.

Say a pair of sets $(A,B)$ is bad iff $\Big{|}e(A,B)-abp\Big{|}\geq t$. We
need only argue that with high probability, there are no bad sets satisfying
$1\leq a\leq b\leq n$. For ease of presentation, we define the following
families of sets:

  * •

$\mathcal{F}=\\{(A,B)\ :\ 1\leq a\leq b\ \ \ A,B\subseteq V\\}$,

  * •

$\mathcal{F}_{0}=\left\\{(A,B)\in\mathcal{F}\ :\
t>\dfrac{C^{2}}{14}anp\right\\}$,

  * •

$\mathcal{F}_{1}=\left\\{(A,B)\in\mathcal{F}\ :\
t<12\mu\dfrac{n/b}{\ln(en/b)}\right\\}$,

  * •

$\mathcal{F}_{2}=\mathcal{F}\setminus(\mathcal{F}_{0}\cup\mathcal{F}_{1})=\left\\{(A,B)\in\mathcal{F}\
:\ 12\mu\dfrac{n/b}{\ln(en/b)}\leq t\leq anp\dfrac{C^{2}}{14}\right\\}$.

We argue that the expected number of bad sets in each of these families is
$o(1).$

#### Case 0, $\mathcal{F}_{0}$:

First suppose $(A,B)\in\mathcal{F}_{0}$. This means we may assume
$t>\dfrac{C^{2}}{14}anp$. But by assumption, we know that with high
probability, every vertex of $G$ has degree at most $(C^{2}/14)np$. Therefore,
$e(A,B)\leq a(C^{2}/14)np<t$. And since $abp\leq anp\leq(C^{2}/14)anp<t$, this
means $|e(A,B)-abp|\leq\max\\{e(A,B),abp\\}<t.$ So because of the maximum
degree condition, there are no bad sets in $\mathcal{F}_{0}$.

#### Case 1, $\mathcal{F}_{1}$:

Now suppose $(A,B)\in\mathcal{F}_{1}$. This means we may assume $t\leq
12\mu\dfrac{n/b}{\ln(en/b)}$. And we can say that
$\mu+t/3\leq\left(1+\dfrac{12}{3}\cdot\dfrac{n/b}{\ln(en/b)}\right)\mu\leq\left(5\cdot\dfrac{n/b}{\ln(en/b)}\right)\mu$.
So by using (1), we have

$\mathbb{P}(\text{$(A,B)$ is bad})\leq
2\exp\left[\dfrac{-8t^{2}}{50d_{1}(\mu+t/3)}\right]\leq
2\exp\left[\dfrac{-8t^{2}b\ln(en/b)}{250d_{1}n\mu}\right].$

For each $1\leq b$, there are at most $\sum_{a=1}^{b}{n\choose a}{n\choose
b}\leq\sum_{a=1}^{b}(en/a)^{a}(en/b)^{b}\leq b(en/b)^{2b}\leq(en/b)^{3b}$
pairs of sets $(A,B)\in\mathcal{F}$ with $|B|=b$. Thus, for all
$(A,B)\in\mathcal{F}_{1}$, the expected number of bad sets is at most

$\displaystyle
2\sum_{b=1}^{n}\exp[3b\ln(en/b)]\exp\left[\dfrac{-8t^{2}b\ln(en/b)}{250d_{1}n\mu}\right]$
$\displaystyle=$ $\displaystyle
2\sum_{b=1}^{n}\exp\left[b\ln(en/b)\left(3-\dfrac{8C^{2}}{250}\right)\right]$
$\displaystyle\leq$ $\displaystyle
2\sum_{b=1}^{n}\exp\left[-b\ln(en/b)/5\right],$

where the last inequality is justified by the fact that $C\geq 10$. Since the
value of this summation tends to $0$, this shows that the expected number of
bad sets in $\mathcal{F}_{1}$ goes to 0.

#### Case 2, $\mathcal{F}_{2}$:

For all $(A,B)\in\mathcal{F}_{2}$ we know $t/\mu\geq
12\dfrac{n/b}{\ln(en/b)}$, meaning
$\ln(t/\mu)\geq\ln(ne/b)+\ln(12/e)-\ln(\ln(en/b))$. Moreover, for all $1\leq
x$ we have $\ln(12/e)-\ln(\ln(ex))>-\ln(ex)/10$, which means $\ln(t/\mu)\geq
0.9\ln(ne/b)$. Since for all $y>0$, we have
$\phi(y)=(1+y)\ln(1+y)-y\geq(5y/8)\ln(5y/4)$, this yields

$\phi\left(\dfrac{4t}{5\mu}\right)\geq\dfrac{1}{2}\dfrac{t}{\mu}\ln(t/\mu)\geq\dfrac{t}{\mu}\cdot\dfrac{(0.9)\ln(en/b)}{2}=(0.45)\dfrac{t\ln(en/b)}{\mu}.$

Therefore, for all $(A,B)\in\mathcal{F}_{2}$, by applying (2) we have

$\displaystyle\mathbb{P}(\text{$(A,B)$ is bad})$ $\displaystyle\leq$
$\displaystyle
2\exp\left[\dfrac{-\mu}{2d_{1}}\varphi\left(\dfrac{4t}{5\mu}\right)\right]\leq
2\exp\left[\dfrac{-(0.225)\mu}{d_{1}}\dfrac{t}{\mu}\ln(en/b)\right]$
$\displaystyle=$ $\displaystyle
2\exp\left[-(0.225)Cb\ln(en/b)\sqrt{\dfrac{apn}{d_{1}b}}\right]\leq
2\exp\left[-3.15\cdot b\ln(en/b)\right],$

where the last inequality follows from the fact that $t\leq
anp\dfrac{C^{2}}{14}$, which means
$\dfrac{14}{C}\leq\sqrt{\dfrac{anp}{d_{1}b}}$.

As before, for each value $b$, there are at most $\exp[3b\ln(ne/b)]$ pairs
$(A,B)\in\mathcal{F}_{2}$. And thus, the expected number of bad pairs
$(A,B)\in\mathcal{F}_{2}$ is at most

$2\sum_{b=1}^{n}\exp[3b\ln(en/b)]\exp\left[-3.15\cdot
b\ln(en/b)\right]=2\sum_{b=1}^{n}\exp[-(0.15)b\ln(en/b)]=o(1).$

Therefore, since the expected number of bad pairs in
$\mathcal{F}_{0},\mathcal{F}_{1},$ and $\mathcal{F}_{2}$ each tends to $0$,
this means that the probability that there exists a bad pair also tends to
$0$. ∎

##  5 Proof of Theorem 5: connectivity

###### Proof.

First we note that claim (ii) of Theorem 5 is rather immediate. Namely, a
connected graph must have at least $n-1$ edges, but by Markov’s inequality,
$\mathbb{P}[|E(G)|\geq n-1]\leq\dfrac{\mathbb{E}[|E(G)|]}{n-1}=np/2,$ which
tends to 0 by assumption.

We now turn our attention to claim (i), whose proof is almost identical to
that of the standard Erdős–Rényi graph. For this, call a set $A\subseteq V$
bad iff $1\leq|A|\leq n/2$ and $e(A,V\setminus A)=0$. In order for
$e(A,V\setminus A)$ to be 0, all of the $|A|(n-|A|)$ edges leaving $A$ must be
absent. But among these, there must be at least $|A|(n-|A|)/d_{1}$ which are
independent. Therefore we have

$\displaystyle\mathbb{E}[\text{\\# bad sets}]$ $\displaystyle=$
$\displaystyle\sum_{A\subseteq V}\mathbb{P}(A\text{ is
bad})=\sum_{a=1}^{n/2}{n\choose a}(1-p)^{a(n-a)/d_{1}}$ $\displaystyle\leq$
$\displaystyle\sum_{a=1}^{n/2}\exp\left[a\ln(en/a)-p\dfrac{a(n-a)}{d_{1}}\right]\leq\sum_{a=1}^{n/2}\left(\exp\left[C\left(2-f(n)\right)\right]\right)^{a},$

which tends to $0$ since $f(n)\to\infty$. Thus there are almost surely no bad
sets, and $G$ is connected. ∎

##  6 Proof of Theorem 7: subgraph containment

###### Proof.

Following aspects of the approach of [6], we restrict our attention to the
presence of subgraphs whose edge sets are suitably uncorrelated. For this, we
need to define an appropriate notion allowing us to deal with the possible
dependence of edges. Since $G$ is a $d$-dependent random graph, this means
that for each edge $e$, there is some set $S(e)$ of size at most $d$ such that
the presence of $e$ is independent of the set of edges outside of
$S(e)\cup\\{e\\}$. With this, we say $e_{1}$ relies on $e_{2}$ iff $e_{1}\in
S(e_{2})$ or $e_{1}=e_{2}$. We write this as $e_{1}\rightsquigarrow e_{2}$

Let $\mathcal{H}$ denote the set of all copies of $H$ appearing in the
complete graph on $n$ vertices. For each $S\in\mathcal{H}$, we say $S$ is
internally uncorrelated iff none of the edges within $S$ rely on any of the
others. Let $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ denote the set of
internally uncorrelated graphs $S$ (i.e., the internally uncorrelated copies
of $H$ in the complete graph on $n$ vertices).

If we select an element $S\in\mathcal{H}$ uniformly at random, then the
expected number of pairs of edges $(e_{1},e_{2})$ in $S$ where $e_{1}\neq
e_{2}$ and $e_{1}\rightsquigarrow e_{2}$ is at most

$\sum_{e_{1}}\sum_{e_{1}\rightsquigarrow
e_{2}}\mathbb{P}\Big{(}\\{e_{1},e_{2}\\}\subseteq E(S)\Big{)}\leq
d|E(H)|\cdot\max_{e,f}\mathbb{P}(f\in E(S)|e\in E(S))\leq
d|E(H)|\dfrac{|V(H)|}{n},$

where the last inequality is because the event $f\in E(S)$ conditioned on
$e\in E(S)$ involves the inclusion of at least one more vertex in $S$, and
inclusion of vertices in $S$ is negatively correlated.

Therefore, we have that the number of internally uncorrelated elements of
$\mathcal{H}$ is at least

$|\mathcal{H}^{\prime}|\geq|\mathcal{H}|\left(1-\dfrac{d|E(H)||V(H)|}{n}\right)\geq|\mathcal{H}|/10,$

which is also essentially Lemma 11 of [6].

For each $S\in\mathcal{H}^{\prime}$, let $X_{S}$ denote the indicator random
variable for the event that all the edges of $S$ are present in the
$d$-dependent random graph $G$, and let
$X=\sum_{S\in\mathcal{H}^{\prime}}X_{S}$. By construction of
$\mathcal{H}^{\prime}$, for each $S\in\mathcal{H}^{\prime}$, we have
$\mathbb{E}[X_{S}]=p^{|E(H)|}$, so
$\mathbb{E}[X]=|\mathcal{H}^{\prime}|p^{|E(H)|}$.

Deviating from the approach in [6], we now directly turn our attention to
estimating the mean and variance of $X$. Suppose $S\in\mathcal{H}^{\prime}$ is
fixed. For each subset of edges $\Gamma\subseteq S$, let
$\mathcal{B}_{\Gamma}$ denote the collection of graphs
$T\in\mathcal{H}^{\prime}$ such that the edges of $T$ can be partitioned as
$T_{0}\cup T_{1}$ where (1) $T_{0}$ is isomorphic to $\Gamma$, (2) each edge
of $T_{0}$ relies on at least one edge of $S$, and (3) the edges of $T_{1}$ do
not rely on any of the edges of $S$.

For each $\Gamma\subseteq S$, we can bound $|\mathcal{B}_{\Gamma}|$ as
follows. Let $f(\Gamma)$ denote the minimum number of edges in a subgraph of
$\Gamma$ spanning the same vertex set (i.e., the edge cover number of
$\Gamma$). Then $T_{0}$ can be chosen in at most $(2(d+1))^{f(\Gamma)}$
ways—because each edge in the minimal edge cover must be selected from a set
of the form $\\{e\\}\cup M(e)$, and we can decide which vertex corresponds
which end point in at most 2 ways. Having done so, we could then specify
$T_{1}$ by selecting the set of the remaining vertices in $V(T)\setminus
V(T_{0})$ and then selecting the edges in one of at most
$|V(H)|!/|\text{Aut}(H)|$ ways. Thus we have

$\displaystyle|\mathcal{B}_{\Gamma}|$ $\displaystyle\leq$
$\displaystyle(2(d+1))^{f(\Gamma)}\cdot{n\choose{|V(H)|-|V(\Gamma)|}}\cdot\dfrac{|V(H)|!}{|\text{Aut}(H)|}$
$\displaystyle=$
$\displaystyle(2(d+1))^{f(\Gamma)}\cdot\dfrac{{n\choose{|V(H)|-|V(\Gamma)|}}}{{n\choose|V(H)|}}\cdot|\mathcal{H}|\leq(2(d+1))^{f(\Gamma)}n^{-|V(\Gamma)|}\cdot\left(\dfrac{|V(H)|}{1-|V(H)|/n}\right)^{|V(\Gamma)|}\cdot|\mathcal{H}|$
$\displaystyle\leq$
$\displaystyle(2(d+1))^{f(\Gamma)}n^{-|V(\Gamma)|}\cdot\left(10|V(H)|\right)^{|V(\Gamma)|}\cdot|\mathcal{H}|,$

where the last line is justified by the assumption $|V(H)|/n<0.9$.

Finally, suppose $T\in\mathcal{B}_{\Gamma}$. If $E(\Gamma)=\emptyset$, then
$\text{Cov}(X_{S},X_{T})=0$ since the edges in $T$ would not rely on any edges
of $S$. Otherwise, we have

$\displaystyle\text{Cov}(X_{S},X_{T})$ $\displaystyle\leq$
$\displaystyle\mathbb{E}[X_{S}X_{T}]\leq p^{|E(S)|}\mathbb{E}[X_{T}|X_{S}=1]$
$\displaystyle\leq$ $\displaystyle
p^{|E(S)|}p^{|E(T)|-|E(T_{0})|}=p^{2|E(H)|-|E(\Gamma)|}.$

Thus, for $X=\sum_{S\in\mathcal{H}^{\prime}}X_{S}$, we have

$\displaystyle\text{Var}(X)$ $\displaystyle=$
$\displaystyle\sum_{S,T\in\mathcal{H}^{\prime}}\text{Cov}(X_{S},X_{T})\leq\sum_{S\in\mathcal{H}^{\prime}}\sum_{\emptyset\neq\Gamma\subseteq
E(H)}|\mathcal{B}_{\Gamma}|\cdot p^{2|E(H)|-|E(\Gamma)|}$ $\displaystyle\leq$
$\displaystyle\sum_{S\in\mathcal{H}^{\prime}}\sum_{\emptyset\neq\Gamma\subseteq
E(H)}(2(d+1))^{f(\Gamma)}n^{-|V(\Gamma)|}\cdot\left(10|V(H)|\right)^{|V(\Gamma)|}\cdot|\mathcal{H}|\cdot
p^{2|E(H)|-|E(\Gamma)|}$ $\displaystyle=$
$\displaystyle\left(|\mathcal{H}^{\prime}|p^{|E(H)|}\right)^{2}\dfrac{|\mathcal{H}|}{|\mathcal{H}^{\prime}|}\sum_{\emptyset\neq\Gamma\subseteq
E(H)}\left(\dfrac{10|V(H)|}{n}\right)^{|V(\Gamma)|}\dfrac{(2(d+1))^{f(\Gamma)}}{p^{|E(\Gamma)|}}.$

Since $\mathbb{E}[X]=|\mathcal{H}^{\prime}|p^{|E(H)|}$ and
$|\mathcal{H}^{\prime}|\geq(0.1)|\mathcal{H}|$, we have by Chebyshev’s
inequality

$\mathbb{P}(X=0)\leq\dfrac{\text{Var}(X)}{(\mathbb{E}[X])^{2}}\leq
10\sum_{\emptyset\neq\Gamma\subseteq
E(H)}\left(\dfrac{20|V(H)|}{n}\right)^{|V(\Gamma)|}\dfrac{(d+1)^{f(\Gamma)}}{p^{|E(\Gamma)|}}.\qed$

##  7 Conclusion and Open Questions

In this paper we study random graph properties when edges have limited local
dependence. In particular, we examine jumbledness, connectivity, and subgraph
containment for $d$-dependent random graphs. Many interesting open problems
remain. We highlight a few below.

As discussed in the introduction, tight threshold functions cannot exist as in
the Erdős-Rényi case [5]. Instead, we believe the following more nuanced
phenomenon should hold.

######  Conjecture 9 (Existence of threshold functions).

For every monotone graph property $\mathcal{P}$ and all $d=O(n/\ln(n))$, there
exist functions $L(n,d)$ and $U(n,d)$ such that the following hold:

  1. (i)

If $p\ll L(n,d)$ then for all $d$-dependent random graph distributions $G\sim
G_{n,p,d}$, $G$ almost surely does not have property $\mathcal{P}$.

  2. (ii)

If $p\gg U(n,d)$ then for all $d$-dependent random graph distributions $G\sim
G_{n,p,d}$, $G$ almost surely has property $\mathcal{P}$.

  3. (iii)

If $L(n,d)\ll p\ll U(n,d)$, then there exists a $d$-dependent random graph
distribution $H_{1}$ and a $d$-dependent random graph distribution $H_{2}$
such that $H_{1}$ almost surely has property $\mathcal{P}$ and $H_{2}$ almost
surely does not have property $\mathcal{P}$.

Moreover, we expect the difference between the lower and upper thresholds will
be bounded by a function depending only on $d$.

######  Conjecture 10.

For all monotone graph properties $\mathcal{P}$, there exists a function
$f(d)$ depending only on $d$ such that $U(n,d)/L(n,d)=O(f(d))$.

One way to interpret our results on connectivity is that introducing local
edge dependencies allows us to correlate edges in such a way that a random
graph remains unconnected even with higher $p$, up to $p=O(d\ln(n)/n)$. We
don’t know if it is possible to _anticorrelate_ edges such that a graph almost
surely is connected for smaller $p$. We conjecture this is not possible:

######  Conjecture 11.

For all $d=O(n/\ln(n))$ and all $p\ll\ln(n)/n$, and for any $d$-dependent
random graph distribution $G\sim G_{n,p,d}$, $G$ is almost surely not
connected.

Couched in the language of threshold functions described above, Conjecture 11
states that for the connectivity property, we have $L(n,d)=\Omega(\ln(n)/n)$.
This is the highest possible value of $L(n,d)$ since the Erdős-Rényi random
graph distribution is almost surely connected when $p\gg\ln(n)/n$.

Brody and Sanchez [6] showed a similar phenomenon holds for clique number—it’s
possible to _correlate_ edges to drive up the clique number of a dependent
random graph, but it is not possible to _anti-correlate_ edges to make the
clique number much smaller than it would be for the Erdős-Rényi random graph.
One possible reason for this phenomenon is because having a large clique is in
a sense a local property of a graph, whereas _not_ having a large clique is a
more global property. We conjecture that this phenomenon is quite general—for
global graph properties, $d$-dependent random graphs behave similarly to
Erdős-Rényi random graph distributions, whereas for local graph properties,
introducing local dependencies can change the behavior of the graph.

It would be interesting to find similar threshold functions for subgraph
containment.

######  Problem 12.

For each fixed $H$, find a lower threshold function $L_{H}(n,d)$ with the
property that for any $G\sim G_{n,p,d}$, if $p\ll L(n,d)$, then almost surely
$G$ will not contain any copies of $H$.

Addressing this even in the special case that $H$ is a triangle would likely
be quite interesting.

Finally, for large $d$, we remark that we naturally lose all control over
what’s going on. For instance, say there are integers $a,m\leq d$ where $pm=a$
and $m$ divides ${n\choose 2}$. Then we can find a $d$-dependent random graph
where the number of edges is always equal to exactly $p{n\choose 2}$. Namely,
partition the ${n\choose 2}$ edges into blocks of size $m$ and uniformly
select $a$ edges from each block. We suspect that in order to be able to make
meaningful statements about $d$-dependent random graphs, we need $pd\leq 1$
and $d\leq n/\log(n)$, but we are unsure how to frame this as a precise
conjecture.

## References

  * [1] N. Alon and A. Nussboim, K-wise independent random graphs, in 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2008, pp. 813–822.
  * [2] N. Alon and J. Spencer, The probabilistic method, John Wiley & Sons, 2016.
  * [3] B. Bollobás, Threshold functions for small subgraphs, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 90, Cambridge University Press, 1981, pp. 197–206.
  * [4] , Random Graphs, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2 ed., 2001\.
  * [5] B. Bollobás and A. G. Thomason, Threshold functions, Combinatorica, 7 (1987), pp. 35–38.
  * [6] J. Brody and M. Sanchez, Dependent random graphs and multi-party pointer jumping, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM 2015), 2015.
  * [7] M. Drobyshevskiy and D. Turdakov, Random graph modeling: A survey of the concepts, ACM computing surveys (CSUR), 52 (2019), pp. 1–36.
  * [8] P. Erdős and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and finite sets, 10 (1975), pp. 609–627.
  * [9] P. Erdős and A. Rényi, On random graphs I, Publ. Math. Debrecen, 6 (1959), p. 18.
  * [10] , On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci, 5 (1960), pp. 17–60.
  * [11] K. Frankston, J. Kahn, B. Narayanan, and J. Park, Thresholds versus fractional expectation-thresholds, Annals of Mathematics, 194 (2021), pp. 475–495.
  * [12] A. Frieze and M. Karoński, Introduction to random graphs, Cambridge University Press, 2016.
  * [13] P. E. Haxell, Y. Kohayakawa, and T. Łuczak, The induced size-ramsey number of cycles, Combinatorics, Probability and Computing, 4 (1995), p. 217–239.
  * [14] S. Janson, Large deviations for sums of partly dependent random variables, Random Structures & Algorithms, 24 (2004), pp. 234–248.
  * [15] S. Janson, T. Łuczak, and A. Rucinski, Random graphs, John Wiley & Sons, 2011.
  * [16] M. Krivelevich and B. Sudakov, Pseudo-random graphs, in More sets, graphs and numbers: A Salute to Vera Sós and András Hajnal, Springer, 2006, pp. 199–262.
  * [17] R. A. Moser and G. Tardos, A constructive proof of the general Lovász local lemma, J. ACM, 57 (2010).
  * [18] J. Park and H. Pham, A proof of the Kahn–Kalai conjecture, Journal of the American Mathematical Society, 37 (2024), pp. 235–243.
  * [19] A. Thomason, Pseudo-random graphs, in North-Holland Mathematics Studies, vol. 144, Elsevier, 1987, pp. 307–331.