Keishiro Yamashita
email: keishiro.yamashita@uibk.ac.at

Kazuki Komatsu

Stefan Klotz

Oscar Fabelo

Maria T Fernández-Díaz

Jun Abe

Shinichi Machida

Takanori Hattori

Tetsuo Irifune

Toru Shinmei

Kazumasa Sugiyama

Toru Kawamata

Hiroyuki Kagi

Atomic distribution and local structure in ice VII from in situ neutron diffraction

Keywords: ice, high pressure, neutron diffraction, disordered structure

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Main Text

Introduction

Water freezes into various solid structures, including crystalline and non-crystalline phases, when compressed or cooled down. Ice VII is one of its 20 crystalline phases and is stable at room temperature between 2 and 60 GPa. In this pressure range, ice VII shows various anomalous behaviors related to pressure-dependent proton dynamics such as a sharpening of the Raman peak of its symmetric vibration mode at 11-13 GPa(1) which is caused by a cross-over of dominant processes from molecular rotation to proton translation [START_REF] Komatsu | Anomalous hydrogen dynamics of the ice VII-VIII transition revealed by high-pressure neutron diffraction[END_REF][START_REF] Iitaka | Simulating proton dynamics in high-pressure ice[END_REF]. Ice VII also undergoes a phase transition involving hydrogen-bond symmetrization toward ice X [START_REF] Benoit | Tunnelling and zero-point motion in high-pressure ice[END_REF][START_REF] Benoit | Quantum effects on phase transitions in high-pressure ice[END_REF]. This anomalous crystalline phase has attracted much scientific interest, and it hence appears crucial to understand its detailed structure.

The structure of ice VII can be regarded as two interpenetrating diamond-like networks formed by hydrogen-bonded water molecules (Figure 1a). In each network, water molecules are orientationally disordered as those in other ice polymorphs (e.g. ordinary ice I h [START_REF] Peterson | A single-crystal neutron diffraction study of heavy ice[END_REF]). Hydrogens of each water molecule randomly occupy two of four sites toward the neighboring oxygens. In other words, the overall structure of ice VII consists of a combination of various configurations. Ice VII transforms into ice VIII by ordering the hydrogen positions (or molecular orientations) at low temperatures (below 273 K at 3 GPa [START_REF] Whalley | Dielectric Properties of Ice VII. Ice VIII: A New Phase of Ice[END_REF]). In ice VIII, the orientations of water molecules are well defined: hydrogens occupy two particular sites, and molecular orientations between the interpenetrating networks are aligned antiparallel along the c-axis, which induces displacement of the network relative to the other along the c-axis. This results in a tetragonal distortion of ice VIII.

The disordered structure of ice VII is generally represented by a cubic unit cell with space group (#224) in which oxygens locate at 2a site, and hydrogens at 8e site with occupancy of 0.5 (hereafter, this model is called a "single-site" model). The symmetric constraints simplify the structure model as it needs only one parameter for the hydrogen position (x, x, x) and two variables for atomic displacement parameters (ADPs) (three for anisotropic ADPs). The singlesite model reproduces well the diffraction patterns and therefore has been adopted in almost all previous studies [START_REF] Klotz | Bulk moduli and equations of state of ice VII and ice VIII[END_REF][START_REF] Komatsu | Crystal structure of magnesium dichloride decahydrate determined by X-ray and neutron diffraction under high pressure[END_REF]. Nevertheless, structure refinements based on the single-site model are known to cause a highly anomalous geometry of the water molecule, e.g. an unrealistically short O-D covalent bond length (0.89 Å( 10)) compared to those in ice VIII (0.97 Å) [START_REF] Kuhs | Structure and hydrogen ordering in ices VI, VII, and VIII by neutron powder diffraction[END_REF][START_REF] Jorgensen | Structure of D 2 O ice VIII from i n s i t u powder neutron diffraction[END_REF] whereas a computational study showed similar distances for both phases [START_REF] Kuo | Structure of Ice-VII and Ice-VIII: A Quantum Mechanical Study[END_REF]. This implies that water molecules in ice VII are not in the positions assumed in the single-site model. The agreement of the single-site model with the diffraction patterns appears to be a result of time and spatial averaging in diffraction measurements.

On the other hand, more reasonable "multi-site" models have been proposed up to date to describe the real structure of ice VII. In these models, the hydrogen atoms are located away from a straight line between adjacent oxygens, especially toward the three non-bonded oxygens belonging to the other hydrogen-bonding network [START_REF] Jorgensen | Disordered structure of D2O ice VII from in situ neutron powder diffraction[END_REF]. Oxygen positions were modelled mainly in two ways: displacements toward <111> [START_REF] Nelmes | Multisite Disordered Structure of Ice VII to 20 GPa[END_REF] or <100> [START_REF] Kuhs | Structure and hydrogen ordering in ices VI, VII, and VIII by neutron powder diffraction[END_REF] as illustrated in Figure 1b.

Displacements along <100> imply that ice VII favours local structures similar to those in the ordered structure of ice VIII while displacements along <111> imply the opposite. The <111 > model entails differences in hydrogen-bond length: a shorter one in which one oxygen gets close to the neighbor and a longer one in which oxygen is away from the neighbor [START_REF] Nelmes | Multisite Disordered Structure of Ice VII to 20 GPa[END_REF]. The existence of the bimodal probability of hydrogen-bond length is still controversial [START_REF] Li | Inelastic incoherent neutron scattering study of the pressure dependence of ice VII and VIII[END_REF][START_REF] Klotz | Incoherent inelastic neutron scattering measurements on ice VII: Are there two kinds of hydrogen bonds in ice?[END_REF]. However, no unambiguous structure refinements have been achieved so far because the atomic displacements from the single-site position are very small (0.1 Å) and this parameter strongly correlates with ADPs in the structure refinement. A computational study from density functional theory (DFT) suggested a probability distribution similar to the <100> displacement of oxygen rather than <111> although it also insisted that both displacement models are too simplistic [START_REF] Knight | Site disorder in ice VII arising from hydrogen bond fluctuations[END_REF].

In conclusion, the actual structure in ice VII has not been experimentally proven up to the present.

Here we report in-situ single-crystal neutron diffraction using a newly developed apparatus.

Previous powder diffraction studies had limitations in resolution related to peak duplicates in onedimensional diffractograms, whereas single-crystal diffraction can directly provide discrete reflection intensities without peak overlap and can lead to a definitive conclusion by doublechecking with the well-established powder diffraction technique [START_REF] Hattori | Design and performance of high-pressure PLANET beamline at pulsed neutron source at J-PARC[END_REF]. In addition to the technical improvements in measurements, non-conventional analytical approaches are also necessary to reveal the detailed disordered structure of the dense ice without constraints from structure models like the single-site model because conventional analyses have considerable difficulties in modeling the real distribution. We applied a maximum entropy method (MEM) analysis to reveal three-dimensional atomic distributions in the unit cell. Moreover, information on local structures like the water geometry was extracted as interatomic correlation by total scattering analysis. For these approaches, neutron diffraction is suitable for this study owing to its sensitivity to hydrogen (deuterium). The scattering length does not decay according to sinθ/λ ∝ 1/d in contrast to x-ray diffraction. Therefore, numerous reflections are observable even for low d-spacing, which allows a structure analysis with high resolution in real space. Deuterated samples (D 2 O) were used in all the experiments instead of light water (H 2 O) to avoid incoherent scattering. This isotope replacement shifts the phase boundary between ices VI and VII toward slightly lower pressure but does not affect significantly the disordered structures investigated in this study.

Results

The MEM analysis is based on the principle of maximum entropy, a part of Bayesian statistics, which expects the most probable density distribution to be one with the largest information entropy under constraints on the observed structure factors F o and their uncertainties σF o .

Results of MEM analyses on both single crystal and powder diffraction data show ring-like distributions of deuterium around the <111> axes, direction toward the oxygen of hydrogenbonded water, away from the position assumed in the single-site model (Figures 2a and2b), and the ring is slightly distorted to a triangular shape. Their maxima are displaced from the axes by 0.1-0.2 Å. These are similar to the reported values [START_REF] Jorgensen | Disordered structure of D2O ice VII from in situ neutron powder diffraction[END_REF][START_REF] Nelmes | Multisite Disordered Structure of Ice VII to 20 GPa[END_REF], but such a ring-like distribution can only be approximately described by the displacement ellipsoid conventionally used in leastsquares structure refinements. The corners of the triangular-like distribution are in staggered directions to other deuterium sites covalently bonded to the oxygen as previously suspected [START_REF] Jorgensen | Disordered structure of D2O ice VII from in situ neutron powder diffraction[END_REF].

From Figures 2c and2d, the distance between the maxima of density assigned to deuterium and the average oxygen site is shorter than a plausible covalent O-D bond length of 0.97 Å as found in ice VIII [START_REF] Kuhs | Structure and hydrogen ordering in ices VI, VII, and VIII by neutron powder diffraction[END_REF][START_REF] Jorgensen | Structure of D 2 O ice VIII from i n s i t u powder neutron diffraction[END_REF]. This explains that the conventional structure analysis using the single-site model results in a shorter (average) O-D covalent bond, whereas the deuterium in ice VIII does not show such spreading distribution (Figure S4).

On the other hand, oxygens show more elongated distributions toward the O-D covalent bond (Figures 2c and2d), which corresponds to <111> direction in the ice VII structure rather than <100> or <110> directions. However, the density distributions are not tetrapodal but pyramidal, meaning that other components such as along <100> are not fully excluded. The real disordered structure would be the combination of dominant displacements toward <111> and some other components with variations. The more diffuse features in the single-crystal data compared to the powder data would be mainly due to the achieved resolution for the observed diffractions. Nonetheless, our examinations from two distinct experimental setups, at different neutron sources, different high-pressure devices, and different detectors, suggest the feature of <111> displacement of oxygen is real and intrinsic for ice VII. This is hence consistent with the model proposed by Nelmes et al. [START_REF] Nelmes | Multisite Disordered Structure of Ice VII to 20 GPa[END_REF].

These displacements of oxygen and deuterium were partly proposed in the previous studies [START_REF] Jorgensen | Disordered structure of D2O ice VII from in situ neutron powder diffraction[END_REF][START_REF] Nelmes | Multisite Disordered Structure of Ice VII to 20 GPa[END_REF], but our study shows for the first time unambiguously the three-dimensional distribution in ice VII by the model-independent MEM approach. Our result shows that the structure of ice VII is clearly distinct from the single-site model. The ring-like distribution of deuterium can be ascribed to the time and spatial average of water molecules in different orientations rather than a distortion of water molecules themselves like DOD bending. Such displacement induces bending of the hydrogen-bonding networks from an ideal diamond-like network with cubic symmetry.

It should be noted that the density distribution of deuterium also elongates toward oxygens of the neighboring water molecules. This suggests two possibilities. One explanation is that hydrogenbonded water molecules get closer, which means the network structure is modified. The other explanation is that the interpenetrating hydrogen-bonding network locally displaces along <111>. This would mean that the local structure of ice VII differs from that of ice VIII, the hydrogenordered phase, with displacement along <100>.

Relating to the displacement of oxygen along the <111> direction, a modulated structure was previously proposed from single-crystal x-ray diffraction [START_REF] Loubeyre | Modulated phases and proton centring in ice observed by X-ray diffraction up to 170 GPa[END_REF][START_REF] Somayazulu | In situ high-pressure x-ray diffraction study of H2O ice VII[END_REF]. In our single-crystal neutron diffraction, however, no superlattice reflection was observed similar to any other studies using powder x-ray and neutron diffraction. There is no technical reason why such reflections cannot be observed in our experiment because the intensity of the superlattice reflection should be comparable to that of 111 reflections (see Figure 2 in ref [START_REF] Loubeyre | Modulated phases and proton centring in ice observed by X-ray diffraction up to 170 GPa[END_REF]) which were observed in our study.

The origin of the previously reported superlattice reflection remains hence unclear.

In order to reveal the short-range structures of ice VII such as interatomic distances and local ordering, the correlation functions were derived from the total scattering of powder diffraction instead of extracted intensities of the Bragg peaks as in the conventional structure refinements and the MEM analysis. The exact O-H(D) distance in ice I h was derived from the total scattering analysis [START_REF] Floriano | Direct determination of the intramolecular O-D distance in ice Ih and Ic by neutron diffraction[END_REF].

The total correlation functions T(r) of ice VII and VIII from powder diffraction at 274 K and 2.2 GPa has a similar profile in the short-r region (Figures 3a and3b). Assuming that each correlation has Gaussian type distribution, T(r) can be divided into several peaks. The representative geometries are listed in Table 1 with corresponding geometry obtained by the Rietveld analysis using the single-site model. The Rietveld analysis resulted in the O-D length of 0.9163 (5) Å in ice VII, significantly shorter than that of 0.9681 (8) Å in ice VIII which agree well with previously reported values [START_REF] Kuhs | Structure and hydrogen ordering in ices VI, VII, and VIII by neutron powder diffraction[END_REF][START_REF] Jorgensen | Structure of D 2 O ice VIII from i n s i t u powder neutron diffraction[END_REF]. Our fitting of T(r) gave an O-D distance of 0.9662 (5) Å for ice VII, proving the suggested similarity of its intramolecular structure with ice VIII [START_REF] Guthrie | The local structure of ice VII determined by neutron total scattering[END_REF]. The coordination numbers of the covalent O-D were estimated to be 1.8 for both ices VII and VIII. The slightly small value from the ideal number 2.0 would be ascribed to the systematic error related to the overall scaling of the scattering patterns, such as multiple scattering and attenuation. The molecular geometry of water in ice VII is hence identical to that in ice VIII, i.e. the apparently short O-D length in ice VII results from time-and spatial-average in Rietveld analyses.

To compare interatomic correlations at longer distances we discuss the pair distribution function G(r) instead of T(r). Figure 3c shows that both ices VII and VIII have a peak at 0.97 Å, which corresponds to the O-D covalent bond as discussed for T(r). On the other hand, the profiles differ from each other in the region longer than the lattice parameter a 0 of ice VII. This mean that ice VII does not have the same interatomic correlation as ice VIII over the distance of the second nearest neighbors. Especially, ice VIII has a tiny bump at 1.9 Å which corresponds to hydrogenbonded O...D whereas that region in ice VII is smooth. Such difference in the correlation function is attributed to the molecular ordering in each phase. Based on a reported DFT-based calculation [START_REF] Umemoto | Order-disorder phase boundary between ice VII and VIII obtained by first principles[END_REF], local configurations like ice VIII are not dominant at pT conditions where ice VII is stable but other configurations have comparative populations. These are consistent with the atomic distribution obtained from the MEM analysis in which <100> displacements are not observed.

Discussion

The atomic distribution observed in the MEM analyses would reflect the dynamic natures of ice VII. The total scattering analyses revealed that the water molecule has chemically plausible geometry in ice VII, as expected in the case of ice I h [START_REF] Floriano | Direct determination of the intramolecular O-D distance in ice Ih and Ic by neutron diffraction[END_REF]. The disorder comprises the molecular orientation and their displacements from the average positions, resulting in the unusual atomic arrangements of ice VII described by the discrete atomic sites in the single-site and multi-site models in conventional structure analyses. Spectroscopic studies [START_REF] Katoh | Protonic diffusion in highpressure ice VII[END_REF][START_REF] Okada | Electrical conductivity of ice VII[END_REF][START_REF] Noguchi | Self-diffusion of protons in H2O ice VII at high pressures: Anomaly around 10 GPa[END_REF] and the quick transformation from ice VIII to ice VII [START_REF] Komatsu | Anomalous hydrogen dynamics of the ice VII-VIII transition revealed by high-pressure neutron diffraction[END_REF] imply that the disordering of ice VII takes place dynamically at around 300 K. The atomic distribution is related to such dynamic conversion among the configurations. The dynamic motions in ice are expressed mainly by two components, rotation and translation. Their contributions depend on pressure in a contrasting way. At lower pressures, water molecules have enough space to flip and rotation motion is dominant. Under higher pressure, the water molecules get closer and become difficult to flip. On the other hand, reducing the intermolecular distances enhances the probability of translation of deuterium between neighboring water molecules. The cross-over of two dynamics takes place at around 10 GPa, first suggested from Raman spectroscopy(1) and recently proven from dielectric measurements [START_REF] Yamane | Direct evidence of the proton-dynamics crossover in ice VII from high-pressure dielectric measurements beyond 10 GPa[END_REF], and illustrates the origin of previously-reported anomalies: e.g. peak widths of stretching mode(1), phase transition kinetics(2), electrical conductivity [START_REF] Okada | Electrical conductivity of ice VII[END_REF], and proton diffusion [START_REF] Noguchi | Self-diffusion of protons in H2O ice VII at high pressures: Anomaly around 10 GPa[END_REF]. In conventional structure refinements, ADPs decrease with increasing pressure (2 < p < 10 GPa) and become almost constant above 10 GPa [START_REF] Klotz | Bulk moduli and equations of state of ice VII and ice VIII[END_REF][START_REF] Nelmes | Multisite Disordered Structure of Ice VII to 20 GPa[END_REF][START_REF] Guthrie | Structure and disorder in ice VII on the approach to hydrogen-bond symmetrization[END_REF]. This suggests that atomic distribution in ice VII will be more localized up to 10 GPa. The localized distribution should be linked with the suppression of rotational motion.

The representation with two types of dynamic movement in ice VII introduces an aspect to attribute the observed unexpected distribution in ice VII to two features. First, the probability density is distributed in a ring-like shape around the <111> axes. Second, the deuterium also has elongated distribution toward the oxygen of hydrogen-bonded water. These distributions correspond to instantaneous deviation from the average position. The ring-like distribution should be related to a precession, assignable to rotational or librational motions of molecules, whereas the elongation along the hydrogen bond would correspond to the translational motion of deuterium approaching the hydrogen-bonded neighboring molecule.

In addition to the dynamic nature of ice VII, static configurations also play important roles in the disordered structure of ice VII. The phase transition boundary between ices VII and VIII are almost temperature independent below 10 GPa, consistent with an estimation from the Clapeyron equation (dp/dT = ΔS/ΔV) with their little volume difference, ~ 5 mm 3 /mol compared to the Pauling entropy, 3.37 J/(K•mol). On the other hand, the boundary slope becomes steeper at higher pressures, suggesting that the volume change between ices VII and VIII is significant in this pressure regime. Ab initio calculation estimated the energy gaps among molecular configurations to be the smallest at this pressure regime, reproducing the tendency of the orderdisorder phase boundary between ices VII and VIII [START_REF] Umemoto | Order-disorder phase boundary between ice VII and VIII obtained by first principles[END_REF]. Our total scattering analysis revealed the clear difference in intermolecular structures of the disordered phase from the ordered counterpart.

Further investigation at higher pressures can provide direct evidence for the pressure-dependent variation of the local structure as a result of the probability of dominant configuration. Moreover, the turning pressure overlaps with where the cross-over of dynamics occurs [START_REF] Yamane | Direct evidence of the proton-dynamics crossover in ice VII from high-pressure dielectric measurements beyond 10 GPa[END_REF]. Fundamental and detailed diffraction techniques can provide direct and pivotal information on the anomalous physical properties of ice VII under pressure.

Our findings would also provide an approach to elucidate the behaviors of water molecules during the phase transition to hydrogen-bond symmetrized ice X. Although spectroscopic studies showed in the 1990s that ice VII transforms into ice X over 60 GPa in H 2 O and 70 GPa in D 2 O(29-31), the symmetric structure of ice X has not been confirmed experimentally yet by neutron diffraction. A powder neutron diffraction study of D 2 O up to 60 GPa reported the elongation of covalently-bonded O-D separation [START_REF] Guthrie | Structure and disorder in ice VII on the approach to hydrogen-bond symmetrization[END_REF]. The separation of the deuterium site between the hydrogen-bonded water molecules also decreases, and its linear extrapolation proposed an upper limit of the symmetrization to be at 113 GPa. Below 60 GPa, water is considered to retain its molecular nature from spectroscopic studies [START_REF] Aoki | Infrared absorption study of the hydrogen-bond symmetrization in ice to 110 GPa[END_REF][START_REF] Goncharov | Compression of ice to 210 gigapascals: Infrared evidence for a symmetric hydrogen-bonded phase[END_REF][START_REF] Pruzan | Raman Scattering and X-ray Diffraction of Ice in the Megabar Range. Occurrence of a Symmetric Disordered Solid above 62 GPa[END_REF] but the physical properties of the BCC ice differ from ice VII [START_REF] Polian | New high-pressure phase of H2O: Ice X[END_REF][START_REF] Sugimura | Compression of H2O ice to 126 GPa and implications for hydrogenbond symmetrization: Synchrotron x-ray diffraction measurements and density-functional calculations[END_REF][START_REF] Méndez | Bulk modulus of H2 O across the ice VII-ice X transition measured by time-resolved x-ray diffraction in dynamic diamond anvil cell experiments[END_REF], called ice VII'. In this pressure regime, the bimodal potential curve of deuterium becomes unimodal and quantum tunnelling takes place dominant. The atomic distribution and the correlation function can provide direct images to observe the transient states toward the hydrogen bond symmetrization.

Materials and Methods

Single-crystal neutron diffraction

The single-crystal diffraction experiment was conducted at the D9 hot neutron single-crystal diffractometer at the Institut Laue-Langevin (ILL, Grenoble, France). The data of ice VII was collected at 298 K and 2.2 GPa using a diamond anvil cell specially designed for this study [START_REF] Yamashita | A nano-polycrystalline diamond anvil cell with bulk metallic glass cylinder for single-crystal neutron diffraction[END_REF].

Single-crystalline specimens of deuterated ice VII were grown directly from a water-alcohol mixture (D 2 O:MeOD:EtOD = 5:4:1 in volume ratio) by cyclic heating and cooling over 2 GPa. The pressure was estimated by the ruby fluorescence method [START_REF] Mao | Calibration of the ruby pressure gauge to 800 kbar under quasihydrostatic conditions[END_REF].

Powder neutron diffraction

The powder diffraction experiments were conducted at the BL11 (PLANET) beamline( 16) of the Material and Life Science Experimental Facility (MLF) at J-PARC (Ibaraki, Japan) using the MITO pressure-temperature variable system [START_REF] Komatsu | Development of a new P-T controlling system for neutron-scattering experiments[END_REF]. Powder samples of deuterated ice VII were obtained by compression of ice at 200 K, below the melting curve of ice phases. The repetitive solid-solid phase transition contributes to preparing fine powder samples suitable for structure analyses. The diffraction patterns of ice VII were collected at 2.2 GPa and temperatures of 298 K and 274 K. A powder diffraction pattern of ice VIII was also collected at 274 K and 2.2 GPa for comparison. The sample pressures were estimated from the equation of state of ice VII and VIII themselves [START_REF] Klotz | Bulk moduli and equations of state of ice VII and ice VIII[END_REF].

The phase transition between ices VII ad VIII is a 1 st -order transition that shows hysteresis so that both phases can metastably exist at approximately 274 K during cooling for ice VII or heating for ice VIII before the phase transition occurs.

MEM analysis

The MEM analysis tends to give the most uniform distribution under conditions that satisfy the constraints. The information entropy S and the constraints C are defined as follows.

(1) [START_REF] Komatsu | Anomalous hydrogen dynamics of the ice VII-VIII transition revealed by high-pressure neutron diffraction[END_REF] where ρ(r) is the normalized density of scattering length at r in a unit cell and τ(r) is the normalized density derived from prior information for r, N k is the number of structure factors, k is the reciprocal lattice vector to identify each Bragg reflection, F c is the structure factors calculated from ρ(r). The most probable density distribution which maximizes S can be derived by a method of undetermined Lagrange multipliers (λ and μ).

(3)

The third term in Eq. 3 is a constraint for the total normalized scattering length to be one. The MEM analyses for both single-crystal and powder diffraction were done using the Dysnomia program [START_REF] Momma | Dysnomia, a computer program for maximumentropy method (MEM) analysis and its performance in the MEM-based pattern fitting[END_REF] and the practical and detailed schemes are in its manual. The crystal structures and density distribution map was drawn with the VESTA program [START_REF] Momma | VESTA 3 for three-dimensional visualization of crystal, volumetric and morphology data[END_REF].

Total scattering analysis

Structure factors, S(Q), were derived after intensity corrections for background, absorption, etc.

SFigure 1 .

 1 Figures and Tables

Figure 2 .

 2 Figure 2. Distribution of scattering-length density in ice VII derived from (a) single-crystal data and (b) powder diffraction data both at 298 K and 2.2 GPa. (c) and (d) are cross sections of (a) and (b) on (110) plane, respectively. The oxygens and deuteriums are illustrated as those in the single-site model with O-D = 0.97 Å, as in the water molecule, and ∠DOD = 109.47° for comparison. Density decreases from red to blue color.

Table 1 .

 1 Summary of interatomic distances derived from Gaussian peak fitting of correlation function T(r) and Rietveld refinement with reported values. Errors estimated from the SD of peak fitting for T(r) are given in parenthesis.° Errors estimated from the refinement procedures are given in parentheses. Riet, Rietveld.

			VIIT(r)	VIIIT(r)	VIIRiet	VIIIRiet	VIII	VIII
		unit			This study		ref. 10)	ref. 11)
	r(O-D)	(Å)	0.9662 (5) *	0.9658 (5) *	0.9163 (5)	0.9681 (8)	0.968 (7)	0.973(11)°
	r(D…D)	(Å)	1.510 (5) *	1.521 (6) *	1.4963 (10)	1.5498 (14)	1.543 (14)	1.532(12)°
	r(O…D)	(Å)	1.86 (13) *	1.89 (26) *	1.9820 (5)	1.9304 (8)	1.911 (9)	1.920(10)°
	∠DOD	(°)	102.8 (4) *	103.9 (6) *	109.47	106.34 (11)	105.6 (11)	103.8(15)°
	p	(GPa)	2.2	2.2	2.2	2.2	2.4	2.8
	T	(K)	274	274	274	274	10	269

*

Acknowledgments

This study was supported by JSPS KAKENHI (grant numbers: 18H05224, 18H01936, 21K18154), the JSPS-CNRS bilateral joint research grant PRC2191, and the GIMRT program of the Institute for Materials Research, Tohoku University (Proposal No. 20K0085).

Neutron diffraction experiments were performed through the J-PARC user programs (No. 2020B0139) and the ILL user programs (No. 5-15-624). The experiment at the J-PARC was performed using the Lab. III at the Comprehensive Research Organization for Science and Society (CROSS) user laboratory. We acknowledge an important contribution of J. S. Loveday which explains and clarifies our findings on the total scattering analysis.


Lyuben Lichev

Bruno Schapira
email: bruno.schapira@univ-amu.fr

Color-avoiding percolation on the Erdős-Rényi random graph

Keywords: color-avoiding percolation, Erdős-Rényi random graph. MSC Class: 05C80, 60C05, 60K35, 82B43

We consider a recently introduced model of color-avoiding percolation defined as follows. Every edge in a graph G is colored in some of k ≥ 2 colors. Two vertices u and v in G are said to be CA-connected if u and v may be connected using any subset of k -1 colors. CA-connectivity defines an equivalence relation on the vertex set of G whose classes are called CA-components.

We study the component structure of a randomly colored Erdős-Rényi random graph of constant average degree. We distinguish three regimes for the size of the largest component: a supercritical regime, a so-called intermediate regime, and a subcritical regime, in which the largest CA-component has respectively linear, logarithmic, and bounded size. Interestingly, in the subcritical regime, the bound is deterministic and given by the number of colors.

Introduction

In this paper, we are interested in the model of (edge-)color-avoiding percolation defined as follows. Fix a set of k ≥ 2 colors and a graph G, and color every edge of G in at least one color. We say that two vertices u and v in G are color-avoiding connected, or CA-connected for short, if u and v may be connected using any subset of k -1 colors. In fact, CA-connectivity defines an equivalence relation on the vertex set of G whose classes are called CA-components. The model has been motivated by a number of real-world applications, for example, avoiding a set of mistrusted information channels (where colors correspond to eavesdroppers), or avoiding a set of possibly corrupted links in a network. In a sense, a network with large CA-components may be considered resistant to attacks from a set of adversaries where the adversaries control all channels but can only attack the network separately.

Color-avoiding percolation was introduced by Krause, Danziger, and Zlatić [START_REF] Krause | Hidden connectivity in networks with vulnerable classes of nodes[END_REF][START_REF] Krause | Color-avoiding percolation[END_REF]. In their work, the authors were interested in vertex-colored graphs and analyzed a vertex analog of CA-connectivity. While some empirical observations were made for scale-free networks, the focus was put on Erdős-Rényi random graphs due to their better CA-connectivity [START_REF] Krause | Hidden connectivity in networks with vulnerable classes of nodes[END_REF]. In a subsequent work, Kadović, Krause, Caldarelli, and Zlatić [START_REF] Kadović | Bond and site color-avoiding percolation in scale-free networks[END_REF] defined mixed CA-percolation where both vertices and edges have colors. To a large extent, each of these foundational papers based their conclusions on experimental evidence. Figure 1: Blue, red and green edges are represented by dotted, dashed, and solid segments, respectively. One may easily check that on the left, every vertex is alone in its CA-component, while on the right, the addition of a single blue edge leads to the appearance of many CA-components of size 2.

Precise mathematical treatment of the subject is challenging for several reasons. Firstly, unlike connected components in a graph, the CA-components cannot be found by a local exploration of the graph in general. Indeed, note that even if two vertices are neighbors in the graph, all paths that connect them and avoid a certain color may be rather long. Secondly, while one edge in a graph may merge at most two components or divide a single connected component into two parts, a single colored edge may lead to a merging of a lot of different CA-components. For example, consider two parallel paths of length 2 + 1, and for every i ∈ [2 + 1], connect the i-th vertex in one of the paths with the i-th vertex in the other path. Also, color the odd edges in the paths in blue, the even edges in red, and the edges between them in green, see Figure 1. Then, it may be easily checked that all CA-components in the obtained graph are of size 1 while adding a blue edge between the last vertices in the two paths creates 2 + 1 components of size 2 at once. Last but not least, in the framework of random graphs, deleting the edges in two different colors from the original graph leads to two distinct subgraphs that can have a large intersection, and can therefore be highly correlated.

To our knowledge, a rigorous mathematical treatment of the behavior of color-avoiding percolation on random graphs has only been studied in a recent work of Ráth, Varga, Fekete, and Molontay [START_REF] Ráth | Color-avoiding percolation in edge-colored Erdős-Rényi graphs[END_REF]. In their paper, they show that under a certain subcriticality assumption, the number of CA-components of a given fixed size renormalized by n converges in probability to a fixed constant. Moreover, under the same assumption, it is proved that the size of the largest CA-component renormalized by n converges in probability to a fixed constant. They also characterize the behavior of that constant in the barely supercritical regime.

Our goal here is to go further in the analysis of the structure of CA-components in a randomly colored Erdős-Rényi random graph around the threshold of appearance of a giant component. Apart from simplifying the approach of [START_REF] Ráth | Color-avoiding percolation in edge-colored Erdős-Rényi graphs[END_REF] and getting rid of their additional hypothesis, we show that the parameter space may be naturally divided into three regimes. In each of them, we conduct a careful analysis of the size of the largest CA-component as well as the number of small CA-components.

Main results

For a positive integer m, we denote [m] = {1, . . . , m}. In particular, we reserve the notation [k] to denote the set of colors, and the notation [n] for the set of vertices of our graphs. Recall that for p ∈ [0, 1], the Erdős-Rényi random graph G(n, p), or ER random graph for short, with parameters n and p is the graph on the vertex set [n] where the edge between any two distinct vertices is present with probability p, independently from all other edges.

Consider now a non-increasing sequence of positive real numbers λ 1 ≥ • • • ≥ λ k , and define a family of k independent Erdős-Rényi random graphs

G i = G(n, λ i n ) for i ∈ [k] on the same vertex set [n]
(alternatively, this family can be seen as a multigraph ([n], E 1 , . . . , E k ) where E i is the edge set of G i ). In order to easily refer to and distinguish the graphs (G i ) k i=1 , we say that for every i ∈ [k], the edges of G i are given color i. Define further

Λ = λ 1 + • • • + λ k , and λ * i = Λ -λ i for every i ∈ [k]. In particular, λ * 1 ≤ λ * 2 ≤ • • • ≤ λ * k . Also, we set G = G 1 ∪ . . . ∪ G k ,
and for I ⊆ [k],

G I = i∈I G i , and G I = i∈[k]\I G i ,
with the shorthand notation G i and G i , respectively, when I = {i}.

Recall that two vertices u and v in G are CA-connected if u and v are connected in each of the graphs (G i ) k i=1 . Moreover, CA-connectivity is an equivalence relation with classes called CA-components. The CA-component of a vertex u ∈ [n] is denoted by C(u), and | C(u)| denotes its size. Our main object of interest is the size of the largest CA-component in G. Under the assumption that i∈I λ i < 1 for every set I ⊆ [k] of size k -2, it was shown in [START_REF] Ráth | Color-avoiding percolation in edge-colored Erdős-Rényi graphs[END_REF] that there exists a constant a ∈ [0, 1] such that

max u∈[n] | C(u)| n P ---→ n→∞ a, (1)
and that the constant a is positive if and only if λ * 1 > 1, which is called the supercritical regime. Here, we improve this result in three directions:

• We observe that (1) can be easily derived from the convergence in distribution of the neighborhood of a typical vertex, and this does not require any additional technical assumptions.

• In the subcritical regime (that is, when λ * k < 1), we prove that asymptotically almost surely (a.a.s.), any CA-component has size at most k. Moreover, the random variables (N ) k =2 which count the number of CA-components of size 2, . . . , k, respectively, jointly converge in distribution to independent Poisson random variables.

• We start investigating the more difficult intermediate regime (that is, when

λ * k > 1 > λ * 1 )
. In this setting, we show a weak law of large numbers under the assumption that λ

* k > 1 > λ * k-1 .
These results are summarized in the following theorem.

Theorem 1.1. Suppose that k ≥ 2.

(i) There exists a 1 ∈ [0, 1), such that

max u∈[n] | C(u)| n P ---→ n→∞ a 1 .
Moreover, one has a 1 > 0 if and only if λ * 1 > 1.

(ii) If λ * k > 1 > λ * k-1 , then there is a positive constant a 2 such that max u∈[n] | C(u)| log n P ---→ n→∞ a 2 . (iii) If λ * k < 1, then a.a.s. max u∈[n] | C(u)| ≤ k.
Moreover, there are positive constants β 2 , . . . , β k , such that

(N 2 , . . . , N k ) d ---→ n→∞ k =2 Po(β ),
that is, the random variables (N ) k =2 jointly converge in distribution to k -1 independent Poisson variables with means β 2 , . . . , β k as n → ∞.

Note that in the above result, we recover an analog of the famous transition from a linear to a logarithmic size for the largest connected component, which appears in an ER random graph G(n, λ n ) as the parameter λ crosses the critical value 1. However, unlike this standard setting, one original feature of CA-percolation is that there is an additional regime where the size of the largest CA-component remains bounded. Furthermore, the critical cases λ * 1 = 1 and λ * k = 1 appear to be more subtle, see Proposition 1.3 below and Section 4 for more on this. Now, we take a closer look at each of the three parts of Theorem 1.1. Part (i) should not be very surprising as, on the one hand, if λ * 1 ≤ 1, then a.a.s. the largest connected component in G 1 has sublinear size, and thus the largest CA-component as well. On the other hand, if λ * 1 > 1, then a.a.s. the largest CAcomponent is obtained by intersecting the largest connected components in each of the graphs G 1 , . . . , G k , which all have linear size. However, we stress that the whole point of the proof is to handle the lack of independence between these components. To do this, we use a local limit argument for a sequence of randomly colored ER random graphs, which also allows us to recover and improve in a simple way a result of [START_REF] Ráth | Color-avoiding percolation in edge-colored Erdős-Rényi graphs[END_REF] on the number of CA-components of given size. Proposition 1.2. There exists a sequence of non-negative real numbers (ν ) ≥1 such that

≥1 ν = 1-a 1 , and for each ≥ 1, |{u ∈ [n] : | C(u)| = }| n = • N n P ---→ n→∞ ν . (2)
Moreover, one has ν > 0 for all ≥ 1 if and only if

λ * k > 1, while if λ * k ≤ 1, then ν 1 = 1.
Altogether, this proposition and Part (i) of Theorem 1.1 answer a question from [START_REF] Ráth | Color-avoiding percolation in edge-colored Erdős-Rényi graphs[END_REF] by showing that one can get rid of their technical assumption.

For Part (ii) of Theorem 1.1, the main observation is that the largest CA-component comes from intersecting a connected component in G k with the largest component of G k . In fact this argument also gives us that the size of the largest CA-component in the critical case

λ * k = 1 > λ * k-1 is tight. Proposition 1.3. Suppose that λ * k = 1 > λ * k-1 . Then, sup n≥1 P max u∈[n] | C(u)| ≥ M ----→ M →∞ 0.
The question of whether in this critical case the size of the largest CA-component converges in distribution remains open. In fact, even knowing if the support is asymptotically bounded by a deterministic constant is unknown.

In the remaining intermediate regime, i.e. when λ * k-1 ≥ 1 > λ * 1 , one can easily show that the size of the largest CA-component is still of logarithmic order. However, proving concentration seems to be a challenging problem, which remains out of reach with our present techniques.

Part (iii), as we already mentioned, is arguably the most original part. In this case, the largest connected component in each of the graphs G 1 , . . . , G k has only logarithmic size, which makes it very difficult for a pair of vertices to be connected in all k graphs. This explains, at least heuristically, why the largest CA-component has bounded size, although the fact that the bound is deterministic may appear as unexpected. Actually, as we shall see, the main reason for which the upper bound is given by the number of colors is that a.a.s. every CA-component is either contained in a single edge, or all paths connecting two of its vertices and avoiding some color are contained in a single cycle.

Finally, we provide an explicit expression of β k in terms of λ 1 , . . . , λ k in Remark 3.7. While it is possible to do the same for the other values of β m for m < k, the formula and the computation tend to get more and more tedious as m decreases.

We now comment on the proofs themselves in more detail.

Outline of the proofs. As already mentioned, the proofs of Part (i) of Theorem 1.1 and Proposition 1.2 are based on the well-known local convergence of Erdős-Renyi random graphs to Bienaymé-Galton-Watson trees, or BGW trees for short, with Poisson offspring distribution. In our setting of edge-colored ER random graph, the local limit can be seen as a BGW tree with Po(Λ) offspring distribution where additionally each edge is colored with color i ∈ [k] with probability λ i /Λ, independently for different edges. Then, the constant a 1 is just the probability that for every i ∈ [k], the connected component of the root is infinite when we erase the edges colored with color i. The same approach allows to prove Proposition 1.2, with (ν ) ≥1 being the probability distribution of the size of the CA-component of the root in the aforementioned BGW tree. However, here the notion of CA-component must be suitably adjusted, as already noticed in [START_REF] Ráth | Color-avoiding percolation in edge-colored Erdős-Rényi graphs[END_REF]: for each i ∈ [k], two vertices are declared to be connected when erasing color i if either they are indeed connected by a path in the BGW tree that avoids color i, or if they both connect to infinity by paths avoiding color i. It is then not difficult to see that, for this notion of CA-connectivity, the constant a 1 is also the probability that the CA-component of the root is infinite.

On the other hand, the proofs of (ii), Proposition 1.3 and (iii) have a different flavor. Firstly, we outline the proof strategy for (ii). To begin with, we make use of the following fact, which might be of independent interest. Consider a subcritical Erdős-Renyi random graph G(n, λ n ), and independently color each of its vertices in black with some probability q ∈ (0, 1]. Then, we show that the maximal number of black vertices which are all connected in G(n, λ n ) divided by log n converges in probability towards a positive constant. This result extends the concentration for the size of the largest component in a subcritical ER random graph, which corresponds to q = 1. The proof is obtained by solving an energy-entropy optimization problem, where the energy corresponds to the cost of having a large number of black vertices in a given connected component of G(n, λ n ), while the entropy factor comes from the fact that as b decreases, the number of connected components of size b log n in G(n, λ n ) increases. The link with (ii) arises as one realizes (the nontrivial fact) that when λ * k-1 < 1, the largest CA-component necessarily comes from intersecting a component in G k (which is subcritical) with the largest component of G k (which is supercritical), the two being independent, and the fact that the vertex set of the giant component in the latter can be approximated by a binomial random subset of vertices. A similar argument also leads to a proof of Proposition 1.3. We refer to Sections 2.3, 2.4, and 3.2 for more details.

Concerning (iii), the crux of the proof is to show that when λ * k < 1, a.a.s. every CA-component of size at least two is contained either in a cycle of G or in a single edge (the latter happening only if the CA-component has exactly two vertices which are linked by an edge in at least two different colors), see Lemma 3.4. The proof of this result relies on a combination of some counting arguments (e.g. showing that a.a.s. connected subgraphs of G(n, λ/n) of size at most some constant times log n contain at most one cycle, see Lemma 2.5), and a more probabilistic lemma showing that a.a.s. all CA-components have bounded size (see in particular Lemma 3.2). Once this is established, (iii) follows from standard results on the asymptotic numbers of short cycles in an Erdős-Renyi random graph.

Remark 1.4. Note that the notion of CA-component of a vertex u is usually defined as the set of vertices connected to u when deleting edges of color i for any i ∈ [k] (that is, unlike in our setting, edges in color i cannot be used even if they have more than one color). While all our results would also hold with this definition, ours is slightly more convenient to deal with, especially in the intermediate regime, since this way G i and G i are independent.

Further notation and terminology. In general, we omit the dependence on n, Λ and (λ i ) i∈[k] for convenience of notation.

For I ⊆ [k] and a vertex u ∈ [n], we denote by C I (u) and C I (u) the connected components of u in G I and G I , respectively. An edge is said to be repeated if it participates in at least two of G 1 , . . . , G k .

In this paper, we often identify graphs with their vertex sets. For instance, given a graph H, we call size of H its number of vertices, which we denote by |H|. For a set S of vertices of H, we denote by H[S] the subgraph of H induced by S (that is, the graph with vertex set S and edge set given by the edges of H with both vertices in S). Moreover, for two vertices u, v in H, we denote by {u H ← → v} the event that u and v are connected in H.

A sequence of events (E n ) n≥1 is said to hold a.a.s. if

P(E n ) → 1 as n → ∞. Given two positive real sequences (f n ) n≥1 and (g n ) n≥1 , we write f n = o(g n ) if f n /g n → 0 when n → ∞, and f n = O(g n ) if there exists a constant C > 0 such that f n ≤ Cg n for all n ≥ 1.
Furthermore, we write d -→ to denote convergence in distribution of a sequence of random variables, and P -→ for convergence in probability. Finally, we denote by Po(λ) the Poisson distribution with parameter λ, and by Bin(n, q) the Binomial distribution with parameters n and q. For a family of distributions (µ i ) i∈I , we denote by i∈I µ i the distribution of a vector (X i ) i∈I of independent random variables where X i ∼ µ i for every i ∈ I.

Plan of the paper. The rest of the paper is organized as follows. In the next section, we recall some known facts about ER random graphs, both in the subcritical and supercritical regimes, and show the result on the size of the largest black connected set in a (vertex-)colored subcritical ER random graph which was mentioned above. Then, in Section 3 we give the proof of our main results, Theorem 1.1 and Propositions 1.2 and 1.3, and finally discuss some open questions in Section 4.

Preliminaries on Erdős-Rényi random graphs

In this section, we gather some results on the random graph G(n, λ n ). Apart from the results in Section 2.4, most of the material presented here is well-known, and we sometimes include short proofs only for the reader's convenience.

We let C(u) denote the connected component of a vertex u ∈ [n]. Also, for λ > 0, set

I λ = λ -1 -log λ. (3)
It is easy to check that this is a positive real number for all λ > 0 different from 1. Also, for every integer s ≥ 0, we define

Z s = u∈[n]
1 {|C(u)| ≥ s} .

Subcritical regime: cluster size and two-point connectivity

Fix λ ∈ (0, 1). Then, it is well-known that

max u∈[n] |C(u)| log n P ---→ n→∞ 1 I λ , (4)
see e.g. Theorems 4.4 and 4.5 in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF]. It will also be useful to have a bound on the upper tail of the typical cluster size. The following one will be sufficient for our purposes.

Lemma 2.1 (see display (4.3.11) in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF]). Fix λ ∈ (0, 1). Then, for every t ≥ 1,

P(|C(u)| ≥ t) ≤ e -I λ • t .
A reverse inequality holds as well when t does not grow too fast with n. In particular, we shall need the following result (see e.g. displays (4.3.34) and (4.3.37) in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF]). Lemma 2.2. Fix λ ∈ (0, 1) and a ∈ (0, 1/I λ ]. Then,

P(|C(u)| ≥ a log n) ≥ n -(1+o(1))I λ • a .
Moreover, Lemma 2.1 has the following important consequence.

Corollary 2.3. Fix λ ∈ (0, 1). Then, for every pair of distinct vertices u, v in G(n, λ n ),

P(v ∈ C(u)) ≤ 1 n • e -I λ 1 -e -I λ .
Proof. It suffices to observe that for every t ≥ 1, conditionally on the event {|C(u)| = t}, the set of vertices different from u and contained in C(u) is uniformly distributed among all possible subsets of [n] \ {u} of size t -1. In particular, for every v = u,

P(v ∈ C(u) | |C(u)| = t) = t -1 n -1 ≤ t n . (5)
By summing over all positive integers t ∈ [n] and using Lemma 2.1, we get

P(v ∈ C(u)) ≤ n t=1 t n • P(|C(u)| = t) = 1 n n t=1 P(|C(u)| ≥ t) ≤ 1 n • e -I λ 1 -e -I λ ,
as desired.

The next result provides concentration of the variables Z s when s is of order log n. The equality for the expectation is a direct consequence of Lemmas 2.1 and 2.2, while the two inequalities for the variance follow from Proposition 4.7 in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF] and Lemma 2.1, respectively.

Lemma 2.4. Let λ ∈ (0, 1) and a ∈ (0, 1/I λ ]. Then, E[Z a log n ] = n 1-(1+o(1))I λ • a and Var[Z a log n ] ≤ n • E |C(1)|1 {|C(1)| ≥ a log n} ≤ n 1-(1+o(1))I λ • a .

On the number of cycles

We start with a result showing that a.a.s. all connected subgraphs of G(n, λ n ) of size at most some constant (depending on λ) times log n contain at most one cycle, and when λ < 1, all those with size at least ε log n are trees for any fixed ε > 0.

Lemma 2.5. Fix λ > 0.

1. There is a positive constant c 1 = c 1 (λ) such that a.a.s. the following holds: for every set S ⊆ [n] with |S| ≤ c 1 log n, whenever the subgraph of G(n, λ n ) induced by S is connected, it contains at most one cycle.

2. If λ < 1, then for every ε > 0, a.a.s. all components of size larger than ε log n are trees.

Remark 2.6. In fact, concerning the second statement of this lemma, more is true: as shown in the proof below, the expected number of vertices whose connected component contains at least one cycle is bounded uniformly in n.

Proof of Lemma 2.5. Concerning the first part of the lemma, note that any connected graph with at least two cycles contains as a subgraph a spanning tree together with two additional edges. Furthermore, by Cayley's formula the number of spanning trees of the complete graph with size m is equal to m m-2 . Therefore, for every c > 0, by using that n m ≤ ne m m , we deduce that the expected number of subgraphs of G(n, λ n ) which are connected, contain at least two cycles and at most c log n vertices, is bounded from above by,

c log n m=1 m m-2 • m 2 2 • n m • λ n m+1 ≤ 1 n c log n m=1 m 2 (eλ) m+1 , which is o(1) if one chooses c < 1 1+max(0,log λ)
. The proof of the first part is completed by an application of Markov's inequality.

For the second part, we compute the expected number of vertices in components of size at most 2I -1 λ log n containing a cycle. Taking also into account the fact that no vertex in a component of size m is connected to any of the n -m vertices outside the component, the previous computation implies that the above expectation is at most

2I -1 λ log n m=1 m • m m-2 • m 2 • n m • λ n m 1 - λ n m(n-m) ≤ (1 + o(1)) 2I -1 λ log n m=1 m • e -I λ m = O(1).
Thus, by Markov's inequality there are a.a.s. less than ε log n vertices in components of size at most 2I -1 λ log n containing a cycle. However, by Lemma 2.1 a.a.s. all components have size at most 2I -1 λ log n, which completes the proof.

Remark 2.7. The following modification of Lemma 2.5 holds with almost the same proof.

1. There exists c 1 = c 1 (Λ) such that a.a.s. for every set S ⊆ [n] with |S| ≤ c 1 log n, whenever the subgraph of G induced by S is connected, it either contains at most one cycle and no repeated edges or at most one repeated edge and no cycles.

2. If λ * i < 1 for some i, then for every ε > 0, a.a.s. all connected components of G i of size at least ε log n are trees with no repeated edges.

The next lemma is a well-known result concerning the number of cycles of given size that will be needed for the proof of Theorem 1.1 (iii). We refer e.g. to Corollary 4.9 from [START_REF] Bollobás | Random Graphs[END_REF] for a proof. Po(γ m ),

where for all m ∈ {3, . . . , }, γ m = λ m 2m . Lemma 2.8 has the following direct consequence. Recall that an edge is said to be repeated in G if it is part of at least two of the graphs G 1 , . . . , G k . Corollary 2.9. Denote by C 2 the number of repeated edges in G. Then, with the same notation as in Lemma 2.8, for every ≥ 2,

(C 2 , . . . , C ) d ---→ n→∞ m=2
Po(γ m ),

where γ 2 = 1 2 i,j∈[k]
,i<j λ i λ j and for all m ∈ {3, . . . , }, γ m = Λ m 2m . Proof. Using that G is distributed as an Erdős-Rényi random graph with parameters n and

p = 1 - k i=1 1 - λ i n = (1 + o(1)) • Λ n ,
the joint convergence of (C 3 , . . . , C ) is given by Lemma 2.8. On the other hand, by definition

C 2 ∼ Bin( n(n-1) 2 , 2(1+o(1))γ 2 n 2
), and thus C 2 converges in distribution to Po(γ 2 ). It only remains to justify the asymptotic independence between C 2 and the other variables. The argument is the same as the one showing asymptotic independence of C 3 , . . . , C , see Theorem 4.8 and Corollary 4.9 in [START_REF] Bollobás | Random Graphs[END_REF]. Briefly, one can first notice by a simple first moment argument that a.a.s. no vertex participates simultaneously in a repeated edge and in a cycle of length at most . Thus, the variables (C 3 , . . . , C ) a.a.s. coincide with the cycle counts in the graph, obtained by deleting all vertices in repeated edges, which conditionally on C 2 is an ER random graph with at least n -2C 2 vertices. Using that E[C 2 ] = O(1), and more precisely that a.a.s. n -2C 2 = n -o(n), implies the corollary.

Supercritical regime: stochastic domination of the giant component

Recall that when λ > 1, the graph G(n, λ n ) has a.a.s. a unique connected component of linear size (called the giant component). More precisely, it is well-known that

max u∈[n] |C(u)| n P ---→ n→∞ µ λ (6)
where µ λ is the survival probability of a Bienaymé-Galton-Watson tree with offspring distribution Po(λ) characterized as the unique positive solution of the equation 1 = e -λt + t, see display (3.6.2) and Theorem 4.8 in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF]. Recall also that conditionally on its size, the set of vertices in the giant component is uniformly distributed among the family of subsets of [n] of that size. As a consequence, one has the following stochastic comparison with binomial random subsets of vertices.

Lemma 2.10. Fix λ > 1 and ε > 0. Let C max be the a.a.s. unique largest connected component of G(n, λ n ). Let also (X v ) v∈[n] and (Y v ) v∈[n] be two sequences of i.i.d. Bernoulli random variables with respective parameters max(µ λ -ε, 0) and min(µ λ + ε, 1). Then, there is a coupling of these two sequences with G(n, λ n ) such that a.a.s. one has {v :

X v = 1} ⊆ C max ⊆ {v : Y v = 1}. (7)
Proof. Note that conditionally on their respective sizes, the three sets appearing in [START_REF] Last | Lectures on the Poisson process[END_REF] are sampled uniformly at random among all subsets of [n] of that size. The lemma then follows by the weak law of large numbers and [START_REF] Krause | Color-avoiding percolation[END_REF], which together imply that a.a.s.

v∈[n] X v ≤ |C max | ≤ v∈[n] Y v .

On the intersection of a giant with independent subcritical clusters

Fix q ∈ (0, 1) and λ ∈ (0, 1). For every x ∈ [q, 1), define

J q (x) = x log x q + (1 -x) log 1 -x 1 -q
, and set ρ(q, λ) = inf x∈[q,1)

I λ + J q (x)
x .

Consider a sequence (X v ) v∈[n] of independent Bernoulli random variables with parameter q, and independently a graph G(n, λ n ). For u ∈ [n] and t ≥ 0, define

Z t = u∈[n] 1 { v∈C(u) Xv ≥ t} .
The next lemma is similar in essence to Lemma 2.4.

Lemma 2.11. Fix a ∈ (0, 1 ρ(q,λ) ]. Then,

E[ Z a log n ] = n 1-(1+o(1))ρ(q,λ) • a and Var[ Z a log n ] ≤ n 1-(1+o(1))ρ(q,λ) • a .
Proof. We begin by proving the estimate on the mean. To start with, we recall two large deviation estimates for Binomial random variables. On the one hand, for every x ∈ [q, 1) and every N ≥ 1 (see e.g. Corollary 2.20 in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF]),

P(Bin(N, q) ≥ xN ) ≤ exp -N • J q (x) , (8)
and on the other hand, for every fixed x ∈ [q, 1) (see e.g. Theorem 2.2.3 and Exercice 2.2.23 in [START_REF] Dembo | Large deviations techniques and applications[END_REF]),

P(Bin(N, q) ≥ xN ) ≥ exp -(1 + o N (1)) • N • J q (x) , (9)
where the o N (1) term goes to 0 as N → ∞. Since conditionally on its size the cluster C( 1) is uniformly distributed among the subsets of [n] of that size containing the vertex 1, we deduce using (8) and Lemma 2.1 that

P v∈C(1) X v ≥ a log n ≤ (a/q) log n s=a log n P(|C(1)| = s) • P(Bin(s, q) ≥ a log n) + P(|C(1)| ≥ (a/q) • log n) ≤ (a/q) log n s=a log n exp -I λ + J q a log n s • s + n -I λ • a/q ≤ O(log n) • n -inf b∈(a,a/q] b(I λ +Jq(a/b)) , (10)
and observing that inf b∈(a,a/q] b(

I λ + J q (a/b)) = a • ρ(q, λ), (11)
concludes the proof of the upper bound. Now, we concentrate on the lower bound. To start with, we extend J q to a continuous function on the interval [q, 1] by defining J q (1) = log(1/q), and let b * be the smallest real number realizing the infimum of the function b → b(I λ + J q (a/b)) over the interval [a, a/q]. Recall that log is a concave function, so by Jensen's inequality the function J q is non-negative. Then, together with the fact that a ≤ 1/ρ(q, λ) by hypothesis, (11) shows that b * = a • ρ(q, λ)

I λ + J q (a/b * ) ≤ a • ρ(q, λ) I λ ≤ 1 I λ .
Thus, by using Lemma 2.2 and (9), we get

P v∈C(1) X v ≥ a log n ≥ P(|C(1)| ≥ b * log n) • P(Bin(b * log n, q) ≥ a log n) ≥ n -(1+o(1))b * •I λ • n -(1+o(1))b * •Jq(a/b * ) = n -(1+o(1))a • ρ(q,λ) ,
which concludes the proof of the lower bound. Finally, the proof of the upper bound on the variance is mutatis mutandis the same as the proof of Lemma 2.4, in particular, the same argument leads to

Var[ Z a log n ] ≤ n • E     v∈C(1) X v   • 1 { v∈C(1) Xv ≥ a log n}   ,
which combined with (10) yields the desired upper bound. Remark 2.12. A close look at the previous proof shows that the upper bound on the mean is in fact valid for all a > 0.

Corollary 2.13. Let a = a(q, λ) = 1 ρ(q,λ) > 0. Then,

max u∈[n] v∈C(u) X v log n P ---→ n→∞ a.
Proof. If h > a(q, λ), then by Markov's inequality and Lemma 2.11 (see also Remark 2.12) we get

P   max u∈[n] v∈C(u) X v ≥ h log n   = P( Z h log n ≥ 1) ≤ E[ Z h log n ] = o(1).
Conversely, if h < a(q, λ), then again Lemma 2.11 together with the Cauchy-Schwarz inequality gives

P   max u∈[n] v∈C(u) X v ≥ h log n   = P( Z h log n ≥ 1) ≥ E[ Z h log n ] 2 E[ Z h log n ] 2 + Var[ Z h log n ] = 1 -o(1).

Proofs of the main results

This section is devoted to the proofs of Theorem 1.1 and Proposition 1.2. We first prove Part (i) of the theorem together with the proposition in Section 3.1, then Part (ii) of the theorem in Section 3.2, and finally Part (iii) in Section 3.3.

Proofs of Theorem 1.1 (i) and Proposition 1.2

The proofs of these two results are based on the well-known local convergence of ER random graphs to BGW trees with Poisson offspring distribution. Recall that in the standard setting of uncolored graphs, the local weak convergence states the following: denoting by V L (u) the L-neighborhood of a vertex u in G or in the BGW tree with Po(Λ) offspring distribution, for every bounded function (u, H) → ϕ(u, H) defined on pairs (u, H) where H is a finite graph and u a vertex of H, one has

1 n u∈[n] E[ϕ(u, V L (u))] ---→ n→∞ E[ϕ(∅, V L (∅))].
It is straightforward to see that the same convergence holds in our setting of colored graphs. The difference is that now, edges are endowed with a label encoding its set of colors. As a consequence, the limiting graph is a BGW tree with Po(Λ) offspring distribution, denoted hereafter by GW(Λ), where each edge is colored in a single color and independently of other edges, and where color i is attributed with probability λ i /Λ (see the proof of Proposition 3.1 below). Moreover, using that finite neighborhoods of two given points are mostly independent (in particular, they are unlikely to intersect), it is possible to strengthen the previous convergence in expectation into a convergence in probability, see e.g. [START_REF] Van Der Hofstad | Random graphs and complex networks, volume II. Book in preparation[END_REF]Theorem 2.19] in the case of uncolored graphs. In our case, we obtain the following result, which is our main tool for proving Theorem 1.1 (i) and Proposition 1.2. Although the proof is standard, we briefly sketch the argument for reader's convenience. Proposition 3.1. Let ϕ be a bounded function on the set of finite rooted graphs whose edges are endowed with a label encoding its set of colors. Then, for any L ≥ 1,

1 n u∈[n] ϕ(u, V L (u)) P ---→ n→∞ E[ϕ(∅, V L (∅))], (12)
where V L (∅) is the L-neighborhood of the root ∅ in the colored graph GW(Λ) defined above.

Proof. As already mentioned, the convergence in expectation is a straightforward consequence of the wellknown local weak convergence of G. Note that conditionally on being present in G, an edge has color i with probability

λ i /n 1 -k j=1 (1 -λ j /n) = (1 + o(1)) λ i Λ .
In particular, since (λ i /Λ) k i=1 sum up to 1, a.s. every edge in the limit has only one color. To prove convergence in probability, we use Chebyshev's inequality and bound the variance of the random variable appearing on the left-hand side of (12). Assume without loss of generality that ϕ is non-negative and bounded by one. Then, on the one hand, for every u ∈ [n] and every fixed L ≥ 1,

v∈[n] E[ϕ(u, V L (u))ϕ(v, V L (v)) • 1 {v∈V 2L (u)} ] ≤ E[|V 2L (u)|] ≤ 1 + • • • + Λ 2L = O(1). (13)
On the other hand, conditionally on the event that v / ∈ V 2L (u), or equivalently that V L (u) ∩ V L (v) = ∅, and |V L (u)| = m for some m ≥ 1, V L (v) is distributed as the L-neighborhood of v in a colored ER random graph with n -m vertices and parameter 1 -k i=1 (1 -λ i n ), denoted hereafter by G n-m . Thus, denoting also by E n-m the expectation with respect to the distribution of G n-m , one has

E[ϕ(u, V L (u))ϕ(v, V L (v)) • 1 {v / ∈V 2L (u)} ] = m≥1 E ϕ(u, V L (u)) • E[ϕ(v, V L (v))1 {V L (u)∩V L (v)=∅} | V L (u)] • 1 {|V L (u)|=m} ≤ m≥1 E ϕ(u, V L (u)) • 1 {|V L (u)|=m} • E n-m [ϕ(v, V L (v))].
Now, the set V L (v) on G n-m is the same as on G unless there is at least one edge between one vertex of this set and one of the m additional vertices which are present in G but not in G n-m . Conditionally on the size of V L (v) in G n-m , this holds with probability bounded from above by m|V L (v)| Λ n . Therefore,

E n-m [ϕ(v, V L (v))] ≤ E n [ϕ(v, V L (v))] + 2mE n-m [|V L (v)|] • Λ n = E n [ϕ(v, V L (v))] + O m n .
As a consequence, using that

E[ϕ(u, V L (u)) • |V L (u)|] ≤ E[|V L (u)|],
which is bounded uniformly in n, we get

E[ϕ(u, V L (u))ϕ(v, V L (v)) • 1 {v / ∈V 2L (u)} ] -E[ϕ(u, V L (u))]E[ϕ(v, V L (v))] = O 1 n .
Together with (13), and summing over all pairs of vertices u, v ∈ [n], this gives

Var   1 n u∈[n] ϕ(u, V L (u))   = O 1 n ,
proving the desired concentration result. This concludes the (sketch of) proof of the proposition.

We can now give the proof of our main results.

Proof of Theorem 1.1 (i). Assume first that λ * 1 ≤ 1. In this case, it is well-known that the size of the largest connected component of G 1 divided by n converges in probability to zero, and thus a fortiori the same must hold for the largest CA-component.

Assume now that λ * 1 > 1. In this case, a.a.s. each of G 1 , . . . , G k contains a unique giant component denoted by C i max . Let also µ i be the asymptotic proportion of vertices in C i max . Since a.a.s. every non-giant connected component in G 1 , . . . , G k has size O(log n), it is sufficient to show that the size of k i=1 C i max divided by n converges to a positive constant in probability. Firstly, note that by ( 6) one has µ i = P(|C i (∅)| = ∞), where we keep the notation C i (u) for the connected component of a vertex u in GW(Λ) after removal of all edges in color i. Thus, for every i ∈ [k],

|C i max | n = 1 n u∈[n] 1 {u∈C i max } P ---→ n→∞ P(|C i (∅)| = ∞).
On the other hand, for every L ≥ 1, by Proposition 3.1 one has

1 n u∈[n] 1 {|C i (u)| ≥ L} P ---→ n→∞ P(|C i (∅)| ≥ L),
since the event of having a connected component of size at least L is a measurable function of the Lneighborhood. Taking the difference between the terms in the last two displays, we deduce that for every i ∈ [k] and every L ≥ 1,

1 n u∈[n] 1 {|C i (u)| ≥ L and u / ∈C i max } P ---→ n→∞ P(L ≤ |C i (∅)| < ∞). ( 14
)
Since the probability on the right-hand side goes to 0 as L → ∞, for every ε > 0 one can find L such that for all i ∈ [k], lim sup

n→∞ P 1 n u∈[n] 1 {|C i (u)| ≥ L and u / ∈C i max } ≥ ε k = 0,
which by summation over i gives

lim sup n→∞ P 1 n u∈[n] 1 {∃i∈[k]: |C i (u)| ≥ L and u / ∈C i max } ≥ ε = 0. ( 15
)
Moreover, using Proposition 3.1 again yields

1 n u∈[n] 1 {|C i (u)| ≥ L for all i∈[k]} P ---→ n→∞ P(|C i (∅)| ≥ L for all i ∈ [k]).
Then, letting L → ∞ together with (15) implies that

| k i=1 C i max | n = 1 n u∈[n] 1 {u∈C i max for all i∈[k]} P ---→ n→∞ P(|C i (∅)| = ∞ for all i ∈ [k]).
To conclude the proof of Theorem 1.1 (i), we show that the above limit is positive. For every L ≥ 1 and a fixed vertex u ∈ [n], the events {|C i (u)| ≥ L} are increasing, so by the FKG inequality (see Theorem 3.1 in [START_REF] Grimmett | The random-cluster model[END_REF])

P(|C i (u)| ≥ L for all i ∈ [k]) ≥ k i=1 P(|C i (u)| ≥ L).
Then, letting n → ∞ and using the local convergence of G towards GW(Λ) implies that

P(|C i (∅)| ≥ L for all i ∈ [k]) ≥ k i=1 P(|C i (∅)| ≥ L).
Finally, letting L → ∞ shows that

P(|C i (∅)| = ∞ for all i ∈ [k]) ≥ k i=1 P(|C i (∅)| = ∞) > 0,
as desired.

Proof of Proposition 1.2. Firstly, we define the notion of CA-connectivity in GW(Λ). Two vertices u and v are declared to be CA-connected if for every i ∈ [k], either u and v are connected in the subgraph of GW(Λ) obtained by removing edges in color i, which we denote by GW i (Λ), or if their connected components in this graph are both infinite. We denote by C(∅) the CA-component of the root. Now, we define I = {i : λ * i > 1}, and J = [k] \ I. Then, for L ≥ 1, M ≥ 1, and u ∈ [n], we let

C L,M (u) = i∈J v ∈ V L (u) : u G i ← → v ∩ i∈I v ∈ V L (u) : u G i ← → v or min(|C i (u)|, |C i (v)|) ≥ M ,
with the notation from the proof of Theorem 1.1 (i), and

C L (u) = i∈J v ∈ V L (u) : u G i ← → v ∩ i∈I v ∈ V L (u) : u G i ← → v or both u, v ∈ C i max . Note that every vertex u such that | C L (u)| < | C L,M (u)| is at distance at most L from the set S M = i∈I {v ∈ G : |C i (v)| ≥ M and v / ∈ C i max }.
However, by the Cauchy-Schwarz inequality, the expected number of such sites divided by n is at most

E   1 n v∈[n] |V L (v)|1 {v∈S M }   = E |V L (1)|1 {1∈S M } ≤ E[|V L (1)| 2 ] 1/2 • P(1 ∈ S M ) 1/2 .
Moreover, by (14), P(1 ∈ S M ) → 0 as M → ∞ uniformly in n, and a straightforward computation shows that |V L (1)| has a bounded second moment (using e.g. that it is stochastically dominated by the size of the L-neighborhood of the root in a BGW tree with Bin(n, Λ n ) offspring distribution). Therefore, Markov's inequality implies that for every ε > 0, one can find M large enough so that

lim sup n→∞ P |{u ∈ G : | C L (u)| < | C L,M (u)|}| n ≥ ε ≤ ε. (16)
Similarly, we define

C L,M (∅) = i∈J v ∈ V L (∅) ∩ C i (∅) ∩ i∈I v ∈ V L (∅) : v ∈ C i (∅) or min(|C i (∅)|, |C i (v)|) ≥ M , and
C L (∅) = i∈J v ∈ V L (∅) ∩ C i (∅) ∩ i∈I v ∈ V L (∅) : v ∈ C i (∅) or |C i (∅)| = |C i (v)| = ∞ , which is the decreasing limit of C L,M (∅) as M → ∞. Moreover, P | C L (∅)| < | C L,M (∅)| ≤ E | C L,M (∅)| -| C L (∅)| ≤ i∈I E   v∈V L (∅) 1 {v / ∈C i (∅), M ≤ |C i (v)| < ∞}   .
Fix i ∈ I. For every edge e ∈ GW(Λ), let us denote by e + the endvertex of e which is farther from the root. Then, for every vertex v ∈ GW(Λ) such that C i (∅) = C i (v), the (unique) path between ∅ and v in GW(Λ) contains an edge in color i. Considering the closest such edge to v, we get v∈V L (∅)

1 {v / ∈C i (∅), M ≤ |C i (v)| < ∞} ≤ e∈V L (∅), e in color i |C i (e + ) ∩ V L (e + )| • 1 {M ≤ |C i (e + )| < ∞} .
Since for any edge e in color i, the component C i (e + ) is contained in the subtree of the descendants of e + , and is thus independent of the remainder of GW(Λ), we have

E   v∈V L (∅) 1 {v / ∈C i (∅), M ≤ |C i (v)| < ∞}   ≤ E[|V L (∅)|] • E |V L (∅)| • 1 {M ≤ |C i (∅)| < ∞} .
Then, using Cauchy-Schwarz inequality as before, we get that uniformly in n,

P(| C L (∅)| < | C L,M (∅)|) ----→ M →∞ 0. (17)
The next step is to notice that since the sets C L,M (u) are measurable with respect to the (L + M )neighborhood of a vertex u, for every ≥ 1, Proposition 3.1 implies that

1 n u∈[n] 1 {| C L,M (u)| = } P ---→ n→∞ P(| C L,M (∅)| = ).
Together with ( 16) and ( 17), by letting M → ∞ we get that for any L ≥ 1,

1 n u∈[n] 1 {| C L (u)| = } P ---→ n→∞ P(| C L (∅)| = ). (18)
Finally, to conclude the proof of (2), it amounts to consider the L → ∞ limit in the last display. For the right-hand side, we just observe that the CA-component of the root is the increasing limit of the sets C L (∅) as L → ∞, from which it follows that for any ≥ 1,

P(| C L (∅)| = , | C(∅)| > ) ----→ L→∞ 0,
which yields for any ≥ 1,

P(| C L (∅)| = ) ----→ L→∞ P(| C(∅)| = ). (19)
It remains to show the corresponding convergence for a typical vertex of G. We distinguish two cases. If the set J is nonempty (or equivalently if λ * 1 ≤ 1), then using that

C(u) ⊆ C 1 (u), for any vertex u ∈ [n], we have { C L (u) = C(u)} ⊆ {|C 1 (u)| ≥ L}.
Now, given ε > 0, one can choose L large enough so that P(|C 1 (∅)| ≥ L) ≤ ε/2, and then using Proposition 3.1, we get that

lim sup n→∞ P |{u ∈ G : | C L (u)| < | C(u)|}| n ≥ ε ≤ lim sup n→∞ P |{u ∈ G : |C 1 (u)| ≥ L}| n ≥ ε = 0. ( 20
)
We consider now the slightly more difficult case when J is empty.

Let A = k i=1 C i max . One has | C L (u)| = , | C(u)| > ⊆ | C L (u)| = , u ∈ A ∪ k i=1 {|C i (u)| ≥ L, C i (u) = C i max } , (21)
since if C(u) is not contained in V L (u), then |C i (u)| ≥ L for all i ∈ [k]. Moreover, note that if u ∈ A, then C(u) = A, and thus | C L (u)| = , u ∈ A ⊆ A ∩ V L (u) = , |V L (u)| ≥ L ∪ {|A| = }.
Indeed, if u ∈ A and |A| ≥ + 1, then A must necessarily contain a vertex outside V L (u), which means that |V L (u)| ≥ L. Note that Theorem 1.1 (i) implies that P(|A| = ) → 0 as n → ∞, so we concentrate on the first event in the union above. For M ≥ 1, define

A M = {v : |C i (v)| ≥ M for all i ∈ [k]},
where for convenience we see A M as a vertex subset of both G or GW(Λ). By (15), we know that for every ε > 0, there exists M such that lim sup

n→∞ P   1 n u∈[n] 1 {|A∩V L (u)| = , |V L (u)| ≥ L} - 1 n u∈[n] 1 {|A M ∩V L (u)| = , |V L (u)| ≥ L} ≥ ε   = 0.
However, by Proposition 3.1 one has for any L ≥ 1 and M ≥ 1,

1 n u∈[n] 1 {|A M ∩V L (u)| = , |V L (u)| ≥ L} P ---→ n→∞ P |A M ∩ V L (∅)| = , |V L (∅)| ≥ L ,
which goes to 0 as L → ∞ for any fixed M ≥ 1. Then, by using also (15) again to handle the second union in (21), we deduce that for every fixed ε > 0 and ≥ 1, there is a sufficiently large L so that,

lim sup n→∞ P |{u ∈ G : | C L (u)| = , | C(u)| > }| n ≥ ε = 0.
Together with (18), ( k ≤ 1, then it is well-known that all the components C i (∅) are a.s. finite, and since edges have a.s. a unique color, this implies that the CA-component of the root is necessarily reduced to a single vertex.

For the last part, note that on the one hand, if

| C(∅)| = ∞, then |C i (∅)| = ∞ for all i ∈ [k], so a 1 = P(|C i (∅)| = ∞ for all i ∈ [k]) ≥ P(| C(∅)| = ∞).
For the reverse inequality, notice first that if a 1 = 0, there is nothing to prove. Thus, we may assume that a 1 > 0, which by Part (i) of Theorem 1.1 is equivalent to λ * 1 > 1. Suppose that each of the components C i (∅) for i ∈ [k] is infinite. We prove that in this case, the CA-component of the root is also a.s. infinite. It is well-known that on the event {|C 1 (∅)| = ∞}, the number of vertices in generation L in the tree C 1 (∅) goes to infinity almost surely as L → ∞. However, conditionally on the vertices v 1 , . . . , v N in the L-th generation of that tree, the subtrees T 1 , . . . , T N of GW(Λ) emanating from the vertices v 1 , . . . , v N , respectively, are all independent. Thus, the probability that for at least a 1 N/2 of them, the connected components of their root are infinite in each of GW i (Λ) for i ∈ [k], goes to one as N → ∞. Moreover, all such vertices are in the CA-component of ∅. But as already mentioned, on the event {|C 1 (∅)| = ∞} we have that N = N (L) → ∞ almost surely as L → ∞, so the result follows.

Proof of Theorem 1.1 (ii) and Proposition 1.3

The proof starts with the following general lemma that will also be used for the proof of Theorem 1.1 (iii) in the next section. For I ⊂ [k], write λ * I = Λ -i∈I λ i .

Lemma 3.2. For every j ∈ [k] and I ⊆ [k] \ {j} such that max(λ * I , λ * j ) < 1, one has uniformly in n, lim

M →∞ P ∃u = v : u G I ← → v, u G j ← → v, u G I∪{j} ←→ v, max(|C I (u)|, |C j (u)|) ≥ M = 0.
Proof. Fix ε > 0 and a set I ⊆ [k] \ {j} with max(λ * I , λ * j ) < 1. For every u, v ∈ [n], define the event

A u,v := u G I ← → v, u G j ← → v, u G I∪{j} ←→ v .
Then, on the event A u,v , there exists a path P connecting u and v not using color j. Since u and v are not connected in G I∪{j} , P must contain at least one edge which is not in G I . In particular, P must exit the graph C I (u) at some point. Consequently, on the event A u,v , there must exist w 1 , w 2 ∈ C I (u) which are connected in G j \ C I (u) (where by this, we mean the subgraph of G j with vertex set [n] obtained by removing only the edges of C I (u)). Moreover, note that conditioning on C I (u) only forces edges in G \ C I (u) with at least one endvertex in C I (u) to have a color in I, while it does not reveal any information for the remaining edges. Thus, for every fixed graph H containing u, one has

P w 1 G j \H ← --→ w 2 | C I (u) = H ≤ P w 1 G j \H ← --→ w 2 ≤ P(w 1 G j ← → w 2 ) = O 1 n ,
where for the last equality we use Corollary 2.3 together with the fact that G j is stochastically dominated by G(n, λ * j /n) (and that λ * j < 1 by hypothesis). As a consequence, on the event {v ∈ C I (u)},

P u G j ← → v, u G I∪{j} ←→ v | C I (u) ≤ w 1 ,w 2 ∈C I (u) P w 1 G j \C I (u) ←----→ w 2 | C I (u) = O |C I (u)| 2 n .
Therefore,

P A u,v , |C I (u)| ≥ M = O   1 n t ≥ M t 2 • P(v ∈ C I (u) | |C I (u)| = t) • P(|C I (u)| = t)   = O   1 n 2 t ≥ M t 3 • P(|C I (u)| = t)   = O M 3 e -M •I λ I n 2 , ( 22
)
where we use [START_REF] Krause | Hidden connectivity in networks with vulnerable classes of nodes[END_REF] for the second equality and Lemma 2.1 for the last one. Also, by a similar argument

P A u,v , |C j (u)| ≥ M = O M 3 e -M •I λ j n 2 . (23)
A union bound by summing ( 22) and ( 23) over all possible pairs of vertices {u, v} of G, and letting M → ∞ finishes the proof.

We call a set connected if its vertices belong to the same connected component. The last important piece towards the proof of Theorem 1.1 (iii) is the following lemma. Lemma 3.6. For every m ∈ {2, . . . , k}, denote by Y m the number of cycles in G that are separated into exactly m parts. Then, there are positive constants β 2 and β 3 , . . . , β k , such that

(Y 2 , . . . , Y k ) d ---→ n→∞ Po( β 2 ) ⊗ k m=3 Po(β m ).
Proof of Lemma 3.6. For every m ∈ {2, . . . , M }, denote by Y m,M the number of cycles in G that are separated into exactly m parts and having length at most M .

The first step of the proof is to show that for every m ∈ {2, . . . , k}, uniformly in n,

E[Y m -Y m,M ] ----→ M →∞ 0. (25)
To show this, note that a cycle of G is separated into (at least) two parts if and only if there exists a nonempty subset I ⊆ [k] different from [k] such that one part of the cycle is contained in G I while the other part of the cycle is contained in G I . For every ≥ 3, set C 2, to be the number of cycles of length in G which are separated into (at least) two parts. Then, using that to form a cycle of length , one may choose its vertices in n ways and order them in ( -1)! 2 ways, we have

E[C 2, ] ≤ n ( -1)! 2 I⊆[k] -1 m=1 i∈I λ i n m i∈[k]\I λ i n -m ≤ 2 k • (λ * k ) . (26)
It follows that

E [Y m -Y m,M ] ≤ n =M +1 E[C 2, ] ≤ 2 k ∞ =M +1 (λ * k ) ,
which goes to 0 as M → ∞ uniformly in n since λ * k < 1 by hypothesis, thus proving (25). The second step of the proof is to show that for every fixed M ≥ k, one has

(Y 2,M , . . . , Y k,M ) d ---→ n→∞ k m=2 Po(β m,M ) (27)
for some positive constants (β m,M ) k m=2 . For m ≤ k, denote by p m, the probability that a cycle of length in G is separated into exactly m parts. Let also Y m, denote the number of cycles of length which are separated into exactly m parts. In particular,

Y m,M = M =max(m,3) Y m, .
Adopting the notation of Lemma 2.8, observe also that for every m ≤ k, conditionally on G, The final step is to show that for every m ∈ {2, . . . , k}, the sequence (β m,M ) M ≥3 is a bounded nondecreasing sequence, which therefore converges as M → ∞ to some positive and finite constant. The fact that it is non-decreasing is straightforward by definition. On the other hand, by (26) we deduce that for every m ∈ {2, . . . , k} and M ≥ 1,

β m,M ≤ lim inf n→∞ E[Y m,M ] ≤ lim inf n→∞ E M =3 C 2, ≤ 2 k 1 -λ * k ,
showing that the sequence (β m,M ) M ≥3 is bounded, which completes the proof.

To finish the proof of Theorem 1.1 (iii), note that by Lemma 3.4 a.a.s. for every m ≥ 3 we have N m = Y m , while N 2 is the sum of Y 2 and the repeated edges in G. Thus, using the notation of Lemma 3.6 and Corollary 2.9, Theorem 1.1 (iii) follows with the constants β 2 = β 2 + γ 2 and (β m ) k m=3 .

Remark 3.7. We note that while it is possible to provide explicit expressions for β 2 , . . . , β k in terms of λ 1 , . . . , λ k , they tend to be more and more complicated as decreases from k to 2. However, one can provide a simple formula for β k . We do this in the case k ≥ 3; in fact, with the notation of Corollary 2.9, in the case k = 2 one simply needs to add γ 2 to the final result to account for the number of repeated edges. By the previous proof, one has

β k = ≥k p k, • γ ,
where p k, is the limit (as n → ∞) of the probability that a cycle of length in G is separated into exactly k parts, and γ = Λ 2 . To compute p k, , one needs to decide the lengths s 1 , . . . , s k ≥ 1 of the portions of the cycle in colors 1, . . . , k, respectively (with the constraint that s 1 + • • • + s k = ). Then, one needs to choose the starting vertex of the path colored in color 1 (say when turning clockwise), for which there are choices, and the order of appearance of the other colors, for which there are (k -1)! choices. Finally, note that as n → ∞, the probability that an edge is colored in color i tends to λ i /Λ, which in total yields the formula p k, = (k -1)! • where the two sums run over k-tuples of ordered pairwise distinct elements of [k] and [n], respectively, with i 1 = 1 (the factor 1/2 coming from the fact that there are two possible ways to orient a cycle). Now, recall that for any pair of distinct vertices u, v ∈ [n] and any i ∈ [k], by ( 5) one has that

P(v ∈ C i (u)) = E[|C i (u)| -1] n -1 .
Thus, by induction we get that for any (i 1 , . . . , i k ), u 1 ,...,u k P(u 1

G i 1 ← -→ u 2 , . . . , u k G i k ← -→ u 1 ) = E[|C i k (1)| -1] n -1 • u 1 ,...,u k P(u 1 G i 1 ← -→ u 2 , . . . , u k-1 G i k-1 ←--→ u k )
= n(n -1) . . . (n -k + 1)

k i=1 E[|C i (1)| -1] n -1 = (1 + o(1)) k i=1 E[|C i (1)| -1],
where for the second equality we use that the number of choices for the sequence (u 1 , . . . , u k ) is n(n -1) . . . (n -k + 1). The formula follows since there are (k -1)! ways to choose i 2 , . . . , i k , and with the notation of Section 3.1

E[|C i (1)| -1] = (1 + o(1)) • E[|GW(λ i )| -1] = (1 + o(1)) • λ i 1 -λ i ,
where the last equality is derived from the fact that for every d ≥ 1, the expected number of vertices at distance exactly d from the root in GW(λ i ) is λ d i .

Conclusion

In this paper, we characterized precisely the size of the largest CA-component in randomly colored Erdős-Rényi random graphs in the entire supercritical and subcritical regimes, and in part of the intermediate regime as well. The most obvious open question that we leave concerns the size of the largest CAcomponent when λ * k-1 ≥ 1 > λ * 1 . The additional difficulty this point presents compared to the second part of Theorem 1.1 is that in general, one cannot obtain the largest CA-component as an intersection of two independent random graphs. Nevertheless, we conjecture that an analogue of Theorem 1.1 (ii) holds in this case as well. Unfortunately, confirming this fact seems to be out of reach with our present techniques even in the simplest case when k = 3. We remark that when λ * m < 1, by a statement similar to Lemma 3.3 (that is also proved in a similar way) one may reduce the problem to the case of k -m + 1 colors where G 2 , . . . , G k-m+1 are all supercritical graphs while G 1 is subcritical.

In the critical case when λ * 1 = 1 < λ * 2 , we suspect that the size of the largest CA-component divided by n 2/3 converges in distribution towards a non-degenerate random variable. The reason is that in G 1 , the size of the largest component divided by n 2/3 converges in distribution, and the largest components in G 2 , . . . , G k are of linear order. However, the lack of independence makes it difficult to turn this heuristic into a rigorous proof.

Another possible direction could be to explore the case of other classical random graphs, or the closely related model of randomly vertex-color-avoiding random graph, which was initially considered in the literature [START_REF] Krause | Hidden connectivity in networks with vulnerable classes of nodes[END_REF][START_REF] Krause | Color-avoiding percolation[END_REF] (and in which, as its name suggests, we color the vertices of the graph instead of the edges). In particular, as suggested in [START_REF] Krause | Hidden connectivity in networks with vulnerable classes of nodes[END_REF], it could be interesting to study the effect of clustering (typical for random graphs with power law degree distributions, for example), as it arises in numerous recently introduced real-world networks models. Indeed, in this case, removing vertices with large degree could have a dramatic effect on the connectivity properties of the graph.

Lemma 2 . 8 (

 28 [START_REF] Bollobás | Random Graphs[END_REF], Corollary 4.9). Fix λ > 0. For m ≥ 3, denote by C m the number of cycles of length m in the graph G(n, p) with p = (1 + o(1)) λ n . Then, for any fixed ≥ 3, (C 3 , . . . , C ) d ---→ n→∞ m=3

  . The last piece of the proof of the proposition is to show that for any ≥ 2, ν = P(| C(∅)| = ) is positive if and only if λ * k > 1, and that the constant a 1 appearing in Part (i) of Theorem 1.1 is equal to the probability that the CA-component of the root is infinite. For the first part, assume that λ * k > 1, and let ≥ 1 be given. Then, with positive probability one can have altogether |C k (∅)| = , all vertices of C k (∅) are connected to infinity in GW k (Λ), and |C i (∅)| < ∞ for all values of i different from k. If the last events hold simultaneously, one can observe that the CA-component of the root is precisely C k (∅), and thus it has size . Conversely, if λ *

Lemma 3 . 3 .

 33 Suppose that λ * k-1 < 1. Then, uniformly in n, limM →∞ P(∃S ⊆ [n] : |S| ≥ M, S is connected in each of G 1 , . . . , G k-1 but not in G k ) = 0.Proof. Fix S ⊆ [n] of size at least M , and assume that S is connected in each of the graphs G 1 , . . . , G k-1 . If S is not connected in G k , it means that one can find two distinct vertices u, v ∈ S which are not connected in G k . Let I be a maximal subset of [k -1] such that u and v are connected in G I . Since u and v are not connected in G k , I = [k -1], and hence there exists j ∈ [k -1] \ I such that u and v are not connected in G I∪{j} . However, using that max(λ * I , λ * j ) < 1 and |C j (u)| ≥ |S| ≥ M , Lemma 3.2 ensures that this event happens with probability converging to 0 as M → ∞, uniformly in n.

=Z

  Bin(C , p m, ). Moreover, recall that G is distributed as an Erdós-Renyi random graph with parameters n and p = (1 + o(1)) • Λ n , so Lemma 2.8 shows that (C 3 , . . . , C M ) where for every ∈ {3, . . . , M }, Z is a Poisson random variable with parameter γ = Λ 2 . It follows that for every fixed , (still writing with a slight abuse of notation p m, for the limiting value of this probability as n → ∞, see Remark 3.7 for an explicit expression when m = k), ( Y 2, , . . . , Y k, ) d ---→ n→∞ Bin(Z , p 2, ), . . . , Bin(Z , p k, ) , which by the thinning property of the Poisson distribution (see e.g. Section 5.3 in [7]) is a vector of independent Poisson variables with parameters (p m, •γ ) m=2 . Summing over and using the independence of the variables (Z ) M =3 , we deduce that (27) holds with β m,M = M =max(m,3) p m, • γ .

s 1 +. 1 2 i 1 P(u 1 G i 1 ←

 112111 •••+s k = Altogether this givesβ k = ≥k p k, • γ = (k -1)! 2 ≥k s 1 +•••+s k = -λ i ,remembering for the third equality that the sum runs over indices {s i } i∈[k] larger than or equal to 1.For completeness, let us mention another slightly different way to compute β k . Note first that since CA-components are supported by cycles or single edges, the expected number of CA-components of size k, or equivalently of cycles which are separated in exactly k parts, is equal to1 + o(1) ,...,i k ∈[k] u 1 ,...,u k ∈[n] -→ u 2 , . . . , u k G i k ← -→ u 1 ),

Acknowledgments. We thank Dieter Mitsche for enlightening discussions.

We are ready conclude the proofs of Theorem 1.1 (ii) and Proposition 1.3.

Proof of Proposition 1.3. Denote by C max the largest CA-component in G. As the vertices of C max form a connected set in G i for every i ∈ [k -1], by Lemma 3.3 we have that uniformly in n, lim

On the other hand, if C max is connected in G k , it is obtained by intersecting a connected component in G k and one in G k . Moreover, by definition the probability of having an edge present in

Thus, G k is stochastically dominated by G(n, 1/n). However, it is well-known that the size of the largest component in G(n, 1/n) is a.a.s. of order n 2/3 (see Proposition 5.2 in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF]), in particular it is a.a.s. smaller than n 3/4 , say. On the other hand, by a similar argument as in [START_REF] Krause | Hidden connectivity in networks with vulnerable classes of nodes[END_REF] one has that for any n > ≥ M ≥ 2 and any distinct vertices v 1 , . . . , v M ∈ [n],

and the same holds with C k (v 1 ) instead of C k (v 1 ). Thus, for any M ≥ 2 and any distinct v 1 , . . . , v M ∈ [n],

Likewise, we know by (4) that a.a.s. the size of the largest connected component in G k is at most 2

log n, and as above one has

Summing over all possible vertices v 1 , . . . , v M ∈ [n] and using independence between G k and G k , we deduce that

where the last equality holds as soon as M ≥ 6. Together with (24), this concludes the proof of the proposition.

Proof of Theorem 1.1 (ii). Recall that now λ * k > 1 > λ * k-1 , and in particular, all graphs G i with i ≤ k -1 are subcritical while G k is supercritical. Firstly, we observe that there exists ε > 0 such that a.a.s. the largest CA-component has size larger than ε log n. Indeed, we know by (4) that a.a.s. there exists a connected component in G k of size at least log n/(2I λ k ), and hence (6) and Lemma 2.10 imply together that a.a.s. its intersection with the giant component of G k has size at least

Next, let C max be the largest CA-component. By definition its vertices are connected in all the graphs G 1 , . . . , G k-1 , and thus by Lemma 3.3 a.a.s. they are also connected in G k . This means that C max is in fact obtained as the intersection of a connected component of G k with one of G k . However, it is well-known that a.a.s. all connected components in a supercritical ER random graph but the largest one have size O(log n) (see e.g. Section 4.4.1 in [START_REF] Van Der Hofstad | Random graphs and complex networks[END_REF]). Thus, by the same argument as in the proof of Proposition 1.3, we deduce that the probability of having three vertices connected in G k and participating in the same non-giant component of

. Hence, a.a.s. every CA-component of size at least 3 (and C max in particular) is contained in the giant in G k .

Finally, by Lemma 2.10 and Corollary 2.13 we conclude that, with the notation of Corollary 2.13,

which finishes the proof.

Proof of Theorem 1.1 (iii)

We assume throughout this section that λ * k < 1. We call support of a CA-component the subgraph of G obtained as the union of all paths in G 1 , . . . , G k between any pair of distinct vertices of the CA-component. The main observation of the proof is the following lemma. Proof. Consider a CA-component C and assume that it is not reduced to a single vertex. Let u and v be two different vertices of C. Assume first that

with the notation of Remark 2.7. By the second point of this remark, and since λ * i < 1 by hypothesis, we know that a.a.s. C i (u) is a tree with no repeated edge. In other words, u and v are connected by a unique path P in G i , and since P contains no repeated edges, u and v cannot be connected in G {i,j} for any color j in P . However, Lemma 3.2 applied for I = {i} shows that a.a.s. this situation does not happen. Thus, we may assume that |C i (u)| ≤ c 1 (Λ) k log n for all i, and by summation over i we may as well assume that C(u), the connected component of u in G, has size at most c 1 (Λ) log n. Then, using the first result from Remark 2.7, we know that a.a.s. either C(u) contains no cycles and at most one repeated edge or no repeated edges and at most one cycle. Moreover, note that for every pair of vertices u and v in C, u and v cannot be disconnected in G by deleting an edge with a single color in C(u). Thus, the unique cycle or repeated edge necessarily supports C, which concludes the proof of the first part.

For the second part, just observe that when | C| ≥ 3, the vertices in C divide its supporting cycle into paths without common colors, so there are at most k such paths.

For a positive integer , we say that a cycle in G is separated into parts if it can be divided into consecutive paths that use disjoint sets of colors. We say that it is separated into exactly parts if it is separated into parts but not into + 1 parts. The following fact follows directly from the previous definition.