# Constructing multi-level urban clusters based on population distributions
and interactions

Wenpu Cao  Institute of Remote Sensing and Geographic Information Systems,
School of Earth and Space Sciences, Peking University, Beijing 100871, China
Lei Dong  Corresponding author<EMAIL_ADDRESS>Institute of Remote Sensing
and Geographic Information Systems, School of Earth and Space Sciences, Peking
University, Beijing 100871, China  Ying Cheng  State Key Laboratory of Media
Convergence Production Technology and Systems, Beijing, China  Lun Wu
Institute of Remote Sensing and Geographic Information Systems, School of
Earth and Space Sciences, Peking University, Beijing 100871, China  Qinghua
Guo  Institute of Remote Sensing and Geographic Information Systems, School of
Earth and Space Sciences, Peking University, Beijing 100871, China  Yu Liu
Institute of Remote Sensing and Geographic Information Systems, School of
Earth and Space Sciences, Peking University, Beijing 100871, China

###### Abstract

A city (or an urban cluster) is not an isolated spatial unit, but a
combination of areas with closely linked socio-economic activities. However,
so far, we lack a consistent and quantitative approach to define multi-level
urban clusters through these socio-economic connections. Here, using granular
population distribution and flow data from China, we propose a bottom-up
aggregation approach to quantify urban clusters at multiple spatial scales. We
reveal six ‘phases’ (i.e., levels) in the population density-flow diagram,
each of which corresponds to a spatial configuration of urban clusters from
large to small. Besides, our results show that Zipf’s law appears only after
the fifth level, confirming the spatially dependent nature of urban laws. Our
approach does not need pre-defined administrative boundaries and can be
applied effectively on a global scale.

urban cluster, population distribution, commuting flow, multi-level, urban
system, big data

##  I Introduction

A city (or an urban cluster) is an integrated area with a dense population and
intensive internal socio-economic connections. It includes not only the core
urban area but also the surrounding areas that interact closely with the core
(Berry et al., 1969; Dash Nelson and Rae, 2016). However, in many countries,
administrative divisions are still the most common way of delineating urban
areas, which poses many urban planning and transportation problems (Ma and
Long, 2020). For example, in China, many people work in Beijing but live in
Sanhe (a small neighboring county close to Beijing) due to the low cost of
living and relatively convenient transportation (Bai and Rong, 2016). Those
people who commute between Sanhe and Beijing contribute to Beijing’s economic
growth and have demands for Beijing’s public services, but they are not part
of Beijing’s resident population according to the current definition of the
city’s boundaries.

Realizing that the administrative boundaries of cities are problematic, many
studies turn to delineating urban areas through data-driven ways. These
efforts include the identification of contiguous urban areas with a high
density of human activity, i.e., density-based methods (Imhoff et al., 1997;
Rozenfeld et al., 2008, 2011; Zhou et al., 2014; Arcaute et al., 2016). For
example, the threshold methods define areas that exceed a certain density of
population, infrastructure (e.g., road networks), or socio-economic activity
(e.g., nighttime light) as urban areas (Rozenfeld et al., 2008; Jiang and Jia,
2011; Cao et al., 2020; Baragwanath et al., 2021). Some machine learning
methods extract impervious surfaces or high-density built-up areas as urban
areas from remote sensing data (Schneider et al., 2010; Galdo et al., 2021).

With the rapid development of transportation and communication technology, the
flows of people, goods, and information between areas are becoming
increasingly frequent. From a flow perspective, a city can be defined in terms
of its core urban areas and surrounding areas with intensive socio-economic
interactions, known as functional urban areas (FUAs) (Hall, 2009; Dijkstra et
al., 2019; Chen and Yeh, 2022). Some developed countries have official
definitions for FUAs, such as the metropolitan statistical areas (MSAs) in the
United States, which encompass areas with high-density populations and the
surrounding commuting zones (Berry et al., 1969). Some recent studies have
used similar flow-based methods to quantify urban areas in the UK (Arcaute et
al., 2015) and France (Cottineau et al., 2017, 2019). However, most previous
works to identify FUAs need detailed census data or commuting survey data,
which are difficult to obtain in developing countries. Meanwhile, the choice
of population and commuting thresholds is arbitrary in most methods, making it
difficult to compare urban clusters across different countries and periods (Wu
et al., 2018).

Another piece of the puzzle that has been overlooked by previous flow-based
methods is the multi-level structure of urban systems. For example, the flow-
based method by the OECD defines urban clusters on only one spatial level
(Dijkstra et al., 2019), whereas urban systems have multiple levels, according
to previous studies (Batty, 2013; Arcaute et al., 2016; Alessandretti et al.,
2020). Although several data-driven approaches are proposed to derive urban
hierarchies based on percolation theory (Arcaute et al., 2016) or community
detection (Hong and Yao, 2019; Jia et al., 2021), robust methods to delineate
multi-scale urban clusters and reveal the different levels of urban systems
require further research.

With the development of information and communication technology, mobile phone
data have shown great potential in mapping dynamic population distributions
(Deville et al., 2014; Chen et al., 2018) and flow interactions (Kung et al.,
2014; Hadachi et al., 2020). These advances in mobile phone data allow us to
quantify multi-scale urban clusters in terms of both population distributions
and flow interactions (Deville et al., 2014; Hadachi et al., 2020; Chen and
Yeh, 2022). In addition, city science has shown that urban systems are
typically complex systems and obey some universal patterns, such as Zipf’s law
(Zipf, 1949; Gabaix, 1999) and allometric growth (Nordbeck, 1971; Bettencourt
et al., 2007), which guide us to study effective multi-level urban clusters.

In this paper, we propose a bottom-up approach to quantify multi-level urban
clusters based on the population distributions and flows inferred from mobile
phone data. We first traverse all population density thresholds and aggregate
spatially contiguous populated units into separate clusters under each
threshold. This process is similar to previous density-based methods
(Rozenfeld et al., 2008, 2011), and we refer to these individual clusters as
population clusters. We then link population clusters to form urban clusters
based on different flow ratio thresholds. Through percolation analysis, we
obtain six ‘phases’ in the population density-flow phase diagram, each of
which corresponds to one level of urban systems. Results show that Zipf’s law
only appears after the fifth level. Our research proposes an effective method
to characterize the population distributions and interactions of cities and to
quantitatively understand urban clusters on different levels.

##  II Data

The population distribution and flow data that we used in this work are
derived from an anonymous mobile phone dataset provided by a large location
service provider from China in 2015 (Cao et al., 2020; Dong et al., 2017,
2022). Individual’s home and work locations are detected by a machine learning
method from the user’s stay points; see Dong et al. (2022) for details. The
population distribution is calculated based on the number of users whose homes
are located within each $0.5^{\prime}\times 0.5^{\prime}$ (approximately $1km$
at the equator) grid. The commuting flow data aggregate the number of home-
work connections between any two $0.5^{\prime}\times 0.5^{\prime}$ grids.

Different location service providers have different market shares in different
regions. Therefore, we need to assess whether the population data derived from
one single service provider can represent the real population dynamics in
China. To assess the accuracy of the population distribution inferred from the
mobile phone data, we compare the estimated data with the micro-census data of
2015 at the prefecture level. The correlation coefficient is $0.9$, indicating
that the estimated population distribution is consistent with the census. Note
that the mobile phone dataset covers approximately 100 million people out of a
total population of 1.4 billion in China. Thus, all reported population-
related values are scaled by $13.9$ (total population number / number of
mobile phone users).

##  III Methods

Figure 1: The method. a) Spatially contiguous cells with values larger than
the population density threshold are aggregated into population clusters. b)
Population clusters with flow ratios greater than the flow ratio threshold are
merged into urban clusters. In panel (b), each node corresponds to a
population cluster, and each edge corresponds to the flow ratio from one
population cluster to another. Line widths are plotted according to the flow
ratio. Solid lines show the edges with weights exceeding the threshold, while
dotted lines show the edges with weights less than the threshold.

To construct multi-level urban clusters, we take the following steps (Fig. 1).
First, we merge the spatially adjacent populated grids into clusters at
different population density thresholds. We refer to these clusters as
population clusters. Second, we merge these population clusters into urban
clusters by different flow ratio thresholds. Similar to the concept of FUAs,
an urban cluster is a combination of populated areas with strong commuting
connections. Finally, we use the percolation theory to analyze the urban
clusters under different population density and flow ratio thresholds with the
density-flow phase diagram.

###  III.1 Clustering by population density thresholds

For a given population density threshold $D_{*}$, we label the cells with
values greater than $D_{*}$ as populated cells and then aggregate
geographically contiguous populated cells into population clusters using the
City Clustering Algorithm (Rozenfeld et al., 2008, 2011). Specifically, we
start with any unprocessed populated cell and iteratively add its neighboring
populated cells (eight nearest neighbors) until the neighbors of all cells in
the cluster are either non-populated cells or within the cluster. Then we
aggregate another population cluster until all populated cells belong to a
specific cluster. The area and population of each population cluster is the
sum of the areas and populations of all cells within that population cluster.
In addition, each population cluster should meet certain area and population
size criteria. Here, we set the minimum area $A_{*}$ of the population cluster
to $10km^{2}$ (for reference, the land area of Sansha, the smallest city in
China, is about $20km^{2}$). We also set the minimum area to 5, 15, 20, and 25
$km^{2}$, and the results are robust (Table A.1); see Appendix for details.

###  III.2 Clustering by flow ratio thresholds

We group the detected population clusters into urban clusters according to
different flow ratio thresholds. For given population clusters $i$ and $j$, we
measure the commuting flow $P_{ij}$ whose origin is located in cluster $i$ and
destination is located in cluster $j$. The flow is then normalized as follows:
$F_{ij}=P_{ij}/\sum^{N}_{j=0}{P_{ij}}$. For a given flow ratio threshold
$F_{*}$ and any two population clusters, a link is established between the two
clusters if the commuting ratio in either direction exceeds the threshold
$F_{*}$. Besides, if a population cluster has multiple commuting flows to
other population clusters that exceed the threshold $F_{*}$, the cluster is
linked only to the cluster with the largest flow ratio. Finally, the linked
population clusters are merged together to construct an urban cluster. This
process is applied only once for all population clusters in parallel, and the
merged clusters will not be iterated again. The area and population of each
urban cluster is the sum of the areas and populations of all population
clusters within that urban cluster.

###  III.3 Percolation analysis on urban clusters

We analyze the urban clusters under different density-flow thresholds using
the percolation theory. The percolation theory studies the transition of many
small clusters merged into a large spanning cluster at the critical point
(Christensen and Moloney, 2005). Around the critical point, cluster systems
exhibit power-law critical phenomena that also exist in urban systems (e.g.,
the size distribution of cities). Therefore, the percolation theory has been
widely used to model urban growth (Makse et al., 1995, 1998) and quantify
urban clusters (Arcaute et al., 2016; Cao et al., 2020). Here, we iterate over
all possible population density thresholds (from non-zero to very dense) and
obtain the population clusters under each density threshold. Then, we traverse
the flow ratio thresholds from $0\%$ to $100\%$ and merge the population
clusters into urban clusters under each flow threshold, where $0$ means that
any two population clusters with interactions are merged together, and $100\%$
means that no population clusters are merged since the flow ratio of two
clusters cannot exceed $100\%$. Finally, we obtain many collections of urban
clusters, each of which corresponds to a specific population density threshold
and a specific flow ratio threshold. Similar to the percolation model, we
calculate the area of the largest urban cluster (ranked by land area) as a
function of the density and flow thresholds and construct the density-flow
phase diagram.

##  IV Results

###  IV.1 Density-flow phase diagram

Figure 2: a) The density-flow phase diagram. Each cell in the diagram indicates the size of the largest urban cluster at the corresponding density and flow thresholds. Solid lines indicate the boundaries of each phase. b) Histogram of the largest cluster areas of all urban systems. We observe clear breakpoints that are demarcated by dotted lines. Table 1: Statistics on the urban clusters from Level 1 to Level 6 Level |  $D_{*}$ (people/$km^{2}$) | $F_{*}$ | $N_{urban}$ |  $A_{total}$ ($km^{2}$) |  $A_{largest}$ ($km^{2}$) |  $P_{total}$ (people) |  $P_{largest}$ (people)
---|---|---|---|---|---|---|---
1 |  $\textgreater$ 0 |  $\textgreater$ 0% | 115 | $1.08\times 10^{6}$ | $6.60\times 10^{5}$ | $1.36\times 10^{9}$ | $7.65\times 10^{8}$
2 |  $\textgreater$ 140 |  $\textgreater$ 0% | 138 | $4.19\times 10^{5}$ | $1.45\times 10^{5}$ | $1.28\times 10^{9}$ | $3.19\times 10^{8}$
3 |  $\textgreater$ 280 |  $\textgreater$ 2% | 191 | $2.66\times 10^{5}$ | $4.26\times 10^{4}$ | $1.21\times 10^{9}$ | $1.68\times 10^{8}$
4 |  $\textgreater$ 700 |  $\textgreater$ 2% | 193 | $1.27\times 10^{5}$ | $1.07\times 10^{4}$ | $1.10\times 10^{9}$ | $1.42\times 10^{8}$
5 |  $\textgreater$ 2,940 |  $\textgreater$ 5% | 349 | $4.89\times 10^{4}$ | $3.04\times 10^{3}$ | $9.01\times 10^{8}$ | $6.47\times 10^{7}$
6 |  $\textgreater$ 4,620 |  $\textgreater$ 28% | 876 | $3.74\times 10^{4}$ | $1.43\times 10^{3}$ | $8.27\times 10^{8}$ | $4.00\times 10^{7}$

We rank urban clusters under each density-flow threshold by land area and
obtain the phase diagram (Fig. 2a). The color of each grid cell in Fig. 2a
indicates the area of the largest urban cluster under the specified population
density-flow thresholds. From bottom left to top right, urban clusters
gradually transition from sparsely populated, weakly connected urban areas to
densely populated, strongly connected urban areas as the thresholds increase.
Remarkably, by transforming Fig. 2a into a histogram of the largest cluster
areas under the different density-flow thresholds, we observe $6$ groups (Fig.
2b). Using the breakpoints (vertical dashed lines) in Fig. 2b, we further
divide the density-flow phase diagram into $6$ phases (solid lines in Fig.
2a), with the cluster systems remaining stable within each phase.

As the population density threshold and the flow ratio threshold increase, the
largest urban cluster in the system remains stable until the urban system
transitions to a lower-level spatial scale. Thus, we regard 6 phases as 6
spatial levels of one urban system. Table 1 shows the population density
threshold $D_{*}$ (people/$km^{2}$), the flow ratio threshold $F_{*}$ (%), the
number of urban clusters $N_{urban}$, the total area $A_{total}$ ($km^{2}$)
and the total population $P_{total}$ (people) of the urban clusters, and the
area $A_{largest}$ ($km^{2}$) and the population $P_{largest}$ (people) of the
largest cluster in each level from Level 1 to Level 6.

###  IV.2 Urban clusters at different levels

We next investigate the spatial distributions of the urban clusters at
different levels. Fig. 3 shows the urban clusters at Level 1 and Level 2, and
Fig. 4 shows the urban clusters from Level 3 to Level 6 in Beijing-Tianjin-
Hebei, the Yangtze River Delta, and the Pearl River Delta (mapped with black
lines in Fig. 3b).

Figure 3: Urban clusters at Level 1 (a) and Level 2 (b). The top $5$ largest
clusters are colored by rank. The black lines show the area of Beijing-
Tianjin-Hebei, the Yangtze River Delta, and the Pearl River Delta. Figure 4:
a-d) Urban clusters in Beijing-Tianjin-Hebei, the Yangtze River Delta, and the
Pearl River Delta at Levels 3 (a), 4 (b), 5 (c), and 6 (d), respectively. The
top $5$ largest clusters in each region are colored by rank.

Level 1 corresponds to the non-zero population density-flow thresholds; that
is, areas with a population $\textgreater 0$ are marked as populated areas,
and any two clusters with flows $\textgreater 0$ are linked together. At Level
1, the areas of the top $5$ largest clusters account for $87\%$ of the total
area of all clusters. The largest urban cluster has an area of $6.60\times
10^{5}km^{2}$ and a population of $7.65\times 10^{8}$, including most of
Central and East China and parts of North and Northeast China. The $2$nd and
$5$th largest urban clusters cover South China. The $3$rd and $4$th largest
urban clusters correspond to the major urban areas in Southwest and Northwest
China, respectively.

Level 2 corresponds to the thresholds of $140$ people per $km^{2}$ and a 0%
flow ratio. Level-2 clusters represent the development poles in each region.
The largest urban cluster covers most of Hebei Province, Henan Province, and
Shandong Province, and has an area of $1.45\times 10^{5}km^{2}$ and a
population of $3.19\times 10^{8}$. Beijing, the capital of China, is within
the cluster. The $2$nd largest urban cluster covers Jiangsu Province, Anhui
Province and Zhejiang Province and includes the Yangtze River Delta; the $3$rd
cluster covers Guangdong Province and includes the Pearl River Delta; the
$4$th and $5$th clusters correspond to Hunan Province and Sichuan Province,
respectively (Fig. 3b).

Level 3 corresponds to the thresholds of $280$ people per $km^{2}$ and a 2%
flow ratio, and Level 4 corresponds to the thresholds of $700$ people per
$km^{2}$ and a 2% flow ratio. The urban clusters at these two levels are
consistent with the concept of urban agglomeration, which is the spatial form
of several highly integrated cities (Fang and Yu, 2017). The largest urban
cluster at Level 3 is located in the Yangtze River Delta, including Shanghai
and major cities in southern Jiangsu Province and northern Zhejiang Province.
At Level 4, Hangzhou and its surrounding cities are separated from this
cluster. The largest urban cluster at Level 4 is located in the Pearl River
Delta, corresponding to the Greater Bay Area, and mainly includes Guangzhou
and Shenzhen (both cities with a population of more than 10 million). The
Yangtze River Delta and the Pearl River Delta are all well-developed regions
in China.

Level 5 corresponds to the thresholds of $2,940$ people per $km^{2}$ and a 5%
flow ratio. At Level 5, each urban cluster has a dense core urban area, as
well as surrounding areas that are closely connected to the core, which is
similar to the definition of an FUA. However, instead of using pre-defined
parameters (population density and flow ratio thresholds), our method obtains
the thresholds objectively through percolation. The number of Level-5 urban
clusters (349) is similar to the number of prefecture-level cities (333) in
China. As shown in Fig. 4, one prefecture-level city corresponds to one urban
cluster in most regions. Yet, in some well-developed regions, intensive socio-
economic connections make urban clusters cross administrative boundaries. For
example, Sanhe (the red circle in Fig. 4c) and Beijing are merged together due
to the large number of commuting, although Beijing and Sanhe are within
different administrative city boundaries.

Level 6 corresponds to the population density threshold of $4,620$ people per
$km^{2}$ and the flow ratio threshold of 28%. Due to the high flow ratio
threshold, most urban clusters in this level consist of one single population
cluster. Compared to the administrative boundaries, the obtained urban
clusters mainly correspond to core urban areas within prefecture-level cities.
There are also some urban clusters that cross the boundaries of prefecture-
level cities. For example, the central bodies of western Shenzhen and Dongguan
are geographically continuous with high population density, forming an urban
cluster across the boundaries, while eastern Shenzhen is not adjacent to this
urban cluster due to geographical barriers (e.g., mountains and forests), and
the flow ratio is also not high enough, forming another urban cluster. As a
validation, we compare the largest urban cluster (Beijing) detected by our
method to the official released built-up area data in 2015. Our results show
that Beijing at Level 6 has an area of $1,381km^{2}$, while the official
number is $1,401km^{2}$, and the two values are very close.

We also perform a sensitivity test by applying our method to Guangdong
Province in China. Although fewer levels are derived, the density-flow phase
diagram and the derived urban clusters at different levels are similar; see
Fig. A.1-A.2 in the Appendix.

###  IV.3 Zipf’s law and allometric growth

To investigate the relationship between area and population in the urban
clusters, we test Zipf’s law and allometric growth. Zipf’s law and allometric
growth reflect the self-organized properties of urban complex systems and have
been widely tested across different countries in different periods (Soo, 2005;
Bettencourt et al., 2007; Bettencourt, 2013). Zipf’s law states that when
cities are ranked by population size, the population size $S$ and the rank $R$
of cities satisfy $S=1/R$. This can also be expressed as the probability
density function (PDF) of urban cluster sizes following a power-law
distribution where $P(S)\sim S^{-\alpha}$ and $\alpha=2$ (Zipf, 1949; Gabaix,
1999). Allometric growth refers to the sub-linear power-law relationship
between the population $P$ and the urban area $A$, which can be expressed as
$A=P^{\beta}$ with $\beta\approx 0.6-0.8$ (Nordbeck, 1971; Bettencourt, 2013).
Allometric growth represents economies of scale, meaning that larger urban
clusters can result in more efficient land use per capita, since the
population is more concentrated (Bettencourt et al., 2007).

Figure 5: a-b) The PDFs of the population sizes of the urban clusters from
Level 1 to Level 6. Solid lines represent the power-law fitting results. c-d)
The sub-linear relationship between the populations and the areas of the urban
clusters from Level 1 to Level 6. Solid lines represent the fitting results.
$\pm$ represents one standard deviation.

Figure 5a-b shows that the population sizes of the urban clusters from Level 1
to Level 6 all follow power-law distributions. We further use the method
proposed by Alstott et al. (2014) to fit the data, and the power-law exponents
$\alpha$ for Level 5 and Level 6 are around $2$, which means that Zipf’s law
holds well at these two levels. However, the exponents $\alpha$ for Levels 1-4
deviate from $2$, indicating that Zipf’s law does not hold at higher levels.
It should be noted that there is a long-standing debate on whether Zipf’s law
holds for urban clusters at different scales (Berry and Okulicz-Kozaryn,
2012), and Zipf’s law is not a validation of the derived urban clusters. As a
complement, we demonstrate that Zipf’s law does not hold on all spatial
scales; it only holds after Level 5. Interestingly, as shown in the previous
section, the Level-5 urban clusters have similar spatial scales to the
prefecture-level cities, indicating that our results are consistent with
previous studies on the empirical test of Zipf’s law (Gabaix, 1999; Soo,
2005).

Figure 5c-d shows the power-law relationship between the populations and the
areas of the urban clusters at different levels. The exponents $\beta$ are all
$<1$, indicating the existence of allometric growth. However, similar to
Zipf’s law, only after Level 5, the exponents begin to approach the previous
theoretical and empirical values (Bettencourt, 2013). This finding also adds
evidence that the allometric growth depends on the definition of urban
clusters (Berry and Okulicz-Kozaryn, 2012; Oliveira et al., 2014).

##  V Discussion

We propose a bottom-up approach to construct multi-level urban clusters using
population distribution and flow data. The density-flow thresholds are derived
according to the critical characteristics of urban systems based on the
percolation theory. We reveal six levels of urban clusters from the density-
flow phase diagram, and show that Zipf’s law holds only for urban clusters
after Level 5, providing empirical evidence for the spatially dependent nature
of urban laws. Regarding applications, our method does not rely on any pre-
defined geographical units and requires only the density-flow thresholds
obtained by percolation, allowing us to efficiently derive multi-level urban
clusters.

The prevalence of mobile phones allows us to obtain population distribution
and flow data at a lower cost and faster update rate. Thus, our approach can
be easily applied to countries that have mobile phone data but do not have
recent census/survey data (e.g., some developing countries). Even for those
regions where mobile phone data are unavailable, we could also consider using
human mobility models to infer population flows from population distributions
(Barbosa et al., 2018), which are usually easy to obtain, such as the WorldPop
dataset (Tatem, 2017).

Some extensions can be explored in further studies. First, in this paper, we
use commuting flows to measure the socio-economic connections between areas.
However, commuting accounts for only approximately 1/3 of all human movements
(Ding et al., 2017), and a large number of non-commuting movements also
reflect the socio-economic connections. The impact of different types of flow
interactions on quantifying urban clusters is worth exploring. Second, the
movements of individuals vary substantially across different periods. For
example, resident commuting dropped significantly during the COVID-19 pandemic
(Kraemer et al., 2020). This might lead to changes in the boundaries of flow-
based urban clusters, and these temporally dynamic boundaries are worth
exploring in our future work.

##  VI Data and codes availability

The dataset and codes to reproduce the results of this paper are available via
https://github.com/caowenpu56/densityflow.

## References

  * Alessandretti et al. (2020) Laura Alessandretti, Ulf Aslak, and Sune Lehmann.  The scales of human mobility.  _Nature_ , 587(7834):402–407, November 2020.
  * Alstott et al. (2014) Jeff Alstott, Ed Bullmore, and Dietmar Plenz.  powerlaw: a Python package for analysis of heavy-tailed distributions.  _PLoS ONE_ , 9(1):e85777, January 2014.
  * Arcaute et al. (2015) Elsa Arcaute, Erez Hatna, Peter Ferguson, Hyejin Youn, Anders Johansson, and Michael Batty.  Constructing cities, deconstructing scaling laws.  _Journal of The Royal Society Interface_ , 12(102):20140745, January 2015.
  * Arcaute et al. (2016) Elsa Arcaute, Carlos Molinero, Erez Hatna, Roberto Murcio, Camilo Vargas-Ruiz, A. Paolo Masucci, and Michael Batty.  Cities and regions in Britain through hierarchical percolation.  _Royal Society Open Science_ , 3(4):150691, April 2016.
  * Bai and Rong (2016) Guang Bai and Chaohe Rong.  From the view of field theory, the basic role of cross urban rail commuting service in metropolitan area — A case study of Beijing, Sanhe and Yanjiao.  In _2016 International Conference on Industrial Economics System and Industrial Security Engineering (IEIS)_ , pages 1–4, Sydney, Australia, July 2016. IEEE.
  * Baragwanath et al. (2021) Kathryn Baragwanath, Ran Goldblatt, Gordon Hanson, and Amit K. Khandelwal.  Detecting urban markets with satellite imagery: An application to India.  _Journal of Urban Economics_ , 125:103173, September 2021\.
  * Barbosa et al. (2018) Hugo Barbosa, Marc Barthelemy, Gourab Ghoshal, Charlotte R. James, Maxime Lenormand, Thomas Louail, Ronaldo Menezes, José J. Ramasco, Filippo Simini, and Marcello Tomasini.  Human mobility: Models and applications.  _Physics Reports_ , 734(6):1–74, March 2018.
  * Batty (2013) Michael Batty.  _The New Science of Cities_.  The MIT Press, 2013.  ISBN 978-0-262-31823-5.
  * Berry et al. (1969) B.J.L. Berry, P.G. Goheen, and H. Goldstein.  _Metropolitan Area Definition: A Re-evaluation of Concept and Statistical Practice_ , volume 28.  Washington, D.C.: U.S. Bureau of the Census, 1969.
  * Berry and Okulicz-Kozaryn (2012) Brian J.L. Berry and Adam Okulicz-Kozaryn.  The city size distribution debate: Resolution for US urban regions and megalopolitan areas.  _Cities_ , 29:S17–S23, March 2012.
  * Bettencourt (2013) Luís M. A. Bettencourt.  The origins of scaling in cities.  _Science_ , 340(6139):1438–1441, June 2013.
  * Bettencourt et al. (2007) Luís M. A. Bettencourt, José Lobo, Dirk Helbing, Christian Kühnert, and Geoffrey B. West.  Growth, innovation, scaling, and the pace of life in cities.  _Proceedings of the National Academy of Sciences_ , 104(17):7301–7306, April 2007.
  * Cao et al. (2020) Wenpu Cao, Lei Dong, Lun Wu, and Yu Liu.  Quantifying urban areas with multi-source data based on percolation theory.  _Remote Sensing of Environment_ , 241:111730, May 2020.
  * Chen et al. (2018) Jie Chen, Tao Pei, Shih-Lung Shaw, Feng Lu, Mingxiao Li, Shifen Cheng, Xiliang Liu, and Hengcai Zhang.  Fine-grained prediction of urban population using mobile phone location data.  _International Journal of Geographical Information Science_ , 32(9):1770–1786, September 2018.
  * Chen and Yeh (2022) Zifeng Chen and Anthony Gar-On Yeh.  Delineating functional urban areas in Chinese mega city regions using fine-grained population data and cellphone location data: A case of Pearl River Delta.  _Computers, Environment and Urban Systems_ , 93:101771, April 2022.
  * Christensen and Moloney (2005) Kim Christensen and Nicholas R. Moloney.  _Complexity and Criticality_ , volume 1.  Imperial College Press, 2005.
  * Cottineau et al. (2017) Clémentine Cottineau, Erez Hatna, Elsa Arcaute, and Michael Batty.  Diverse cities or the systematic paradox of urban scaling laws.  _Computers, Environment and Urban Systems_ , 63:80–94, May 2017.
  * Cottineau et al. (2019) Clémentine Cottineau, Olivier Finance, Erez Hatna, Elsa Arcaute, and Michael Batty.  Defining urban clusters to detect agglomeration economies.  _Environment and Planning B: Urban Analytics and City Science_ , 46(9):1611–1626, November 2019.
  * Dash Nelson and Rae (2016) Garrett Dash Nelson and Alasdair Rae.  An economic geography of the United States: From commutes to megaregions.  _PLOS ONE_ , 11(11):e0166083, November 2016.
  * Deville et al. (2014) Pierre Deville, Catherine Linard, Samuel Martin, Marius Gilbert, Forrest R. Stevens, Andrea E. Gaughan, Vincent D. Blondel, and Andrew J. Tatem.  Dynamic population mapping using mobile phone data.  _Proceedings of the National Academy of Sciences_ , 111(45):15888–15893, November 2014.
  * Dijkstra et al. (2019) L. Dijkstra, H. Poelman, and P. Veneri.  The EU-OECD definition of a functional urban area.  _OECD Regional Development Working Papers_ , December 2019.
  * Ding et al. (2017) Chuan Ding, Chao Liu, Yi Zhang, Jiawen Yang, and Yunpeng Wang.  Investigating the impacts of built environment on vehicle miles traveled and energy consumption: Differences between commuting and non-commuting trips.  _Cities_ , 68:25–36, August 2017.
  * Dong et al. (2017) Lei Dong, Sicong Chen, Yunsheng Cheng, Zhengwei Wu, Chao Li, and Haishan Wu.  Measuring economic activity in China with mobile big data.  _EPJ Data Science_ , 6(1):29, December 2017.
  * Dong et al. (2022) Lei Dong, Paolo Santi, Yu Liu, Siqi Zheng, and Carlo Ratti.  The universality in urban commuting across and within cities, 2022.  URL https://arxiv.org/abs/2204.12865.
  * Fang and Yu (2017) Chuanglin Fang and Danlin Yu.  Urban agglomeration: An evolving concept of an emerging phenomenon.  _Landscape and Urban Planning_ , 162:126–136, June 2017\.
  * Gabaix (1999) X. Gabaix.  Zipf’s law for cities: An explanation.  _The Quarterly Journal of Economics_ , 114(3):739–767, August 1999.
  * Galdo et al. (2021) Virgilio Galdo, Yue Li, and Martin Rama.  Identifying urban areas by combining human judgment and machine learning: An application to India.  _Journal of Urban Economics_ , 125:103229, September 2021\.
  * Hadachi et al. (2020) Amnir Hadachi, Mozhgan Pourmoradnasseri, and Kaveh Khoshkhah.  Unveiling large-scale commuting patterns based on mobile phone cellular network data.  _Journal of Transport Geography_ , 89:102871, December 2020\.
  * Hall (2009) Peter Hall.  Looking backward, looking forward: The city region of the mid-21st century.  _Regional Studies_ , 43(6):803–817, July 2009\.
  * Hong and Yao (2019) Ye Hong and Yao Yao.  Hierarchical community detection and functional area identification with OSM roads and complex graph theory.  _International Journal of Geographical Information Science_ , 33(8):1569–1587, August 2019.
  * Imhoff et al. (1997) Marc L. Imhoff, William T. Lawrence, David C. Stutzer, and Christopher D. Elvidge.  A technique for using composite DMSP/OLS “City Lights” satellite data to map urban area.  _Remote Sensing of Environment_ , 61(3):361–370, September 1997.
  * Jia et al. (2021) Tao Jia, Xi Luo, and Xin Li.  Delineating a hierarchical organization of ranked urban clusters using a spatial interaction network.  _Computers, Environment and Urban Systems_ , 87:101617, May 2021.
  * Jiang and Jia (2011) Bin Jiang and Tao Jia.  Zipf’s law for all the natural cities in the United States: A geospatial perspective.  _International Journal of Geographical Information Science_ , 25(8):1269–1281, August 2011.
  * Kraemer et al. (2020) Moritz U. G. Kraemer, Chia-Hung Yang, Bernardo Gutierrez, Chieh-Hsi Wu, Brennan Klein, David M. Pigott, Open COVID-19 Data Working Group†, Louis du Plessis, Nuno R. Faria, Ruoran Li, William P. Hanage, John S. Brownstein, Maylis Layan, Alessandro Vespignani, Huaiyu Tian, Christopher Dye, Oliver G. Pybus, and Samuel V. Scarpino.  The effect of human mobility and control measures on the COVID-19 epidemic in China.  _Science_ , 368(6490):493–497, May 2020.
  * Kung et al. (2014) Kevin S. Kung, Kael Greco, Stanislav Sobolevsky, and Carlo Ratti.  Exploring universal patterns in human home-work commuting from mobile phone data.  _PLoS ONE_ , 9(6):e96180, June 2014.
  * Ma and Long (2020) Shuang Ma and Ying Long.  Functional urban area delineations of cities on the Chinese mainland using massive Didi ride-hailing records.  _Cities_ , 97:102532, February 2020.
  * Makse et al. (1995) Hernán A. Makse, Shlomo Havlin, and H. Eugene Stanley.  Modelling urban growth patterns.  _Nature_ , 377(6550):608–612, October 1995.
  * Makse et al. (1998) Hernán A. Makse, José S. Andrade, Michael Batty, Shlomo Havlin, and H. Eugene Stanley.  Modeling urban growth patterns with correlated percolation.  _Physical Review E_ , 58(6):7054–7062, December 1998.
  * Nordbeck (1971) Stig Nordbeck.  Urban allometric growth.  _Geografiska Annaler: Series B, Human Geography_ , 53(1):54–67, April 1971.
  * Oliveira et al. (2014) Erneson A. Oliveira, José S. Andrade, and Hernán A. Makse.  Large cities are less green.  _Scientific Reports_ , 4(1):4235, December 2014\.
  * Rozenfeld et al. (2008) H. D. Rozenfeld, D. Rybski, J. S. Andrade, M. Batty, H. E. Stanley, and H. A. Makse.  Laws of population growth.  _Proceedings of the National Academy of Sciences_ , 105(48):18702–18707, December 2008.
  * Rozenfeld et al. (2011) H. D. Rozenfeld, D. Rybski, Xavier Gabaix, and H. A. Makse.  The area and population of cities: new insights from a different perspective on cities.  _American Economic Review_ , 101(5):2205–2225, August 2011.
  * Schneider et al. (2010) Annemarie Schneider, Mark A. Friedl, and David Potere.  Mapping global urban areas using MODIS 500-m data: New methods and datasets based on ‘urban ecoregions’.  _Remote Sensing of Environment_ , 114(8):1733–1746, August 2010.
  * Soo (2005) Kwok Tong Soo.  Zipf’s law for cities: a cross-country investigation.  _Regional Science and Urban Economics_ , 35(3):239–263, May 2005.
  * Tatem (2017) Andrew J. Tatem.  WorldPop, open data for spatial demography.  _Scientific Data_ , 4(1):170004, April 2017.
  * Wu et al. (2018) Wenjia Wu, Hongrui Zhao, and Shulong Jiang.  A Zipf’s law-based method for mapping urban areas using NPP-VIIRS nighttime light data.  _Remote Sensing_ , 10(1):130, January 2018.
  * Zhou et al. (2014) Yuyu Zhou, Steven J. Smith, Christopher D. Elvidge, Kaiguang Zhao, Allison Thomson, and Marc Imhoff.  A cluster-based method to map urban area from DMSP/OLS nightlights.  _Remote Sensing of Environment_ , 147:173–185, May 2014\.
  * Zipf (1949) G. K. Zipf.  _Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology_.  Cambridge: Addison-Wesley, 1949.


ampmtime

# Counting orientations of random graphs
with no directed $k$-cycles

Marcelo Campos  ,  Maurício Collares  and  Guilherme Oliveira Mota  IMPA,
Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ, Brazil
<EMAIL_ADDRESS>Departamento de Matemática, Universidade Federal de
Minas Gerais, Belo Horizonte, MG, Brazil<EMAIL_ADDRESS>Instituto de
Matemática e Estatística, Universidade de São Paulo, São Paulo, Brazil
<EMAIL_ADDRESS>
(Date: , )

###### Abstract.

For every $k\geqslant 3$, we determine the order of growth, up to
polylogarithmic factors, of the number of orientations of the binomial random
graph containing no directed cycle of length $k$. This solves a conjecture of
Kohayakawa, Morris and the last two authors.

M. Campos was supported by CNPq and FAPERJ. M. Collares was supported by CNPq
(406248/2021-4). G. O. Mota was supported by CNPq (306620/2020-0,
406248/2021-4, 406248/2021-4) and FAPESP (2018/04876-1, 2019/13364-7). This
study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de
Nível Superior, Brazil (CAPES), Finance Code 001. FAPESP is the São Paulo
Research Foundation.

##  1\. Introduction

An orientation $\vec{H}$ of a graph $H$ is an oriented graph obtained by
assigning an orientation to each edge of $H$. The study of the number of
$\vec{H}$-free orientations of a graph $G$, denoted by $D(G,\vec{H})$, was
initiated by Erdős [Er74], who posed the problem of determining
$D(n,\vec{H}):=\max\big{\\{}D(G,\vec{H}):|V(G)|=n\big{\\}}$. For tournaments,
this problem was solved by Alon and Yuster [AlYu06], who proved that
$D{(n,\vec{T})=2^{\mathop{\text{\rm ex}}\nolimits(n,K_{k})}}$ holds for any
tournament $\vec{T}$ on $k$ vertices if $n\in\mathbb{N}$ is sufficiently large
as a function of $k$.

Let $C^{\circlearrowright}_{k}$ denote the directed cycle of length $k$. Bucić
and Sudakov [BuSu20+] determined $D(n,C^{\circlearrowright}_{2\ell+1})$ for
every $\ell\geqslant 1$ as long as $n$ is sufficiently large, extending the
proof in [AlYu06]. Another extension of the results in [AlYu06] was given by
Araújo, Botler, and the last author [ArBoMo20+] who determined
$D(n,C^{\circlearrowright}_{3})$ for every $n\in\mathbb{N}$ (see also
[BoHoMo21]).

In the context of random graphs, Allen, Kohayakawa, Parente, and the last
author [AlKoMoPa14] investigated the problem of determining the typical number
of $C^{\circlearrowright}_{k}$-free orientations of the Erdős–Rényi random
graph $G(n,p)$. They proved that, for every $k\geqslant 3$, with high
probability as $n\rightarrow\infty$ we have
$\log_{2}D(G(n,p),C^{\circlearrowright}_{k})=o(pn^{2})$ for $p\gg
n^{-1+1/(k-1)}$, and
$\log_{2}D(G(n,p),C^{\circlearrowright}_{k})=(1+o(1))p\binom{n}{2}$ for
$n^{-2}\ll p\ll n^{-1+1/(k-1)}$. This result was improved in the case of
triangles by Kohayakawa, Morris and the last two authors [CoKoMoMo20], who
proved, among other things, the following result111The
$\widetilde{\Theta}(\cdot)$ and $\widetilde{O}(\cdot)$ notation are analogous
to $\Theta$ and $O$ notation but with polylogarithmic factors omitted. For
convenience, from now on $\log$ will denote the natural logarithm..

######  Theorem 1.1 ([CoKoMoMo20]*Theorem 1.2).

If $p\gg n^{-1/2}$, then, with high probability as $n\rightarrow\infty$,

$\log
D(G(n,p),C^{\circlearrowright}_{3})=\widetilde{\Theta}\big{(}n/p\big{)}.$

A first step towards determining $\log D(G(n,p),C^{\circlearrowright}_{k})$
for $k\geqslant 4$ was also given in [CoKoMoMo20], where it was proved that
$\log D(G(n,p),C^{\circlearrowright}_{k})=\widetilde{O}\big{(}n/p\big{)}$.
Moreover, they proved that a natural generalisation of the lower bound
construction used in the proof of Theorem 1.1 gives

$\log
D(G(n,p),C^{\circlearrowright}_{k})=\Omega\left(\frac{n}{p^{1/(k-2)}}\right)$
(1)

with high probability when $p\gg n^{-1+1/(k-1)}$. They conjectured that this
lower bound is sharp up to polylogarithmic factors, and we confirm this
conjecture by proving the following result.

######  Theorem 1.2.

Let $k\geqslant 3$ and $p=p(n)\gg n^{-1+1/(k-1)}$. Then, with high probability
as $n\rightarrow\infty$,

$\log
D\big{(}G(n,p),C^{\circlearrowright}_{k}\big{)}=\widetilde{\Theta}\bigg{(}\frac{n}{p^{1/(k-2)}}\bigg{)}.$

The proof of this result will be outlined in the next section, but we present
here a short overview of three key ideas in the proof. First, we ensure that
the graph encoding $(k-2)$-paths is dense enough to apply the graph container
lemma in an unexpected way. To do so, we define, for each $1\leqslant
r\leqslant k-2$, a pseudorandomness condition on the number of directed
$r$-paths between small sets, and split the proof into $k-2$ cases according
to whether such a pseudorandomness condition holds for a given $r$. We design
these conditions in such a way that the case $r=1$ holds for any orientation
of $G(n,p)$ with high probability, and such that we may finish the proof using
the graph container method (introduced by Kleitman and Winston [KlWi82], and
rediscovered and developed by Sapozhenko [Sa01]) if the condition holds for
$r=k-2$. The second key idea is how to deal with orientations that do not
satisfy the pseudorandomness condition for some $2\leqslant r\leqslant k-2$.
In this situation, we provide a way to efficiently “encode” the orientations
that do not satisfy the condition for some value of $r$ but do for all smaller
values.

We remark that, to implement the above two ideas, we need to construct the
orientation “online”, that is, to consider a subgraph $H\subset G(n,p)$, and
for each possible orientation $\vec{H}$ of $H$, reveal the randomness between
a new subset of vertices and $V(H)$ and consider all ways to extend $\vec{H}$.
Counting orientations of $G(n,p)$ is, however, an “offline” problem: when
exposing $G(n,p)$ in multiple rounds, the orientation of an early-round edge
may depend on the randomness of later rounds. To circumvent this fact, we use
our third key idea, which is to count the expected number of orientations of
$G(n,p)$ that are $C^{\circlearrowright}_{\ell+2}$-free. When estimating this
expectation we will be able to split it in a way that makes possible to
proceed inductively and use the randomness in steps after orienting part of
the edges.

##  2\. Outline of the proof of Theorem 1.2

We start by presenting a short sketch of the proof of Theorem 1.2 for
$C^{\circlearrowright}_{3}$, as proved in [CoKoMoMo20]. This will motivate the
idea behind the proof for general directed cycles $C^{\circlearrowright}_{k}$.

###  2.1. The proof in [CoKoMoMo20]

The idea is to obtain, by induction on the number of vertices, the following
upper bound on the number of $C^{\circlearrowright}_{3}$-free orientations of
an $n$-vertex graph $G$:

$\binom{n}{\leqslant\alpha(G)}^{2n}.$ (2)

In order to obtain such a bound, let $G$ be a graph on vertex set $V$ and
consider $v\in V$. Let $H=G\setminus\\{v\\}$ and suppose that the number of
$C^{\circlearrowright}_{3}$-free orientations of $H$ is

$\binom{n-1}{\leqslant\alpha(H)}^{2(n-1)}.$ (3)

Then, for each $C^{\circlearrowright}_{3}$-free orientation $\vec{G}$ of $G$,
let $\vec{H}$ be its restriction to $H$ and pick $\vec{T}\subset
E(\vec{G})\setminus E(\vec{H})$ minimal such that $\vec{G}$ is the only
$C^{\circlearrowright}_{3}$-free orientation of $G$ containing
$\vec{T}\cup\vec{H}$. The key observation is that, by the minimality of $T$,
the vertex sets $N^{+}_{\vec{T}}(v)$ and $N^{-}_{\vec{T}}(v)$ are independent
sets in $H$, so there are at most $\binom{n}{\leqslant\alpha(G)}^{2}$ choices
for $\vec{T}$. This together with (3) and $\alpha(H)\leqslant\alpha(G)$
completes the proof of (2). Since $\alpha(G(n,p))\leqslant\frac{3\log n}{p}$
holds with high probability, one can check that the bound (2) implies Theorem
1.2 for $C^{\circlearrowright}_{3}$.

We will generalise the ideas depicted above in two ways, which will be
described in the next two subsections. Directed paths of length ${k-2}$
starting or ending in the neighbourhood of a vertex will play a key role in
our proofs. For this reason, we fix $\ell=k-2\geqslant 1$, and our aim is to
count orientations of $G(n,p)$ avoiding copies of
$C^{\circlearrowright}_{\ell+2}$.

###  2.2. Pseudorandomness

To count the desired orientations of $G(n,p)$, we define a “pseudorandom”
oriented graph property, and we proceed to separately count the
$C^{\circlearrowright}_{\ell+2}$-free orientations depending on whether some
already-oriented subgraph $\vec{H}$ is pseudorandom. We then use the
randomness of $G(n,p)$ in a stronger way, exposing the randomness bit by bit
in each step of the induction.

Let us discuss the pseudorandom property we mentioned in the previous
paragraph. We write $\vec{P}_{r}$ for the directed path with $r$ edges and,
given a oriented graph $\vec{G}$, we denote by $\vec{G}^{r}$ the digraph such
that $(u,v)$ is an edge whenever there is a $\vec{P}_{r}$ from $u$ to $v$ in
$\vec{G}$. Roughly speaking, we say an oriented graph $\vec{G}$ is _$r$
-locally dense_ (for a complete description of this property, see Definition
3.2), if

$\stackon[-5.2pt]{e}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{G}\setminus
X)^{r}}(A^{\prime},B)\geqslant\frac{1}{2}\cdot
p^{\frac{\ell-r+1}{\ell}}|A^{\prime}||B|$ (4)

for all disjoint sets $A^{\prime},B,X\subset V(G)$ of size roughly $(\log
n)/p$, where $\vec{G}\setminus X$ is a shorthand for $\vec{G}[V(G)\setminus
X]$ and $\stackon[-5.2pt]{e}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{G}\setminus
X)^{r}}(A^{\prime},B)$ denotes the number of edges between $A^{\prime}$ and
$B$ (in either direction) in the digraph $(\vec{G}\setminus X)^{r}$.

Observe that being $1$-locally dense does not depend on the orientation of the
graph (and the set $X$ plays no role in this case), i.e., being $1$-locally
dense is a pseudorandom property that depends only on the underlying graph
$G$. By Chernoff’s inequality, any orientation of $G(n,p)$ is $1$-locally
dense with high probability, and one may think of this property as a
strengthening of the fact that $\alpha(G(n,p))\leqslant\frac{3\log n}{p}$.

###  2.3. Sketch of the proof

We will count separately the orientations which are $\ell$-locally dense and
the orientations which are not $r$-locally dense but are $(r-1)$-locally dense
for some $2\leqslant r\leqslant\ell$. To count the
$C^{\circlearrowright}_{\ell+2}$-free, $\ell$-locally dense orientations
$\vec{G}$ (see Lemma 3.6 (ii)), we proceed similarly to the proof in
[CoKoMoMo20]: let $v\in V$, put $H=G\setminus\\{v\\}$, and let $\vec{H}$ be
the restriction of $\vec{G}$ to $H$. Moreover, let $\vec{T}\subset
E(\vec{G})\setminus E(\vec{H})$ be minimal such that $\vec{G}$ is the only
$C^{\circlearrowright}_{\ell+2}$-free orientation of $G$ containing
$\vec{T}\cup\vec{H}$. Note that, since we are avoiding copies of
$C^{\circlearrowright}_{\ell+2}$, the sets $T^{+}:=N^{+}_{\vec{T}}(v)$ and
$T^{-}:=N^{-}_{\vec{T}}(v)$ are independent sets in $\vec{H}^{\ell}$ by
minimality of $\vec{T}$. Since $\vec{G}$ is $\ell$-locally dense, the edge
density of $\vec{H}^{\ell}$ is at least of order $p^{1/\ell}$. This allows us
to prove that the largest independent set in $N_{G}(v)$ has size roughly
$(\log n)/p^{1/\ell}$, which will be enough to finish the proof of this case
using the graph container lemma.

To count orientations $\vec{G}$ that are not $r$-locally dense but are
$(r-1)$-locally dense (see Lemma 3.6 (i)), we use the fact that there are
“large” disjoint sets $A^{\prime},B\subset V$ and $A\subset A^{\prime}$, with
$|A|\geqslant|A^{\prime}|/2$, such that for every $a\in A$ it holds that
$\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar
382\relax$}}}}_{\vec{G}^{r}}(a,B)<p^{\frac{\ell-r+1}{\ell}}|B|$, where
$\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}(a,B)$ denotes
$d^{+}(a,B)+d^{-}(a,B)$ (for simplicity, in this outline we assume the set $X$
in (4) is empty). Put $\vec{H}=\vec{G}\setminus A$ and note that, since
$\vec{G}$ is $(r-1)$-locally dense, $\vec{H}^{r-1}$ has “many” edges between
any two “sufficiently large” sets222Note that we want
$\vec{H}^{r-1}=(\vec{G}\setminus A)^{r-1}$ to have many edges between pairs of
sets. This does not directly follow from $\vec{G}$ being $(r-1)$-locally-
dense, because many $(r-1)$-paths could pass through $A$. The set $X$ in the
definition of $r$-locally-dense graphs is used to handle this issue..

Now given $a\in A$ we may choose $S^{+}\subset V(H)\cap N_{\vec{G}}^{+}(a)$,
the set of all $v\in N_{\vec{G}}^{+}(a)$ such that

$d^{+}_{\vec{H}^{r-1}}(v,B)\geqslant\frac{1}{4}\cdot
p^{\frac{\ell-r+2}{\ell}}|B|$

and $S^{-}\subset V(H)\cap N_{\vec{G}}^{-}(a)$, the set of all $a\in
N_{\vec{G}}^{-}(a)$ such that

$d^{-}_{\vec{H}^{r-1}}(v,B)>\frac{1}{4}\cdot p^{\frac{\ell-r+2}{\ell}}|B|.$

We claim that $|S^{+}|+|S^{-}|\leqslant 4p^{-1/\ell}$. Indeed, every $v\in
S^{+}\cup S^{-}$ corresponds to at least $p^{\frac{\ell-r+2}{\ell}}|B|/4$
paths of length $r$ starting with the edge $av$ or ending with the edge $va$,
so if $|S^{+}|+|S^{-}|>4p^{-1/\ell}$ then
$\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{\vec{G}^{r}}(a,B)$
would be too large. Moreover, we are able to use the randomness of $G$ to show
that $S^{+}$ and $S^{-}$ determine the orientation of all but a very small
number of edges of $G$ between $a$ and $V(H)$.

##  3\. The main result

In this section our goal is to count orientations of $G(n,p)$ containing no
copies of $C^{\circlearrowright}_{\ell+2}$. We prove the following result,
which implies Theorem 1.2.

######  Theorem 3.1.

Let $\ell,n\in\mathbb{N}$ and $0<p\leqslant(2^{7}\ell)^{-\ell}$. With high
probability $G(n,p)$ admits at most

$\exp\left(\frac{13\ell n(\log n)^{2}}{p^{1/\ell}}\right)$

$C^{\circlearrowright}_{\ell+2}$-free orientations.

We present the proof of Theorem 3.1 (assuming the validity of Lemma 3.6, which
will be proved in Sections 4 and 5) at the end of the section. Throughout the
rest of the paper, $\ell$, $n$ and $p$ will be fixed, all graphs will have
vertex set contained in $[n]$, and we set

$\alpha:=2^{6}(\log n)/p.$

For any oriented graph $\vec{G}$, its underlying undirected graph will be
denoted by $G$. We recall other useful notation introduced in Section 2: Given
a graph $\vec{G}$, the digraph $\vec{G}^{r}$ contains the edge $(u,v)$
precisely whenever there is an oriented path of length $r$ starting at $u$ and
ending at $v$ in $\vec{G}$. Moreover, $\vec{G}\setminus X$ is a shorthand for
$\vec{G}[V(G)\setminus X]$, and, for disjoint sets $A,B\subset V(G)$,
$\stackon[-5.2pt]{e}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{\vec{G}}(A,B)$ denotes
the number of edges between $A$ and $B$ (in either direction) in $\vec{G}$.

The following definition will be used to “encode” orientations of
$C^{\circlearrowright}_{\ell+2}$-free graphs.

######  Definition 3.2.

Given $1\leqslant r\leqslant\ell$, an oriented graph $\vec{G}$ is _$r$
-locally dense_ if for every pairwise disjoint sets $A^{\prime}$, $B$, $X$ of
$V(G)$ such that

$|A^{\prime}|=\alpha,\qquad
r\alpha\leqslant|B|\leqslant\ell\alpha,\qquad\text{and}\qquad|X|\leqslant(\ell+1-r)\alpha,$
(5)

we have

$\stackon[-5.2pt]{e}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{G}\setminus
X)^{r}}(A^{\prime},B)\geqslant\frac{1}{2}\cdot
p^{\frac{\ell-r+1}{\ell}}|A^{\prime}||B|.$ (6)

Otherwise, the orientation $\vec{G}$ is called _$r$ -locally-sparse_.

Even though the following lemma is a trivial application of Chernoff’s
inequality together with the fact that the definition of $1$-locally-dense
depends solely on the underlying undirected graph and not on the orientation
of the edges, it will be crucial.

######  Lemma 3.3.

With high probability every orientation of $G(n,p)$ is $1$-locally-dense.

Given a graph $G$ and an induced subgraph $H$ of $G$, an orientation $\vec{G}$
of $G$ is an _extension_ of an orientation $\vec{H}$ of $H$ if
$E(\vec{H})\subset E(\vec{G})$. Furthermore, we say that $\vec{G}$ _extends_
$\vec{H}$. Due to Lemma 3.3, in the rest of the paper we count $1$-locally-
dense $C^{\circlearrowright}_{\ell+2}$-free orientations.

######  Definition 3.4.

Let $G=(V,E)$ be a graph and let $\vec{H}$ be an orientation of an induced
subgraph $H$ of $G$. We denote by $\mathcal{D}_{r}(G,\vec{H})$ (resp.
$\mathcal{S}_{r}(G,\vec{H})$) the set of all $1$-locally-dense,
$C^{\circlearrowright}_{\ell+2}$-free orientations of $G$ that extend
$\vec{H}$ and are $r$-locally-dense (resp. $r$-locally-sparse). For
convenience, we also write $\mathcal{D}_{r}(G)$ for
$\mathcal{D}_{r}(G,\emptyset)$ and $\mathcal{S}_{r}(G)$ for
$\mathcal{S}_{r}(G,\emptyset)$.

In view of Lemma 3.3 and using the language described in Definition 3.4, our
goal is to prove that $|\mathcal{D}_{1}(G(n,p))|\leqslant\exp\big{(}13\ell
n(\log n)^{2}/p^{1/\ell}\big{)}$ holds with high probability.

Note that if $\vec{G}\in\mathcal{S}_{r}(G)$, then there exist pairwise
disjoint sets $A^{\prime}$, $B$ and $X$ of $V(G)$ satisfying (5) such that (6)
fails to hold. This fact implies the existence of $A\subset A^{\prime}$ with
$|A|=|A^{\prime}|/2$ such that
$\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{G}\setminus
X)^{r}}(a,B)\leqslant p^{\frac{\ell-r+1}{\ell}}|B|$ for every $a\in A$. This
motivates the following definition, where $H$ will play the role of
$G\setminus A$. Recall that $\alpha=2^{6}(\log n)/p$.

######  Definition 3.5.

Let $H$ be a graph, $A\subset[n]\setminus V(H)$ and let $B$ and $X$ be
disjoint subsets of $V(H)$. The quadruple $(A,H,B,X)$ is an _$r$ -frame_ if

$|A|=\alpha/2,\qquad
r\alpha\leqslant|B|\leqslant\ell\alpha,\qquad\text{and}\qquad|X|\leqslant(\ell+1-r)\alpha.$

Given an an $r$-frame $(A,H,B,X)$, an orientation $\vec{H}$ of $H$, and a
graph $G$ with $A=V(G)\setminus V(H)$, an orientation $\vec{G}$ of $G$ is said
to be an _$(r,B,X)$ -sparse extension_ of $\vec{H}$ if it holds that
$\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{G}\setminus
X)^{r}}(a,B)\leqslant p^{\frac{\ell-r+1}{\ell}}|B|$ for every $a\in A$.

We let $\mathcal{S}_{r}(G,\vec{H},B,X)$ denote the set of all orientations of
$\vec{G}$ that are $(r,B,X)$-sparse extensions of $\vec{H}$. Observe that we
have

$\mathcal{S}_{r}(G)=\bigcup_{(A,B,X)}\bigcup_{\vec{H}\in\mathcal{D}_{1}(G\setminus
A)}\mathcal{S}_{r}(G,\vec{H},B,X),$ (7)

where the first union is over all $(A,B,X)$ such that $(A,G\setminus A,B,X)$
is an $r$-frame.

Given a graph $H$ and a set $A$ disjoint from $V(H)$, we define $G(A,H,p)$ as
the random graph $G$ on vertex set $V(G)=A\cup V(H)$ such that $G[V(H)]=H$ and
such that each element of $\binom{V(G)}{2}\setminus\binom{V(H)}{2}$ is present
in $E(G)$ with probability $p$ independently at random. We are now ready to
state the main tool for the proof of Theorem 3.1, consisting of two bounds on
the expected number of extensions of a digraph $\vec{H}$. Its proof is
postponed to Sections 4 and 5.

######  Lemma 3.6.

Let $\vec{H}$ be an oriented graph and $A\subset[n]\setminus V(H)$ of size
$\alpha/2$. The following holds for $G=G(A,H,p)$.

  1. $(i)$

If $2\leqslant r\leqslant\ell$ and $B,X\subset V(H)$ are such that $(A,H,B,X)$
is an $r$-frame, then

$\mathbb{E}\left[\big{|}\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)\big{|}\right]\leqslant\exp\left(9\alpha
p^{-\frac{1}{\ell}}\log n\right).$

  2. $(ii)$

$\mathbb{E}\left[\big{|}\mathcal{D}_{\ell}(G,\vec{H})\big{|}\right]\leqslant\exp\left(\alpha(\ell+2)p^{-\frac{1}{\ell}}(\log
n)^{2}\right).$

Before proving Theorem 3.1, we state a simple probabilistic estimate which
will be used a few times throughout the paper.

######  Lemma 3.7.

Let $0\leqslant p\leqslant 1$ and $C>0$. If $S_{p}$ is a $p$-random subset of
a finite set $S$, then

$\mathbb{E}\left[C^{|S_{p}|}\right]\leqslant e^{Cp|S|}.$

###### Proof.

Since $\mathbb{P}(|S_{p}|=t)\leqslant\big{(}p|S|\big{)}^{t}/t!$ for every
$t\geqslant 0$, we can compute

$\mathbb{E}[C^{|S_{p}|}]\leqslant\sum_{t=0}^{\infty}\frac{\big{(}Cp|S|\big{)}^{t}}{t!}=e^{Cp|S|},$

as claimed. ∎

We are ready to prove Theorem 3.1.

###### Proof of Theorem 3.1.

Recall that $n$ is fixed, and put
$z:=\exp\big{(}4(\ell+2)p^{-\frac{1}{\ell}}(\log n)^{2}\big{)}$. We will show
by induction on $n^{\prime}\leqslant n$ that

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime},p))\big{|}\Big{]}\leqslant
z^{n^{\prime}},$ (8)

which together with Lemma 3.3 and Markov’s inequality implies the desired
result since $4(\ell+2)\leqslant 12\ell$. Note that if $n^{\prime}\leqslant
p^{-1-1/\ell}(\log n)^{2}$ holds, then an application of Lemma 3.7 gives

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime},p))\big{|}\Big{]}\leqslant\mathbb{E}\Big{[}2^{e(G(n^{\prime},p))}\Big{]}\leqslant\exp\Big{(}p(n^{\prime})^{2}\Big{)}\leqslant
z^{n^{\prime}}.$

Therefore, we may assume $n^{\prime}>p^{-1-1/\ell}(\log n)^{2}$, which implies
$p\gg(\log n)/n$. We claim that it is enough to prove that

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime},p))\big{|}\Big{]}\leqslant
z^{\alpha/2}\cdot\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime}-\alpha/2,p))\big{|}\Big{]}.$
(9)

Indeed, by (9) and the induction hypothesis we obtain

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime},p))\big{|}\Big{]}\leqslant
z^{\alpha/2}\cdot\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime}-\alpha/2,p))\big{|}\Big{]}\leqslant
z^{\alpha/2}\cdot z^{n^{\prime}-\alpha/2}=z^{n^{\prime}},$

which proves (8). Thus, the remainder of the proof is dedicated to showing
that (9) holds. Let $G=G(n^{\prime},p)$ and notice that, since every
$1$-locally-dense orientation is either $\ell$-locally dense or admits a
minimal $2\leqslant r\leqslant\ell$ for which it is $r$-locally sparse, we
have

$\mathcal{D}_{1}(G)=\mathcal{D}_{\ell}(G)\;\cup\;\bigcup_{r=2}^{\ell}\,\,(\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G)).$
(10)

Thus, it suffices to bound the expected sizes of the sets in the right-hand
side of (10). Let $A\subset V(G)$ be an arbitrary set of size $\alpha/2$, and
let $H=G\setminus A$ and $F$ be the graph with $V(F)=V(G)$ and
$E(F)=E(G)\setminus\binom{V(H)}{2}$. Observe that $F$ and $H$ are independent.
Therefore,

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{\ell}(G)\big{|}\Big{]}=\mathbb{E}_{H}\Bigg{[}\mathbb{E}_{F}\Big{[}\sum_{\vec{H}}\big{|}\mathcal{D}_{\ell}(G,\vec{H})\big{|}\;\Big{|}\;H\Big{]}\Bigg{]}=\mathbb{E}_{H}\Bigg{[}\sum_{\vec{H}}\mathbb{E}_{F}\Big{[}\big{|}\mathcal{D}_{\ell}(G,\vec{H})\big{|}\;\Big{|}\;H\Big{]}\Bigg{]},$
(11)

where the sums are over $\vec{H}\in\mathcal{D}_{1}(H)$. Conditioned on $H$
(that is, on $G\setminus A=H$), the distribution of $F\cup H$ is the same as
$G(A,H,p)$. Then, from Lemma 3.6(ii) we obtain

$\mathbb{E}_{F}\Big{[}\big{|}\mathcal{D}_{\ell}(G,\vec{H})\big{|}\;\Big{|}\;H\Big{]}\leqslant
z^{\alpha/4},$

and hence, by (11),

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{\ell}(G)\big{|}\Big{]}\leqslant\mathbb{E}_{H}\Bigg{[}\sum_{\vec{H}\in\mathcal{D}_{1}(H)}z^{\alpha/4}\Bigg{]}=z^{\alpha/4}\cdot\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime}-\alpha/2),p)\big{|}\Big{]}.$

To bound the expected sizes of the remaining sets of the right-hand side of
(10), we proceed analogously. For any $2\leqslant r\leqslant\ell$, using (7)
we have

$\displaystyle\mathbb{E}\Big{[}\big{|}\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G)\big{|}\Big{]}$
$\displaystyle\leqslant\;\mathbb{E}\;\Big{[}\sum_{(A,B,X)}\sum_{\vec{H}\in\mathcal{D}_{1}(H)}\big{|}\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)\big{|}\Big{]}$
$\displaystyle=\sum_{(A,B,X)}\mathbb{E}_{H}\Bigg{[}\sum_{\vec{H}\in\mathcal{D}_{1}(H)}\mathbb{E}_{F}\Big{[}\big{|}\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)\big{|}\;\Big{|}\;H\Big{]}\Bigg{]},$

where the first sums are over all triples $(A,B,X)$ such that $(A,H,B,X)$ is
an $r$-frame for $H=G\setminus A$. Since there are at most
$n^{(2\ell+1)\alpha}\leqslant z^{\alpha/4}$ such triples, an application of
Lemma 3.6(i) gives

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G)\big{|}\Big{]}\leqslant\sum_{(A,B,X)}\mathbb{E}_{H}\Bigg{[}\sum_{\vec{H}\in\mathcal{D}_{1}(H)}z^{\alpha/12}\Bigg{]}=z^{\alpha/3}\cdot\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime}-\alpha/2),p)\big{|}\Big{]}.$

By (10), we thus have

$\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime},p))\big{|}\Big{]}\leqslant\ell
z^{\alpha/3}\cdot\mathbb{E}\Big{[}\big{|}\mathcal{D}_{1}(G(n^{\prime}-\alpha/2,p))\big{|}\Big{]}$

which verifies (9) and concludes the proof of Theorem 3.1, since
$\ell\leqslant p^{-1/\ell}\leqslant z^{\alpha/6}$. ∎

##  4\. Extending locally-sparse orientations

The main goal of this section is to prove Lemma 3.6(i), which bounds the
expected number of $(r-1)$-locally dense, $(r,B,X)$-sparse extensions of an
oriented graph $\vec{H}$. The deterministic part of the proof is the following
proposition. We remark that, although we intentionally state the result in a
way that emphasises its container-type nature, its proof does not use the
Hypergraph Container Lemma.

######  Proposition 4.1.

Let $\vec{H}$ be an oriented graph and $2\leqslant r\leqslant\ell$. If
$(A,H,B,X)$ is an $r$-frame, then there exists a family $\mathcal{C}$ of
digraphs on vertex set $A\cup V(H)$ such that

  1. $(i)$

For every graph $G$ with $V(G)=A\cup V(H)$ and every orientation
$\vec{G}\in\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)$, there
exists some $\vec{C}\in\mathcal{C}$ such that $E_{\vec{G}}(A,V(H))\subset
E(\vec{C})$.

  2. $(ii)$

For every $\vec{C}\in\mathcal{C}$, at most $\ell\alpha^{2}$ pairs
$\\{u,v\\}\subset V(\vec{C})$ satisfy $\\{uv,vu\\}\subset E(\vec{C})$,

  3. $(iii)$

$|\mathcal{C}|\leqslant\exp(4\alpha p^{-1/\ell}\log n)$.

###### Proof of Proposition 4.1.

The proof loosely follows the idea behind the proof of the Kleitman–Winston
graph container lemma. We will describe an algorithm which takes as input a
fixed graph $G$ on vertex set $A\cup V(H)$ and an orientation
$\vec{G}\in\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,H,B,X)$, and outputs a
bipartite digraph $\vec{C}$ with parts $A$ and $V(H)$ trivially satisfying
properties (i) and (ii). Along with $\vec{C}$, the algorithm will output a
special subgraph $\vec{T}\subset\vec{C}$, called a _fingerprint_ , which will
be useful for proving (iii).

Recall that $\alpha=2^{6}(\log n)/p$. Recall also, from the definition of
$r$-frame, that $A\subset[n]\setminus V(H)$, that $B,X\subset V(H)$ are
disjoint and that

$|A|=\alpha/2,\qquad
r\alpha\leqslant|B|\leqslant\ell\alpha,\qquad\text{and}\qquad|X|\leqslant(\ell+1-r)\alpha.$

Let $L=|V(H)|-|B|-|X|-\alpha$ and observe that we may assume $L\geqslant 0$,
since otherwise $|V(H)|<|B|+|X|+\alpha\leqslant 2\ell\alpha$ and therefore it
would suffice to take $\mathcal{C}=\\{\vec{C}\\}$, where $\vec{C}$ is the
complete bipartite digraph between $A$ and $V(H)$. We are ready to present
Algorithm 1 (Encode).

Input : an extension $\vec{G}$ of $\vec{H}$ on vertex set $A\cup V(H)$

1 foreach  _$a\in A$_ do

2 $B_{0}$ $\leftarrow$ $B$

3 for  _$i\leftarrow 1\textrm{ to }L$_ do

4 pick $v_{i}\in V(H)\setminus(B\cup X\cup\\{v_{1},\ldots,v_{i-1}\\}$)
maximising $\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(\,\cdot\,,B_{i-1})$, with ties broken canonically

5 if  _$\big{|}N^{+}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})\big{|}\geqslant\frac{1}{2}\big{|}N_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})\big{|}$_ then

6 $e_{i}$ $\leftarrow$ $av_{i}$

7 else

8 $e_{i}$ $\leftarrow$ $v_{i}a$

9 if  _$e_{i}\in E(\vec{G})$_ then

10 add the edge $e_{i}$ to $\vec{T}$ and to $\vec{C}$

11 $B_{i}$ $\leftarrow$ $B_{i-1}\setminus N_{(\vec{H}\setminus
X)^{r-1}}(v_{i})$

12 else

13 add the edge $\operatorname{reverse}(e_{i})$ to $\vec{C}$, where
$\operatorname{reverse}(uw)=wu$

14 $B_{i}$ $\leftarrow$ $B_{i-1}$

15

16 foreach  _$v\in V(H)\setminus\\{v_{1},\ldots,v_{L}\\}$_ do

17 add the edges $av$ and $va$ to $\vec{C}$

18

return _$\vec{T}$ and $\vec{C}$_

Algorithm 1 Encode: A container-like algorithm for
$C^{\circlearrowright}_{\ell+2}$-free extensions of $\vec{H}$

We will denote the outputs of $\textsc{Encode}(\vec{G})$ by $\vec{T}(\vec{G})$
and $\vec{C}(\vec{G})$, respectively. Define

$\mathcal{C}=\left\\{\,\vec{C}(\vec{G}):\vec{G}\in\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)\,\right\\}.$
(12)

Observe that, for every extension $\vec{G}$ of $\vec{H}$, it holds that
$E(\vec{T})\subset E_{\vec{G}}(A,V(H))$, since edges are only added to
$\vec{T}$ in line 1. Moreover, whenever $e_{i}=uw$ is added to $\vec{C}$ in
line 1, it holds that $wu\not\in E(\vec{G})$, and therefore
$E_{\vec{G}}(A,V(H))\subset E(\vec{C})$, verifying property (i). Similarly,
property (ii) holds because, for every $a\in A$, the loop in line 1 adds
$|V(H)|-L\leqslant 2\ell\alpha$ pairs of antiparallel edges to $\vec{C}$ by
the choice of $L$, and the other places in which $\vec{C}$ is modified (lines
1 and 1) add edges in one direction only.

Showing that $\mathcal{C}$ satisfies property (iii) will require the most
amount of work. The intuition for it (which will be formalised in Claim 4.3)
is easy to describe, however: the if-statement in lines 1–1 determines the
orientation of $\\{a,v_{i}\\}$ that “extends the majority of $(r-1)$-paths”
with one endpoint in $B_{i}$ to $r$-paths. If this directed edge is in
$\vec{G}$, it is added to $\vec{T}$. Therefore, if the input $\vec{G}$ is
$(r-1)$-locally-dense, each edge added to $\vec{T}$ extends
$\Omega(p^{\frac{\ell-r+2}{\ell}}|B|)$ $(r-1)$-paths of $\vec{H}$ to $r$-paths
of $\vec{G}$. Since $\vec{G}$ is an $(r,B,X)$-sparse extension of $\vec{H}$,
however, there can be at most $O(p^{\frac{\ell-r+1}{\ell}}|B|)$ $r$-paths
starting or ending at a given $a\in A$. Therefore, at most $O(p^{-1/\ell})$
edges can be added to $\vec{T}$ in line 1 for each $a\in A$. Since $\vec{T}$
determines $\vec{C}$ (Claim 4.2), this implies that there are few choices for
$\vec{C}$.

We start the formal proof of (iii) by showing that, given an oriented graph
$\vec{H}$ and an $r$-frame $(A,H,B,X)$, one of the outputs of the algorithm,
$\vec{C}$, is determined by the other.

######  Claim 4.2.

Let $\vec{G}_{1}$ and $\vec{G}_{2}$ be extensions of $\vec{H}$ on vertex set
$A\cup V(H)$. If $\vec{T}(\vec{G}_{1})=\vec{T}(\vec{G}_{2})$, then
$\vec{C}(\vec{G}_{1})=\vec{C}(\vec{G}_{2})$ (even if the underlying graphs
$G_{1}$ and $G_{2}$ differ).

###### Proof.

Line 1 is the only time at which the algorithm examines edges outside $V(H)$.
Therefore, if $\vec{C}(\vec{G}_{1})\neq\vec{C}(\vec{G}_{2})$, we may suppose
without loss of generality there exists $a\in A$ and $1\leqslant i\leqslant L$
such that $e_{i}\in E(\vec{G}_{1})$ and $e_{i}\not\in E(\vec{G}_{2})$. If $i$
is minimal with this property, then $e_{i}$ is the same in both executions,
but then $e_{i}$ is added to $\vec{T}(\vec{G}_{1})$ and not added to
$\vec{T}(\vec{G}_{2})$, contradicting the fact that
$\vec{T}(\vec{G}_{1})=\vec{T}(\vec{G}_{2})$. ∎

If the extension $\vec{G}$ of $\vec{H}$ given as input to Encode is not
restricted, then it is possible for the graph $\vec{T}$ to have many edges.
Roughly speaking, the following claim shows this cannot happen when
$\vec{G}\in\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)$. In other
words, for these digraphs, $\vec{T}$ can be thought of as an “efficient
encoding” of most of the edges of $E_{\vec{G}}(A,V(H))$.

######  Claim 4.3.

Let $\vec{G}\in\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)$. If
$\vec{T}=\vec{T}(\vec{G})$ is the fingerprint output by Encode with input
$\vec{G}$, then $d_{\vec{T}}(a)\leqslant 4p^{-1/\ell}$ for every $a\in A$.

###### Proof.

Fix $a\in A$, and let $S$ be the set of values of $i\in[L]$ for which lines 1
and 1 of the algorithm are executed (that is, for which $e_{i}\in
E(\vec{G})$). Observe that $|S|=d_{\vec{T}}(a)$, since only line 1 adds edges
to $\vec{T}$. Therefore, our goal is to upper bound $|S|$. We claim that

$\frac{1}{2}\sum_{i\in
S}\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})\leqslant\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{G}\setminus
X)^{r}}(a,B)\leqslant p^{(\ell-r+1)/\ell}|B|.$ (13)

Indeed, the second inequality follows directly from the assumption that
$\vec{G}\in\mathcal{S}_{r}(G,\vec{H},B,X)$. To see the first inequality, let
$S^{+}\subset S$ be those values of $i$ for which $d^{+}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})\geqslant\frac{1}{2}\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})$ (see line 1), let $S^{-}=S\setminus S^{+}$, and
define

$N_{i}=\begin{cases}N^{+}_{(\vec{H}\setminus X)^{r-1}}(v_{i},B_{i-1})&\text{if
}i\in S^{+}\\\ N^{-}_{(\vec{H}\setminus X)^{r-1}}(v_{i},B_{i-1})&\text{if
}i\in S^{-}.\end{cases}$

Then $N_{i}\subset N_{(\vec{G}\setminus X)^{r}}(a,B)$, since we can use the
edge $e_{i}$ to extend an $(r-1)$-path starting or ending at $v_{i}$ to an
$r$-path starting or ending at $a$. Moreover, since $N_{i}\subset B_{i-1}$ by
definition and $N_{j}\cap B_{i-1}=\emptyset$ if $j<i$ by line 1, the family
$\\{N_{i}:i\in S\\}$ is pairwise disjoint. Therefore, $\sum_{i\in
S}|N_{i}|\leqslant\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{G}\setminus
X)^{r}}(a,B)$. Since
$|N_{i}|\geqslant\frac{1}{2}\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})$ by line 1 (that is, by the condition used to decide
whether an $i\in S$ is in $S^{+}$ or $S^{-}$), we obtain (13).

We will obtain an upper bound on $|S|$ by lower bounding the terms in the
left-hand side sum of (13), which will use the assumption that
$\vec{G}\in\mathcal{D}_{r-1}(G)$. To do so, recall that $v_{i}$ was chosen in
line 1 to maximise
$f(x)=\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(x,B_{i-1})$ on $V_{i}\coloneqq V(H)\setminus(B\cup
X\cup\\{v_{1},\ldots,v_{i-1}\\})$ and note that $|V_{i}|\geqslant\alpha$.
Thus, let $A^{\prime}$ be any subset of $V_{i}$ with $v_{i}\in A^{\prime}$ and
$|A^{\prime}|=\alpha$ and observe that $\vec{H}\setminus
X=\vec{G}\setminus(X\cup A)$. Then, we have

$\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})\geqslant\frac{1}{|A^{\prime}|}\cdot
e_{(\vec{G}\setminus(X\cup A))^{r-1}}(A^{\prime},B_{i-1}).$ (14)

We want to use the hypothesis $\vec{G}\in\mathcal{D}_{r-1}(G)$ to bound the
right-hand side of (14). For that, from Definition 3.2, we need that
$|A^{\prime}|=\alpha$, $(r-1)\alpha\leqslant|B_{i-1}|\leqslant\ell\alpha$, and
$|X\cup A|\leqslant(\ell+2-r)\alpha$. It suffices to show that
$|B_{i-1}|\geqslant(r-1)\alpha$, since the other bounds hold trivially. We
observe that $|B_{0}|=|B|$ and, for every $i\in[L]$,

$|B_{i-1}|-|B_{i}|=\begin{cases}\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})&\text{if }i\in S\\\ 0&\text{if }i\in[L]\setminus
S,\end{cases}$

by lines 1 and 1. Therefore, summing and using (13), we obtain

$|B_{L}|\geqslant|B|-\sum_{i\in
S}\stackon[-5.2pt]{d}{\,\smash{\stackon[-2.35pt]{\mathchar
382\relax}{\rotatebox{180.0}{$\mathchar 382\relax$}}}}_{(\vec{H}\setminus
X)^{r-1}}(v_{i},B_{i-1})\geqslant|B|-2p^{(\ell-r+1)/\ell}|B|.$

Since $p\leqslant\left(2\ell\right)^{-\ell}$, we have
$|B_{i-1}|\geqslant|B_{L}|\geqslant(1-1/\ell)|B|$. In particular,
$|B_{i-1}|\geqslant(r-1)\alpha$, as claimed. Therefore, the condition in
Definition 3.2 tells us that

$e_{(\vec{G}\setminus(X\cup
A))^{r-1}}(A^{\prime},B_{i-1})\geqslant\frac{1}{2}\cdot
p^{(\ell-r+2)/\ell}|A^{\prime}||B_{i-1}|.$ (15)

Combining (14) and (15), plugging the resulting bound into (13) and using that
$|B_{i-1}|\geqslant|B_{L}|$, we obtain that

$\frac{|S|}{2}\cdot p^{(\ell-r+2)/\ell}\cdot|B_{L}|\leqslant
p^{(\ell-r+1)/\ell}|B|,$

As we have already shown that $|B_{L}|\geqslant|B|/2$, we obtain that
$d_{\vec{T}}(a)=|S|\leqslant 4p^{-1/\ell}$, as claimed. ∎

We have already seen that the collection $\mathcal{C}$, defined in (12),
satisfies the claimed properties (i) and (ii), and we are now ready to prove
(iii). Let

$\mathcal{T}=\left\\{\,\vec{T}(\vec{G}):\vec{G}\in\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)\,\right\\}$

and notice that by Claim 4.2 we have $|\mathcal{C}|=|\mathcal{T}|$. Moreover,
Claim 4.3 implies that

$|\mathcal{T}|\leqslant\Bigg{(}\sum_{i=0}^{4p^{-1/\ell}}\binom{n}{i}\Bigg{)}^{2|A|}\leqslant\exp\left(4\alpha
p^{-1/\ell}\log n\right),$

since to choose a $\vec{T}\in\mathcal{T}$ it suffices to choose
$N^{+}_{\vec{T}}(a)$ and $N^{-}_{\vec{T}}(a)$ for each $a\in A$. ∎

Having proved Proposition 4.1, we are now ready to deduce Lemma 3.6(i) from
Proposition 4.1.

###### Proof of Lemma 3.6(i).

Let $G=G(A,H,p)$, recalling that, by definition, we have $V(G)=A\cup V(H)$,
$G[V(H)]=H$ and each element of $\binom{V(G)}{2}\setminus\binom{V(H)}{2}$ is
an edge of $G$ with probability $p$ independently at random. Let
$\mathcal{O}=\mathcal{D}_{r-1}(G)\cap\mathcal{S}_{r}(G,\vec{H},B,X)$, and
recall that our goal is to bound the expected size of $\mathcal{O}$.

Let $\mathcal{C}$ be given by Proposition 4.1 and say an orientation
$\vec{G}\in\mathcal{O}$ is _compatible_ with a container
$\vec{C}\in\mathcal{C}$ if $E_{\vec{G}}(A,V(H))\subset E(\vec{C})$, and let
$D(\vec{C})$ be the set of pairs $\\{u,v\\}$ for which $\\{uv,vu\\}\subset
E(\vec{C})$. Given a container $\vec{C}\in\mathcal{C}$, let

$N(\vec{C})=|E(G)\cap(D(\vec{C})\cup(A\times A))|$

and observe that $2^{N(\vec{C})}$ is an upper bound on the number of
orientations $\vec{G}\in\mathcal{O}$ which are compatible with $\vec{C}$.
Moreover, by Proposition 4.1(i), every element of $\mathcal{O}$ is compatible
with at least one element of $\mathcal{C}$, and therefore

$|\mathcal{O}|\leqslant\sum_{\vec{C}\in\mathcal{C}}2^{N(\vec{C})}.$

We can take expectations on both sides and apply Lemma 3.7 to obtain

$\mathbb{E}\big{[}|\mathcal{O}|\big{]}\leqslant\sum_{\vec{C}\in\mathcal{C}}e^{2p\cdot(|D(\vec{C})|+|A\times
A|)}\leqslant\exp\left(8\alpha p^{-1/\ell}\log n+\ell p\alpha^{2}\right),$

where the last inequality uses Proposition 4.1(ii)–(iii) to bound
$|D(\vec{C})|$ and $|\mathcal{C}|$, respectively. Since $p\alpha=2^{6}\log n$
and $p\leqslant(2^{7}\ell)^{-\ell}$, we have $\ell p\alpha\leqslant
p^{-1/\ell}(\log n)/2$. Therefore,

$\mathbb{E}\big{[}|\mathcal{O}|\big{]}\leqslant\exp\left(9\alpha
p^{-1/\ell}\log n\right).$

This finishes the proof. ∎

##  5\. Extending locally-dense orientations

In this section we count the number of $\ell$-locally dense orientations. For
that we use the _graph container lemma_ , implicit in the work of Kleitman and
Winston [KlWi82] and explicitly stated by Sapozhenko [Sa01]. The version we
use can be found on a survey of Samotij [SamotijIndep].

######  Lemma 5.1 ([SamotijIndep]*Lemmas 1 and 2).

Let $G$ be a graph on $n$ vertices, an integer $q$ and reals
$0\leqslant\beta\leqslant 1$ and $R$ such that $R\geqslant e^{-\beta q}n$.
Suppose that every set $U\subset V(G)$ with $|U|\geqslant R$ satisfies

$e(G[U])\geqslant\beta\binom{|U|}{2}.$

Then there exists a collection $\mathcal{C}\subset\mathcal{P}(V(G))$ such
that:

  1. $(i)$

Every independent set of $G$ is contained in some $C\in\mathcal{C}$,

  2. $(ii)$

$|C|\leqslant R+q$ for every $C\in\mathcal{C}$,

  3. $(iii)$

$|\mathcal{C}|\leqslant\sum_{i=0}^{q}\binom{n}{i}$.

The following simple averaging result will be useful for applying the graph
container lemma in the proof of Lemma 3.6 (ii).

######  Lemma 5.2.

Let $\vec{G}$ be an $\ell$-locally-dense oriented graph. For every pair of
disjoint sets $U,~{}X\subset V(G)$ with $|U|\geqslant(\ell+1)\alpha$ and
$|X|=\alpha$, the graph $\vec{H}=\vec{G}\setminus X$ satisfies
$e(\vec{H}^{\ell}[U])\geqslant p^{1/\ell}\binom{|U|}{2}/(2\ell+2)$.

###### Proof.

Let $W$ be a random subset of $U$ of size $(\ell+1)\alpha$. By splitting $W$
arbitrarily into two sets of size $\alpha$ and $\ell\alpha$ and applying the
hypothesis that $\vec{G}$ is $\ell$-locally-dense, we see that

$e(\vec{H}^{\ell}[W])\geqslant\frac{p^{1/\ell}\cdot\ell\alpha^{2}}{2}\geqslant\frac{\ell
p^{1/\ell}}{(\ell+1)^{2}}\cdot\binom{|W|}{2}\geqslant\frac{p^{1/\ell}}{2(\ell+1)}\cdot\binom{|W|}{2}.$

On the other hand, the probability that an edge of $\vec{H}[U]$ is present in
$\vec{H}[W]$ equals $\binom{|W|}{2}/\binom{|U|}{2}$. Therefore,
$\mathbb{E}[e(\vec{H}[W])]=e(\vec{H}[U])\cdot\binom{|W|}{2}/\binom{|U|}{2}$,
and the result follows. ∎

We are now ready to estimate the expected number of $\ell$-locally dense
extensions of an oriented graph $\vec{H}$. Recall that we need to show that

$\mathbb{E}\left[\big{|}\mathcal{D}_{\ell}(G,\vec{H})\big{|}\right]\leqslant\exp\left(\alpha(\ell+2)p^{-\frac{1}{\ell}}(\log
n)^{2}\right).$

###### Proof of Lemma 3.6 (ii).

Given the random graph $G=G(A,H,p)$ and an orientation $\vec{H}$, we want to
find the expected size of $\mathcal{D}_{\ell}(G,\vec{H})$, that is, the
expected number of $C_{\ell+2}$-free, $\ell$-locally-dense extensions of
$\vec{H}$. We will follow the proof strategy from [CoKoMoMo20]. For each
orientation $\vec{G}$, let $\vec{T}=\vec{T}(\vec{G})$ be a minimal subset of
$E(\vec{G})\setminus E(\vec{H})$ such that $\vec{G}$ is the unique
$C^{\circlearrowright}_{\ell+2}$-free orientation of $G$ containing
$\vec{T}\cup E(\vec{H})$. For $a\in A$, let

$\vec{T}^{+}_{a}=\\{v\in V(H):av\in\vec{T}\\}.$

We claim that $\vec{T}^{+}_{a}$ is an independent set in $\vec{H}^{\ell}$.
Indeed, suppose there are $x,y\in\vec{T}^{+}_{a}$ such that $xy\in
E(\vec{H}^{\ell})$. Let $\vec{T}^{\prime}=\vec{T}\setminus\\{ay\\}$ and
observe that every orientation containing
$\vec{T}^{\prime}\cup\\{ya\\}\cup\vec{H}$ contains a $C_{\ell+2}$ of the form
$ax\vec{P}ya$ for some path $\vec{P}\subset\vec{H}$ of length $\ell$.
Therefore, any $C_{\ell+2}$-free orientation of $\vec{G}$ containing
$\vec{T}^{\prime}\cup\vec{H}$ also contains the edge $ay$, contradicting the
minimality of $\vec{T}$. By symmetry, the sets $\vec{T}^{-}_{a}$, defined
analogously for $a\in A$, are also independent sets in $\vec{H}^{\ell}$. With
this in mind, set

$\mathcal{T}_{1}=\big{\\{}\,\vec{T}(\vec{G})\setminus(A\times
A):\vec{G}\in\mathcal{D}_{\ell}(G,\vec{H})\,\big{\\}}.$

To bound $|\mathcal{T}_{1}|$ using the graph container lemma (Lemma 5.1), set

$\beta=\frac{p^{1/\ell}}{2(\ell+1)},\qquad q=\frac{2(\ell+1)\log
n}{p^{1/\ell}},\qquad R=(\ell+1)\alpha.$

Using Lemma 5.2, one can check that these constants satisfy the conditions of
Lemma 5.1, from which we obtain a family $\mathcal{C}$ of containers for the
independent sets of $\vec{H}^{\ell}$. Therefore, since $T^{+}_{a}$ and
$T^{-}_{a}$ are independent sets in $\vec{H}^{\ell}$ contained in $N_{G}(a)$
for each $a\in A$, we obtain

$|\mathcal{T}_{1}|\leqslant\prod_{a\in
A}\Big{(}\sum_{C\in\mathcal{C}}2^{|C\cap
N_{G}(a)|}\Big{)}^{2}\leqslant\prod_{a\in
A}\Big{(}|\mathcal{C}|\cdot\sum_{C\in\mathcal{C}}4^{|C\cap N_{G}(a)|}\Big{)},$
(16)

where the last inequality follows by convexity. On the other hand, it is clear
that the set $\mathcal{T}_{2}=\\{\vec{T}(\vec{G})\cap(A\times
A):\vec{G}\in\mathcal{D}_{\ell}(G,\vec{H})\\}$ satisfies

$|\mathcal{T}_{2}|\leqslant 3^{|E(G)\cap(A\times A)|}.$ (17)

Since $\vec{T}(\vec{G})$ uniquely determines an orientation
$\vec{G}\in\mathcal{D}_{\ell}(G,\vec{H})$ by definition, we can use linearity
of expectation and the fact that the exponents in (16) and (17) depend on
pairwise disjoint sets of edges of $G$ to obtain

$\mathbb{E}\big{[}|\mathcal{D}_{\ell}(G,\vec{H})|\big{]}\leqslant\mathbb{E}\big{[}3^{|E(G)\cap(A\times
A)|}\big{]}\cdot\prod_{a\in
A}\Big{(}|\mathcal{C}|\cdot\sum_{C\in\mathcal{C}}\mathbb{E}\Big{[}4^{|C\cap
N_{G}(a)|}\Big{]}\Big{)}$ (18)

By Lemma 5.1, we have

$|\mathcal{C}|\leqslant\sum_{i=0}^{q}\binom{n}{i}\leqslant\left(\frac{en}{q}\right)^{q}\leqslant
e^{q\log n}$

for every $a\in A$. Moreover, since $|C|\leqslant R+q\leqslant 2R$ for every
$C\in\mathcal{C}$, we can apply Lemma 3.7 and obtain

$\mathbb{E}\big{[}3^{|E(G)\cap(A\times A)|}\big{]}\leqslant
e^{3p|A|^{2}}\quad\text{and}\quad\mathbb{E}\Big{[}4^{|C\cap
N_{G}(a)|}\Big{]}\leqslant e^{8pR}\,.$

Plugging these bounds in (18) and recalling that $|A|=\alpha/2$,
$R=(\ell+1)\alpha$ and $q=2(\ell+1)p^{-1/\ell}\log n$, we have

$\displaystyle\mathbb{E}\big{[}|\mathcal{D}_{\ell}(G,\vec{H})|\big{]}$
$\displaystyle\leqslant\exp\Big{(}3p|A|^{2}+|A|(q\log n+8pR)\Big{)}$
$\displaystyle\leqslant\exp\Big{(}p\alpha^{2}+\alpha(\ell+1)p^{-1/\ell}(\log
n)^{2}+4p(\ell+1)\alpha^{2}\Big{)}$
$\displaystyle\leqslant\exp\Big{(}\alpha(\ell+2)p^{-1/\ell}(\log
n)^{2}\Big{)},$

where in the last inequality we used that $\ell p\alpha=o(p^{-1/\ell}(\log
n)^{2})$, a consequence of $p\alpha=2^{6}\log n$ and
$p\leqslant\left(2^{7}\ell\right)^{-\ell}$. This finishes the proof. ∎

##  6\. Concluding Remarks

This paper fits into the effort of understanding the number of $\vec{H}$-free
orientations of $G(n,p)$, and there is still much to be understood about this
problem. It is still an open problem to provide good estimates on $\log
D(G(n,p),\vec{H})$ when $\vec{H}$ is a strongly connected tournament with at
least $4$ vertices.

######  Conjecture 6.1.

Let $\vec{H}$ be a strongly connected tournament with $k:=v(H)\geqslant 4$ and
let $p\gg n^{-2/(k+1)}$. Then, with high probability,

$\log D(G(n,p),\vec{H})=\tilde{\Theta}\left(\frac{n}{p^{(k-1)/2}}\right).$

We remark that a more general version of Conjecture 6.1 appeared in
[CoKoMoMo20]. Coming back to the case studied in the present paper, there are
also several open problems when $\vec{H}$ is a directed cycle. We believe the
result in Theorem 3.1 can be tightened as in the following.

######  Conjecture 6.2.

If $p\gg n^{-1+1/(k-1)}$ then, with high probability,

$\log
D(G(n,p),C^{\circlearrowright}_{k})=\Theta\left(\frac{n}{p^{1/(k-2)}}+n\log
n\right).$

The lower bound for this conjecture was proved in [CoKoMoMo20], but the upper
bound is not known even in the case $k=3$. It would also be interesting to
understand the behaviour of $\log D(G(n,p),C^{\circlearrowright}_{k})$ as $k$
grows with $n$. It is not clear to us what should happen when $k\gg\log n$ for
instance.

##  7\. Acknowledgements

The research that led to this paper started at WoPOCA 2019, and we thank the
workshop organisers for a productive working environment. We would also like
to thank Rob Morris for helpful comments on previous drafts of this paper.

## References