Maxime Bertauts

Adrien Vezinet

Emilie Janots

Magali Rossi

Isabelle Duhamel-Achin

Philippe Lach

Pierre Lanari

Cenozoic Pb-Zn-Ag mineralization in the Western Alps

INTRODUCTION

World-class Pb-Zn-Ag deposits are commonly associated with fluid circulation at basement/cover unconformities in extensive basins [START_REF] Boiron | Fluid flows and metal deposition near basement /cover unconformity: lessons and analogies from Pb-Zn-F-Ba systems for the understanding of Proterozoic U deposits[END_REF]. However, less-common Pb-Zn-Ag deposits may have an extended evolution influenced by orogenic processes [START_REF] Williams | Metalliferous economic geology of the Mt Isa Eastern Succession[END_REF] that redistributed the ore minerals [START_REF] Cugerone | Behavior of critical metals in metamorphosed Pb-Zn ore deposits: example from the Pyrenean Axial Zone[END_REF]. Extracting the ages of crystallization and subsequent remobilization of polymetallic ore deposits has proven challenging due to potential reopening of the isotopic systems [START_REF] Chiaradia | Radiometric Dating Applied to Ore Deposits: Theory and Methods[END_REF]. Dating actinide-rich accessory minerals is the most common and reliable method for obtaining accurate ages because of the possibility to check for concordance using the triple U-Th-Pb decay series [START_REF] Rasmussen | Testing ore deposit models using in situ U-Pb geochronology of hydrothermal monazite: Paleoproterozoic gold mineralization in northern Australia[END_REF][START_REF] Li | High-Grade Magnetite Mineralization at 1.86 Ga in Neoarchean Banded Iron Formations, Gongchangling, China[END_REF]. However, that approach has limitations due to the relative scarcity and small size of accessory minerals suitable for dating [START_REF] Engi | Petrochronology Based on REE-Minerals: Monazite, Allanite, Xenotime[END_REF]. The recent development of in situ Rb-Sr dating [START_REF] Zack | Laser ablation Rb/Sr dating by online chemical separation of Rb and Sr in an oxygen-filled reaction cell[END_REF] on ubiquitous and abundant minerals (e.g., mica, feldspar, apatite) has opened new avenues for constraining the age of deposits as young as 28.1 ± 2.2 Ma (Şengün et al., 2019). The Rb-Sr method can assess not only the primary age but also subsequent periods of mineralization [START_REF] Olierook | Resolving multiple geological events using in situ Rb-Sr geochronology: implications for metallogenesis at Tropicana[END_REF][START_REF] Tillberg | Reconstructing craton-scale tectonic events via in situ Rb-Sr geochronology of polyphased vein mineralization[END_REF]. Proterozoic Rb-Sr ages preserved within Caledonian ore bodies imply inheritance and remobilization during the subsequent orogenic stages [START_REF] Tillberg | Reconstructing craton-scale tectonic events via in situ Rb-Sr geochronology of polyphased vein mineralization[END_REF].

Our study investigates the timing and tempo of Pb-Zn-Ag mineralization along a lithostructural profile in the Western Alps in France, where the tectonic and metamorphic evolution and fluid circulation are well constrained [START_REF] Handy | Reconciling plate-tectonic reconstructions of Alpine Tethys with the geological-geophysical record of spreading and subduction in the Alps[END_REF][START_REF] Gnos | Episodes of fissure formation in the Alps: connecting quartz fluid inclusion, fissure monazite age, and fissure orientation data[END_REF]. The abundance of Pb-Zn-Ag mineralization in this area has been attributed to Variscan orogenesis, Mesozoic Tethyan opening, or Alpine remobilization [START_REF] Nägler | Initial isotopic heterogeneity and secondary disturbance of the Sm-Nd system in fluorites and fluid inclusions: A study on mesothermal veins from the central and western Swiss Alps[END_REF]. However, recent in situ U-Pb dating by [START_REF] Bertauts | A New Alpine Metallogenic Model for the Pb-Ag Orogenic Deposits of Macôt-la Plagne and Peisey-Nancroix[END_REF] of stratabound Pb-Zn-Ag deposits at Mâcot-la Plagne and Peisey-Nancroix (southeastern France) suggests a new Alpine orogenic period of metallization.

To consolidate these results, we used a multi-system approach involving in situ U-Th-Pb and Rb-Sr dating to compare and constrain ages.

GEOLOGY AND SAMPLING

Samples were collected along an east-west transect from the Briançonnais domain of the internal Alps to the Belledonne external crystalline massif (Fig. 1). The Briançonnais domain corresponds to the European continental margin and consists of Variscan basement comprising Carboniferous schists and locally some Mesozoic sediments. It was partially subducted under the African tectonic plate before being thrust over the European tectonic plate during the Cenozoic Alpine convergence [START_REF] Handy | Reconciling plate-tectonic reconstructions of Alpine Tethys with the geological-geophysical record of spreading and subduction in the Alps[END_REF]. The sedimentary cover is characterized by lowtemperature metamorphism (<500 °C) and intense deformation [START_REF] Strzerzynski | Tectono-metamorphic evolution of the Briançonnais zone (Modane-Aussois and Southern Vanoise units, Lyon Turin transect[END_REF]. The Belledonne massif is composed of Variscan basement rocks of the European plate, which underwent lower greenschist facies metamorphism and only localized deformation during the Alpine collision [START_REF] Rossi | Geochemical variations and element transfer during shear-zone development and related episyenites at middle crust depths: insights from the Mont Blanc granite (French -Italian Alps[END_REF]. The internal metamorphic Alps are separated from the external Alps by the Penninic front, which marks the onset of the European margin collision at ca. 35 Ma [START_REF] Ceriani | Multi-stage thrusting at the "Penninic Front[END_REF].

We collected 44 samples from mine tailings of seven historic Pb-Zn-Ag deposits. Of these, only four samples from two different lithostructural contexts contain accessory allanite and monazite suitable for U-Th-Pb dating. In the internal Briançonnais domain, one sample from the Peisey-Nancroix deposit is located within the deformed Permian-Triassic cover along the Internal Briançonnais fault (IBF; Fig. 1). In the Belledonne massif, the three samples come from the subsidiary Pb-Zn-Ag mineralization of the Penay and Le Gros Villan deposits, which are located in sub-vertical northeast-southwest dextral shear zones along major faults separating the massif 69 from the Mesozoic cover (Fig. 1). 70

RESULTS

Mineralogy and Microstructures

The Pb-Zn-Ag mineralization consists mainly of galena with variable amounts of chalcopyrite, sphalerite, tetrahedrite-tennantite, and pyrite. The four samples show evidence of a high-strain regime with clasts hosted in a fine-grained equigranular recrystallized matrix.

Based on mineralogy and microstructures [START_REF] Bertauts | A New Alpine Metallogenic Model for the Pb-Ag Orogenic Deposits of Macôt-la Plagne and Peisey-Nancroix[END_REF], mineralization in the Peisey-Nancroix deposit appears to be synchronous with dynamic quartz recrystallization associated with the precipitation of phengite (Fig. 2A) and monazite (Fig. 2B). The Penay sample shows massive sphalerite in a galena-sphalerite matrix. Clasts of albite, quartz, and foliated phengite aggregates are found within the massive sphalerite and recrystallized matrix (Fig. 2C).

Subhedral to anhedral allanite grains are intergrown with sulfides (galena and sphalerite) and phengite contains inclusions of these minerals, indicating a common origin (Fig. 2D). The Le Gros Villan mineralization consists of centimeter-long galena-chalcopyrite-sphalerite-quartz veins hosted in a matrix of recrystallized, partially sericitized quartz and K-feldspar clasts. Phengite that formed at this stage is referred to herein as Ph1. Fractures within the K-feldspar clasts are filled by sulfides (galena and chalcopyrite). Monazite occurs as inclusions within other minerals and forms part of intergrowths with sulfides (Fig. 2F). Hourglass sector zoning within the monazite indicates a single crystallization stage during primary mineralization. The primary mineralization is affected by a second stage of deformation and recrystallization expressed by a foliation made of phengite (Ph2) and secondary fine-grained foliated galena (Gn2) that in places cuts the primary sulfides (Fig. 2E). In these foliated domains, the shape of monazite grains is controlled by foliation deflection of oriented acicular phengite grains. Electron microprobe point analysis and X-ray mapping demonstrated that phengite from the three deposits have homogeneous major and minor element compositions (Tab1e S1 and Figs.

S1 and S2 in the Supplemental Material1).

In situ LA-ICP-MS Rb-Sr and U-Th-Pb Dating

The U-Pb analyses on 26 monazite grains from the Peisey-Nancroix deposit (Fig. 3A; Table S5) define an isochron in the Tera-Wasserburg diagram that intersects the Concordia at 35.1 ± 0.6 Ma [START_REF] Bertauts | A New Alpine Metallogenic Model for the Pb-Ag Orogenic Deposits of Macôt-la Plagne and Peisey-Nancroix[END_REF]. This age is similar to that obtained on 52 in situ Rb-Sr isotopic analyses on five phengite crystal aggregates (Table S8) showing 87Rb/86Sr values ranging from 350 to 800, aligned along an array with a slope corresponding to an age of 34.6 ± 4.7 Ma with an initial 87Sr/86Sr value of 0.771 ± 0.034. Two spots have higher Sr contents and Rb/Sr values <70, which could correspond to phengite with higher Sr contents or inclusions of Sr-rich minerals such as apatite. When these two spots are added, the resulting isochron gives an older age of 40.1 ± 3.2 Ma with an initial Sr isotope ratio of 0.724 ± 0.014 (Fig. 3B).

The Th-Pb analyses of allanite from the Penay deposit (Table S7) are plotted in an isochron diagram 208Pb/206Pbc (c-common) versus 232Th/206Pbc (n = 10, Fig. 3C). The regression yields a Th/Pb age for allanite of 14.9 ± 7.6 Ma. In situ Rb-Sr isotope analyses of three Penay phengite aggregates located within massive sphalerite or fine-grained galena-sphalerite matrix (Table S8) define an isochron age of 18.4 ± 7.2 Ma (n = 35) with an initial 87Sr/86Sr value of 0.7214 ± 0.0065 consistent with the Th-Pb age. Six analyses of co-genetic albite grains yield a scattered Sr-isotope weighted mean of 0.7213 ± 0.0030. When included in the regression, the age remains the same, but the uncertainty of the isochron regression decreases to 3.6 Ma (Fig. 3D). The U-Th-Pb monazite dating from the Le Gros Villan deposit was performed on 22 monazite grains obtained from two different thin sections (Table S6). After common Pb correction for the three Pb isotopes (206Pb, 207Pb, and 208Pb), the monazite data yield a Concordia age of 37.1 ± 0.7 Ma (n = 30/43) on a 208Pbr/232Th (r-radiogenic) versus 206Pbr/238U diagram (Fig. 3E). Furthermore, Rb-Sr isotopic analyses were also performed on 10 phengite clusters (Table S8) within sericitized feldspar (Ph1) or secondary foliation (Ph2). All data from the Ph2 foliation align along an isochron that yields an age of 19.3 ± 2.1 Ma. In comparison, the Ph1 results are more complex to interpret, but phengites in one clast plot on a Rb-Sr linear array give an age of 49 ± 12 Ma, overlapping the U-Th-Pb age. The other analyses plot between the two isochrons between ca. 49 and 19 Ma (Fig. 3F).

DISCUSSION

Strenght of U-Th-Pb and Rb-Sr Geochronology

In fluid-rich environments, the Rb-Sr isochron ages are generally recording the phengite crystallization age [START_REF] Glodny | Diffusion versus recrystallization processes in Rb-Sr geochronology: Isotopic relics in eclogite facies rocks, Western Gneiss Region, Norway[END_REF][START_REF] Villa | Diffusion in mineral geochronometers: Present and absent[END_REF]. To prepare the groundwork for in situ dating, careful mineralogical and microstructural relationships were established to determine the crystallization sequences. Homogeneous major and minor elements compositions of phengite are interpreted as one phengite population without recrystallizations (Fig. S1 and Fig. S2). Intergrowth and inclusion relationships (Fig. 2), as well as mineral zoning, indicate that the phengite and REEminerals are cogenetic. Except Ph2 from the Le Gros-Villan, they coincide with the main stage of sulfide precipitation and thus record the primary age of the Pb-Zn-Ag deposits. Indeed, there is equilibration of the two isotopic systems (Rb-Sr and U-Th-Pb) giving consistent Alpine ages (Fig. 3). Even in the more complex case of the Le Gros Villan deposit, the primary phengite (Ph1) which corresponds to sericitization of K-feldspar, has scattered Rb-Sr isotopic analyses but with a discrete alignment at 49 ± 12 Ma. This older age overlaps with the U-Th-Pb age of the monazite (37.1 ± 0.7 Ma) attributed to the primary mineralization (Fig. 2E,F), with probably some inheritance from K-feldspar. Such results clearly demonstrate the strength of the in situ method used here, because mixing between incompletely reset mica and/or K-feldspar domains has been a recurring problem in solution-based studies (e.g., [START_REF] Müller | Deformation-induced resetting of Rb/Sr and 40Ar/39Ar mineral systems in a low-grade, polymetamorphic terrane[END_REF][START_REF] Bröcker | The geological significance of 40Ar/ 39Ar and Rb-Sr white mica ages from Syros and Sifnos, Greece: a record of continuous (re)crystallization during exhumation[END_REF].

The U-Th-Pb dating was complicated by two factors: (i) the scarcity and small size of mineral grains suitable for dating, with only 3 samples out of 44 yielding suitable material, and (2) the possible incorporation of common Pb in this Pb-rich environment, as seen for the Le Gros Villan monazite and, more importantly, for the Penay allanite. In contrast, the ubiquity of mica, the structural control of this mineral, and minimal sample preparation, are advantages of the Rb-Sr system when used for dating of orogenic mineralization. With a wide range of Rb/Sr ratios, in situ dating of white mica can yield a well-resolved Alpine age of 19.3 Ma ± 2.1 Ma for the Le Gros Villan deposit without isochron anchoring by other phases (10% precision). For samples with lower Rb/Sr spreading (40% precision), isochron anchoring with co-genetic Sr-rich phases improves the precision by about 20%. For samples from the Peisey-Nancroix deposit, isochron anchoring modifies the initial 87 Sr/ 86 Sr value and thus the calculated age, but within the range of uncertainties (40.1 Ma ± 3.2 Ma instead of 34.6 ± 4.7 Ma). The Rb/Sr calibration on the Mica-Mg nano-powder (Tab. S9) may induce a few percent drifted phengite age, but this would represent less than 1 Ma for such young deposit within the uncertainty.

Another advantage of cross-comparison of Rb-Sr and U-Th-Pb dating paired in thin section is the ability to distinguish different crystallization stages [START_REF] Chiaradia | Radiometric Dating Applied to Ore Deposits: Theory and Methods[END_REF]. The primary Eocene mineralization of the Le Gros Villan deposit (37.1 ± 0.7 Ma, monazite) contains secondary phengite (Ph2) and galena (Gn2) in post-mineralization microstructures (localized foliation and fractures, Fig. 2E). Thus, Ph2 in this deposit is thought to record secondary Miocene remobilization at 19.3 ± 2.1 Ma during deformation. In this case, two Rb-Sr ages correspond to two distinct microstructures (Fig. 3).

Evidence of Alpine Mineralization and Remobilization

In Peisey-Nancroix, one of the two largest historical Pb-Zn-Ag deposits from the French Alps, the new Rb-Sr dating (Fig. 3B) is consistent with the well-resolved U-Pb syn-orogenic Alpine ages from [START_REF] Bertauts | A New Alpine Metallogenic Model for the Pb-Ag Orogenic Deposits of Macôt-la Plagne and Peisey-Nancroix[END_REF], ruling out a possible sedimentary-diagenetic origin or inheritance for these deposits despite their presence in Triassic quartzite [START_REF] Rogel | Le gisement de Plomb de La Plagne (Savoie). Etude géologique et métallogénique[END_REF]. The deposits formed over a short period of time, which was less than the analytical resolution of in situ U-Pb dating (35.1 ± 0.6 Ma) and Rb-Sr dating (35)(36)(37)(38)(39)(40). The age of ca. 35 Ma is attributed to fluid circulation coeval with the major top-to-west thrusting within the Penninic front (and the Internal Briançonnais front) at the onset of the collision [START_REF] Strzerzynski | Tectono-metamorphic evolution of the Briançonnais zone (Modane-Aussois and Southern Vanoise units, Lyon Turin transect[END_REF].

The two deposits in the external crystalline massifs are located in the Variscan basement and show evidence of sulfide recrystallization, suggesting episodic growth and/or remobilization. However, neither in situ U-Th-Pb dating of REE-rich phases nor Rb-Sr dating of white mica indicate a pre-Alpine age. The Miocene ages (15-20 Ma) obtained in these deposits could correspond to the circulation of non-mineralizing fluids [START_REF] Rolland | Two-stage fluid flow and element transfers in shear zones during collision burial-exhumation cycle: Insights from the Mont Blanc Crystalline Massif (Western Alps)[END_REF]. The new Late Eocene U-Th-Pb monazite ages in the Le Gros Villan mineralization (Fig. 3E) document early, previously undocumented fluid circulation and are more comparable to those obtained in the internal domains [START_REF] Gnos | Episodes of fissure formation in the Alps: connecting quartz fluid inclusion, fissure monazite age, and fissure orientation data[END_REF]. In the external domains, sedimentation had started in a flexural basin, and thrusting in the internal domain along the Penninic front had just begun [START_REF] Simon-Labric | 40Ar/39Ar dating of Penninic Front tectonic displacement (W Alps) during the Lower Oligocene[END_REF]. Thus, early mineralization in the Belledonne massif basement may have been promoted by fluid circulation in Variscan-inherited structures reactivated during burial of the massif [START_REF] Guillot | Paleozoic evolution of the External Crystalline Massifs of the Western Alps[END_REF].

CONCLUSIONS

Figure 1 .

 1 Figure 1. Location of the studied Pb-Zn-Ag mineralizations on the tectonic map of the Western Alps (northern French Alps), modified from Bousquet et al. (2012).

Figure 2 .

 2 Figure 2. Examples of analyzed phengite (A, C, E) and accessory minerals (B, D, F) used for dating, observed using optical (A, C) and backscattered electron (B, D, E, F) microscopy. The two Peisey-Nancroix samples show: (A) deformed quartz (Qz) Qz1 porphyroclasts shaped by micrometric phengite (Ph) oriented in the foliation, sulfides, and equigranular micrograins of Qz2 (thick section, polarized light) (Gn-galena); and (B) prismatic monazite (Mnz) grain with a poikilitic texture highlighted by quartz, spherical florencite (Flo), and acicular phengite inclusions (Apapatite). The massive sulfides from thin sections of Penay show: (C) porphyroclasts of a foliated phengite foliated and folded, albite (Ab), and quartz hosted in a sphalerite-galena matrix (Gn + Sp); and (D) intergrowth texture between galena, sphalerite, and anhedral allanite (Aln) grains within the foliated phengite clast. The sample from Le Gros Villan shows: (E) chalcopyrite (Ccp) cracks filled by oriented acicular phengite and Gn2 crystallization; and (F) subhedral monazite inclusion within chalcopyrite. Abbreviations from Warr (2021).

Figure

  Figure 3. U-Pb (A, C, E) and Rb-Sr (B, D, F) laser ablation-inductively coupled plasma-mass spectrometry analyses on rare earth element-rich phases and phengite (Ph), respectively, for the Peisey-Nancroix (PN) (A, B), Penay (PEN) (C, D) and Le Gros Villan (LGV) (E, F) mineralizations. (A) Tera-Wasserburg diagram of PN monazite without any correction from Bertauts et al. (2022). (C) 206Pbc normalized Th-Pb isochron of PEN allanite. (E) U-Th-Pb data from LGV monazite are plotted on a 208Pbr/232Th versus 206Pbr/238U Concordia diagram using the total Pb/U-Th algorithm of Vermeesch (2020). Rb-Sr isochrons and calculated ages for (B) PN sample; (D) PEN sample (Ab-albite); and (F) LGV sample. Fds-K-K-feldspar. Data ellipses represent 2σ errors. MSWD-mean square of weighted deviates.

  Concordance of the paired in situ Rb-Sr and U-Th-Pb ages in the Western Alps suggests that these isotopic systems reached equilibrium during hydrothermal Pb-Zn-Ag mineralization. The combination of Rb-Sr and U-Th-Pb systems unambiguously indicates Alpine ages for these Pb-Zn-Ag deposits. Two ages, 35-40 Ma and 15-20 Ma, are associated with collision and exhumation of the Belledonne massif. The Rb-Sr geochronological data set obtained on texturally distinctive micas provides evidence for episodic evolution of Alpine Pb-Zn-Ag mineralization. The Pb-Zn-Ag mineralization was produced by fluid circulation along major lithostructural contacts during the Alpine collision.

ACKNOWLEDGMENTS

This work was initially supported by the "Référentiel Géologique de la France" RGF-Alps Program of the Bureau de Recherche Géologiques et Minières (BRGM), which financed the Ph.D. grant of M. Bertauts. Additional support was received from the TelluS Program of Centre National de la Recherche Scientifique / Institut national des sciences de l'Univers (CNRS/INSU), the IDEX-Initiative de Recherche à Grenoble Alpes 2021 funding provided by the University Grenoble Alpes, and local BQR funding. The work was mainly carried out at l'Institut des Sciences de la Terre (ISTerre, Université Grenoble Alpes), which is part of the Laboratoires d'excellence (LabEx) OSUG@2020 (ANR10 LABX56). Rb-Sr analyses were conducted in the ISTerre MicroAnalytical Platform (IMAP) at Université Grenoble Alpes, funded by grants from the European Research Council (ERC) under the European Union's Horizon H2020 research and innovation program (Synergy Grant MEET, grant agreement no. 856555); Auvergne-Rhône-Alpes region (2020 AURA P3 -CPER 2015/2020) and CNRS-INSU. We acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grant ANR-23-CE01-0017 (project CMiO). The three anonymous reviewers helped with clarifying several aspects of the paper and are sincerely acknowledged.


Nicolas Bousquet

Laurent Feuilloley

Sébastien Zeitoun

Global certification via perfect hashing *

In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of information called certificates. Here, there is only one global certificate which is shared by all the nodes, and the property we want to certify is the existence of a graph homomorphism to a given graph.

For bipartiteness, a special case of graph homomorphism, Feuilloley and Hirvonen proved in [3] some upper and lower bounds on the size of the optimal certificate, and made the conjecture that their lower bound could be improved to match their upper bound. We prove that this conjecture is false: their lower bound was in fact optimal, and we prove it by providing the matching upper bound using a known result of perfect hashing.

Introduction

The topic of certification originates from self-stabilization in distributed computing, and consists in the following. Nodes of a network are provided with a unique identifier, and with some pieces of information called certificates. These certificates can either be local (each node receive its own certificate), or global (there is a unique certificate, which is the same for all the nodes). The aim of the nodes is then to decide if the network satisfies a given property. To do so, each node should take its decision (accept or reject) based only on its local view in the network, which consists in its neighbors, their identifiers and their certificates. The correctness requirement for a certification scheme is the following one: for every network, the property is satisfied if, and only if, there exists an assignment of the certificates such that all the nodes accept. Unsurprisingly, the parameter we want to optimize is the size of the certificates, which is usually expressed as a function of n, the number of nodes in the network. For a given property P, the optimal size of the certificates can be seen in some sense as a measure on the locality of P: the smaller it is, the more local P is. We refer to the survey [START_REF] Feuilloley | Introduction to local certification[END_REF] for an introduction to certification.

As mentioned above, there are two kinds of locality in certification. In one case, the certificates are local, and the verification is local too; in the other case, the certificate is global, but the verification remains local. When speaking about local or global certification, we thus refer to the locality or globality of the certificate (and not of the verification, which is always local). In general, these two kinds of certification are somehow linked, because bounds for one can be derived from bounds for the other. Namely, a global certification scheme is a particular case of a local one, and conversely, a local certification scheme can be transformed into a global one by giving as global certificate the list of the local certificates of each node in the network (so that each node can simulate the local certification scheme by recovering its own local certificate from the global one, see [START_REF] Feuilloley | Local verification of global proofs[END_REF] for more details). However, these generic transformations are often not optimal.

In this work, the property we want to certify is the existence of a homomorphism to a given graph H. A particular case which has already been studied in [START_REF] Feuilloley | Local verification of global proofs[END_REF] is bipartiteness (it corresponds to the case where H is a clique on two vertices). Note that there exists a local certification scheme for bipartiteness using only one bit per vertex (where the certificate is the color in a proper two-coloring, and the verification of every node just consists in checking if it received a different color from all its neighbors). Here, we focus on global certification, and with a global certificate it is less clear how to certify it. Authors in [START_REF] Feuilloley | Local verification of global proofs[END_REF] made the following Conjecture 1 (which is also discussed in [START_REF] Feuilloley | Introduction to local certification[END_REF], see Open Problem 9), in the standard case where the range of identifiers is polynomial in n: Conjecture 1. The optimal size for global certification of bipartiteness is Θ(n log n).

In [START_REF] Feuilloley | Local verification of global proofs[END_REF], the authors proved upper and lower bounds, both parametrized by n (the number of vertices in the graph), and by the range of identifiers, denoted by M (n) (or simply M , keeping in mind that it is a function of n). More precisely, they proved the following: Theorem 2. Let s denote the optimal size for global certification of bipartiteness. Then, we have:

s = Ω(n + log log M ) and s = O(min{M, n log M })
In the standard case where M = n c for some constant c > 1, Conjecture 1 is equivalent as saying that the lower bound of Theorem 2 can be improved to match the upper bound. It would also mean that the generic transformation which turns a local certification scheme of size O(1) into a global one of size O(n log n) (where the global certificate is the list of the local certificates with each corresponding identifier), is optimal for bipartiteness.

In fact, we show that Conjecture 1 is false. Interestingly, it turns out that the lower bound of Theorem 2 is optimal, as stated in Theorem 3.

Theorem 3. There exists a global certification scheme for bipartiteness with a certificate of size O(n + log log M ).

Note that, in the standard case where M is polynomial in n, it gives a certificate of size Θ(n), which is better than the generic transformation from O(1)-local certificates to a O(n log n)-global one, corresponding to Conjecture 1. Note also that this bound remains Θ(n) even in the case where M = 2 2 O(n) (while the previous upper bound provided by Theorem 2 would be 2 O(n) in that case).

We actually prove a generalization of Theorem 3, in terms of graph homomorphisms. Remember that a homomorphism from a graph G to a graph H is a function ϕ : V (G) → V (H) such that, for every edge {u, v} ∈ E(G), we have {ϕ(u), ϕ(v)} ∈ E(H). Graph homomorphisms generalize graph colorings, since one can easily remark that a graph is k-colorable if and only if there exists a homomorphism from G to the clique on k vertices. For example, a graph is bipartite if and only if there is a homomorphism from G to an edge.

Our main result is then the following.

Theorem 4. Let H = (V ′ , E ′ ) be a graph. There exists a global certification scheme for the existence of a homomorphism to H with a certificate of size O(n log n ′ + log log M ) (where

n ′ = |V (H ′ )|).
Finally, let us give some intuition on the proof technique used to obtain the bound of Theorem 3 (which is the same as in Theorem 4 because it is just a particular case). As well as in the proof of the upper bounds of Theorem 2, the prover writes a proper two-coloring in the certificate. Then, each vertex recovers its own color and the colors of its neighbors, and checks if the coloring is locally correct. What differs is the way to encode this coloring. For the O(M ) bound, the prover gives as certificate a list of M bits, where the color of the vertex with identifier i ∈ {0, . . . , M -1} is the i-th bit of the list. For the O(n log M ) bound, the certificate is the following: for each identifier i appearing in the graph, the prover writes i (with O(log M ) bits) together with the color of the vertex having the identifier i. In the new upper bound of Theorem 3, the idea is to somehow compress the identifiers in the range {1, . . . , n}, and then use the same technique as for the O(M ) bound. The compression phase is performed using a known result of perfect hashing, stated in Theorem 7. This result have independently been used in [START_REF] Esperet | Optimal adjacency labels for subgraphs of cartesian products[END_REF] with another type of labeling, but to our knowledge, it is the first time that perfect hashing is used in distributed computing. We hope that this technique could have other applications in future works, in particular for problems related to space complexity.

Model and definitions

For completeness, let us remind some basic graph definitions. All the graphs we consider are finite, simple, and non-oriented. Let G = (V, E) be a graph. For every u ∈ V , we denote by N (u) the open neighborhood of u, which is set of vertices v ∈ V such that {u, v} ∈ E. A proper two-coloring of G is a function ϕ : V → {0, 1} such that, for every u ∈ V and v ∈ N (u), we have ϕ(u) = ϕ(v). We remind that a graph G is bipartite if and only if it has a proper two-coloring. Now, let us define formally the model of certification. Let M : N → N, called the identifier range (which is fixed: it is part of the framework for which certification schemes will be designed). Let n = |V |. In the following, we just write M instead of M (n) to have lighter notations. An identifier assignment of G is an injective mapping Id : V → {0, . . . , M -1}. Finally, let C be a set, called the set of certificates.

Definition 5. Let Id be an identifier assignment of G, and c ∈ C (called the global certificate). Let u ∈ V . The view of u consists in all the information available in its neighborhood, that is:

• its own identifier Id(u);

• the set of identifiers of its neighbors, which is {Id(v) | v ∈ N (u)};

• the global certificate c.

A verification algorithm is a function which takes as input the view of a vertex, and outputs a decision (accept or reject ).

Let P be a property on graphs. We say that there is a global certification scheme with size s(n) and identifier range M if there exists a verification algorithm A such that, for all n ∈ N, there exists set C of size 2 s(n) satisfying the following condition: for every graph G with n vertices, G satisfies P if and only if, for every identifier assignment Id with range M , there exists a certificate c ∈ C such that A accepts on every vertex.

A verification algorithm is just a function, with no more requirements. In particular, it does not have to be decidable. However, in practice, when designing a certification scheme to prove upper bounds, it turns out to be decidable and often computable in polynomial time. The fact that no assumptions are made on this verification function in the definition just strengthens the results when proving lower bounds, by showing that it does not come from computational limits.

Let us give a last definition, about perfect hashing.

Definition 6. Let k, ℓ ∈ N with k ℓ, and let H be a set of functions {0, . . . , ℓ -1} → {0, . . . , k -1}.

a) A function h ∈ H is a perfect hash function for S ⊆ {0, . . . , ℓ -1} if h(x) = h(y) for all x, y ∈ S, x = y.
b) The family of functions H is a (k, ℓ)-perfect hash family if, for every S ⊆ {0, . . . , ℓ -1} with |S| = k, there exists h ∈ H which is perfect for S.

Main result

Let us now prove our main result:

Theorem 4. Let H = (V ′ , E ′
) be a graph. There exists a global certification scheme for the existence of a homomorphism to H with a certificate of size O(n log n ′ + log log M ) (where

n ′ = |V (H ′ )|).
The key ingredient to prove Theorem 3 is the following Theorem 7 (see e.g. [START_REF] Mehlhorn | Data Structures and Algorithms 1: Sorting and Searching[END_REF] for a proof).

Theorem 7. Let k, ℓ ∈ N with k ℓ. There exists a (k, ℓ)-perfect hash family H k,ℓ which has size ⌈ke k log ℓ⌉.

Proof of Theorem 3. Let us describe a global certification scheme for the existence of a homomorphism to H using a certificate of size O(n log n ′ + log log M ) where n ′ = |V (H)|. First, since H has n ′ vertices, we can number them from 1 to n ′ and write the number of a vertex of H on log n ′ bits. Similarly, for every k, ℓ ∈ N with k ℓ, by applying Theorem 7, we can number the functions in H k,ℓ between 0 and |H k,ℓ | -1. Thus, a function of H k,ℓ can be represented using log |H k,ℓ | = O(k + log log ℓ) bits. Let G = (V, E) be a graph with |V | = n, for which there exists a homomorphism ϕ from G to H. Let Id be an identifier assignment of G. The certificate given by the prover is the following one. Let us denote by S := {Id(v) | v ∈ V } the set of identifiers appearing in G. The set S is included in {0, . . . , M -1} and has size n. Let h ∈ H n,M be a perfect hash function for S. By definition, the function h induces a bijection between S and {0, . . . , n -1}. Let L be the list of size n such that the i-th element of L, denoted by L[i], is equal to ϕ(v), where v is the unique vertex in V such that h(Id(v)) = i. The certificate given by the prover to the vertices is the triplet (n, h, L), where h is represented by its numbering in H n,M . Since it uses O(n log n ′ ) bits to represent L and O(n + log log M ) bits to represent h, the overall size of the certificate is O(n log n ′ + log log M ).

Let us describe the verification algorithm. Each vertex u does the following. First, it reads n in the global certificate and computes M . Then, it can determine h in H n,M thanks to its numbering in the certificate. Finally, u accepts if and only if, for all

v ∈ N (u), {L[h(Id(u))], L[h(Id(v))]} ∈ E ′ . If it is not the case, u rejects.
Let us prove the correctness. First, assume that G admits indeed a homomorphism to H. Then, by giving the certificate as described above, since ϕ is a homomorphism, each vertex u ∈ V accepts. Conversely, assume that every vertex accepts with some certificate c, and let us prove that there exists a homomorphism from G to H. Since all the vertices accept, every vertex u checked if {L[h(Id(u))], L[h(Id(v))]} ∈ E ′ for every v ∈ N (u), for some function h which is written in c. Note that nothing ensures that h is indeed a perfect hash function for the set S of identifiers, but in fact, it is not necessary to check that h is injective on S. Indeed, since every vertex u accepted, then for every v ∈ N (u), we have {L[h(Id(u))], L[h(Id(v))]} ∈ E ′ . So ϕ(u) := L[h(Id(u))] defines a homomorphism from G to H. Thus, it proves the correctness of the scheme.

Generalization : global certification of a Constraint Satisfaciton Problem

More generally, perfect hashing can be used to certify the existence of a solution to a Constraint Satisfaction Problem (abbreviated into CSP). A CSP consists in a set V of variables, a domain D of values for the variables, and a set C of constraints. We say that it admits a solution if there is a mapping from the variables to the domain satisfying all the constraints. For instance, k-colorability is a particular case of a CSP, where there is one variable x u for each vertex u, the domain is {0, . . . , k -1}, and the constraints are x u = x v for every edge {u, v}.

Using the same perfect hashing technique, we can design a global certification scheme in O(n log |D| + log log M ) for the existence of a solution for any CSP with n variables and domain D, such that the variables perform the verification, have identifiers, and each variable v knows the identifiers of all the variables w sharing a constraint with v.

Acknowledgments. The authors would like to thank William Kuszmaul for fruitful discussion on hashing.

The authors are supported by ANR project GrR (ANR-18-CE40-0032).