Template-assisted growth of silver nanowires by electrodeposition

Kumaresh K R1,2, Lakshman Neelakantan2,3#, Parasuraman Swaminathan1,3*

1Electronic Materials and Thin Films Lab,

2Corrosion Engineering and Materials Electrochemistry Laboratory,

3Ceramics Technologies Group - Center of Excellence in Materials and

Manufacturing for Futuristic Mobility,

Dept. of Metallurgical and Materials Engineering,

Indian Institute of Technology, Madras, Chennai, India

#Email<EMAIL_ADDRESS>
*Email<EMAIL_ADDRESS>
## Abstract

Template-assisted synthesis is a facile way of growing various one-dimensional
nanostructures. Among various nanoporous templates, anodic aluminium oxide
(AAO) is most commonly used. In this work, the kinetics of silver nanowire
growth by electrodeposition in AAO templates was investigated. The AAO
templates were fabricated using the standard two-step anodisation process. The
geometrical features of the fabricated templates, such as pore diameter
($55.03\pm 6.36$ nm), interpore distance ($115.74\pm 6.52$ nm), wall thickness
($27.78\pm 3.4$ nm), porosity (19.87 %), and pore density ($9.12\times 10^{9}$
pores cm-2) were obtained using scanning electron microscopy. The oxide layer
at the bottom of the pores was modified by the barrier layer thinning process
and chemical etching in order to facilitate uniform metal deposition. This was
followed by pore widening to increase the diameter of the pores to $65.17\pm
7.68$ nm to enhance deposition. Interpore distance increased to $119.82\pm
5.91$ nm and wall thickness remained almost constant at $27.71\pm 2.13$ nm.
Silver was deposited using conventional electrodeposition in constant current
mode. Deposition parameters such as time, current, solution concentration, and
temperature were systematically investigated. For each deposition, the
efficiency of the process was calculated by considering the filling fraction
of the pores and the average length of the wires, all of which were measured
from the SEM images. A linear growth versus time was observed within the
parameter range. From the experiments, it was observed that decreasing the
current, increasing the deposition temperature, and depositing for longer
duration increased the average length of the nanowires. The use of
electrodeposition to grow metallic nanowires can be extended to other pure
metal and alloy systems.

Keywords: Silver nanowires; Anodic aluminium oxide; Electrodeposition;
Kinetics; Scanning electron microscopy;

##  1 Introduction

Silver nanowires are an important part of flexible optoelectronic devices[1].
They are primarily used as transparent electrodes and considered a viable
replacement for indium tin oxide (ITO)[2], especially for flexible
applications. Silver has one of the highest bulk conductivities among metals,
while the incomplete surface coverage (arising out of the percolation network
of nanowires in the deposit) makes the film optically transparent[3, 4].
Silver also possess good ductility, unlike ITO which is brittle (ceramic)[5].
The aspect ratio of silver nanowires is an important parameter to gauge its
efficiency as a transparent electrode. Shorter wires, i.e., smaller aspect
ratios, will reduce the transparency since a greater surface coverage is
needed to obtain good electrical conduction[4, 6]. On the other hand, longer
wires are difficult to deposit, especially through techniques such as
extrusion or inkjet printing[5]. Also, since the number of individual
junctions are small, surface adhesion issues can also arise in these long
wires. Silver nanowires in both pure and composite form are used
extensively[5, 7, 8, 9] for flexible optoelectronic devices and hence
researchers are devising new/general methods of synthesis and deposition.

The most commonly used technique for the synthesis of silver nanowires is the
polyol process[10, 11, 12, 13, 14]. This is a chemical reduction process,
which involves the reduction of silver from its salt (typically silver nitrate
or acetate) in the presence of a reducing agent. The same process is also used
to synthesize silver nanoparticles[15]. A surfactant, usually polyvinyl
alcohol (PVA), is also used to prevent the agglomeration of the individual
nanoparticles and wires. By properly controlling the concentration of the
surfactants it is possible produce directed growth, leading to the
preferential formation of nanowires. Various growth parameters, including
concentration, temperature, and pH need to be controlled in order to obtain
nanowires[11, 12]. The process is usually specific to silver and cannot be
directly extended to other noble metals, such as copper[16] or gold[17, 18],
which are also used in flexible electronics. Other techniques are also
available for the growth of silver nanowires, such as thermal evaporation[19].
However, this process is not controllable and hard to scale up for commercial
production. Template-assisted techniques are also available for nanowire
production[20, 21]. Silver nanowires have been synthesized using polymer
templates[22, 23]. Similarly, mesoporous silica has also been used to grow
silver nanowires[24]. Among the various template-assisted routes, anodic
aluminium oxide (AAO) is the most widely used route to fabricate one-
dimensional nanostructures.

Aluminium anodization is a popular technique to form a protective oxide film
on the surface. The two-step anodization process to produce highly ordered
hexagonal nanoporous alumina was reported in 1995 by Masuda and co-
workers[25]. After that, a variety of researchers have studied the effect of
anodization parameters such as voltage, temperature, electrolyte, and time on
the growth of AAO[26, 27]. AAO membranes, with their highly ordered nanopore
arrangement, typically serve as ideal templates for the formation of various
nanostructured materials[28, 29]. The method offers good control over shape,
size, and length of the wires. To deposit the wires, various processes exist,
including DC electrodeposition[30], pulsed electrodeposition[31], electroless
deposition[32] and, photo deposition[33]. Recently, we also demonstrated the
growth of copper nanowires in a AAO template using galvanic displacement[34].
In this work, electrodeposition is used to grow silver nanowires using a home-
grown AAO template. The effect of the deposition parameters on the length of
the nanowires have been studied and the process efficiency has also been
calculated. These results show that electrodeposition in AAO templates offers
a facile route to synthesize metallic nanowires.

##  2 Materials and methods

AAO templates were grown using the two-step anodization process, using the
procedure described in detail elsewhere[34]. To describe the process briefly,
strips of 99.99% pure aluminium were cut from a foil and then cleaned in
acetone, ethanol, and finally, deionized (DI) water. The foils were then
electropolished in a solution consisting of ethanol and perchloric acid
(HClO4). Electropolishing was carried out at 10 °C at a potential of 20 V for
60 s. Two-step anodization was then carried out on these electropolished
foils. In the first step, anodization was carried out in 0.3 M oxalic acid at
a voltage of 45 V. The electropolished template was the anode and a Pt gauze
was used as the inert cathode. Anodization was carried out for an hour at 20
°C. After the first anodization, chemical etching was carried out to etch away
the pores. The etchant solution used was a mixture of phosphoric and chromic
acid and the process was carried out at an elevated temperature of 60 °C.
Second anodization was carried out using the same conditions as the first
anodization, but for a duration of 2 h. The process produced mostly defect-
free pores which were parallel to each other. The new pores were grown from
the nucleation sites created from the first anodization and this helped
achieve a more uniform distribution of pores. Second anodization can be done
for a longer duration too, and the thickness of the AAO layer increases
linearly with time.

The as-produced nanoporous alumina channels produced by two-step anodization
are separated from the aluminium substrate by an oxide barrier layer[25].
Hence, for use of these channels for electrodeposition the barrier layer has
to be removed, which is carried out by a process called Barrier Layer Thinning
(BLT), developed by Furneaux et al.[35]. BLT leads to the formation of
branched cracks and openings at the template bottom, exposing the underlying
aluminium substrate. The process was immediately carried out after second
anodization and it involved the reduction of the applied voltage in a
regulated fashion to reduce the thickness of the barrier layer. From 45 V, the
voltage was brought down at a rate of 2 V min-1 till 29 V and then at a rate
of 1 V min-1 till 5 V. During the potential drop, the amount of electro-
generated Al3+ ions reduces and leads to lower oxide formation rate. On the
other hand, at the bottom of the pores, the micro-environments are still the
same and it leads to a higher dissolution rate and the barrier layer thins.
Post BLT, chemical pore widening was used to remove the barrier layer
completely. The process also causes a slight widening of the pores. Pore
widening was carried out in phosphoric acid at 20 °C for 45 min. The final
prepared template is now ready for nanowire deposition.

In this work, electrodeposition was carried out to deposit silver nanowires
inside the pores of the AAO template. The electrolyte prepared was a 0.05 M
silver nitrate solution, prepared by mixing silver nitrate and boric acid in
DI water. The contents are mixed using a magnetic stirrer for around 20 min.
The template was connected to the negative terminal and a platinum mesh to the
positive terminal. The source meter was adjusted to provide 5 mA constant
current, with a compliance of 20 V. To investigate the effect of the
deposition parameters on the length of the nanowires the following parameters
were varied: deposition time, applied current, solution concentration, and
bath temperature.

Post deposition, all samples were imaged by scanning electron microscopy (SEM)
in a FEI Quanta 400F instrument. Plan-view images were used to analyse the
pore dimensions, while cross sectional imaging was used to measure the length
of the deposited nanowires. Multiple images were recorded and analyzed to
obtain reliable statistics on the average nanowire lengths. Energy dispersive
spectroscopy (EDS) was used for qualitative elemental analysis.

##  3 Results and Discussion

###  3.1 AAO template characterization

In order to characterize the AAO templates SEM was carried out, before and
after pore widening. From an analysis of the images, the dimensions of the AAO
template were extracted. Representative SEM images of the AAO template, before
and after pore widening, are shown in figure 1. The extracted dimensions are
tabulated in table 1.

Figure 1: Representative SEM images of the AAO template (a) before and (b)
after pore widening. The dimensions of the template have been extracted by
analyzing similar SEM images of the templates and are tabulated in table 1.
Table 1: AAO template dimensions extracted from the SEM images, such as those
displayed in figure 1. Pore widening causes an increase in pore diameter and
porosity, while the pore areal density remains the same.
Parameter | After second anodization | After pore widening
---|---|---
Pore diameter (nm) | 55.03 $\pm$ 6.36 | 65.17 $\pm$ 7.68
Wall thickness (nm) | 27.78 $\pm$ 3.00 | 27.71 $\pm$ 2.13
Interpore distance (nm) | 115.74 $\pm$ 6.52 | 119.82 $\pm$ 5.91
Barrier layer thickness (nm) | 48 $\pm$ 3 | 48 $\pm$ 3
Porosity (%) | 19.87 | 26.36
Pore density (cm-2) | $9.12\times 10^{9}$ | $9.12\times 10^{9}$

The dimensions of the AAO template can be controlled by the anodization
potential, while the anodization time affects the overall length of the pores.
In these experiments the length of pores is approximately 30 $\mu$m for a
second anodization time of 2 h.

###  3.2 Kinetics of nanowire growth

Initial experiments were carried out to determine the effect of growth time on
the length of the electrodeposited wires. SEM images of the wires inside the
pores were taken for samples of different deposition times and representative
images for three different times are shown in figure 2. The individual wire
lengths are calculated using the ImageJ software, and an average length is
calculated for a particular deposition time. The SEM image of calculated wire
lengths are shown in figure 3. In order to confirm deposition of silver,
energy dispersive spectroscopy (EDS) was carried out in the SEM and it is
shown in figure 4.

Figure 2: SEM images of the silver nanowires within AAO template for different
growth times, (a) 20, (b) 40, and (c) 60 min. The overall nanowire length
increases with deposition time. Figure 3: Two representative measurements from
the 20 min deposition sample (15k magnification). The yellow lines drawn next
to the wires indicate their lengths. Similar measurements were carried out for
other images recorded for other deposition times. Figure 4: EDS data from the
silver nanowires within the AAO template. The Al signal is from the nanoporous
template, while the Ag is from the nanowires.

From the SEM images, nanowires lengths are extracted and the data is shown in
5. The data indicates a reaction-controlled growth rather than a diffusion-
controlled growth. The linear rate law corresponds to a surface reaction being
rate-limiting, the surface reaction possibly being the adsorption reaction of
hydrogen on the metal surface.

Figure 5: Plot of the nanowire length vs. deposition time. The plot is linear
indicating that growth is reaction-controlled rather than diffusion-
controlled.

###  3.3 Efficiency of the deposition process

It is important to estimate the efficiency of the electrodeposition process
since this can be used to calculate the amount of silver required for
synthesis of the nanowires. Two techniques have been used in this work to
estimate efficiency. One technique is based on the analysis of the SEM images
to calculate the lengths of the silver nanowires and from that estimate the
total volume of silver in a given area. Let $L_{av}$ denote the average length
of the silver nanowires and $L_{tot}$ be the total length of the nanowires.
Both can be measured from the SEM images. From the images, it is also possible
to find out the fraction of pores ($f$) that are filled. Under these
conditions, the ratio $f*(\nicefrac{{L_{av}}}{{L_{tot}}})$ is a measure of the
efficiency of the process. The efficiency values calculated by this technique
are listed in table 2.

Table 2: Efficiency calculations using the image analysis method. With this
method of calculation, an increasing trend in efficiency is seen because the
average length of the nanowires increases with time.
Deposition time (min) |  $L_{av}$ ($\mu$m) | $f$ | $f*(\nicefrac{{L_{av}}}{{L_{tot}}})$
---|---|---|---
20 | 1.61 | 0.57 | 0.027
30 | 1.77 | 0.54 | 0.028
40 | 2.41 | 0.55 | 0.039
50 | 2.59 | 0.54 | 0.042
60 | 2.92 | 0.55 | 0.048

From the table, we can conclude that the filling fraction is independent of
the time of deposition. Filling fraction is an indication of the nucleation of
the wires in the pores, and this happens wherever there is a seed layer
(substrate aluminium in this case). If $f$ does not depend on the deposition
time, it means that the initial nucleation is constant for a given electrolyte
concentration. One way to increase $f$ is to use a deposited seed layer such
as Cu or Ni so that silver nucleation happens in more of the pores. Similarly,
a different electrolyte can also help in increasing $f$. It should be noted
that the value of $f$ tabulated in table 2 is only a lower limit, since there
could be a number of pores where nucleation has occurred but not growth (and
hence, they could not be counted). Since $f$ is nearly the same in all cases
and $L_{avg}$ increases with time, the efficiency also increases in the same
fashion.

A more accurate and involved method of calculating efficiency is to consider
the electrochemical reactions in the system. This method involves comparing
the actual mass of silver deposited and the theoretical mass of silver that
should have been deposited from the electrolyte, in that time. To arrive at
this efficiency, SEM images were used to obtain values of interpore distance,
pore diameter, and other structural features. The volume of a single pore can
be found out using the pore diameter and the length of the pore, obtained from
the cross sectional view of the template, i.e. $V_{1}\;=\;\pi r^{2}L_{tot}$.
The product of the pore areal density and the area under consideration in the
SEM images gives the total number of pores in that area ($n$). The product,
$V_{1}\times n$, provides the total volume available for silver deposition.
The volume of silver actually deposited can be found using pore diameter and
the average length (for a particular deposition time) i.e. $V_{2}\;=\;\pi
r^{2}L_{av}nf$, where $f$ is the filling fraction for that particular
deposition time as described earlier. The product of $V_{2}$ with the mass
density of silver (10.49 gcm-3) gives the total mass of silver deposited in
that particular area. Given that the current is fixed during deposition, its
product with deposition time gives the total charge density. Using Faraday’s
law and the molar mass of silver (107.86 gmol-1), the theoretical mass of
silver that should be deposited can be calculated. The relationship is given
by

$m=\dfrac{QM}{Fz}$ (1)

where $m$ is the theoretical mass deposited, $Q$ is the total charge, $M$ is
the molar mass of silver, $F$ is Faraday constant (96485 Cmol-1) and $z$ is
the valency (1 for silver). The ratio of the theoretical mass that can be
deposited to the actual mass deposited is then the efficiency of the process.
The values generated are tabulated in table 3.

Table 3: Efficiency values using the electrochemistry method. The mass of
silver deposited shows an increasing trend while efficiency shows a decreasing
trend. The data is in contrast to that presented in table 2 which shows an
increasing efficiency with deposition time. This is because these calculations
take into account the effect of deposition time on the efficiency of the
process.
Deposition | Volume of | Charge | Mass of silver | Theoretical | Efficiency
---|---|---|---|---|---
time | silver deposited | supplied | deposited | mass |
(min) | ($\times 10^{-5}$ cm3) | (C) | (mg) | (mg) |
20 | 1.39 | 6 | 0.14 | 7 | 0.02
30 | 1.45 | 9 | 0.15 | 10 | 0.015
40 | 2.01 | 12 | 0.21 | 13 | 0.016
50 | 2.12 | 15 | 0.22 | 17 | 0.013
60 | 2.44 | 18 | 0.25 | 20 | 0.012

The data from table 3 shows a clear reverse to the trend obtained in table 2.
The method outlined here is more accurate since it is based on using Faraday’s
law as the benchmark in calculating the efficiency. The data also shows that
the efficiency decreases with increase in deposition time. One reason for this
could be a saturation limit of deposition as time increases though the plot in
figure 5 seems to indicate a linear growth regime (though the error bars
indicate large variations in the individual pores). More importantly, there
are competing reactions to silver reduction during deposition. Hydrogen
evolution could draw current away from silver deposition leading to a lowering
in efficiency with time.

###  3.4 Effect of deposition parameters

Various deposition parameters such as current, solution concentration,
temperature, and duration (at low current) were also investigated and the
final structures and efficiencies were evaluated. The normal current used
during deposition was 5 mA. Two other current values, 8 and 3 mA, were
evaluated. With larger current there was increased agitation in the bath due
to competing reactions such as hydrogen evolution. This caused the wires to
break up and hence the overall length and efficiency was lower. Lower current,
3 mA, was better in terms of wire length and efficiency though the fill factor
was slightly lowered, indicating that nucleation was probably affected. When
the concentration of silver in the solution was increased, deposition happened
at the openings, as seen in figure 6. Little deposition is seen in the pores
due to pore blocking but there is significant clustering at the top.

Figure 6: Silver deposited on top of the pores for 0.1 M silver concentration.
This non-uniform deposition is not suitable for nanowire deposition and hence
wire growth is favoured by low silver concentration.

Increasing the deposition temperature to 40 °C increases the length and the
efficiency has also slightly increased. This can be attributed to the
increased kinetics at elevated temperature. The slight increase in fill factor
can also be due to the improved nucleation in the pores. A combination of two
factors, long deposition time (2 h) and low current (3 mA), was also
investigated. While there was some increase in length the overall efficiency
was still the same as that observed earlier.

##  4 Conclusion

Home-grown templates were made using the two-step anodization process,
followed by BLT and pore widening. The template dimensions were uniform and
very close to the theoretical values. Electrodeposition was used to deposit
silver inside the pores. EDS confirmed the presence of silver deposition and
SEM images were used, along with ImageJ software, to analyse the images and
lengths of the wires. The variation in the length of the wires and the filling
fraction (and hence efficiency) of the process was studied by modifying
different experiment conditions. Increasing deposition time increases the
average length of the wires but filling fraction remains nearly the same.
Similarly, increasing the current leads to smaller wire lengths but greater
filling fraction and decreasing the current leads to the opposite trend.
Increasing the concentration of silver in the solution hinders deposition
because the aluminium layer at the bottom is not as conductive as the silver
deposited on top. Increasing the deposition temperature leads to longer wires
and slightly higher filling fraction. As future work, the effect of silver
complex such as silver thiocyanate (AgSCN) can be studied. Silver is released
more easily from complexes because of the lower activation energy. Similarly,
the solution can also be modified using additives such as suppressors,
brighteners, or hydrogen poisons. These can arrest the competing reaction of
hydrogen evolution and can enhance deposition of silver.

## Acknowledgments

Support from the Ceramics Technologies Group - Center of Excellence in
Materials and Manufacturing for Futuristic Mobility (project number
SB/2021/0850/MM/MHRD/008275) is acknowledged. SEM imaging was carried out at
the facility available in the Dept. of Chemical Engineering, IIT Madras.

## References

  * 1. Xiaoli Wu, Zhimin Zhou, Yuehui Wang, and Jingze Li.  Syntheses of silver nanowires ink and printable flexible transparent conductive film: A review.  Coatings, 10(9), 2020.
  * 2. Mohammad-Reza Azani, Azin Hassanpour, and Tomás Torres.  Benefits, problems, and solutions of silver nanowire transparent conductive electrodes in indium tin oxide (ito)-free flexible solar cells.  Advanced Energy Materials, 10(48):2002536, 2020.
  * 3. Haihua Zhou and Yanlin Song.  Fabrication of silver mesh/grid and its applications in electronics.  ACS Applied Materials & Interfaces, 13(3):3493–3511, 2021.
  * 4. Sophie Sorel, Philip E Lyons, Sukanta De, Janet C Dickerson, and Jonathan N Coleman.  The dependence of the optoelectrical properties of silver nanowire networks on nanowire length and diameter.  Nanotechnology, 23(18):185201, 2012.
  * 5. Nitheesh M Nair, Kevin Daniel, Sai Chandrahaas Vadali, Debdutta Ray, and P Swaminathan.  Direct writing of silver nanowire-based ink for flexible transparent capacitive touch pad.  Flexible and Printed Electronics, 4(4):045001, 2019.
  * 6. Rose M Mutiso, Michelle C Sherrott, Aaron R Rathmell, Benjamin J Wiley, and Karen I Winey.  Integrating simulations and experiments to predict sheet resistance and optical transmittance in nanowire films for transparent conductors.  ACS Nano, 7(9):7654–7663, 2013.
  * 7. Nitheesh M Nair, Jayaram Kizhekke Pakkathillam, Krishna Kumar, Kavitha Arunachalam, Debdutta Ray, and Parasuraman Swaminathan.  Printable silver nanowire and pedot: Pss nanocomposite ink for flexible transparent conducting applications.  ACS Applied Electronic Materials, 2(4):1000–1010, 2020.
  * 8. Nitheesh M Nair, Ishani Khanra, Debdutta Ray, and Parasuraman Swaminathan.  Silver nanowire-based printable electrothermochromic ink for flexible touch-display applications.  ACS Applied Materials & Interfaces, 13(29):34550–34560, 2021.
  * 9. Nitheesh M Nair, Mohammad Mahaboob Jahanara, Debdutta Ray, and P Swaminathan.  Photoresponse of a printed transparent silver nanowire-zinc oxide nanocomposite.  Flexible and Printed Electronics, 6(4):045004, 2021.
  * 10. Yugang Sun, Brian Mayers, Thurston Herricks, and Younan Xia.  Polyol synthesis of uniform silver nanowires: a plausible growth mechanism and the supporting evidence.  Nano letters, 3(7):955–960, 2003.
  * 11. Hongwei Ding, Yujuan Zhang, Guangbin Yang, Shengmao Zhang, Laigui Yu, and Pingyu Zhang.  Large scale preparation of silver nanowires with different diameters by a one-pot method and their application in transparent conducting films.  RSC advances, 6(10):8096–8102, 2016.
  * 12. Pei Zhang, Ian Wyman, Jiwen Hu, Shudong Lin, Zhiwei Zhong, Yuanyuan Tu, Zhengzhu Huang, and Yanlong Wei.  Silver nanowires: Synthesis technologies, growth mechanism and multifunctional applications.  Materials Science and Engineering: B, 223:1–23, 2017.
  * 13. Shanyong Chen, Youwei Guan, Ying Li, Xingwu Yan, Haitao Ni, and Lu Li.  A water-based silver nanowire ink for large-scale flexible transparent conductive films and touch screens.  Journal of Materials Chemistry C, 5(9):2404–2414, 2017.
  * 14. Prathamesh Patil, Suneha Patil, Prachi Kate, and Amol A Kulkarni.  Inkjet printing of silver nanowires on flexible surfaces and methodologies to improve the conductivity and stability of the printed patterns.  Nanoscale Advances, 3(1):240–248, 2021.
  * 15. A Kosmala, R Wright, Qi Zhang, and P Kirby.  Synthesis of silver nano particles and fabrication of aqueous ag inks for inkjet printing.  Materials Chemistry and Physics, 129(3):1075–1080, 2011.
  * 16. Vu Binh Nam and Daeho Lee.  Copper nanowires and their applications for flexible, transparent conducting films: a review.  Nanomaterials, 6(3):47, 2016.
  * 17. Aditi Halder and N Ravishankar.  Ultrafine single-crystalline gold nanowire arrays by oriented attachment.  Advanced Materials, 19(14):1854–1858, 2007.
  * 18. Mariana Chirea, Andreia Freitas, Bogdan S Vasile, Cristina Ghitulica, Carlos M Pereira, and Fernando Silva.  Gold nanowire networks: synthesis, characterization, and catalytic activity.  Langmuir, 27(7):3906–3913, 2011.
  * 19. CL Chen, H Furusho, and H Mori.  Silver nanowires with a monoclinic structure fabricated by a thermal evaporation method.  Nanotechnology, 20(40):405605, 2009.
  * 20. Timothy R Kline, Mingliang Tian, Jinguo Wang, Ayusman Sen, Moses WH Chan, and Thomas E Mallouk.  Template-grown metal nanowires.  Inorganic chemistry, 45(19):7555–7565, 2006.
  * 21. Yiding Liu, James Goebl, and Yadong Yin.  Templated synthesis of nanostructured materials.  Chemical Society Reviews, 42(7):2610–2653, 2013.
  * 22. Xuchuan Jiang, Yi Xie, Jun Lu, Liying Zhu, Wei He, and Yitai Qian.  Oleate vesicle template route to silver nanowires.  Journal of Materials Chemistry, 11(7):1775–1777, 2001.
  * 23. Thomas D Lazzara, Gilles R Bourret, R Bruce Lennox, and Theo GM Van De Ven.  Polymer templated synthesis of agcn and ag nanowires.  Chemistry of Materials, 21(10):2020–2026, 2009.
  * 24. Michael H Huang, Amer Choudrey, and Peidong Yang.  Ag nanowire formation within mesoporous silica.  Chemical Communications, (12):1063–1064, 2000.
  * 25. Hideki Masuda and Kenji Fukuda.  Ordered metal nanohole arrays made by a two-step replication of honeycomb structures of anodic alumina.  science, 268(5216):1466–1468, 1995.
  * 26. Ji-Lin Zhang and Guang-Yan Hong.  The nanomaterials synthesized by using aao template.  Chinese Journal of Applied Chemistry, 21(1):6–11, 2004.
  * 27. Xiaojie LI, Haiming ZHANG, Guofeng HU, and Yujie LI.  Fabrication and application of aao template.  Mater Rev, 22(11):80–82, 2008.
  * 28. Carmen Mijangos, Rebeca Hernández, and Jaime Martin.  A review on the progress of polymer nanostructures with modulated morphologies and properties, using nanoporous aao templates.  Progress in Polymer Science, 54:148–182, 2016.
  * 29. Yadian Xie, Duygu Kocaefe, Chunying Chen, and Yasar Kocaefe.  Review of research on template methods in preparation of nanomaterials.  Journal of Nanomaterials, 2016, 2016.
  * 30. AJ Yin, J Li, W Jian, AJ Bennett, and JM Xu.  Fabrication of highly ordered metallic nanowire arrays by electrodeposition.  Applied Physics Letters, 79(7):1039–1041, 2001.
  * 31. Kyungtae Kim, Moonjung Kim, and Sung M Cho.  Pulsed electrodeposition of palladium nanowire arrays using aao template.  Materials chemistry and physics, 96(2-3):278–282, 2006.
  * 32. Wei Wang, Nan Li, Xiaotian Li, Wangchang Geng, and Shilun Qiu.  Synthesis of metallic nanotube arrays in porous anodic aluminum oxide template through electroless deposition.  Materials research bulletin, 41(8):1417–1423, 2006.
  * 33. Wen-Bo Zhao, Jun-Jie Zhu, and Hong-Yuan Chen.  Photochemical synthesis of au and ag nanowires on a porous aluminum oxide template.  Journal of crystal growth, 258(1-2):176–180, 2003.
  * 34. Arulkumar Ganapathi, P Swaminathan, and Lakshman Neelakantan.  Anodic aluminum oxide template assisted synthesis of copper nanowires using a galvanic displacement process for electrochemical denitrification.  ACS Applied Nano Materials, 2(9):5981–5988, 2019.
  * 35. RC Furneaux, WR Rigby, and AP Davidson.  The formation of controlled-porosity membranes from anodically oxidized aluminium.  Nature, 337(6203):147–149, 1989.


# Spread of Infection over P.A. random graphs with edge insertion

Caio Alves1 1 Alfréd Rényi Institute of Mathematics, Budapest.  and  Rodrigo
Ribeiro2 2 Departament of Mathematics, University of Colorado Boulder.
e-mail<EMAIL_ADDRESS>
(Date:
1 Institute of Mathematics, University of Leipzig
2 Departament of Mathematics, University of Colorado Boulder
)

###### Abstract.

In this work we investigate a bootstrap percolation process on random graphs
generated by a random graph model which combines preferential attachment and
edge insertion between previously existing vertices. The probabilities of
adding either a new vertex or a new connection between previously added
vertices are time dependent and given by a function $f$ called the edge-step
function. We show that under integrability conditions over the edge-step
function the graphs are highly susceptible to the spread of infections, which
requires only $3$ steps to infect a positive fraction of the whole graph. To
prove this result, we rely on a quantitative lower bound for the maximum
degree that might be of independent interest.

###### Key words and phrases:

preferential attachment, random graphs, Bootstrap percolation, Karamata’s
theory, regular varying function

###### 2010 Mathematics Subject Classification:

Primary 05C82; Secondary 60K40, 68R10

##  1\. Introduction

Investigation of spread of infections or propagation of information over
networks is a crucial problem which arises naturally in many areas of science
going from social sciences to economics. The recent pandemic and the
dissemination of fake news in a highly interconnected society make evident the
relevance of studies involving dissemination over networks.

An accurate model for spread of infections must accommodate somehow the
randomness of the environment, since concrete situations such as human
societies produce networks which evolve in time according to random rules. In
this direction, random graph models whose rule of evolution combines the so-
called preferential attachment rule became a natural environment to the
investigation of infectious processes [7, 12, 9]. The reason is that this
mechanism of attachment which is driven by popularity, that is, individuals
tends to get connected with the more popular ones, proved that it is capable
of capturing network properties shared by many networks in real-file [13, 6].
We do not intend to cover the vast literature of preferential attachment
random graphs, but we refer the reader to the book of R. van der Hofstad [14]
and of R. Durrett [11] for a wide and rigorous introduction to many important
random graph models.

In this work we investigate the bootstrap percolation process on random graphs
generated by a random graph model which combines preferential attachment and
edge insertion between previously existing vertices. In order to properly
state and discuss the nature of our results we will define the underlying
random graph model and latter the Bootstrap percolation process performed over
our random graphs.

###  1.1. The model

The model depends on a real non-negative function $f$, called the edge-step
function, with domain given by the semi-line $[1,\infty)$ such that
$||f||_{\infty}\leq 1$. Though the results here stated also apply for any
finite given initial graph, we will assume henceforth that the process starts
from an initial graph $G_{1}$ consisting in one vertex and one loop in order
to simplify notation. As the process evolves, one of the two graph stochastic
operations below may be performed on the graph $G$:

  * •

Vertex-step \- Add a new vertex $v$ and add an edge $\\{u,v\\}$ by choosing
$u\in G$ with probability proportional to its degree. More formally,
conditionally on $G$, the probability of attaching $v$ to $u\in G$ is given by

$P\left(v\rightarrow u\middle|G\right)=\frac{\mathrm{degree}(u)}{\sum_{w\in
G}\mathrm{degree}(w)}.$ (1)

  * •

Edge-step \- Add a new edge $\\{u_{1},u_{2}\\}$ by independently choosing
vertices $u_{1},u_{2}\in G$ according to the same rule described in the
vertex-step. We note that both loops and parallel edges are allowed.

We let $\\{Z_{t}\\}_{t\in\mathbb{N}}$ be an independent sequence of random
variables such that $Z_{t}\stackrel{{\scriptstyle\tiny
d}}{{=}}\mathrm{Ber}(f(t))$. We then define a markovian random graph process
$\\{G_{t}(f)\\}_{t\geq 1}$ as follows: begin with initial state $G_{1}$. Given
$G_{t}(f)$, obtain the (multi)graph $G_{t+1}(f)$ by either performing a
vertex-step on $G_{t}(f)$ when $Z_{t}=1$ or performing an edge-step on
$G_{t}(f)$ when $Z_{t}=0$.

We will make use of natural numbers, mainly $i,j$ and $k$, to denote
respectively the $i$-th, $j$-th and $k$-th vertex added by the random graph
process. Moreover, we will let $d_{t}(i)$ be the degree of the $i$ vertex at
time $t$. If $i$ has not been added yet, then $d_{t}(i)=0$.

###  1.2. Regularity conditions

Again, in order to properly state and discuss our results we will need to
introduce some regularity conditions for the functions $f$. Some of theses
conditions have the objective of preventing pathological examples, for
instance if one drops monotonicity it is possible to construct $f$ such that
the sequence of graphs $\\{G_{t}(f)\\}_{t\in\mathbb{N}}$ has two sub sequences
of graphs: one similar to the BA random tree and the other one a quasi-
complete graph, see the discussion in Section 8 of [2].

Some of our results will require information about the asymptotic behavior of
$f$ and for this reason a wide class of functions will play important role:
the regularly varying functions. We say that a positive function $f$ is a
regularly varying function (r.v.f for short) at infinity with index of regular
variation $-\gamma$, for some $\gamma\geq 0$, if

$\lim_{t\to\infty}\frac{f(at)}{f(t)}=a^{-\gamma},$

for all $a>0$. The special case $\gamma=0$ is called slowly varying function.
Below we define the conditions over $f$ that will be useful to our purposes.
For $p\in[0,1]$, we define conditions

$f\text{ decreases to }p.$ (Dp)

We will also need to define some summability conditions:

$\sum_{s=1}^{\infty}f(s)=\infty.$ (V∞)

The above condition relates to the expected number of vertices. Since at each
step $s$ we add a vertex with probability $f(s)$, the above condition tells us
that the process keeps introducing new vertices into the graph.

$\sum_{s=1}^{\infty}\frac{f(s)}{s}<\infty.$ (S)

Whenever (S) does not hold for a specific $f$, we say that $f$ satisfies (S)c.
For any $\gamma\in[0,1]$, we let ${\rm RES}(-\gamma)$ be the following class
of functions

$\begin{split}\mathrm{RES}(-\gamma):=\left\\{f:[1,\infty]\longrightarrow[0,1]\;\middle|\;f\text{
satisfies (D)}_{0}\text{ and is r.v.f with index
}-\gamma\right\\}.\end{split}$ (RES)

Due to degree of freedom one has to choose $f$, since it is a function, one
can study this model in several different contexts. It has been studied under
different regularity conditions on $f$ and different graph properties have
been investigated. In [3] the authors proved that, under
$\mathrm{RES}(-\gamma)$, the empirical degree distribution of $G_{t}(f)$ is
close to a power-law whose exponent is given by $2-\gamma$, when
$\gamma\in[0,1)$. Whereas in [4], the authors investigated how the diameter of
$G_{t}(f)$ depends on $f$ under different conditions on the asymptotic
behavior of $f$. A variety of regimes for the diameter can be achieved, from
$O(1)$ regimes to $\Theta(\log t)$ ones. In [1], the clique number has been
investigated for $f\equiv p\in(0,1)$.

###  1.3. Main Results

One of the central questions in the study of infectious processes is the
outbreak, when the whole or a large proportion of the network becomes
infected. This macro phenomena can be triggered by local decisions whose
effect scales to a macro state. In a nutshell part of our results address the
‘amount’ of local decisions needed to trigger the outbreak and the time needed
to observe it.

In order to investigate the Bootstrap percolation process we need to prove
certain properties of the underlying environment. For this reason, our first
result is a quantitative lower bound for the maximum degree. In order to state
it, we need to introduce new notation. Given an edge-step function $f$, we
define the normalizing function $\phi:\mathbb{N}\to(0,\infty)$ by

$\phi(t)=\phi(t,f):=\prod_{s=1}^{t-1}\Big{(}1+\frac{1}{s}-\frac{f(s+1)}{2s}\Big{)}$
(2)

We note that condition (S) is equivalent to $\phi(t)$ growing linearly as a
function of $t$. We have

######  Theorem 1 (Lower bound for maximum degree).

Let $f$ be an edge-step function such that $f(t)$ goes to zero as $t$ goes to
infinity. For every $N\in\mathbb{N}$, there exists $C_{f}>0$ depending on $f$
only such that

$\begin{split}\mathbb{P}\left(\forall t\in\mathbb{N},\exists
i\in\\{1,2,\cdots,N\\}\text{ such that
}d_{t}(i)\geq\frac{\phi(t)}{\phi(N)}\right)&\geq
1-\exp\\{-C_{f}N\\}.\end{split}$ (3)

Furthermore, there exists almost surely a random integer $N_{0}\geq 0$ such
that for every $t\geq N_{0}$, there exists at least one vertex $i$ in
$G_{t}(f)$ such that

$d_{t}(i)\geq\frac{\phi(t)}{\phi(N_{0})}.$ (4)

As said before, in this work we analyze the Bootstrap Percolation model over
$G_{t}(f)$. We will consider $f\in{\rm RES}(-\gamma)$, with $\gamma\in[0,1)$
and satisfying condition (S). Our estimates allow us to construct structures
on the graph $G_{t}(f)$ that make it highly susceptible to the spread of
infections.

Now, let us define the Bootstrap Percolation process. Given a finite
(multi)graph $G=(V(G),E)$, a number $a\in[0,|V(G)|]$, and an integer $r\geq
2$, we define the bootstrap percolation measure $\mathbb{Q}_{G,a,r}$ on $G$
with threshold $r$ and rate of infection $a$ in the following manner:

  * •

Each vertex $v\in V(G)$ is  _infected_ at round $0$ independently of the
others with probability $a|V(G)|^{-1}$. The collection of all infected
vertices at round $0$ is denoted by $\mathcal{I}_{0}$.

  * •

At round $s\in\mathbb{N}$, every vertex connected to $\mathcal{I}_{s-1}$ via
at least $r$ edges becomes infected.

  * •

We let $\mathcal{I}_{\infty}$ be the set of all infected vertices when the
process stabilizes, that is,

$\mathcal{I}_{\infty}=\cup_{s\geq 0}\mathcal{I}_{s}.$

In [5] the authors study the bootstrap percolation process on the preferential
attachment random graph where each vertex has $m\in\mathbb{N}$ outgoing edges
with end vertices chosen according to an affine preferential attachment rule,
that is, the PA rule in (1) but with a $\delta>-m$ summed in both the
numerator and denominator. There they prove the existence of a  _critical
function_ $a_{t}^{c}:\mathbb{N}\to\mathbb{R}_{+}$ such that the bootstrap
percolation process on this random graph at time $t$ with threshold $r\leq m$
and rate $a_{t}\gg a_{t}^{c}$ infects the whole graph with high probability,
but the same process with rate $a_{t}^{\prime}\ll a_{t}^{c}$ dies out without
before infecting a positive proportion of the graph, also with high
probability.

In our context it is not possible for the infection to spread to the whole
graph due to the existence of many vertices with degree smaller than $r$ at
all times. We therefore turn the problem into asking if $\mathcal{I}_{\infty}$
eventually encompasses a set with positive density in the vertex set. In this
sense, we show in our next result that the bootstrap percolation is always
supercritical for the graph $G_{t}(f)$, with $f$ under (S), i.e., every
unbounded rate sequence gives rise to a set of infected vertices with positive
density:

######  Theorem 2 (The outbreak phenomenon).

Let $f$ be an edge-step function in ${\rm RES}(-\gamma)$, with
$\gamma\in[0,1)$, and satisfying the summability condition (S). Then, for any
sequence $(a_{t})_{t\in\mathbb{N}}$ increasing to infinity and a integer
number $r\geq 2$ there exists a collection of graphs
$\mathcal{G}_{t}=\mathcal{G}_{t}((a_{t})_{t\in\mathbb{N}},r)$ and a
$(f,r)$-dependent constant $c>0$ such that,

$\mathbb{P}\left(G_{t}(f)\in\mathcal{G}_{t}\right)=1-o(1)$ (5)

and for all $G\in\mathcal{G}_{t}$ the bootstrap percolation process on $G$
with parameters $a_{t}$ and $r\geq 2$ satisfies

$\mathbb{Q}_{G,a_{t},r}\left(|\mathcal{I}_{\infty}|\geq
c|V(G)|\right)=1-o(1).$ (6)

The above theorem illustrates how interconnected $G_{t}(f)$ is. From the
definition of the bootstrap percolation on $G_{t}(f)$, it follows that the
initial infected set $\mathcal{I}_{0}$ is essentially $a_{t}$. Thus, by
Theorem 2 one can choose $a_{t}$ of order arbitrarily smaller than the
expected number of vertices in $G_{t}(f)$, as long as it increases to
infinity, the infection manages to spread to a positive fraction of the whole
graph with high probability.

In order to prove Theorem 2 we actually prove a stronger result, which
provides an upper bound for the time it takes for the infection to spread to a
positive fraction of the whole graph. Formally, for a bootstrap process on $G$
with parameter $r$ and $a$, given a positive constant $c$, let $\tau_{c}$ be
the following stopping time

$\tau_{c}:=\inf\\{s\geq 0\;:\;|\mathcal{I}_{s}|\geq c|V(G)|\\}.$ (7)

Then we have the following result which is a stronger version of Theorem 2.

######  Theorem 2’ (Number of steps for the outbreak).

Let be $\mathcal{G}_{t}$ and $c$ as in Theorem 2. Then, for any sequence
$(a_{t})_{t\in\mathbb{N}}$ increasing to infinity, $r\geq 2$ and
$G\in\mathcal{G}_{t}$ the following holds

$\mathbb{Q}_{G,a_{t},r}\left(\tau_{c}\leq 3\right)=1-o(1).$

Roughly speaking, the above result states that typically, a bootstrap
percolation process on $G_{t}(f)$ needs at most $3$ steps to reach a positive
fraction of $G_{t}(f)$, making clearer the interconnectedness of the graphs
$\\{G_{t}(f)\\}_{t\geq 1}$ when $f$ is under $(S)$ and
$\mathrm{RES}(-\gamma)$.

##  2\. Lower bound for the maximum degree

In this section, we will use martingale arguments in order to show a
quantitative lower bound for the maximum degree of $G_{t}(f)$. This type of
result is usually not as strong as its upper bound counterpart, since we may
pay a relatively small price in order to make a vertex $i$ behave like it was
born much after its mean appearance time. We can however obtain stronger
results when dealing with the _total degree of a collection of vertices_. This
in turn gives us good lower bounds for the degree of some random vertex, by
the pigeonhole Principle.

We start with an elementary stochastic recurrence identity concerning the
degree of a given vertex $i$. Define as $\tau(i)$ the random time in which the
$i$-th vertex is born.

######  Lemma 2.1.

Given the vertex with index $i$ we have, in the event where $s\geq\tau(i)$,

$\begin{split}\mathbb{E}\left[\Delta
d_{s}(i)\middle|\mathcal{F}_{s}\right]&=\left(\frac{1}{s}-\frac{f(s+1)}{2s}\right)d_{s}(i),\end{split}$
(8)

which implies that for $X_{t_{i},s}$ defined as

$\begin{split}X_{t_{i},s}:=\frac{d_{s}(i)}{\phi(s)}\mathds{1}\\{\tau(i)=t_{i}\\}\end{split}$
(9)

the process $\\{X_{t_{i},s}\\}_{s\geq t_{i}}$ is a martingale.

###### Proof.

We start by noticing that $\Delta d_{s}(i)$ is either $0$, $1$, or $2$. In
order for it to be $1$, we may either add a new vertex to the graph and
connect it to $i$, or we add a new edge and choose $i$ to be one of its
endvertices. In the case where the increment is $2$, we add a new edge to the
graph and choose $i$ twice, adding a loop to it. This yields the formula, on
the event where $s>\tau_{i}$,

$\begin{split}\mathbb{E}\left[\Delta
d_{s}(i)\middle|\mathcal{F}_{s}\right]&=f(s+1)\frac{d_{s}(i)}{2s}+2\left(1-f(s+1)\right)\frac{d_{s}(i)}{2s}\left(1-\frac{d_{s}(i)}{2s}\right)+2\left(1-f(s+1)\right)\Bigg{(}\frac{d_{s}(i)}{2s}\Bigg{)}^{2}\\\
&=\left(\frac{1}{s}-\frac{f(s+1)}{2s}\right)d_{s}(i),\end{split}$ (10)

which in turn, by the definition of $\phi$ in (2), implies that the process in
(9) is a martingale. ∎

Let the function $\xi:\mathbb{N}\to\mathbb{R}$ be defined by

$\xi(s)=\xi(s,f):=\frac{\phi(s)}{s}=\prod_{r=1}^{s-1}\frac{r}{r+1}\prod_{r=1}^{s-1}\left(1+\frac{1}{r}-\frac{f(r+1)}{2r}\right)=\prod_{r=1}^{s-1}\left(1-\frac{f(r+1)}{2(r+1)}\right).$
(11)

In order to properly calculate sums involving $\phi$, the following lemma
about $\xi$ will be necessary:

######  Lemma 2.2.

If $f$ satisfies $(\mathrm{D}_{0})$, that is, $f(t)$ decreases monotonically
to $0$ as $t$ increases, then $\xi$ is a slowly varying function.

###### Proof.

We may write $\xi$ as

$\xi(s)=\exp\left\\{\sum_{r=1}^{s-1}\log\left(1-\frac{f(r+1)}{2(r+1)}\right)\right\\}=\exp\left\\{\sum_{r=1}^{s-1}\left(-\frac{f(r+1)}{2(r+1)}+O(r^{-2})\right)\right\\}.$
(12)

Therefore $\xi$ is a slowly varying function as long as $f(t)$ goes to zero as
$t$ goes to infinity, since for any $a\in\mathbb{R}_{+}$,

$\begin{split}\frac{\xi(as)}{\xi(s)}&=\exp\left\\{\sum_{r=\lceil
as\rceil}^{s-1}\left(\frac{f(r+1)}{2(r+1)}+O(r^{-2})\right)\right\\}\\\
&\leq\exp\left\\{C\cdot as^{-1}+\frac{\inf_{r\geq as}f(r)}{2}\left(\log s-\log
as\right)\right\\}\\\ &\leq\exp\left\\{C\cdot as^{-1}-\frac{\inf_{r\geq
as}f(r)}{2}\left(\log a\right)\right\\}\\\
&\xrightarrow{s\to\infty}1.\end{split}$ (13)

∎

With all the previous results at our disposal we can finally prove the main
result of this section, which states a lower bound for the maximum degree of
$G_{t}(f)$.

###### Proof of Theorem 1.

Fix $N\in\mathbb{N}$ and denote by $\\{W_{N,s}\\}_{s\geq N}$ the process

$W_{N,s}:=\frac{\sum_{i=1}^{N}d_{s}(i)\mathds{1}\\{\tau(i)\leq
N\\}}{\phi(s)},$ (14)

i.e., $W_{N,s}$ denotes the sum of the degree of all vertices added by the
process up to time $N$ normalized by $\phi(s)$. Since

$\tilde{W}_{N,s}=\frac{1}{\phi(s)}\sum_{i\geq
1}d_{s}(i)\mathds{1}\\{\tau(i)\leq N\\},$ (15)

Lemma 2.1 implies that $\\{W_{N,s}\\}_{s\geq N}$ is a positive martingale such
that

$\mathbb{E}W_{N,s}=W_{N,N}\equiv\frac{2N}{\phi(N)}.$ (16)

Indeed, at time $N$ the sum of the degree of all vertices added up to this
time equals twice the number of edges, which is $N$. In order to shorten the
notation, we define

$D_{N,s}=\sum_{i=1}^{N}d_{s}(i)\mathds{1}\\{\tau(i)\leq N\\}.$

Since we can update the degree of at most two vertices by an amount of at most
$2$, it follows that $\\{W_{N,s}\\}_{s\geq N}$ has bounded increments:

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\left|\Delta
W_{N,s}\right|$\mbox{}\hfil\quad\\\
&=\left|\frac{1}{\phi(s+1)}D_{N,s+1}-\frac{1}{\phi(s)}D_{N,s}\right|\\\
&=\frac{1}{\phi(s+1)\phi(s)}\left|\phi(s)D_{N,s+1}-\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right)\phi(s)D_{N,s}\right|\\\
&=\left|\frac{1}{\phi(s+1)}\Delta
D_{N,s}-\frac{(2-f(s+1))}{2s\phi(s+1)}D_{N,s}\right|\\\
&\leq\frac{3}{\phi(s+1)},\end{split}$ (17)

which implies $(\Delta W_{N,s})^{2}\leq 9\phi(s+1)^{-1}$. We have by Lemma 2.2
that $\xi^{-2}$ is a slowly varying function. By Karamata theory (see Theorem
6 in the Appendix), the above inequality, and the fact that $f$ is decreasing,
we obtain

$\sum_{s=N}^{t}\left|\Delta W_{N,s}\right|^{2}\leq
16\sum_{s=N}^{t}s^{-2}\xi(s)^{-2}\leq\frac{C}{N\xi(N)^{2}}=\frac{C}{\phi(N)\xi(N)}.$
(18)

We are going to stop our martingale when it becomes unexpectedly small. For
this, let $\eta$ be the stopping time

$\eta:=\inf_{s\geq N}\left\\{W_{N,s}\leq\frac{N}{\phi(N)}\right\\}.$ (19)

By the Optional Stopping Theorem, it follows that
$\\{W_{N,s\wedge\eta}\\}_{s\geq N}$ is a martingale having the same expected
value as $\\{W_{N,s}\\}_{s\geq N}$. Furthermore, stopping a martingale can
only decrease its increments. Thus, by Azuma’s inequality, we obtain, by
equation (18) and the definition of $\xi$,

$\mathbb{P}\left(W_{N,s\wedge\eta}\leq\frac{2N}{\phi(N)}-\frac{N}{\phi(N)}\right)\leq\exp\left\\{-C\frac{N^{2}}{\phi(N)^{2}}\phi(N)\xi(N)\right\\}\leq\exp\left\\{-CN\right\\}.$
(20)

Now, by the definition of $\eta$, we obtain

$\begin{split}\mathbb{P}\left(\exists s\in\mathbb{N}\text{ such that
}W_{N,s}\leq\frac{N}{\phi(N)}\right)&\leq\mathbb{P}\left(\eta<\infty\right)\\\
&=\lim_{s\to\infty}\mathbb{P}\left(\eta\leq s\right)\\\
&=\lim_{s\to\infty}\mathbb{P}\left(W_{N,s\wedge\eta}\leq\frac{N}{\phi(N)}\right)\\\
&\leq\exp\left\\{-CN\right\\}.\end{split}$ (21)

By the pigeonhole Principle the above inequality implies (3) since

$W_{N,t}>\frac{N}{\phi(N)}\iff\sum_{i=1}^{N}d_{t}(i)\mathds{1}\\{\tau(i)\leq
N\\}>\frac{N\phi(t)}{\phi(N)},$ (22)

implying the existence of at least one vertex with degree $\phi(t)/\phi(N)$
among the $N$ first vertices. ∎

##  3\. The outbreak phenomenon

In this section we prove Theorem 2’ which is a stronger version of Theorem 2.
The reader may find useful to recall the definition of the bootstrap
percolation process at page 2 as well as definition of $\tau_{c}$ in (7). For
the sake of organization we will split the proof into several lemmas.

Throughout this section, $f$ will be a function satisfying conditions
$(\mathrm{D}_{0})$, $\eqref{def:condS}$, and $\mathrm{RES}(-\gamma)$ for
$\gamma\in[0,1)$. We will also use the notation $a_{n}\sim b_{n}$ to mean
$a_{n}/b_{n}\to 1$ as $n\to\infty$. Moreover, whenever we use the letter $r$
when dealing with the graph process $\\{G_{t}(f)\\}_{t\geq 2}$, this $r$ is
the exact same $r$ as the threshold parameter of the Bootstrap Percolation
process to be performed in the graphs $G_{t}(f)$. We then begin by some useful
properties of $G_{t}(f)$ and $f$ when $f$ satisfies the aforementioned
conditions. The first lemma is a small result concerning the speed of
convergence to zero of $f$.

######  Lemma 3.1.

Let $f$ be an edge-step function satisfying conditions $\eqref{def:condS}$ and
$\mathrm{RES}(-\gamma)$ for $\gamma\in[0,1)$. Then,

$\lim_{t\to\infty}f(t)\log(t)=0$

###### Proof.

In the regime $\gamma>0$ the product $f(t)\log(t)$ converges to zero as $t$
goes to infinity by virtue of Corollary 5, since in this case by Theorem 4, we
have $f(t)=\ell(t)t^{-\gamma}$, where $\ell$ is a slowly varying function. On
the other hand, if $f$ is slowly varying ($\gamma=0$), then for any
$K\in\mathbb{N}$, the monotonicity of $f$ implies

$\begin{split}\sum_{s=K}^{Kt}\frac{f(s)}{s}\geq
f(Kt)\sum_{s=K}^{Kt}\frac{1}{s}\geq f(Kt)\log t(1-o(1))\sim
f(t)\log(t)(1-o(1)),\end{split}$ (23)

since $f$ is slowly varying. Finally, using condition $(S)$ which states that
$\sum_{s}f(s)/s$ is finite and sending $K$ to infinity, we obtain the desired
result.

∎

It will be useful to our purposes to know the order of magnitude of the
expected number of vertices in $G_{t}(f)$. By the Karamata’s Theorem (Theorem
B) we have that

$\mathbb{E}V_{t}(f)\sim\frac{f(t)t}{1-\gamma}\implies\mathbb{E}V_{t}(f)\leq\frac{5}{4(1-\gamma)}f(t)t,$
(24)

for large enough $t$.

In order to prove Theorem 2’, we will prove all the intermediate results and
the theorem itself under the assumption that the sequence $(a_{t})_{t\geq 1}$
satisfies the following technical conditions

$\begin{split}(i)\quad tf(t)f(a_{t})\log(a_{t})\to\infty;\;\quad(ii)\quad
a_{t}\leq t;\quad(iii)\quad f(a_{t})\log(a_{t})\geq f(t)\log t,\end{split}$
(L)

for sufficiently large $t$. The reason why we need $(L)$ is of technical
nature. Having such control over $(a_{t})_{t\geq 1}$ makes some arguments
easier to follow. However, the following lemma, whose proof is straightforward
and will be omitted, guarantees that (L) is not restrictive.

######  Lemma 3.2 (Monotonicity on $(a_{t})_{t\geq 1}$).

Let $(a_{t})_{t\geq 1}$ and $(a^{\prime}_{t})_{t\geq 1}$ be two sequence of
positive real numbers such that $a_{t}\leq a^{\prime}_{t}$ for all $t\geq 1$.
Then, given a (multi)graph $G$, a positive constant $c$ and a natural number
$r$, the following holds

$\mathbb{Q}_{G,a_{t},r}\left(|\mathcal{I}_{\infty}|\geq
c|V(G)|\right)\leq\mathbb{Q}_{G,a^{\prime}_{t},r}\left(|\mathcal{I}_{\infty}|\geq
c|V(G)|\right),$

for all $t\geq 1$.

Recall that the parameter $a_{t}$ is essentially the size of
$\mathcal{I}_{0}$, which is the set of initially infected vertices. Thus, the
above result states that if we increase the average size of $\mathcal{I}_{0}$,
we increase our chances of percolating. The upshot is that we do not lose
generality by imposing conditions on the growth rate of $(a_{t})_{t\geq 1}$,
as long as such conditions require making $(a_{t})_{t\geq 1}$ go to infinity
slower.

In general lines, in order to prove that $G_{t}(f)$ is supercritical for the
Bootstrap percolation process, the key steps are to construct specific
subgraphs in $G_{t}(f)$, which have good infectious properties in the sense
that the infectious process reach those subgraphs more easily and they are
interconnected in way that once the infection has reached them, it manages to
spread to a positive proportion of the whole graph in a few steps.

In the next lemmas we will make sure $G_{t}(f)$ has some useful graph
properties a.a.s.. We let $g$ and $h$ be the following functions:

$\begin{split}g(t):=\frac{1-\gamma}{f(t)};\;h(t):=\frac{C_{1}}{6(r+1)^{2}C_{2}}\cdot\frac{g(t)}{\log(t)},\end{split}$
(25)

where $r$ is the threshold parameter of the Bootstrap Percolation process and
$C_{1}$ and $C_{2}$ are positive constants such that

$C_{1}t\leq\phi(t)\leq C_{2}t.$ (26)

Note that, by Lemma 3.1, $h(t)$ goes to infinity as $t$ increases.

We now present a sketch of the proof of the outbreak phenomenon, proving
w.h.p. the existence of a structure that is highly susceptilble to infections.
In what follows, everything happens w.h.p. as $t$ goes to infinity.

  * (i)

At time $t$ the graph has a number of vertices of order at most $\approx
f(t)t$, and a distinguished vertex $v^{*}$ with degree of order at least
$\approx t/h(a_{t})$;

  * (ii)

At time $(r+1)t$, the above bounds are still valid, but there exists a
subgraph $H$ whose _total degree_ in $G_{(r+1)t}(f)$ has order at least
$\approx t$, and every vertex of $H$ sends at least $r$ edges to $v^{*}$;

  * (iii)

At time $2(r+1)^{2}t$, the above is still valid, but now there exists a subset
$S\subset V(G_{2(r+1)^{2}t}(f))$ with cardinality of the same order as
$V(G_{2(r+1)^{2}t}(f))$ such that each vertex of $S$ has at least $r$
connections with $H$. Other than that, the distinguished vertex $v^{*}$ has
order at least $\approx f(t)t/h(a_{t})$ distinct neighbours.

This is enough to prove our result for the graph $G_{2(r+1)^{2}t}(f)$:

  * (i)

The lower bound on the number of distinct neighbours of $v^{*}$ and our choice
of $h$ imply that this vertex becomes infected in the first step;

  * (ii)

Since every vertex of $H$ has at least $r$ connections to $v^{*}$, $H$ as a
whole becomes infected in the second step;

  * (iii)

Now $S$ has cardinality comparable to $V(G_{2(r+1)^{2}t})$, and each vertex in
$S$ sends $r$ connections to $H$, implying that $S$ becomes infected in the
third step, implying the existence of an outbreak.

We can prove the same result for the graph $G_{t}$ just by adjusting the
constants. In accordance to the proof sketch above, for each time
$t\in\mathbb{N}$, let $\mathcal{P}_{t}^{1}$ be the following collection of
(multi)graphs

$\begin{split}\mathcal{P}^{1}_{t}:=\left\\{G=(V,E):|V|\leq\frac{15f(t)t}{8(1-\gamma)}\text{
and }\exists v^{*}\in V,\text{with
}d_{G}v^{*}\geq\frac{C_{1}t}{C_{2}h(a_{t})}\right\\}.\end{split}$ (27)

In words, $\mathcal{P}^{1}_{t}$ is the collection of multigraphs with at most
$15f(t)t/8(1-\gamma)$ vertices and containing at least one vertex $v^{*}$
whose degree is at least $C_{1}C_{2}^{-1}t/h(a_{t})$, where $C_{1}$ and
$C_{2}$ are the $f$-dependent constants in (26). We call the distinguished
vertex $v^{*}$ a star. The next result ensures $G_{t}(f)$ has property
$\mathcal{P}^{1}_{t}$ a.a.s..

######  Lemma 3.3.

Let $f$ be an edge-step function satisfying conditions $(S)$ and
$\mathrm{RES}(-\gamma)$ for $\gamma\in[0,1)$. Then, there exists a
$f$-dependent positive constant $C_{f}$ such that

$\mathbb{P}\left(G_{t}(f)\in\mathcal{P}^{1}_{t}\right)\geq
1-\exp\\{-C_{f}h(a_{t})\\}-\exp\left\\{-\mathbb{E}V_{t}(f)/4\right\\}.$

###### Proof.

By Theorem 1, choosing $N=h(a_{t})$, we have that

$\mathbb{P}\left(\exists i\in\\{1,2,\cdots,h(a_{t})\\},\text{ such that
}d_{t}(i)\geq\frac{C_{1}}{C_{2}}\frac{t}{h(a_{t})}\right)\geq
1-\exp\\{-C_{f}h(a_{t})\\}$ (28)

for some $f$-dependent constant $C_{f}$. Since $V_{t}(f)$ is the sum of
independent Bernoulli random variables and $\mathbb{E}V_{t}(f)\leq
5f(t)t/4(1-\gamma)$, a Chernoff bound yields

$\mathbb{P}\left(V_{t}(f)\geq\frac{15f(t)t}{8(1-\gamma)}\right)\leq\exp\left\\{-\mathbb{E}V_{t}(f)/4\right\\},$
(29)

which proves that $G_{t}(f)$ has property $\mathcal{P}^{1}_{t}$ a.a.s. ∎

Now, if $H$ is a subset of vertices of a (multi)graph $G$, then $d_{G}(H)$,
the degree of $H$, is simply the sum of the degree of the vertices in $H$.
With this terminology in mind, let $\mathcal{P}_{(r+1)t}^{2}$ be the property
below

$\begin{split}\mathcal{P}_{(r+1)t}^{2}:=\left\\{\begin{array}[]{c}G=(V,E):|V|\leq\frac{15f((r+1)t)(r+1)t}{8(1-\gamma)},\exists
v^{*}\in V,\text{ s.t }d_{G}(v^{*})\geq\frac{C_{1}t}{C_{2}h(a_{t})},\\\
\exists H\subset G\text{ s.t. }d_{G}(H)\geq t/8\\\ \text{ and }\forall v\in
H\text{ there are }r\text{ edges between }v\text{ and
}v^{*}\end{array}\right\\}.\end{split}$ (30)

Now we will prove that $G_{t}(f)$ has property $\mathcal{P}_{(r+1)t}^{2}$
a.a.s.

######  Lemma 3.4.

Let $f$ be an edge-step function satisfying conditions $(S)$ and
$\mathrm{RES}(-\gamma)$ for $\gamma\in[0,1)$. Then,

$\mathbb{P}\left(G_{t}(f)\in\mathcal{P}_{(r+1)t}^{2}\right)=1-o(1).$

###### Proof.

Since $f$ will be fixed the entire proof, to avoid clutter, we will drop the
reference on $f$ in the notation $G_{t}(f)$, writing simply $G_{t}$. We will
prove first that conditioned on $G_{t}\in\mathcal{P}_{t}^{1}$, the graph
$G_{(r+1)t}$ has property $\mathcal{P}_{(r+1)t}^{2}$ a.a.s. Thus, suppose that
$G_{t}$ has property $1$ and let $v^{*}$ be its star. Let $j$ be a vertex
whose degree is at least $g(t)$ at time $t$. Notice that on the event
$V_{t}(f)\leq 15f(t)t/8(1-\gamma)$, there exists at least one such vertex,
otherwise we would have

$\sum_{v\in
G_{t}}d_{t}(v)\leq\frac{15g(t)f(t)t}{8(1-\gamma)}=\frac{15t}{8}<2t,$

which is a contradiction since $G_{t}$ is a graph with $t$ edges. Now, fix
$k\in\\{2,3,\cdots,r+1\\}$ and note that, for any $s\in[(k-1)t,kt]$, we have

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}\left(j\text{
connects to }v^{*}\text{ at time }s+1\;\middle|\;G_{s},d_{t}(j)\geq
g(t),G_{t}\in\mathcal{P}_{t}^{1}\right)$\mbox{}\hfil\phantom{************}\phantom{************}\phantom{*******}\\\
&=(1-f(s+1))\frac{d_{s}(j)d_{s}v^{*}}{2s^{2}}\\\
&\geq\frac{C_{1}}{3(r+1)^{2}C_{2}}\frac{g(t)t}{t^{2}h(a_{t})},\end{split}$
(31)

since the degree of a vertex is increasing in $s$, $s\leq(r+1)t$ and
$f\searrow 0$ implies that $1-f(t)\geq 2/3$ for sufficiently large $t$. Thus,
using condition (L), our choice of $h$ leads to

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}\left(j\text{
is not connected to }v^{*}\text{ in
}G_{kt}\;\middle|\;G_{(k-1)t},d_{(k-1)t}(j)\geq
g(t),G_{t}\in\mathcal{P}_{t}^{1}\right)$\mbox{}\hfil\phantom{************}\phantom{*******************}\\\
&\leq\left(1-\frac{C_{1}}{3(r+1)^{2}C_{2}}\frac{g(t)}{th(a_{t})}\right)^{t}\\\
&\leq\exp\left\\{-2\frac{f(a_{t})\log(a_{t})}{f(t)}\right\\}\\\
&\leq\exp\left\\{-2\frac{f(a_{t})\log(a_{t})}{f(t)\log t}\log t\right\\}\\\
&\leq e^{-2\log t}.\end{split}$ (32)

Now, let $M_{t}(g(t))$ be the set of vertices in $G_{t}$ whose degree is at
least $g(t)$. Observe that $|M_{t}(g(t))|\leq t$ almost surely. Then, for each
$k\in\\{2,\dots,r\\}$ we have

$\mathbb{P}\left(\exists j\in M_{t}(g(t))\text{ that does not connect to
}v^{*}\text{ in the interval
}[(k-1)t,kt]\;\middle|\;G_{t}\in\mathcal{P}_{t}^{1}\right)\leq\frac{1}{t}.$

Consequently, we have

$\mathbb{P}\left(\exists j\in M_{t}(g(t))\text{ that does not send }r\text{
edges to }v^{*}\text{ in
}G_{(r+1)t}\;\middle|\;G_{t}\in\mathcal{P}_{t}^{1}\right)\leq\frac{r}{t}.$
(33)

Finally, let $H$ be the subgraph of $G_{t}$ composed by all its vertices whose
degree is at least $g(t)$. On the event where $V_{t}(f)\leq
15f(t)t/8(1-\gamma)$ the sum of the degree of all vertices not in $H$
satisfies

$\sum_{v\notin H}d_{t}v<\frac{15}{8(1-\gamma)}g(t)f(t)t=\frac{15t}{8}.$ (34)

Since the sum of all degrees equals in $G_{t}$ equals $2t$, by the above
inequality,

$d_{t}(H):=\sum_{v\in H}d_{t}(v)\geq t/8,$

whenever $V_{t}(f)\leq 15f(t)t/8$, which is satisfied when
$G_{t}\in\mathcal{P}_{t}^{1}$. This shows that whenever $G_{t}$ is in
$\mathcal{P}^{1}_{t}$, then w.h.p $G_{(r+1)t}$ has a subgraph $H$ with total
degree in $G_{(r+1)t}$ larger than $t/8$, such that each vertex in $H$ shares
at least $r$ edges with $v^{*}$. Moreover, when $v^{*}$ is seen as a vertex of
$G_{(r+1)t}$ it is a vertex of degree at least $C_{1}t/C_{2}h(a_{t})$ as well,
since the degree of a vertex is increasing in time. Therefore, using Lemma
3.3, we obtain

$\begin{split}\mathbb{P}\left(G_{(r+1)t}\notin\mathcal{P}_{(r+1)t}^{2}\right)&\leq\mathbb{P}\left(G_{(r+1)t}\notin\mathcal{P}_{(r+1)t}^{2},G_{t}\in\mathcal{P}^{1}_{t}\right)+\mathbb{P}\left(G_{t}\notin\mathcal{P}^{1}_{t}\right)\\\
&\leq\frac{r}{t}\mathbb{P}\left(G_{t}\in\mathcal{P}_{t}^{1}\right)+\mathbb{P}\left(G_{(r+1)t}^{1}\notin\mathcal{P}_{(r+1)t}^{1}\right)+\mathbb{P}\left(G_{t}\notin\mathcal{P}^{1}_{t}\right)=o(1),\end{split}$
(35)

which completes the proof. ∎

We move to our third required property. To avoid clutter in its definition we
define the properties we are interested in below. Fix a (multi)graph $G=(V,E)$
and a number $\zeta>0$ and consider the graph properties:

  1. (1)

$|V|\leq\frac{15f((r+1)^{2}t)(r+1)^{2}t}{8(1-\gamma)}$;

  2. (2)

there exists $v^{*}\in V$ whose degree is bounded from bellow by

$d_{G}v^{*}\geq\frac{C_{1}t}{C_{2}h\left(a_{t}\right)}$

  3. (3)

there exists $H\subset V$ such that $d_{G}H\geq t/8$ and $\forall v\in H$
there are $r$ edges between $v$ and $v^{*}$;

  4. (4)

there exists $S\subset V$ such that $|S|\geq\zeta f(t)t$ and each $v\in S$
sends at least $r$ edges to $H$.

For a fixed number $\zeta>0$, we let $\mathcal{P}_{(r+1)^{2}t}^{3}(\zeta)$ be
the (multi)graph family defined below

$\begin{split}\mathcal{P}_{(r+1)^{2}t}^{3}(\zeta):=\left\\{G=(V,E):G\text{
satisfies all the properties (1)-(4) with parameter
}\zeta\right\\}.\end{split}$

######  Lemma 3.5.

Let $f$ be an edge-step function satisfying conditions $(S)$ and
$\mathrm{RES}(-\gamma)$ for $\gamma\in[0,1)$. Then, there exists a number
$\zeta_{0}>0$ depending on $r$ and $f$ only such that

$\mathbb{P}\left(G_{(r+1)^{2}t}(f)\in\mathcal{P}_{(r+1)^{2}t}^{3}(\zeta_{0})\right)=1-o(1).$

###### Proof.

Observe that $(1)$ is a consequence of Lemma 3.3 applied to
$G_{(r+1)^{2}t}(f)$. Whereas $(2)$ and $(3)$ are implied by Lemma 3.4 applied
to $G_{(r+1)^{2}t}(f)$.

Thus, we are left to prove that $(4)$ holds a.a.s. The way we prove this is by
showing that conditioned on $G_{(r+1)t}(f)\in\mathcal{P}_{(r+1)t}^{2}$, a
positive proportion of vertices of degree $1$ in $G_{(r+1)t}(f)$ connects to
$H$ at time $2(r+1)t$. Then we iterate this argument $r$ times, similarly to
what we have done to show the existence of $H$. For this, we need some
definitions. Denote by $S_{(r+1)t}(1)$ the random set consisting of vertices
of degree exactly $1$ at time $(r+1)t$ and let $N_{(r+1)t}(1)$ be its
cardinality. Also, let $A_{s}$ and $C_{s}$ be the random sets

$\begin{split}A_{s}&:=\left\\{v\in S_{(r+1)t}(1);\;v\text{ does not connect to
}H\text{ up to time }s\right\\};\\\ C_{s}&:=\left\\{v\in
S_{(r+1)t}(1);\;v\text{ connects to }H\text{ between times }(r+1)t\text{ and
}s\right\\}.\end{split}$ (36)

We say a vertex in $A_{s}$ is available to connect to $H$. At each step, we
try to connect an available vertex to $H$ using an edge-step. We are going to
prove that w.h.p. $|C_{2(r+1)t}|$ is a positive proportion of $S_{(r+1)t}(1)$.
So, let $\\{Y_{s}\\}_{s\geq t}$ be the following process

$Y_{s}:=\mathds{1}\left\\{\text{some vertex }v\text{ in }A_{s}\text{ connects
to }H\text{ at time }s\right\\}.$ (37)

Note that $|C_{2(r+1)t}|=\sum_{s=t}^{2(r+1)t}Y_{s}$. Consider the following
stopping time

$\eta:=\inf\left\\{s\geq t:|A_{s}|\leq N_{(r+1)t}(1)/2\right\\},$ (38)

To simplify our writing, we will denote by $\mathbb{P}_{G_{(r+1)t}}$ the law
of $\\{G_{s}(f)\\}_{s\geq(r+1)t}$ conditioned on the event where graph
$G_{(r+1)t}(f)=G_{(r+1)t}$ for some given admissible
$G_{(r+1)t}\in\mathcal{P}_{(r+1)t}^{2}$. With this notation in mind, observe
that, for $s\in[(r+1)t,2(r+1)t]$ and large enough $t$

$\mathbb{P}_{G_{(r+1)t}}\left(Y_{s+1}=1\;\middle|\;G_{s}(f)\right)\geq(1-f(s+1))\frac{|A_{s}|d_{s}H}{2s^{2}}\geq\frac{65|A_{s}|}{t},$
(39)

since $d_{s}H\geq t/8$ and $1-f(s+1)\geq 64/65$ for large $t$. Then, by the
definition of $\eta$, it also follows that

$\mathbb{P}_{G_{(r+1)t}}\left(Y_{s+1}=1,\eta>s\;\middle|\;G_{s}(f)\right)\geq\frac{N_{(r+1)t}(1)/130}{t}\mathds{1}_{\\{\eta>s\\}}=:q_{(r+1)t}\mathds{1}_{\\{\eta>s\\}}.$
(40)

The above inequality implies that, on the event $\\{\eta>2(r+1)t\\}$, the sum
$\sum_{s=(r+1)t}^{2(r+1)t}Y_{s}$ dominates a r.v. following a binomial
distribution of parameters $(r+1)t$ and $q_{(r+1)t}$. Then,

$\begin{split}\mathbb{P}_{G_{(r+1)t}}\left(|C_{2(r+1)t}|\leq\frac{N_{(r+1)t}(1)}{260}\right)&\leq\mathbb{P}_{G_{(r+1)t}}\left(\mathrm{bin}(t,q_{(r+1)t})\leq\frac{N_{(r+1)t}(1)}{260},\eta>2(r+1)t\right)\\\
&\quad+\mathbb{P}_{G_{(r+1)t}}\left(|C_{2(r+1)t}|\leq\frac{N_{(r+1)t}(1)}{260},\eta\leq
2(r+1)t\right)\\\
&=\mathbb{P}_{G_{(r+1)t}}\left(\mathrm{bin}(t,q_{(r+1)t})\leq\frac{cN_{(r+1)t}(1)}{4},\eta>2(r+1)t\right),\end{split}$
(41)

since on $\\{\eta\leq 2(r+1)t\\}$ we have that $|C_{2(r+1)t}|\geq
N_{(r+1)t}(1)/2$. Thus, by Chernoff bounds

$\begin{split}\mathbb{P}_{G_{(r+1)t}}\left(|C_{2(r+1)t}|\leq\frac{N_{(r+1)t}(1)}{260}\right)&\leq\mathbb{P}_{G_{(r+1)t}}\left(\mathrm{bin}(t,q_{(r+1)t})\leq\frac{N_{(r+1)t}(1)}{260}\right)\leq
e^{-N_{(r+1)t}(1)/520},\end{split}$ (42)

since $\mathrm{bin}(t,q_{(r+1)t})$ has mean $N_{(r+1)t}(1)/130$ (which is
measurable with respect to $G_{(r+1)t}$). Bow, a Chernoff bound and Theorem 1
of [3] imply that, w.h.p. $N_{(r+1)t}(1)\geq c_{f}f(t)t$ for an $f$-dependent
constant $c_{f}>0$ (indeed, just take $A=o(\mathbb{E}V_{(r+1)t}(f))$ in the
Theorem mentioned, and use a Chernoff bound to show that $V_{(r+1)t}(f)$
concentrates). The above upper bound combined with Lemma 3.4 gives us that
$\mathbb{P}\left(C_{2(r+1)t}\leq(1/65)\cdot c_{f}f(t)t\right)$ is bounded from
above by

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}\left(|C_{2(r+1)t}|\leq
N_{(r+1)t}(1)/260,\,N_{(r+1)t}(1)\geq
c_{f}f(t)t,\,G_{(r+1)t}(f)\in\mathcal{P}^{2}_{(r+1)t}\right)$\mbox{}\hfil\quad\\\
&\quad+\mathbb{P}\left(G_{(r+1)t}(f)\notin\mathcal{P}_{(r+1)t}^{2}\right)+\mathbb{P}\left(N_{(r+1)t}(1)\leq
ctf(t)\right)\\\ &=o(1),\end{split}$

Now we can iterate this argument with the set $C_{2(r+1)t}$ instead of
$N_{(r+1)t}(1)$ to guarantee w.h.p that there exist at least
$c^{\prime}f(t)t$, for some constant $c^{\prime}$ depending on $r$ and $f$,
vertices sending at least two edges to $H$ in $G_{3(r+1)t}(f)$ and so on.
Choosing $\zeta_{0}$ appropriately, and recalling that, by the fact $f$ is a
regularly varying function, we have that

$\frac{f(t)t}{(r+1)f((r+1)t)t}\to(r+1)^{\gamma-1},$

as $t$ goes to infinity, is enough to conclude the proof.

∎

We define the last property we want our graphs to satisfy a.a.s. Given a
vertex $v$ in a $G_{t}(f)$, we let $\Gamma_{t}(v)$ be the number of neighbors
of $v$. Observe that $\Gamma_{t}(v)\leq d_{t}(v)$. For two fixed positive
numbers $\zeta$ and $\kappa$, consider the following list of graph properties

  1. (1)’

$|V|\leq\frac{15f(2(r+1)^{2}t)2(r+1)^{2}t}{8(1-\gamma)}$;

  2. (2)’

there exists $v^{*}\in V$ whose degree is bounded from bellow by

$d_{G}v^{*}\geq\frac{C_{1}t}{C_{2}h\left(a_{t}\right)};\quad\Gamma_{t}(v^{*})\geq\kappa\frac{f(t)t}{h(a_{t})};$

  3. (3)’

there exists $H\subset V$ such that $d_{G}H\geq t/16$ and $\forall v\in H$
there are $r$ edges between $v$ and $v^{*}$;

  4. (4)’

there exists $S\subset V$ such that $|S|\geq\zeta f(t)t$ and each $v\in S$
sends at least $r$ edges to $H$.

We then let $\mathcal{P}_{2(r+1)^{2}t}^{4}(\zeta,\kappa)$ be

$\begin{split}\mathcal{P}^{4}_{2(r+1)^{2}t}(\zeta,\kappa):=\left\\{G=(V,E):G\text{
satisfies all properties }(1)^{\prime}-(4)^{\prime}\text{ with parameters
}\zeta\text{ and }\kappa\right\\}.\end{split}$

Next result also guarantees that the above property holds a.a.s..

######  Lemma 3.6.

Let $f$ be an edge-step function satisfying conditions $(S)$ and
$\mathrm{RES}(-\gamma)$ for $\gamma\in[0,1)$. Then, there exist positive
parameters $\zeta_{0}$ and $\kappa_{0}$ depending on $f$ and $r$ only such
that

$\mathbb{P}\left(G_{t}(f)\in\mathcal{P}_{2(r+1)^{2}t}^{4}(\zeta,\kappa)\right)=1-o(1).$

###### Proof.

As usual we will prove that $G_{2(r+1)^{2}t}(f)$ satisfies
$(1)^{\prime}-(4)^{\prime}$ for some oarameters $\zeta_{0}$ and $\kappa_{0}$.
The property $(1)^{\prime}$ is consequence of Lemma 3.3 applied directly to
$G_{2(r+1)^{2}t}(f)$. Whereas $(3)^{\prime}$ and $(4)^{\prime}$ follow by
conditioning on $G_{(r+1)^{2}t}(f)\in\mathcal{P}_{(r+1)^{2}t}^{3}(\zeta)$ and
seeing it as a subgraph of $G_{2(r+1)^{2}t}(f)$.

Thus we are left to prove $(2)^{\prime}$. The key step is to show
$(2)^{\prime}$ is seeing that, conditioned on
$G_{(r+1)^{2}t}(f)\in\mathcal{P}_{(r+1)^{2}t}^{3}(\zeta)$, the graph
$G_{2(r+1)^{2}t}(f)$ has w.h.p a vertex $v^{*}$ such that
$\Gamma_{2(r+1)^{2}t}(v^{*})\geq\kappa f(t)t/h(a_{t})$, for some positive
number $\kappa$ w.h.p.. For this purpose, observe that if $v^{*}$ has degree
at least $C_{1}C_{2}^{-1}t/h(a_{t})$ at time $(r+1)^{2}t$, then for any
$s\in((r+1)^{2}t,2(r+1)^{2}t)$, we have that

$\mathbb{P}\left(\Gamma_{s+1}(v^{*})-\Gamma_{s}(v^{*})=1\;\middle|\;\mathcal{F}_{s},d_{t}v^{*}\geq\frac{C_{1}t}{C_{2}h(a_{t})}\right)\geq\frac{C_{1}}{C_{2}}f(s)\frac{t}{2sh(a_{t})}\geq\frac{C_{1}}{C_{2}}\frac{f(2(r+1)^{2}t)}{4(r+1)^{2}h(a_{t})}.$

Thus, using the fact that $f$ is a regularly varying function with index
$-\gamma$, setting

$\kappa_{1}=\frac{C_{1}}{4(r+1)^{2+\gamma}C_{2}},$

and conditioning on $G_{(r+1)^{2}t}(f)\in\mathcal{P}_{(r+1)^{2}t}^{3}(\zeta)$,
the number of neighbors $v^{*}$ has at time $2(r+1)^{2}t$ dominates a binomial
random variable with parameters $(r+1)^{2}t$ and $\kappa_{1}f(t)/2h(a_{t})$
for large $t$. Recalling the definition of functions $h$ and $g$ at (25) it
follows that

$\frac{\kappa_{1}(r+1)^{2}tf(t)}{h(a_{t})}=\kappa_{1}(r+1)^{2}\frac{C_{1}(1-\gamma)}{6}{C_{2}(r+1)^{2}}^{\prime}tf(t)f(a_{t})\log(a_{t})\to\infty,$

by condition (L). Thus, conditioned on
$G_{(r+1)^{2}t}(f)\in\mathcal{P}_{(r+1)^{2}t}^{3}$, by Chernoff bounds on the
binomial

$\mathrm{bin}((r+1)^{2}t,\kappa_{1}f(t)/h(a_{t})),$

it follows that the (multi)graph $G_{2(r+1)^{2}t}(f)$ has a vertex $v^{*}$
with at least $2\kappa_{1}tf(t)/3h(a_{t})$ neighbors. Using that
$G_{(r+1)^{2}t}(f)\in\mathcal{P}_{(r+1)^{2}t}^{3}(\zeta)$ a.a.s., and defining
$kappa_{0}=(2/3)\kappa_{1}$, we conclude the proof.

∎

Finally we are able to prove Theorem 2’ which implies Theorem 2 immediately.

###### Proof of Theorem 2’.

We first fix the parameter $r$ of the bootstrap percolation process and define
$\mathcal{G}_{t}$ as $\mathcal{P}_{t}^{4}(\zeta,\kappa)$, where $\zeta_{0}$
and $\kappa_{0}$ are the positive numbers given by Lemma 3.6. Now we are left
to prove that the bootstrap percolation process on a (multi)graph in the
collection $\mathcal{G}_{t}$ and parameters $a_{t}$ and $r$ w.h.p has an
outbreak of infection in at most $3$ steps.

Summarizing all we have proven about $G_{t}(f)$ so far, a (multi)graph in
$\mathcal{G}_{t}$ has the following structure:

  1. (1)

$G_{t}(f)$ has at most $15f(t)t/8(1-\gamma)$ vertices;

  2. (2)

There exists a star $v^{*}\in G_{t}(f)$ such that

$\Gamma_{t}(v^{*})\geq\frac{\kappa_{0}f(t)t}{h(a_{t/2(r+1)^{2}})};$ (43)

  3. (3)

All vertices of degree at least $g(t)$ at time $t/(2(r+1)^{2})$ are connected
$r$ times to $v^{*}$ in $G_{t}(f)$. This is the subgraph $H$;

  4. (4)

There exists a subset $S\subset G_{t}$ containing at least $\zeta_{0}f(t)t$
vertices whose elements are connected to $H$ at least $r$ times, that is, each
vertex in $S$ sends at least $r$ edges to $H$.

Having all the properties above in mind, we start the bootstrap percolation
process. In the round zero we construct $\mathcal{I}_{0}$. We add each vertex
in $G_{t}(f)$ to $\mathcal{I}_{0}$ independently and with probability
$a_{t}/|V(G_{t}(f))|$. Observe that by $(1)$, it follows that

$\frac{a_{t}}{|V(G_{t}(f))|}\geq\frac{c_{1}a_{t}}{f(t)t},$

where $c_{1}=8(1-\gamma)/15$.

Now, observe that the number of neighbors of $v^{*}$ infected at round zero
dominates a binomial random variable with parameters
$\kappa_{0}f(t)t/h(a_{t/2(r+1)^{2}})$ and $c_{1}a_{t}/f(t)t$. Since $f$ is a
regularly varying function with index $-\gamma\in(-1,0]$, and $a_{t}$ is
increasing to infinity, Corollary 5 implies that $a_{t}/h(a_{t/2(r+1)^{2}})$
goes to infinity as $t$ goes to infinity. This and Chernoff bounds implies
that

$\mathbb{Q}_{G_{t}(f),a_{t},r}\left(\mathcal{I}_{0}\text{ contains at least
}r\text{ neighbors of }v^{*}\right)=1-o(1).$ (44)

In words, at round zero $v^{*}$ has at least $r$ infected neighbors w.h.p. Now
observe that given that $v^{*}$ has at least $r$ neighbors in
$\mathcal{I}_{0}$, it follows that at round one $v^{*}$ gets infected. Then,
at the next round all the subgraph $H$ gets infected since all of its vertices
send at least $r$ edges to $v^{*}$. Finally at round three, $S$ gets infected
since all of its vertices send at least $r$ edges to $H$. This proves that
$\mathcal{I}_{3}$ is a positive proportion of $G_{t}(f)$ and proves our
theorem. ∎

##  Appendix A Martingale concentration inequalities

For the sake of completeness we state here two useful concentration
inequalities for martingales which are used throughout the paper.

######  Theorem 3 (Azuma-Höffeding Inequality - see [10]).

Let $(M_{n},\mathcal{F})_{n\geq 1}$ be a martingale satisfying

$\lvert M_{i+1}-M_{i}\rvert\leq a_{i}$

Then, for all $\l>0$ we have

$\mathbb{P}\left(|M_{n}-M_{0}|>\lambda\right)\leq\exp\left(-\frac{\lambda^{2}}{\sum_{i=1}^{n}a_{i}^{2}}\right).$

##  Appendix B Karamata theory

The three following results are used throughout the paper.

######  Corollary 4 (Representation theorem - Theorem $1.4.1$ of [8]).

Let $f$ be a continuous regularly varying function with index of regular
variation $\gamma$. Then, there exists a slowly varying function $\ell$ such
that

$f(t)=t^{\gamma}\ell(t),$ (45)

for all $t$ in the domain of $f$.

######  Corollary 5.

Let $f$ be a continuous regularly varying function with index of regular
variation $\gamma<0$. Then,

$f(x)\to 0,$ (46)

as $x$ tends to infinity. Moreover, if $\ell$ is a slowly varying function,
then for every $\varepsilon>0$

$x^{-\varepsilon}\ell(x)\to 0\text{ and }x^{\varepsilon}\ell(x)\to\infty$ (47)

###### Proof.

Comes as a straightforward application of Theorem $1.3.1$ of [8] and Corollary
4. ∎

######  Theorem 6 (Karamata’s theorem - Proposition $1.5.8$ of [8]).

Let $\ell$ be a continuous slowly varying function and locally bounded in
$[x_{0},\infty)$ for some $x_{0}\geq 0$. Then

  * (a)

for $\alpha>-1$

$\int_{x_{0}}^{x}t^{\alpha}\ell(t)dt\sim\frac{x^{1+\alpha}\ell(x)}{1+\alpha}.$
(48)

  * (b)

for $\alpha<-1$

$\int_{x}^{\infty}t^{\alpha}\ell(t)dt\sim\frac{x^{1+\alpha}\ell(x)}{1+\alpha}.$
(49)

Acknowledgements  C.A. was supported by the Noise-Sensitivity everywhere ERC
Consolidator Grant 772466.

## References

  * [1] C. Alves, R. Ribeiro, and R. Sanchis.  Large communities in a scale-free network.  Journal of Statistical Physics, 166(1):137–149, 2017.
  * [2] C. Alves, R. Ribeiro, and R. Sanchis.  Topological properties of p.a. random graphs with edge-step functions.  arXiv preprint arXiv: 1902.10165, 2019.
  * [3] C. Alves, R. Ribeiro, and R. Sanchis.  Preferential attachment random graphs with edge-step functions.  Journal of Theoretical Probability, 34, 03 2021.
  * [4] Caio Alves, Rodrigo Ribeiro, and Rémy Sanchis.  Diameter of p.a. random graphs with edge-step functions.  Random Structures & Algorithms, 57(3):612–636, 2020.
  * [5] M. Amin Abdullah and N. Fountoulakis.  A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs.  Random Structures & Algorithms, 52(3):379–418, 2018.
  * [6] A-L. Barabási and R. Albert.  Emergence of scaling in random networks.  Science, 1999.
  * [7] Noam Berger, Christian Borgs, Jennifer T Chayes, and Amin Saberi.  On the spread of viruses on the internet.  2005\.
  * [8] N H Bingham, C M Goldie, and J L Teugels.  Regular variation, volume 27.  Cambridge university press, 1989.
  * [9] Van Hao Can.  Metastability for the contact process on the preferential attachment graph.  arXiv preprint arXiv:1502.05633, 2015.
  * [10] F. Chung and L. Lu.  Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics).  American Mathematical Society, Boston, MA, USA, 2006.
  * [11] R. Durrett.  Random Graph Dynamics (Cambridge Series in Statistical and Probabilistic Mathematics).  Cambridge University Press, 2006.
  * [12] Emmanuel Jacob, Amitai Linker, Peter Mörters, et al.  Metastability of the contact process on fast evolving scale-free networks.  Annals of Applied Probability, 29(5):2654–2699, 2019.
  * [13] S.H Strogatz and D. J. Watts.  Tcollective dynamics of ’small-world’ networks.  Nature, 1998.
  * [14] R. van der Hofstad.  Random Graphs and Complex Networks: Volume 1.  Cambridge University Press, 1st edition, 2016.