Pierre Pétroff

W and Z Production and Properties

Electroweak precision measurements performed by CDF and DØ are reported, corresponding to data collected at the center-of-mass energy of 1.96 TeV with the integrated luminosity ranging from 0.75 fb -1 to 4.9 fb -1 . These include the measurement of the W boson charge asymmetry, the measurement of the Z boson rapidity distribution, the measurement of the Z boson p T distribution, and direct measurement of the W boson mass and width.

Introduction

The study of the electroweak gauge bosons W and Z is an important part of the physics programs at the Tevatron. Their large production rates and clean experimental signatures in leptonic decay modes facilitate several important measurements, such as the determination of the electroweak parameters M W and Γ W and the extraction of the parton distribution functions of the proton.

These decay modes are characterized by a high transverse energy lepton p l T and large transverse missing energy E T for W , or by two high transverse energy leptons for Z.

Electrons are identified as an electromagnetic (EM) cluster using a simple cone algorithm. To reduce the background of jets faking electrons, electron candidates are required to have a large fraction of their energy deposited in the EM section of the calorimeter and pass energy isolation and shower shape requirements. Electron candidates are classified as tight if a track is matched spatially to EM cluster and if the track transverse momentum is close to the transverse energy of the EM cluster. In CDF [1], electrons are reconstructed both in the central calorimeter and plug calorimeter (|η| < 2.8) while electrons in DØ [2] are reconstructed in the central and endcaps calorimeters (|η| < 1.05 and 1.5 < |η| < 3.2). Here η = -ln tan(θ/2), and θ is the polar angle with respect to the proton direction. Both CDF and DØ require tight electrons in the central calorimeter (|η| < 1.05) for Z → e + e -candidates.

Muons are identified by a track in the muon system matched to a track in the central tracking system. For CDF the measurement in the muon channel includes the muons reconstructed in the central muon extension subdetector which extends the coverage from |η| < 0.6 to |η| < 1. For DØ the muon reconstruction is extended to the forward muon detector with a coverage up to |η| = 2.0. Muons from the decay of heavy-flavor hadrons are significant background to vector bosons production. It can be reduced by requiring that the muon is isolated. Cosmic ray muons contaminate the muon sample. Timing capabilities and distance of the muon track to the vertex are used to reduce the cosmic-ray muons background to low level.

We describe recent results from CDF and DØ collaborations. Two that constrain the parton distribution function (PDF) of the proton, the W boson charge asymmetry and the Z boson rapidity measurements, one that contrains the prediction of quantum chromodynamics (QCD), the Z boson p T distribution measurement and two precision measurements of the W boson mass and width.

W Boson Charge Asymmetry

Direct Measurement of W boson charge asymmetry provides new input on the momentum fraction dependence of the u and d quark parton distribution function within the proton.

As the u quark tends to carry a higher fraction of the proton's momentum than the d quark, the W + (W -) is boosted, on average, in the proton(anti-proton) direction.

The W ± charge asymmetry is defined as

A(y W ) = dσ(W + )/dy W -dσ(W -)/dy W dσ(W + /dy W ) + dσ(W -)/dy W
Measurements are typically performed using the charged leptons (e or µ) for the W boson decays. Since the longitudinal momentum of the neutrino is unmeasured, the asymmetry has been measured traditionally as

A(η l ) = dσ(l + )/dση l -dσ(l -)/dση l dσ(l + )/dση l + dσ(l -)/dση l
where η l is the lepton pseudorapidity. The lepton asymmetry, A(η l ) is the convolution of W ± production and V-A (vector-axial vector) decay asymmetries.

The DØ collaboration has recently published [5] results obtained from more than twice the integrated luminosity of previous measurements by the CDF [3] and DØ [4] collaborations and extend the measurement for electrons with |η| e < 3.2. By extending the higher rapidity electrons, more information is provided about PDFs for a broader x range (0.002 < x < 1.0 for

|y W | < 3.2) at high Q 2 ∼ M 2 W
, where Q 2 is the momentum transfer squared, x is the fraction of momentum of the proton carried by the parton and M W is the W boson mass. The integrated luminosity is 0.75 fb -1 . c 2010 by Universal Academy Press, Inc. The shaded band is the envelope determined using forty CTEQ6.1M PDF uncertainty sets, the solid (red) line is the CTEQ6.1M central value, and the dotted (blue) line is the charge asymmetry determined using MRST04 NLO PDFs.

The asymmetry measurement is sensitive to misidentification of the electron charge. The charge misidentification rate is measured with Z → ee events. The rate ranges from 0.2% at |η| ∼ 0 to 9% at |η| ∼ 3. The absolute uncertainty in the charge misidentification ranges from 0.1% to 2.6% depending on the electron rapidity and is dominated by the statistics of the Z boson sample. Assuming A(-η e ) = -A(η e ) due to CP invariance, data are folded to increase the available statistics. Fig. 1 shows the folded electron charge assymetry with theoretical predictions. These predictions are obtained using resbos event generator [6] (with gluon resummation at low boson p T and NLO perturbative QCD calculations at high boson p T ) with photos [7] (for QED final state radiation). The PDFs used to generate these predictions are the CTEQ6.6 NLO PDFs [8] and MRST04 NLO PDFs [9]. The asymmetric PDF uncertainty band is calculated using the formula described in Ref. [10].

The experimental uncertainties are smaller than the theoretical predictions across almost all electron pseudorapidities and these results can be used to improve the precision and accuracy of next generation PDF sets. Fig. 2 shows a new preliminary DØ measurement of the lepton charge asymmetry using W → µν from 4.9 fb -1 data sample. The measured asymmetry is compared to a theoretical prediction based on CTEQ6.6 PDF model [8]. The results can already improve constraints on PDFs, especially for 0.7 < |η µ | < 1.6. The charge asymmetry results presented above are made as a function of pseudorapidity of the leptons from W decay and the lepton charge asymmetry is a convolution of the W production charge asymmetry and the V-A asymmetry from W decays. These two asymmetries tend to cancel at large pseudorapidities (|η| > 2.0), and the convolution complicates the constraint on the proton PDFs. CDF has used a new analysis technics [11] to publish [12] the first direct measurement of the W production charge asymmetry in the W → eν decay channel with an integrated luminosity of 1.0 fb -1 . This method fully exploits the kinematic information in W events to directly reconstruct the underlying W boson production asymmetry. The W boson rapidity is ambiguous since the longitudinal momentum of the neutrino from its decay cannot be measured. However the neutrino momentum can be determined to a two-fold ambiguity by constraining the W boson mass.This ambiguity can be partly solved on a statistical basis from the known V-A decay distribution and the W ± production cross section as a function of y W and dσ/dy. Fig. 3 shows the measured asymmetry A(|y W |, which combines the positive and negative y W bins. The theroretical predictions at NNLO QCD calculation using the MRST2006 NNLO PDF sets [13] and a NLO QCD calculation using the CTEQ6.1 NLO PDF sets [14] are also shown. The CDF direct asymmetry measurement method indicates the possibility of a significant increase in sensitivity. In conclusion the charge asymmetry measurements from CDF and DØ collaborations will help to reduce the PDF uncertainty for high precision M W measurements and also improve the predictions for the Higgs boson production at the hadron colliders.

Z Boson Rapidity

Measurement of the differential boson production cross section over the full rapidity range provide stringent constraints on PDF parametrizations. The dilepton decay modes of the Z boson allow for precise measurements, since backgrounds in these final states are small, and the full event kinematics can be precisely reconstructed.

At leading order Z/γ * bosons are produced through the annihilation of a quark and an anti-quark, with the partons in the proton and anti-proton carrying momentum fractions x 1 and x 2 , respectively. The rapidity of the boson, defined as y = 1 2 ln E+p L E-p L , where E is the energy of the boson and p L is its longitudinal component, is directly related to the momentum fractions by

x 1,2 = M Z/γ * √ s e ±y .
Here, M Z/γ * is the mass of the boson, and √ s is the center of mass energy. The forward rapidity region |y| > 1.5 probes quarks with low x and high 4-momentum transfer squared

Q 2 (Q 2 ≈ M 2
Z ) as well as quarks with very large x.

CDF has made a measurement of the differential cross section 1/σ dσ dy , using 2.1 fb -1 of Z → ee data with |η| < 2.8. The total cross section, derived from integrating dσ/dy up to |y| < 2.8, is σ = 256.0 ± 0.7(stat) ± 2.0(syst) ± 15.1(lum) pb. The measured total cross section is consistent with both NLO and NNLO calculations. Fig. 4 shows the measured dσ/dy values, which are symmetric about y = 0. The results are compared to QCD predictions at NLO with CTEQ6.1M [15], MRST2001E [16] PDFs and at NNLO with MRST2006 [13] PDFs. Fig. 5 shows the ratios of the measured dσ/dy to theory calculated at NLO with CTEQ6.1M PDFs and at NNLO with MRST2006 PDFs. The experimental dσ/dy is larger than the theoretical prediction at large Fig. 4 The measured dσ/dy over the entire rapidity range. The points are the measured cross sections versus dy and the solid line is the theory prediction (scaled to the measured total cross section) for CTEQ6.1M NLO PDFs.The 6% uncertainty in the integrated luminosity is not included in the error bars.

Fig. 5 The ratio of experimental distribution of dσ/dy to the theoretical predictions for CTEQ6.1M(NLO), and MRST2006(NNLO) PDF models. The shaded band corresponds to the PDF's uncertainty obtained from CTEQ6.1M PDFs.

rapidities. Additional tuning of both NLO and NNLO PDF models may be needed.

Z Boson Transverse Momentum Study

Z boson production serves as an ideal testing ground for predictions of QCD at higher order calculations. A good understanding of electroweak vector boson production is important in precision measurement of W mass. The boson's transverse momentum, p Z T , can be measured over a wide range of values and can be correlated with its rapidity. At low p Z T the emission of multiple soft gluons is important and calculations in fixed order perturbative QCD diverge. A soft gluon emission resummation technique has been developed by Collins, Soper and Sterman (CSS) [17]. The resummation includes the BLNY [18] non-perturbative form factor that needs to be determined from data. The p Z T distribution at the Tevatron is sensitive to g 2 , one of the phenomenological parameters of the form factor and almost insensitive to g 1 and g 3 , the two other free parameters.

DØ has recently measured the g 2 parameter using dimuon and di-electron channels with 2 fb -1 . A novel technique has been used which allows to built an observable that is less sensitive to the resolution and more sensitive to the angular resolution, considering that collider detector generally have far better angular resolution than calorimeter or track transverse momentum resolution. The event axis (see Fig. 6) is defined as : t =

p 1 T -p 2 T | p 1 T -p 2 T |
where p i T is the transverse momentum vector of lepton i. The transverse momentum of the di-lepton system, p Z T is decomposed into component transverse to the axis t, a T = | p Z T × t|, and aligned with the axis, a L = p Z T • t. The a T observable which has previously been used at LEP by the OPAL collaboration [19] is almost insensitive to the transverse momentum resolution of the individual leptons [20] Fig. 7 Comparison of the di-muon data with MC simulation for a T Fig. 7 shows the a T distributions for di-muons events. Data are fitted to pythia [21] Monte Carlo templates weighted with resbos [6] using CTEQ6.6 [8] PDFs and photos [7] (for QED radiative corrections). Finally the combined measurement is: g 2 = 0.63 ± 0.02 ± 0.04 GeV 2 . The first uncertainty is experimental and the second uncertainty is due to PDF dependence of the theroretical prediction. This measurement is compatible with the world average: g 2 = 0.68 +0.02 -0.01 GeV 2 which does not include the PDFs uncertainty.

W Mass Measurement

A precision measurement of the W boson mass (M W ) is of the highest priority for the Tevatron experiments.

The W boson mass, combined with precise measurement of the top quark mass (M top ), constrains the mass of the Higgs boson. Self-energy corrections to the W boson depend on the masses of the top quark (∝ M 2 top ) and the Higgs boson (∝ ln M H ), as well as potential contributions from non-SM physics [22,23].

The combined CDF and DØ result [START_REF]CDF and DØ Collaborations (combined top mass result)[END_REF] on the top quark mass is 173.1 ± 1.3 GeV. The uncertainty corresponds to roughly a 0.75% measurement of M top . For equal contribution to the Higgs boson mass uncertainty, The W boson mass would need to be measured to about 0.01% corresponding to a total uncertainty of 8 MeV.

The current world-average measured value is M W = 80.399±0.025 GeV from a combination of measurements from ALEPH [START_REF] Schael | [END_REF], DELPHI [26], L3 [27], OPAL [28], CDF [29,30] and DØ [31] collaborations.

We will report here a more recent measurement of M W by the DØ collaboration [32] in the W → eν decay mode with an integrated luminosity of 1 fb -1 . This W mass is measured using three kinematic variables measured in the plane perpendicular to the beam direction: the transverse mass m T = 2p e T p ν T (1 -cos ∆φ), the lepton (p e T ) and neutrino (p ν T ) transverse momentum distributions, where ∆φ is the opening angle between the electron and neutrino momenta in the plane transverse to the beam. The magnitude and direction of p ν T is inferred from the missing transverse energy ( E T ).

In order to select W boson data with low background and well-understood charged electron and neutrino kinematics, p e

T and E T are required to be greater than 25 GeV, and recoil energy in the calorimeter is required to be less than 15 GeV. Moreover the electron is required to be in the central calorimeter with |η| < 1.05.

A sophisticated parametrized Monte Carlo simulation is used to predict the shape of the transverse mass distribution as well as the lepton and neutrino p T distributions as a function of M W . The W boson mass is extracted by fitting the M W prediction of the Monte Carlo simulation to the data with a binned maximum-likelihood fit.

The lineshape predictions depend on a number of physical and detector effects, which can be constrained either from control samples or calculation. Important physical effects include internal QED radiation, the intrinsic W boson transverse momentum, and the proton parton distribution functions (PDF). Electron efficiency, hadronic recoil modelling, calorimeter response both to electromagnetic shower and hadronic shower and calorimeter fiducial acceptance are among the most important detector effects.

The major steps of the W mass measurement will be explained by the following: Kinematics are simulated using the resbos [6] next-to-leading order generator which includes nonperturbative effects at low boson p T . These effects are parametrized by three constants (g 1 , g 2 and g 3 ) (as explained in Sec: 4.). Their values are taken from global fits to data [33]. The radiation of one or two photons is calculated using the photos [7] program.

Detector efficiencies, energy response and resolution for the electron and hadronic energy are applied to the resbos+photos events using a fast parametric Monte Carlo simulation (fastmc) developed for this analysis. The fastmc parameters are determined using a combination of detailed simulation and control data samples. The primary control sample used for both the electromagnetic and hadronic response tuning is Z → ee events. Since the Z boson mass and width are known with high precision from measurements [34] at the CERN e + e - collider (LEP), these values are used to calibrate the electromagnetic calorimeter response assuming a form E meas = α E true + β with α and β constants determined by calibration. The M W measurement presented here is effectively a measurement of the ratio of W and Z boson masses. Fig. 8 shows a comparison of the m ee distributions for data and fastmc, as well as the χ distribution defined as the difference between data and the fastmc prediction divided by the statistical uncertainty on the difference. Transverse recoil u T is defined as all particles recoiling against the W or Z bosons. A combination of events recorded in random beam crossings, with or without requiring hits in the luminosity counters and Z → ee data is performed to describe the behavior of the hadronic recoil. Then the hadronic response (resolution) is tuned using the mean (width) of the η imb distribution in Z → ee events in bin of p ee T . Here η imb is defined as the sum of the projections of the dielectrons momentum ( p ee T ) and recoil momentum ( u T ) in the transverse plane on the axis (η) bisecting the dielectron opening angle [35] (see Fig. 9). The backgrounds in the W boson sample are Fig. 9 Definition of η imb for Z → ee events, as first defined by UA2 [35]. The η unit vector is coincident with the bisector of the two electron directions in the transverse plane.

Z → ee events in which one electron escapes detection, multijet events (MJ) in which a jet is misidentified as an electron with E T arising from misreconstruction, and W → τ ν → eννν events. The backgrounds expressed as a fraction of the final sample are (0.90 ± 0.01)% from Z → ee, (1.49 ± 0.03)% from MJ, and (1.60 ± 0.02)% from W → τ ν → eννν.

The Z boson mass value from the final tuning fit is 91.185 ± 0.033 (stat) GeV, in agreement with the world average of 91.188 GeV used for the tuning. In Table 1 the results of the fit of the W mass are given together with the range of the fit and the χ 2 per degrees of freedom (dof). Fig. 10 shows the m T distributions for the data and the fastmc template with backgrounds and the binby-bin χ values defined as the difference between the data and the template divided by the data uncertainty. This fastmc template corresponds to the best M W fit. The uncertainties on the electron energy calibration and the hadronic recoil model are determined by simultaneously varying the parameters determined in the tuning to Z → ee events by one statistical standard deviation including correlation coefficients. The electron energy resolution systematic uncertainty is determined by varying resolution parameters determined in the fit to the width of the observed Z → ee m ee distribution. The shower modeling systematic uncertainties are determined by varying the amount of material representing the detector in the detailed simulation within the uncertainties found by comparing the electron showers in the simulation to those observed in data. The electron efficiency systematic is determined by varying the efficiency by one standard deviation. Table 2 also shows the M W uncertainties arising from variation of the background uncertainties indicated above. Among the production uncertainties, the parton distribution function (PDF) uncertainty is determined by generating W boson events with the pythia [21] program using the CTEQ6.1M [15] PDF set. The CTEQ prescription [36] is used to determine a one standard deviation uncertainty [12] on M W . The QED uncertainty is determined using wgrad [37] and zgrad [38], varying the photon-related parameters and assessing the variation in M W and by comparisons between these and photos. The boson p T uncertainty is determined by varying g 2 by its quoted uncertainty [33]. Variation of g 1 and g 3 has negligible impact. The quality of the simulation is indicated by the good χ 2 values computed for the difference between the data and fastmc shown in the figures. The data are also subdivided into statistically independent categories based on instantaneous luminosity, time, the total hadronic transverse energy in the event, the vector sum of the hadronic energy, and electron pseudorapidity range. The fit ranges are also varied. The results are stable too within the measurement uncertainty for each of these tests. The results from the three methods have combined statistical and systematic correlation coefficients of 0.83, 0.82, and 0.68 for (m T , p e T ), (m T , E T ), and (p e T , E T ) respectively. The correlation coefficients are determined using ensembles of simulated events. The results are combined [39] including these correlations to give the final result M W = 80.401 ± 0.021 (stat) ± 0.038 (syst) GeV = 80.401 ± 0.043 GeV.

The dominant uncertainties arise from the available statistics of the W → eν and Z → ee samples. Thus, this measurement can still be expected to improve as more data are analyzed.

The M W measurement reported here agrees with the world average and the individual measurements and is more precise than any other single measurement. This new direct measurement has been combined with the previous CDF and DØ measurements. The new Tevatron result for the W boson mass is: M W = 80.420 ± 0.031 GeV. For the first time the total uncertainty from the Tevatron is smaller that of 0.033 GeV from LEP [START_REF]The LEP Electroweak Working Group[END_REF].

Fig. 11 shows the W boson mass measurement at LEP and Tevatron experiments as well as the world average: M W = (80.399 ± 0.023) GeV. The result from the Tevatron corresponds to the value which includes corrections to the same W boson width and PDFs. The DØ value has been increased by one MeV to take into account these corrections. The updated world average impacts the global precision electroweak fits. By using this new world average only in the fit the Gfitter group [START_REF] Flächer | [END_REF] predicts that the Higgs mass is: m H = 42 +295 -166 GeV. It predicts at 2 σ intervals that the Higs mass is included in the interval [114,153] GeV with a global precision electroweak fit including the LEP and Tevatron direct limits.

With more statistics, both experiments CDF and DØ are looking forward in the very near future, to measuring the W boson mass with a precision of the order of 25 MeV per experiment.

W Boson Width Measurement

A precise measurement of width (Γ W ) provides a stringent test of SM prediction which is accurate to 2 MeV [START_REF] Rosner | [END_REF]. The first Run II published result [43] on Γ W has been presented by CDF with an integrated luminosity of .350 fb -1 . The W direct width measurement was determined to be Γ W = 2.032 ± 0.071 GeV by combining both the electron and muon decay channels. More recently DØ has performed a W direct width measurement with 1 fb -1 of data sample [44]. The measurement is performed in the eν channel.

The analysis is very similar to the W mass analysis. A Monte Carlo simulation is used to predict the m T distribution as a function of Γ W . Then these predictions are fitted to the data with a binned maximum-likelihood fit to extract Γ W . While the fit for M W is performed in the region around the peak of the distribution (65-90 GeV), the fit for Γ W is performed in the high m T tail region (90-200 GeV). This region is sensitive to the Breit-Wigner line-shape and less sensitive to the detector resolution. The modeling of the recoil is based on the recoil library obtained from Z → ee events. A Bayesian unsmearing procedure [45] allows the transformation of the two-dimensional distribution of reconstructed Z boson p T and the measured recoil momentum u T to one between the true Z boson p T and the measured recoil u T . For each simulated W → eν event with a generator-level transverse momentum value p T , we select u T randomly from the Z boson recoil library with the same value of p T . Details can be found in [46]. The uncertainty on the recoil system simulation from this method is dominated by the limited statistics of the Z boson sample; other systematic uncertainties originate from the modelling of photon radiative corrections, acceptance differences between W and Z boson events, underlying energy corrections beneath the electron cluster, residual efficiencyrelated correlations between the electron and the recoil system, and the unfolding procedure.

Previous M W and Γ W measurements have relied upon parameterizations of the recoil kinematics based on phenomenological models of the recoil and detector response. The library method used here includes the actual detector response for the hadronic recoil and also the complex correlations between different components of the hadronic recoil. It requires no first-principles description of the recoil system and has no adjustable parameters. Table 3 gives the detailed breakdown of the systematic uncertainties. We fit the m T data distribution to a set of templates at different assumed widths between a lower m T value and m T = 200 GeV. The lower m T cut is varied from 90 to GeV to test the stability of the fitted result. While the statistical uncertainty decreases as the lower m T cut is reduced, the systematic uncertainty increases. The lowest overall uncertainty is obtained for a lower m T cut of 100 GeV with Γ W = 2.028±0.039(stat)±0.061(syst) GeV. Fig. 12 shows the m T distributions for the data and the fastmc template with backgrounds and the bin-by-bin χ val- ues defined as the difference between the data and the template divided by the data uncertainty. This fastmc template corresponds to the best M W fit.

Fig. 12 The M T distributions for data and fast MC simulation with background added (top) and the χ values for each bin (bottom). The fitted Γ W value is used for the fast MC prediction. The distribution of the fast MC simulation with background added is normalized to the number of data events in the region 50 < M T < 100 GeV.

Conclusion

The analyses reported here are based on only a small fraction of the expected data. There is significant room for improving the precision of current measurement with around 10 fb -1 data sample expected at the completion of the Tevatron. Nevertheless, the large sample analysed up to now accommodate a wide variety of electroweak measurements. Future prospects in W mass measurement (≈ 25 MeV per experiment) will further constrain the Higgs mass.

Fig. 1

 1 Fig. 1 DØ folded electron charge asymmetry distribution. the horizontal bars show the statistical uncertainty and the full vertical lines show the total uncertainty on each point. The solid line is the theoretical prediction for the asymmetry using CTEQ6.6 NLO central PDF set. The dashed line shows the same prediction using the MRST04 NLO PDFs. The shaded band is the uncertainty band using CTEQ6.6 PDF uncertainty sets.

Fig. 2

 2 Fig. 2 DØ folded muon charge asymmetry distribution.The shaded band is the envelope determined using forty CTEQ6.1M PDF uncertainty sets, the solid (red) line is the CTEQ6.1M central value, and the dotted (blue) line is the charge asymmetry determined using MRST04 NLO PDFs.

Fig. 3

 3 Fig. 3 CDF direct measured asymmetry, A|y W | with prediction from NLO CTEQ6.1 (top) and NNLO MRST2006 (bottom) with their associated PDF uncertainties

Fig. 6 A

 6 Fig.6A schematic representation in the transverse plane, of the constructionof a T and a L in a typical leptonic Z decay

Fig. 8

 8 Fig. 8 (a) The dielectron invariant mass distribution in Z → ee data and from the fast simulation fastmc and (b) the χ values where χ i = [N i -(fastmc i )]/σ i for each point in the distribution, N i is the data yield in bin i and σ i is the statistical uncertainty in bin i.

Fig. 10

 10 Fig. 10 The m T distribution for DØ data and the fast simulation with backgrounds added (top), and χ value for each boin (bottom). The fit result is m W = 80.401 ± 0.023(stat) GeV.

Fig. 11

 11 Fig.11Summary of the measurements of the W boson mass and their average. The result from the Tevatron corresponds to the values which includes corrections to the same W boson width and PDFs. The LEP II results is from[START_REF]The LEP Electroweak Working Group[END_REF]. An estimate of the world average of the Tevatron and LEPP results assuming no correlations between the tevatron and LEP is included.

Table 1

 1 Results from the fits to data. The uncertainty is only the statistical component.

	Variable Fit Range (GeV)	MW (GeV)	chi 2 /dof
	mT p e T E T	65 < mT < 90 32 < p e T < 48 32 < E T < 48	80.401 ± 0.023 80.400 ± 0.027 80.402 ± 0.023	48/49 39/31 32/31

Table 2

 2 Systematic uncertainties of the M W measurement.

		∆MW (MeV)
	Source	mT p e T	E T
	Electron energy calibration	34	34	34
	Electron resolution model	2	2	3
	Electron shower modeling	4	6	7
	Electron energy loss model	4	4	4
	Hadronic recoil model	6	12	20
	Electron efficiencies	5	6	5
	Backgrounds	2	5	4
	Experimental Subtotal	35	37	41
	PDF	10	11	11
	QED	7	7	9
	Boson pT	2	5	2
	Production Subtotal	12	14	14
	Total	37	40	43

Table 3

 3 Systematic uncertainties on the measurement of Γ W .

	Source	∆ΓW (MeV)
	Electron energy scale	33
	Electron resolution model	10
	Recoil model	41
	Electron efficiencies	19
	Backgrounds	6
	PDF	20
	Electroweak radiative corrections	7
	pT	1
	MW	5
	Total Systematic	61

Acknowledgments

It is a pleasure to thank my CDF and DØ colleagues for the exciting and fruitful collaboration, and our Tevatron colleagues for the excellent luminosity. I also thank very warmly the organisers for the very nice and interesting XXIX PHYSICS IN COLLISION conference.


Salim Jouili
email: salim.jouili@loria.fr

Salvatore Tabbone
email: tabbone@loria.fr

Indexation de graphes à partir d'une structure d'hypergraphe 1

Keywords: graphe, clustering de graphes, indexation de graphes, recherche de graphes, hypergraphe Graph, graph clustering, graph indexing, graph retrieval, hypergraph. 1. Ce travail est partiellement

Dans ce papier, nous proposons une nouvelle méthode de clustering de graphes basée sur une modélisation d'hypergraphe. En premier lieu, nous appliquons un algorithme de sélection de prototype dédié aux bases de graphes où le nombre de prototype à sélectionner est déduit automatiquement. En second lieu, nous définissons une méthode de chevauchement des classes pour aboutir à la structure d'hypergraphe, où les hyperarcs sont les classes et les noeuds sont les graphes. Ainsi, un graphe peut être attribué à une ou plusieurs classes. L'originalité de notre approche réside dans la structure d'hypergraphe qui nous permet d'indexer une base de graphes à partir des centroïdes des hyperarcs. En plus, cette nouvelle approche permet de rechercher des graphes similaires à une requête et de naviguer dans une base de graphes en parcourant la structure d'hypergraphe.

ABSTRACT. In this paper, we propose a new hypergraph-based method for graph clustering. For this aim, we introduce firstly a prototype selection algorithm dealing with graphs where the number of clusters is automatically detected. Then, we define a clusters overlapping method to build our hypergraph-based model. Therefore, in this representation one graph can be assigned to more than one cluster. The originality of our contribution lies in the hypergraph structure which allows the indexing of the graph database using the centroids of the hyperedges. In addition, this model is interesting to travel the data set and efficient to cluster and retrieve graphs.

Introduction

Récemment, nous pouvons constater à nouveau un engouement pour la représentation des objets par des graphes car les graphes offrent des alternatives polyvalentes aux vecteurs caractéristiques dans les domaines de reconnaissance des formes [START_REF] Jouili | Applications des graphes en traitement d'images[END_REF], l'apprentissage automatique et la recherche d'images [START_REF] Shokoufandeh | A Unified Framework for Indexing and Matching Hierarchical Shape Structures[END_REF]. Les graphes sont beaucoup plus puissants en termes de représentation et plus flexibles que les vecteurs caractéristiques qui ne fournissent aucune possibilité directe de décrire les relations structurelles pour les objets en considération. En outre, alors que la taille d'un graphe peut être ajustée à la taille de l'objet, un vecteur est limité à une taille prédéfinie, qui doit être préservée pour tous les objets rencontrés dans une application particulière. Cependant, deux inconvénients majeurs des représentations sous forme de graphes sont leurs manque de méthodes appropriées pour les organiser en cluster dans l'optique d'y accéder efficacement (indexation) et la complexité élevée de l'appariemment des graphes. Par conséquent, ces inconvénient limitent l'utilisation des graphes dans des domaines comme la recherche d'image par le contenu où il s'agit d'explorer de grande bases d'images. Notant que la phase d'appariemment des graphes augmente radicalement la complexité (voir [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF])) de tout système de recherche. Alors pour réduire le nombre d'opérations d'appariemment, une organisation de la base des graphes sous forme de clusters est généralement requise. De cette façon, pour regrouper les images similaires dans une base, il suffit de regrouper leurs représentations sous formes de graphes. Dans ce contexte, il est naturel d'appliquer une technique de clustering aux bases de graphes. Dans la littérature, le clustering de grandes bases de graphes est resté largement inexploré et est parmi les problèmes les plus ouverts dans la reconnaissance des formes utilisant des approches structurelles.

Durant les dernières années quelques investigations sur le clustering et l'organisation des bases de graphes ont été revitalisées dans [START_REF] Bunke | Graph Clustering Using the Weighted Minimum Common Supergraph[END_REF][START_REF] Hlaoui | A graph clustering algorithm with applications to content-based image retrieval[END_REF][START_REF] Luo | Spectral feature vectors for graph clustering[END_REF][START_REF] Shokoufandeh | A Unified Framework for Indexing and Matching Hierarchical Shape Structures[END_REF] et l'approche que nous préconisons dans ce papier est différente. Nous proposons un modèle basé sur la structure d'hypergraphe pour regrouper un ensemble de graphes. Récemment, l'hypergraphe a été utilisé, dans le domaine de la reconnaissance des formes, pour la représentation des objets [START_REF] Ren | Spectral Embedding of Feature Hypergraphs[END_REF], les mesures de similarité [START_REF] Bunke | Matching of Hypergraphs -Algorithms, Applications, and Experiments[END_REF], et le clustering des objets [START_REF] Agarwal | Beyond Pairwise Clustering[END_REF]. Dans ce papier, nous établissons un modèle d'hypergraphe pour représenter une base de graphes. Nous avons procédé comme suit : premièrement, une technique de clustering basée sur la sélection de prototype est proposée pour regrouper les graphes en k clusters indépendants (k est définit automatiquement à l'aide d'un certain seuil). Deuxièmement, ces clusters sont organisés de telle façon qu'ils se recouvrent partiellement pour définir la structure d'hypergraphe finale. L'idée de chevauchement des clusters est dans la même veine que les travaux de [START_REF] Bezdek | Fuzzy Models and Algorithms for Pattern Recognition and Image Processing[END_REF][START_REF] Torsello | Beyond partitions : Allowing overlapping groups in pairwise clustering[END_REF] mais la représentation est différente ici. Enfin, à partir d'une série d'expériences, nous avons remarqué que la structure d'hypergraphe fournit aussi un cadre pour rechercher un graphe dans une base de graphes et la parcourir. Ces experimentations affichent également des taux élevés de clustering et montrent une amélioration de la performance de la recherche.

La notion d'hypergraphe

Les hypergraphes sont des objets mathématiques généralisant la notion de graphes où les arêtes peuvent connecter n'importe quel nombre de sommets. L'hypergraphe a été défini par Berge [START_REF] Berge | Graphes et Hypergraphes[END_REF] comme suit, soit H = (ϑ,ξ) un hypergraphe, où :

-ϑ={x 1 ,x 2 , x 3 ... , x n } : est un ensemble fini de sommets -ξ={E 1 , E 2 , E 3 ... , E m } : est une famille de sous-ensembles de ϑ.

-E j = ∅, j=1,...,m E j =ϑ. Dans un hypergraphe, deux sommets x i et x j sont dits adjacents s'il existe une hyperarc E k , qui contient les deux sommets (x i ∈ E k , x j ∈ E k ). Deux hyperarcs E i et E j sont dits adjacents si leur intersection n'est pas vide. Tout hypergraphe a une matrice d'incidence A j i de taille mxn avec m colonnes représentant les hyperarcs et les n lignes représentant les sommets. Les éléments dans A indiquent l'appartenance de sommets aux hyperarcs comme suit :

A j i = 1 if x i ∈ E j 0 if x i / ∈ E j
Par exemple, considerons l'hypergraphe H=(ϑ, ξ) dans la figure 1 x1 1 0 0 0 0 0 x2 1 0 0 0 0 0 x3 1 0 0 0 0 1 x4 1 1 0 0 0 0 x5 0 1 0 0 1 0 x6 0 1 1 0 0 0 x7 0 1 1 0 0 0 x8 0 0 1 0 0 0 x9 0 0 1 0 0 0 x10 0 0 0 1 0 0 x11 0 0 0 0 1 0 x12 0 0 0 0 0 1 x13 0 0 0 0 0 1

E 1 E 2 E 3 E 4 E 5 E 6

Figure 1. Exemple d'un hypergraphe et sa matrice d'incidence

considéré comme un problème NP-complet et nécessite un temps et un espace exponentiels pour trouver la solution optimale [START_REF] Bunke | Recent Developments in Graph Matching[END_REF]. Toutefois, pour surmonter ce problème de nombreuses approches ont été proposées pour approcher la distance d'édition des graphes. Nous renvoyons le lecteur intéressé à l'état de l'art de [START_REF] Conte | Thirty years of graph matching in pattern recognition[END_REF]. Dans ce papier, nous avons utilisé un travail précédent sur l'appriement des graphes (Jouili et al., 2009a) dont le calcul des mesures de dissimilarité entre graphes repose sur trois étapes :

-l'extraction d'une signature locale en chacun des noeuds du graphe ; -le calcul d'une matrice des distances entre chaque couple de noeuds dans les deux graphes à comparer ; -le calcul de la mesure de dissimilarité entre les deux graphes à comparer, basée sur la matrice de dissimilarités entre les noeuds précédemment extraite.

Extraction des signatures de noeuds

La signature associée à chacun des noeuds du graphe est un vecteur calculé directement depuis la matrice d'adjacence du graphe. Notons V l'ensemble des noeuds du graphe ; la signature du noeud n i est :

S(n i ) = {a i , d 0 (n i ), {a ij } ∀nj∈V } où a i est le vecteur d'attributs du noeud n i , d 0 (n i ) donne le degré de n i , et {a ij } ∀nj∈V est l'
ensemble des vecteurs d'attributs des arêtes reliant le noeud n i à l'ensemble des autres noeuds n j du graphe.

Cette méthode est générique et peut s'appliquer à tous types de graphes (e.g. attribué, pondéré ...).

Calcul de la matrice de distances entre noeuds

Puisque les signatures peuvent contenir des éléments de différents types (numériques et/ou symboliques), la plupart des distances usuelles (eg. les distances L 1 ou L 2 dédiées à des attributs numériques ou la distance overlap pour des attributs symboliques) ne peuvent être utilisées. Parmi l'ensemble des métriques proposées par Wilson et al. dans (Wilson et al., 1997) et permettant de traiter à la fois des données numériques et symboliques, nous avons choisi d'utiliser la distance Heterogeneous Euclidean Overlap Metric (HEOM) comme dans (Jouili et al., 2009a). La raison de ce choix est qu'à la différence des distances basées sur des métriques de différences de valeurs, comme par exemple la Heterogeneous Value Difference Metric, la distance HEOM est indépendante du contexte d'étude et peut être utilisée dans un cadre plus général que celui de la classification. La distance HEOM utilise la distance overlap pour des données symboliques et une distance Euclidienne normalisée pour les attributs numériques. La normalisation permet d'obtenir des distances comprises entre 0 et 1.

Calcul de la dissimilarité entre graphes

Dans un premier temps, la dissimilarité entre deux graphes est exprimée par une matrice de distance HEOM entre les noeuds des graphes à comparer pris deux à deux. À partir de cette matrice on cherche à extraire une mesure de dissimilarité scalaire entre les deux graphes. La méthode utilisée dans (Jouili et al., 2009a) est l'algorithme Hungarian [START_REF] Kuhn | The Hungarian Method for the assignment problem[END_REF] de complexité O(n 3 ), où n est la taille du plus grand des deux graphes à comparer. Cet algorithme permet d'obtenir une matrice de permutation P définissant la fonction M de mise en correspondance optimale entre les noeuds des deux graphes :

M (n (g1) i ) = n (g2) j si P ij = 1 0 sinon où n (g1) i et n (g2) j
sont respectivement les noeuds n i et n j des deux graphes g 1 et g 2 à comparer.

La dissimilarité entre les deux graphes peut alors être calculée comme suit :

d(g 1 , g 2 ) = M |M | + |g 1 | -|g 2 |
oû |M | est la taille de la fonction de mise en correspondance M (ie. la taille du plus petit des deux graphes à comparer) et M est le coût de mise en correspondance, défini comme étant M = i=1,...N1 HEOM (n

(g1) i , M (n (g1) i
)) où N 1 est le nombre total de noeuds du graphe g 1 .

Un exemple concret de calcul de la dissimilarité entre deux graphes est donné dans (Jouili et al., 2009a).

Modélisation par hypergraphe

En se basant sur la proprieté d'hypergraphe, l'idée est de représenter une clustering de graphes par un hypergraphe où les sommets correspondent à des graphes et les hyperarcs à des clusters.

Dans ce papier, un graphe peut appartenir à plusieurs hyperarcs (clusters) simultanément. Par conséquent, chaque graphe G i dans la structure proposée est assigné à ∆ ϑ (G i ) groupes et chaque cluster C j contient ∆ ξ (C j ) graphes. Cependant, deux problèmes clés se posent dans la structuration d'un ensemble de graphes avec un modèle d'hypergraphe, la détermination du nombre de clusters (hyperarcs) et la détermination de graphes connexes (graphes similaires) qui peuvent être regroupés dans un hyperarc. Dans cette perspective, nous considérons que le nombre d'hyperarcs est égale à la taille d'un ensemble représentatif, définie sur une sélection de graphes les plus représentatifs de l'ensemble. On note chaque graphe sélectionné comme le centroïde d'un hyperarc. La sélection de ces graphes est similaire au problème de la sélection de prototypes [START_REF] Babu | Comparaison of genetic algorithm based prototype selection schemes[END_REF][START_REF] Riesen | Graph Embedding in Vector Spaces by Means of Prototype Selection[END_REF][START_REF] Spath | Cluster Analysis Algorithms for Data Reduction and Classification of Objects[END_REF]. K. Riesen et al. [START_REF] Riesen | Graph Embedding in Vector Spaces by Means of Prototype Selection[END_REF] énumèrent quelques techniques de sélection de prototypes à partir d'un ensemble d'apprentissage. Ces techniques nécessitent de préciser le nombre de prototypes et il n'y a pas de règles pour déterminer automatiquement ce nombre. Par conséquent, si nous nous situons dans un contexte non supervisé, où aucune information sur le nombre de graphes représentatifs est disponible, ce nombre ne sera déterminé que d'une manière empirique. Dans cette perspective, Spath [START_REF] Spath | Cluster Analysis Algorithms for Data Reduction and Classification of Objects[END_REF] propose un algorithme utilisant les "leaders" et un seuil où le nombre de prototypes sélectionné est inversement proportionnel à la valeur du seuil sélectionné. Cependant, l'algorithme de Leader [START_REF] Spath | Cluster Analysis Algorithms for Data Reduction and Classification of Objects[END_REF] est sensible à la sélection du premier prototype qui est choisi au hasard parmi les données en entrée. Pour surmonter ce problème, nous introduisons une technique de sélection de graphes représentatifs (centroïdes des hyperarcs) fondée sur une stratégie de pelure d'oignon. Cette méthode peut être considérée comme une amélioration de l'algorithme du Leader et de l'algorithme de K-Centres [START_REF] Riesen | Graph Embedding in Vector Spaces by Means of Prototype Selection[END_REF]. Après la sélection des centroïdes des hyperarcs, nous définissons la structure d'hypergraphe en attribuant chaque graphe aux hyperarcs correspondants.

Sélection de centroïdes des hyperarcs.

Comme indiqué ci-dessus, la sélection des centroïdes des hyperarcs est similaire au problème de sélection de prototypes. Par conséquent, notre objectif est de sélectionner un sous-ensemble de graphes qui captent les aspects les plus significatifs d'un ensemble de graphes. Nous introduisons une amélioration de l'algorithme du Leader [START_REF] Spath | Cluster Analysis Algorithms for Data Reduction and Classification of Objects[END_REF]. L'algorithme proposé procède comme suit : 1) Sélectionner le graphe médian ( à partir d'une technique classique [START_REF] Jiang | On median graphs :properties, algorithms, and applications[END_REF]) G m des graphes non affectés de l'ensemble initial des graphes S. Puis choisir le graphe le plus distant G p k , en fonction d'une mesure de distance choisie, (qui n'a pas été préalablement affecté) de G m , et affecter ce graphe au cluster C k comme centroïde.

Dans la première itération, le graphe G p k est le prototype sélectionné initialement.

2) Comparer les distances de tout les graphes non affectés g i ∈ S {G p k } à celle du dernier prototype sélectionné G p k . Si les distances d(g i , G p k ) et d(g i , g j ∈C k ) sont inférieures à un seuil prédéfini T que nous définissons de manière automatique en fonction de nos données (voir §3), le graphe g i est affecté au cluster C k avec le centroïde G p k et g i est étiquetté et affecté.

3

) Recalculer le graphe médian G m k de C k , si G m k = G p k , remplacer G p k par G m k . Si aucun remplacement n'est fait (G m k = G p k )
, passez à l'étape suivante, sinon tous les g j ∈ C k sont marqués comme non affectés, puis revenez à l'étape 2.

4) Si S contient encore des graphes non-affectés revenir à l'étape 1, sinon arrêter.

Une première amélioration consiste à une adaptation de l'algorithme du Leader dans l'espace de graphes en utilisant la notion de graphe médian. Ensuite, une nouvelle méthode de sélection du premier prototype a été mise au point. Dans l'algorithme du Leader, le choix du prototype initial est fait par hasard ce qui influe sur le résultat final du clustering (i.e. à chaque exécution les résultats changent). Nous avons choisi, de fixer comme prototype initial de l'algorithme le graphe le plus éloigné du médian de la base. Ce choix garanti, par conséquent, la stabilité des résultats. Une deuxième amélioration consiste à ajouter une méthode itérative de sélection de prototype. En fait, comme il est indiqué dans le pseudo-code de l'algorithme, dès que le prototype initial est sélectionné nous considérons tous les graphes qui ont une distance au prototype inférieure ou égal à un seuil donné et la distance entre chaque couple de graphes de ce sous-ensemble doit être aussi inférieure ou égal au même seuil. En revanche, dans l'algorithme du Leader, on ne considère que les distances entre le prototype et chaque objets (il n'y a pas de critère sur les distances entre les objets). Une fois le sous-ensemble construit on recalcule le nouveau graphe médian et on itère jusqu'à convergence vers un graphe médian prototype considéré comme un centroïde.

Compte tenu d'un seuil T, l'algorithme ci-dessus regroupe l'ensemble des graphes avec une inertie intra-classe (I i ) inférieure ou égale à T. Cette propriété est conservée dans l'étape 2. En plus, cet algorithme garantit : 1) la sélection des prototypes qui sont les centroïdes des clusters ; 2) une certaine séparabilité entre classes d'une partition. En outre, en fixant le prototype initial comme le graphe le plus distant du graphe médian dans l'ensemble des graphes, l'algorithme produit des résultats identiques et est déterministe. Nous notons cet algorithme de clustering par D-hypergraphe pour hypergraphe déconnecté.

La représentation sous forme d'hypergraphe.

Soit S un ensemble de graphes et P l'ensemble de prototypes sélectionnés P (P⊂S). Les techniques de clustering classique cherchent pour chaque graphe g∈ S P son plus proche voisin p i ∈ P et ajoutent le graphe dans le cluster C i correspondant au prototype p i . En fait, si un graphe g présente une distance similaire à deux prototypes p i et p j , g est ajouté au cluster avec le prototype le plus proche même si la différence et al., 2005[START_REF] Sebastian | Shock-Based Indexing into Large Shape Databases[END_REF][START_REF] Sengupta | Organizing large structural modelbases[END_REF][START_REF] Shapiro | Organization of Relational Models for Scene Analysis[END_REF], mais il sera difficile de trouver un algorithme pour naviguer dans l'ensemble de la base de graphes.

Au contraire, nous proposons un modèle basé sur l'hypergraphe qui permet le chevauchement des clusters. Désormais, les clusters seront considérés comme des hyperarcs d'hypergraphe et les graphes comme les sommets. Tout d'abord, pour chaque prototype p i un hyperarc h i est défini avec un centroïde p i . Deuxièmement, chaque hyperarc est défini comme suit : chaque graphe g∈ S P est ajouté aux hyperarcs avec les prototypes proche de g (leurs distances à g est inférieur au seuil T utilisé dans l'algorithme précédent). Nous désignions cette procédure par C-hypergraphe (hypergraphe connecté).

La figure 2 illustre notre motivation, soit d i = d(p i , g 1 ), nous supposons que d 1 et d 2 sont inférieures ou égales à un seuil T, alors le graphe g 1 partage quelques informations avec p 1 et p 2 (les informations sont illustrées en couleur). Avec le modèle d'hypergraphe nous serons en mesure d'affecter g 1 à la fois aux hyperarcs h 1 et h 2 . La partie la plus à droite de la figure 2 décrit comment deux hyperarcs (clusters) peuvent se chevaucher avec un graphe en commun. Ici, ∆ ϑ (g 1 )=2 et ∆ ξ (h 1 )=∆ ξ (h 2 )=2.

Une fois que tout les hyperarcs sont définis à partir des graphes, on recalcule, pour chaque hyperarc, le graphe médian généralisé qui sera le nouveau centroïde de l'hyperarc. L'objectif de cette étape est de mettre à jour le centroïde de l'hyperarc et de maintenir autant d'informations que possible des graphes dans le hyperarc correspondant. Nous avons utilisé le graphe médian généralisé pour définir le centroïde d'un cluster car contrairement au supergraphe minimum et commun [START_REF] Bunke | Graph Clustering Using the Weighted Minimum Common Supergraph[END_REF] il est moins coûteux en temps de calcul.

Figure 3. Illustration de l'interface développée pour la navigation dans une base de graphes

Interrogation et Navigation d'une base de graphe à partir du modèle d'hypergraphe.

Classiquement, l'interrogation d'un ensemble de graphes consiste à rechercher les graphes les plus semblable à une requête donnée. Cette tâche de recherche trie les distances entre la requête et les graphes de la base dans un ordre croissant. Comme il est déjà indiqué dans la littérature [START_REF] Robles-Kelly | Graph Edit Distance from Spectral Seriation[END_REF][START_REF] Sebastian | Shock-Based Indexing into Large Shape Databases[END_REF][START_REF] Sengupta | Organizing large structural modelbases[END_REF][START_REF] Shapiro | Organization of Relational Models for Scene Analysis[END_REF], cette méthode n'exploite pas efficacement la distribution des distances, et les auteurs proposent des techniques basées sur le clustering pour améliorer les résultats de recherche. Dans ce travail, nous introduisons une procédure qui implique le modèle de l'hypergraphe proposé précédemment. L'idée principale est de trouver le centroïde (parmi tous les centroïdes des hyperarcs) le plus proche à une requête donnée. Puis, nous recherchons les graphes les plus similaires au sein de l'hyperarc. Nous décrivons la procédure de recherche dans le modèle de l'hypergraphe comme suit : 1) Pour un graphe de requête g q , calculer l'ensemble des distances entre g q et le centroïde de chaque hyperarc.

2) Déterminer le plus proche centroïde p i à g q .

3) Récupérer les graphes les plus similaires g j à g q , où g j ∈ h i et h i est le hyperarc avec le centroïde p i .

Ce modèle basé sur l'hypergraphe peut être exploité pour naviguer à travers l'hypergraphe. Une fois la procédure précédente effectuée, l'utilisateur peut parcourir l'ensemble des graphes, à travers une interface graphique. Dans la figure 3 les clusters (hyperarcs) sont représentés par des ellipses qui se chevauchent. Dans cette figure, l'utilisateur a sélectionné la lettrine avec la lettre D et, en cliquant sur les lettrines voisines, a pu explorer une partie de la base liée à sa requête. Les images au centre de chaque hyperarc sont les centroïdes.

Expérimentations

Dans cette partie nous évaluons d'un côté la qualité du clustering à partir de trois bases d'images ( §3.1) et de l'autre l'efficacité du modèle proposé pour la recherche de graphes ( §3.2).

L'évaluation de clustering

Dans cette première partie des expérimentations, nous effectuons des tests de clustering de graphes. Ici, nous évaluons les deux algorithmes proposés. Le premier est le clustering basé sur la sélection de prototypes, sans connexion des hyperacs dans l'hypergraphe, notée D-hypergraphe. Le second permet le chevauchement des hyperarcs, noté C-hypergraphe. Nous avons établi une comparaison avec l'algorithme de K-means sur trois bases d'images (voir figure 4). La première est la base d'images COIL [START_REF] Nene | Columbia Object Image Library (COIL-100)[END_REF] qui contient différents vues d'objets 3D. Les images de COIL sont converties en graphes par extraction des points d'intérêt en utilisant l'algorithme de Harris [START_REF] Harris | A Combined Corner and Edge Detection[END_REF] et la triangulation de Delaunay. La seconde est la base GREC 1 [START_REF] Riesen | IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[END_REF] qui se compose de symboles issus de plans architecturaux et électroniques. Ici, les points finaux (les coins, les intersections et les cercles) sont représentés par des noeuds dans le graphe qui sont reliés par des arêtes non orientés et étiquetés comme des lignes ou des arcs. Enfin, nous avons effectué l'évaluation du clustering sur une base de lettres ornementales qui contient des Lettrines (objet graphique) extraites de documents anciens numérisés 2 . Puisqu'une Lettrine contient beaucoup d'informations (i.e la texture, décor de fond, lettres), les graphes sont extraits suite à une segmentation en régions [START_REF] Felzenszwalb | Efficient Graph-Based Image Segmentation[END_REF] de la Lettrine. Les noeuds du graphe sont représentés par les régions et les arcs décrivent leurs relations d'adjacence. La mesure de distance entre les graphes utilisé est l'appariemment de graphes basé sur les signatures de noeuds (Jouili et al., 2009a, Jouili et al., 2009b). Les résultats du clustering sont évalués par l'indice de Rand [START_REF]Objective criteria for the evaluation of clustering methods[END_REF], l'indice de Dunn [START_REF] Dunn | Well separated clusters and optimal fuzzy-partitions[END_REF] et l'indice de [START_REF] Davies | Pattern Analysis and Machine Intelligence[END_REF].

L'indice de Rand mesure à quel point les groupes crées par l'algorithme de clustering correspondent à la vérité terrain. Pour calculer l'indice de Rand, nous considérons toutes les paires de graphes (g i , g i ) avec g i =g j . Soit N 11 le nombre de paires (g i , g i ) appartenant à la même classe (dans la vérité terrain) et au même cluster (dans la clustering). Soit N 00 le nombre de paires (g i , g i ) n'appartenant ni à la même classe (dans la vérité terrain) et ni au même cluster (dans la clustering), soit N 10 le nombre de paires (g i , g i ) appartenant à la même classe (dans la vérité terrain) mais pas au même cluster (dans la clustering) et soit N 01 est le nombre de paires (g i , g i ) appartenant au même cluster (dans la clustering) mais pas à la même classe (dans la vérité terrain), L'indice de Rand s'écrit : La table 1 montre les résultats des trois indices de validation du clustering. A partir de ces résultats, il est clair que notre méthode d'hypergraphe déconnecté produit des clusters plus compactes et bien séparées. Nous remarquons que lorsque l'algorithme du C-hypergraphe est appliqué, l'indice de Dunn prend la valeur 0, parce que certains clusters partagent des graphes et la distance minimale entre les clusters devient nulle. En outre, d'un point de vue de similitude avec la vérité terrain, notre modèle donne de meilleurs résultats pour les bases GREC et Lettrines, et nous pouvons également remarquer que les indices de Rand produis par l'algorithme du C-hypergraphe pour les trois bases de données sont plus élevés que ceux du D-hypergraphe. Par conséquent, l'hypergraphe connecté s'adapte mieux à la vérité terrain et nous encourage à exploiter la structure de l'hypergraphe pour le problème de la recherche de graphes.

Évaluation de la recherche avec le modèle de l'hypergraphe.

Dans cette partie, nous évaluons la recherche à partir du modèle de l'hypergraphe en exécutant l'algorithme détaillé précédemment ( §2.3) sur la base des lettres ornementales. Nous fournissons une comparaison avec une recherche classique dans laquelle la requête est comparée à tous les graphes dans la base de données, en triant les distances du plus similaire au moins similaires. Dans l'approche proposée, les centroïdes des hyperarcs sont les entrées (l'index) de la base de graphes. Plus précisemment, tout d'abord le graphe requête n'est comparé qu'aux centroïdes des hyperacs. Puis, la recherche est effectuée parmi les graphes qui appartiennent à l'hyperarc avec le plus proche centroïde à la requête. Nous avons utilisé la courbe Précision 3 -Rappel 4 pour visualiser les performances de la recherche. Ces courbes sont formées par le taux de précision par rapport au taux de rappel (voir figure 5). En analysant les deux courbes, on peut remarquer que les résultats sont meilleurs lorsque la recherche est effectuée dans un seul hyperarc. En outre, le modèle de l'hypergraphe est plus rapide que la technique classique car il ne compare pas la requête avec tous les graphes dans la base mais seulement avec des graphes dans un cluster approprié. La figure 6

Conclusion

Dans ce papier, nous avons étudié comment la structure d'hypergraphe peut être utilisée à des fins de représentation de base de graphes. Nous avons proposé une mé-3. Précision : rapport du nombre de documents pertinents trouvés au nombre total de documents sélectionnés. 4. Rappel : rapport du nombre de documents pertinents trouvés au nombre total de documents pertinents

ϑ

  est appelé l'ensemble des sommets, ξ est l'ensemble des hyperacs et |ϑ| est le cardinal de H. Dans la figure 1(a), un hyperarc E i est représenté par une ligne entourant ses sommets si |E i | ≥2 (par exemple E 1 dans la figure 1(a)), par une boucle sur l'élément si |E i |=1(E 4 dans figure 1(a)), et par une ligne reliant les deux éléments si |E i |=2 (E 5 dans figure 1(a)). Si |E i |=2 pour tout les i, l'hypergraphe devient un graphe non orienté ordinaire.

Figure 2 .

 2 Figure 2. Illustration du modèle proposé

Figure 4 .

 4 Figure 4. Exemples des bases d'images utilisée pour les expérimentations : (a) Lettrine, (b) GREC, (c) COIL.

Figure 5 .

 5 Figure 5. Les courbes Précision-Rappel : comparaison entre la recherche classique et la recherche basée sur le modèle proposé

Figure 6 .

 6 Figure 6. Nombre de comparaisons effectuées lors de la recherche d'images

(a), ϑ={x 1 ,x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 , x 9 , x 10 , x 11 , x 12 , x 13 } et ξ={ E 1 , E 2 , E 3 , E 4 , E 5 , E 6 }. La cardinalité de H est |ϑ|= 13, et la matrice d'incidence est définie dans dans la figure 1(b). Le degré d'un sommet, noté ∆ ϑ , est le nombre d'hyperarcs auquel il appartient, et le degré d'un hyperarc, noté ∆ ξ (h), est le nombre de sommets qu'il contient.

	Nous pouvons noter que la différence entre une arête dans un graphe et un hyperarc
	dans un hypergraphe est que le premier est toujours un sous-ensemble d'un ou deux
	sommets, et dans le second, le sous-ensemble de sommets peut être de cardinalité
	arbitraire.
	1.2

. Appariemment de graphes

	En fait, le calcul d'une distance entre deux graphes est un problème ouvert. Ce
	problème est généralement désigné comme la distance d'édition des graphes qui est

  illustre une comparaison entre la méthode classique de recherche et le modèle proposé. Pour chaque image de la base de Lettrines nous avons compté le nombre d'opérations d'appariemment effectué pour aboutir à l'image correspondant à la requête. Il s'agit ici d'une recherche exacte. Le nombre de comparaisons pour la recherche classique reste constant car nous calculons à chaque fois pour chaque image la distance entre cette image et toutes les autres images de la base. Nous remarquons qu'avec notre approche le nombre d'appriements effectués dépend de l'image requête, mais pour toutes les images testées le nombre de comparaisons est nettement inferieur à la méthode classique de recherche d'images.

financé par le projet Navidomass de l'Agence Nationale de la Recherche référencé sous le numéro ANR-06-MCDA-012 et par la région Lorraine.


Matthieu Alfaro

Arnaud Ducrot

Sharp interface limit of the Fisher-KPP equation when initial data have slow exponential decay

We investigate the singular limit, as ε → 0, of the Fisher equation ∂ t u = ε∆u + ε -1 u(1u) in the whole space. We consider initial data with compact support plus perturbations with slow exponential decay. We prove that the sharp interface limit moves by a constant speed, which dramatically depends on the tails of the initial data. By performing a fine analysis of both the generation and motion of interface, we provide a new estimate of the thickness of the transition layers.

Key Words: Fisher equation, singular perturbation, generation of interface, motion of interface, travelling waves, tails of the initial data.

.

Assumption 1.3. We assume that Ω 0 is convex.

Introduction

In this work, we consider u ε = u ε (t, x) the solution of the rescaled Fisher-KPP equation

(P ε )    ∂ t u ε = ε∆u ε + 1 ε u ε (1 -u ε ) in (0, ∞) × R N u ε (0, x) = u 0,ε (x) in R N ,
with ε > 0 a small parameter, related to the thickness of a diffuse interfacial layer. Let us recall that, in the classical works of Fisher [START_REF] Fisher | The wave of advance of advantageous genes[END_REF] and Kolmogorov, Petrovsky and Piskunov [START_REF] Kolmogorov | Etude de l'équation de la diffusion avec croissance de la quantité de matière et son application à un problème biologique[END_REF], the authors consider a smooth monostable nonlinearity f : [0, 1] → R such that f (0) = f (1) = 0 , 0 < f (u) ≤ f ′ (0)u for all u ∈ (0, 1) .

1 AMS Subject Classifications: 35K57, 35B25, 35R35, 35B50, 92D25.

1

Our results would hold for such nonlinearities but, for the sake of clarity, we restrict ourselves to the case where f (u) = u(1u).

In [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF] we have investigated the singular limit, as ε → 0, of (P ε ) when initial data have compact support plus, possibly, perturbations with a fast exponential decay. We proved that the sharp interface limit moves by constant speed which is the minimal speed c * = 2 of the underlying travelling waves. We also obtained a new O(ε| ln ε|) estimate for the thickness of the transition layers of the solutions u ε .

The present paper is a completion of [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF]: we are concerned with initial data with a slow exponential decay. In this case, it turns out that the limit interface moves by a speed which dramatically depends on the tails of the initial data. We prove the convergence and again obtain a new O(ε| ln ε|) estimate for the thickness of the transition layers of the solutions u ε .

We shall assume the following properties on the initial data.

Assumption 1.1. We assume that u 0,ε = g + h ε where (i) g is a bounded, nonnegative and compactly supported function. We define Ω 0 := supp g.

(ii) We define g as the restriction of g on Ω 0 and assume that g is of the class C 2 .

(iii) h ε is a nonnegative function and there exist λ ∈ (0, 1) and 0 < m < M such that, for all ε > 0 small enough,

me -λ |d(0,x)| ε ≤ h ε (x) ≤ M e -λ |d(0,x)| ε , ∀x ∈ R N ,
where d(0, •) denotes the cut-off signed distance function to the "initial interface" Γ 0 := ∂Ω 0 (see subsection 2.3).

Remark 1.2 (Fast/Slow exponential decay). In the fast exponential decay case considered in [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF], (iii) is replaced by h ε (x) ≤ M e -λ x ε for some λ ≥ 1. In some sense, see subsection 2.2 for details, the exponential decay of the initial data is faster than the exponential decay of the underlying travelling wave of minimal speed c * . In this case, λ ≥ 1 does not affect the asymptotic speed of the limit interface which is always c * .

In the present case λ ∈ (0, 1) we consider, (3.6) indicates that the exponential decay of the initial data and that of the underlying travelling wave of speed λ + λ -1 are the same; it follows that the construction of efficient sub-solutions is more involved than in [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF]. Here, λ ∈ (0, 1) does affect the asymptotic speed of the limit interface, which turns out to be λ + λ -1 . Assumption 1.4. We assume the existence of δ > 0 such that, if n denotes the Euclidian unit normal vector exterior to the initial interface Γ 0 , then ∂ g ∂n (y) ≥ δ for all y ∈ Γ 0 .

(1.1) Assumption 1.1 gives the structure of our allowed initial data. Note that Assumption 1.3 is used to find upper bounds for the solutions u ε (see Lemma 4.1) whereas Assumption 1.4 is only used to derive the correspondence (3.4).

Before going into much details, let us comment on related known results. It is long known that the tails of the initial data play a key role in the study of the long time behavior of u = u(t, x) the solution of the Fisher-KPP equation ∂ t u = ∆u + u(1u). As far as initial data with exponential decay are concerned, we refer among others to [START_REF] Mckean | Application of Brownian motion to the equation ofKolmogorov-Petrovskii-Piskunov[END_REF], [START_REF] Bramson | Convergence of solutions of the Kolmogorov equation to travelling waves[END_REF], [START_REF] Lau | On the nonlinear diffusion equation of Kolmogorov, Petrovsky, and Piscounov[END_REF] for a probabilistic framework and to [START_REF] Larson | Transient bounds and time-asymptotic behavior of solutions to nonlinear equations of Fisher type[END_REF], [START_REF] Rothe | Convergence to travelling fronts in semilinear parabolic equations[END_REF], [START_REF] Uchiyama | The behavior of solutions of some nonlinear diffusion equations for large time[END_REF] for a reaction-diffusion framework. More recently, Hamel and Roques [START_REF] Hamel | Fast propagation for KPP equations with slowly decaying initial conditions[END_REF] studied the case where the initial data decays more slowly than any exponentially decaying function.

In a singular limit framework, the question of the convergence of Problem (P ε ) has been addressed when the initial data u 0,ε does not depend on ε and is compactly supported : first by Freidlin [START_REF] Freidlin | Limit theorems for large deviations and reactiondiffusion equations[END_REF] using probabilistic methods and later by Evans and Souganidis [START_REF] Evans | A PDE approach to geometric optics for certain semilinear parabolic equations[END_REF] using Hamilton Jacobi technics (in this framework we also refer to [START_REF] Barles | Wavefront propagation for reaction-diffusion systems of PDE[END_REF][START_REF] Barles | A remark on the asymptotic behavior of the solution of the KPP equation[END_REF]). In [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF], we provide a new proof of convergence for Problem (P ε ) with fast exponentially decaying initial data, by using specific reaction-diffusion tools such as the comparison principle. Moreover, we obtain an O(ε| ln ε|) estimate of the thickness of the transition layers of the solutions u ε . To the best of our knowledge, no such fine estimate of the thickness of the transition layers existed for the Fisher-KPP equation (in contrast with the Allen-Cahn equation).

As ε → 0, by formally neglecting the diffusion term, we see that, in the very early stage, the value of u ε quickly becomes close to either 1 or 0 in most part of R N , creating a steep interface (transition layer) between the regions {u ε ≈ 1} and {u ε ≈ 0}. Once such an interface develops, the diffusion term is large near the interface comes to balance with the reaction term. As a result, the interface ceases rapid development and starts to propagate in a much slower time scale. Therefore the limit solution ũ(t, x) will be a step function taking the value 1 on one side of the moving interface, and 0 on the other side.

We shall prove that this sharp interface, which we will denote by Γ c λ t , obeys the law of motion

(P c λ ) V n = c λ := λ + λ -1 on Γ c λ t Γ c λ t t=0 = Γ 0 ,
where V n denotes the normal velocity of Γ c λ t in the exterior direction. Note that c λ = λ + λ -1 > 2 = c * , with c * = 2 the minimal speed of some related one-dimensional travelling waves (see subsection 2.2 for details). Therefore, as expected, the slower the initial data decay, the larger is the the speed of the sharp interface limit.

Since the region enclosed by Γ 0 , namely Ω 0 , is smooth and convex, Problem (P c λ ), possesses a unique smooth solution on [0, ∞), which we denote by Γ c λ = t≥0 ({t} × Γ c λ t ). Hereafter, we fix T > 0 and work on (0, T ]. For each t ∈ (0, T ], we denote by Ω c λ t the region enclosed by the hypersurface Γ c λ t . We define a step function ũ(t, x) by

ũ(t, x) = 1 in Ω c λ t 0 in R N \ Ω c λ t for t ∈ (0, T ] , (1.2)
which represents the asymptotic limit of u ε as ε → 0.

Our main result, Theorem 1.5, shows that, after a short time of order O(ε| ln ε|), the solution u ε quickly becomes close to 1 or 0, except in a small neighborhood of the initial interface Γ 0 , creating a steep transition layer around Γ 0 (generation of interface). The theorem then states that the solution u ε remains close to the step function ũ on the time interval [t ε , T ] (motion of interface). Last, (1.3) shows that, for any 0 < a < 1, for all t ε ≤ t ≤ T , the level-set Γ ε t (a) := {x ∈ R N : u ε (t, x) = a} lives in an O(ε| ln ε|) tubular neighborhood of the limit interface Γ c λ t . In other words, we provide a new estimate of the thickness of the transition layers of the solutions u ε . Theorem 1.5 (Generation, motion and thickness of interface). Let Assumptions 1.1, 1.3 and 1.4 be satisfied. Then there exist positive constants α and C such that, for all ε > 0 small enough, for all t ε ≤ t ≤ T , where

t ε := αε| ln ε| , we have u ε (t, x) ∈      [0, 1 + ε] if x ∈ N Cε| ln ε| (Γ c λ t ) [1 -2ε, 1 + ε] if x ∈ Ω c λ t \ N Cε| ln ε| (Γ c λ t ) [0, ε] if x ∈ (R N \ Ω c λ t ) \ N Cε| ln ε| (Γ c λ t ) , (1.3)
where

N r (Γ c λ t ) := {x ∈ R N : dist(x, Γ c λ t ) < r} denotes the tubular r- neighborhood of Γ c λ t .
As a immediate consequence of the above Theorem, we collect the convergence result.

Corollary 1.6 (Convergence). Let Assumptions 1.1, 1.3 and 1.4 be satisfied. Then, as ε → 0, u ε converges to ũ everywhere in 0<t≤T ({t}

× Ω c λ t ) and 0<t≤T {t} × (R N \ Ω c λ t ) .
The organization of this paper is as follows. In Section 2, we present the basic tools that will be used in later sections for the construction of sub-and super-solutions. In Section 3 we construct two sub-solutions, one for small times (during the generation of interface) and one for later times (during the motion of interface). Section 4 is devoted to the construction of a single super-solution which is efficient to study both the generation and the motion of interface. Last, in Section 5, by using our different sub-and super-solutions we prove Theorem 1.5.

Materials

The needed tools are the same than in [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF]. For the self-containedness of the present paper we recall them here. Let us note than the non monotone travelling waves of speed 0 < c < c * used in [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF] are useless here.

A monostable ODE

The generation of interface is strongly related to the dynamical properties of the ordinary differential equation associated to (P ε ), that is

dz(t) dt = z(t)(1 -z(t)) , t > 0 .
In the sequel, for technical reasons we shall apply the semiflow generated by the above dynamical system to negative initial data. In order to have some good dynamical properties, let us modify the monostable nonlinearity u → u(1u) on (-∞, 0) so that the modified function, we call it f : R → R, is of the class C 2 and enjoys the bistable assumptions. More precisely, f has exactly three zeros -1 < 0 < 1 and

f ′ (-1) < 0 , f ′ (0) = 1 > 0 , f ′ (1) = -1 < 0 . (2.1) Note that f (u) = u(1 -u) if u ≥ 0.
As done in Chen [START_REF] Chen | Generation and propagation of interfaces for reactiondiffusion equations[END_REF], we consider fε a slight modification of f defined by

fε (u) := ψ(u) u -ε| ln ε| | ln ε| + (1 -ψ(u)) f (u) ,
with ψ a smooth cut-off function satisfying conditions (29)-(32) as they appear in [START_REF] Hilhorst | Interface dynamics of the Fisher equation with degenerate diffusion[END_REF]. As explained in [START_REF] Hilhorst | Interface dynamics of the Fisher equation with degenerate diffusion[END_REF],

fε (u) ≤ f (u) for all u ∈ R . (2.2)
Then we defined w(s, ξ) as the semiflow generated by the ordinary differential equation

     dw ds (s, ξ) = fε (w(s, ξ)) , s > 0 , w(0, ξ) = ξ .
(2.3)

Here ξ ranges over the interval [-g ∞ -M -1, g ∞ + M + 1].
We claim that w(s, ξ) has the following properties (for proofs, see [START_REF] Chen | Generation and propagation of interfaces for reactiondiffusion equations[END_REF] or [START_REF] Hilhorst | Interface dynamics of the Fisher equation with degenerate diffusion[END_REF]).

Lemma 2.1 (Behavior of w). The following holds for all

ξ ∈ [-g ∞ -M - 1, g ∞ + M + 1].
(i) If ξ ≥ ε| ln ε| then w(s, ξ) ≥ ε| ln ε| > 0 for all s > 0 .

If ξ < 0 then w(s, ξ) < 0 for all s > 0 .

If ξ ∈ (0, ε| ln ε|) then w(s, ξ) > 0 for all s ∈ (0, s ε (ξ)), with

s ε (ξ) := | ln ε| ln 1 - ξ ε| ln ε . (ii) w(s, ξ) ∈ (-g ∞ -M -1, g ∞ + M + 1) for all s > 0 .
(iii) w is of the class C 2 with respect to ξ and w ξ (s, ξ) > 0 for all s > 0 .

(iv) For all a > 0, there exists a constant C(a) such that

w ξξ w ξ (s, ξ) ≤ C(a)
ε for all 0 < s ≤ a| ln ε| .

(v) There exists a positive constant α such that, for all s ≥ α| ln ε|, we have

if ξ ∈ [ε| ln ε|, g ∞ + M + 1] then 0 < w(s, ξ) ≤ 1 + ε , and if ξ ∈ [3ε| ln ε|, g ∞ + M + 1] then 1 -ε ≤ w(s, ξ) .

Travelling waves

A travelling wave is a couple (c, U ) with c > 0 and

U ∈ C 2 (R, R) a function such that      U ′′ (z) + cU ′ (z) + U (z)(1 -U (z)) = 0 for all z ∈ R U (-∞) = 1 U (∞) = 0 .
< r < R such that re -η|z| ≤ 1 -U (z) ≤ Re -η|z| for z ≤ 0 , (2.5
)

re -µz ≤ U (z) ≤ Re -µz for z ≥ 0 , (2.6
)

re -η|z| ≤ |U ′ (z)| + |U ′′ (z)| ≤ Re -η|z| for z ≤ 0 , (2.7
)

re -µ|z| ≤ |U ′ (z)| + |U ′′ (z)| ≤ Re -µ|z| for z ≥ 0 , (2.8)
with η > 0 the positive root of equation η 2 + cη -1 = 0 and µ > 0 the smallest root of equation µ 2cµ + 1 = 0.

We refer the reader to [START_REF] Aronson | Nonlinear diffusion in population genetics, combustion, and nerve pulse propagation, Partial differential equations and related topics[END_REF][START_REF] Volpert | Travelling Wave Solutions of Parabolic Systems[END_REF] and the references therein for more details.

Cut-off signed distance functions

Recall that Γ c λ = t≥0 ({t}×Γ c λ t ) is the smooth solution of the free boundary problem (P c λ ) and that, for each t > 0, Ω c λ t is the region enclosed by the hypersurface Γ c λ t . Let d(t, •) be the signed distance function to Γ c λ t defined by

d(t, x) = -dist(x, Γ c λ t ) for x ∈ Ω c λ t dist(x, Γ c λ t ) for x ∈ R N \ Ω c λ t .
(2.9)

We remark that d = 0 on Γ c λ and that |∇ d| = 1 in a neighborhood of Γ c λ . We now introduce the "cut-off signed distance function" d, which is defined as follows. Recall that T > 0 is fixed. First, choose d 0 > 0 small enough so that d is smooth in the tubular neighborhood of Γ c λ

{(t, x) ∈ [0, T ] × R N : | d(t, x)| < 4d 0 } . Next let ζ(s) be a smooth function satisfying 0 ≤ ζ ′ (s) ≤ 1 for all s ∈ R , (2.10)
such that

ζ(s) =      s if |s| ≤ d 0 -2d 0 if s ≤ -3d 0 2d 0 if s ≥ 3d 0 .
We then define the cut-off signed distance function d by

d(t, x) := ζ d(t, x) . (2.11) Note that if |d(t, x)| < d 0 then |∇d(t, x)| = 1 , (2.12)
and that the equation of motion (P c λ ) yields

if |d(t, x)| < d 0 then ∂ t d(t, x) + c λ = 0 . (2.13)
Then the mean value theorem provides a constant A > 0 such that

|∂ t d(t, x) + c λ | ≤ A|d(t, x)| for all (t, x) ∈ [0, T ] × R N . (2.14)
Moreover, there exists a constant C > 0 such that

|∇d(t, x)| + |∆d(t, x)| ≤ C for all (t, x) ∈ [0, T ] × R N .
(2.15)

Sub-solutions

As explained before, the construction of efficient sub-solutions is more involved than in the fast exponential decay case considered in [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF]. We start by constructing refined sub-solutions for small times.

Generation of interface

Let us recall that me -λ |d(0,x)| ε ≤ h ε (x) ≤ M e -λ |d(0,x)| ε for all x ∈ R N . We then define the map

u(t, x) := max me -λ |d(0,x)| ε , w t ε , g(x) -Kt , (3.1)
where w(s, ξ) is the solution of the ordinary differential equation (2.3) and where m = min( 1 2 , m). The constant K > 0 is to be specified below.

Lemma 3.1 (Sub-solutions for small times). Let Assumption 1.1 be satisfied. Then for all a > 0, there exists K > 0 such that, for all ε > 0 small enough, we have

u(t, x) ≤ u ε (t, x) , ∀t ∈ [0, aε| ln ε|] , ∀x ∈ R N . (3.2)
Proof. Let us first notice that, for all x ∈ R N ,

u(0, x) = max me -λ |d(0,x)| ε , g(x) ≤ me -λ |d(0,x)| ε + g(x) = u ε (0, x) .
Then it remains to show that u is a sub-solution of Problem (P ε ). Let us consider the operator

L ε [v] := ∂ t v -ε∆v - 1 ε v(1 -v) .
Let a > 0 be arbitrary. We show below that, if K > 0 is sufficiently large then, for all ε > 0 small enough, L ε [u] ≤ 0. We distinguish two cases.

We first consider the points (t, x) where u(t, x) = me -λ |d(0,x)| ε . Assume further that d(0, x) ≥ 0 so that u(t, x) = me -λ d(0,x) ε =: ϕ ε (x). We compute

∂ t u = 0 ∆u = λ 2 |∇d| 2 ε 2 ϕ ε -λ ∆d ε ϕ ε .
Therefore, we get

εL ε [u](t, x) = ϕ ε -λ 2 |∇d| 2 + ελ∆d -1 + ϕ ε . Since 0 ≤ ϕ ε ≤ 1/2, we get εL ε [u](t, x) ≤ ϕ ε ελ∆d - 1 2 ≤ 0 ,
for ε > 0 sufficiently small. The case where d(0, x) ≤ 0 is very similar and omitted.

Next we consider the points (t, x) where u(t, x) = w t ε , g(x) -Kt . We have

∂ t u = 1 ε w s -Kw ξ ∆u = w ξξ |∇g| 2 + w ξ ∆g .
Then, we get

L ε [u](t, x) = 1 ε w s -Kw ξ -ε w ξξ |∇g| 2 + w ξ ∆g - 1 ε w(1 -w) ≤ 1 ε w s -Kw ξ -ε w ξξ |∇g| 2 + w ξ ∆g - 1 ε fε (w) = -w ξ K + ε w ξξ w ξ |∇g| 2 + ∆g ,
where we have successively used (2.2) and (2.3). In view of Lemma 2.1 (iv), there exists a constant C(a) > 0 such that, for all (t, x) with 0 ≤ t ≤ aε| ln ε|, we have

w ξξ w ξ |∇g| 2 + ∆g ≤ C(a) ε .
Therefore, choosing K > C(a) implies

L ε [u](t, x) ≤ -w ξ (K -C(a)) ≤ 0 , since w ξ > 0.
This completes the proof of Lemma 3.1.

As a consequence of the above construction of sub-solutions for small times, we deduce that, after a very short time, the solution u ε approaches 1 in most part of the support of the initial data. Corollary 3.2 (Generation of interface "from the inside"). Let Assumption 1.1 be satisfied. Then there exist k > 0, α > 0 such that, for all ε > 0 small enough,

d(0, x) ≤ -kε| ln ε| =⇒ 1 -ε ≤ u ε (t ε , x) ≤ 1 + ε , (3.3)
wherein t ε := αε| ln ε|.

Proof. In Lemma 3.1, we select a = α where α > 0 is as in Lemma 2.1 (v). Note that, in view of (1.1), the mean value theorem provides the existence of a constant k > 0 such that if d(0, x) ≤ -kε| ln ε| then g(x) ≥ (3 + Kα)ε| ln ε| .

(3.4)

Then, using (3.2), we see that, for all x satisfying d(0, x) ≤ -kε| ln ε|,

u ε (t ε , x) ≥ u(t ε , x) ≥ w(α| ln ε|, 3ε| ln ε|) ≥ 1 -ε .
The last inequality follows from Lemma 2.1 (v). Note that the upper bound 1 + ε is actually valid for all x and all t ≥ t ε , as seen in (5.1), and will be proved in Section 5.

The corollary is proved.

Motion of interface

In the fast exponential decay case, the limit speed of the sharp interface limit is c * . Therefore sub-solutions for the motion of interface are constructed in [START_REF] Alfaro | Sharp interface limit of the Fisher-KPP equation[END_REF] by using the travelling waves associated with the speeds c *o(ε) < c * . Since they are changing sign, a slight modification make the sub-solutions compactly supported from one side. In the slow exponential decay case we consider, the limit interface moves with speed c λ > c * . Since the travelling waves with speeds c λo(ε) > c * are not changing sign we are not able to construct compactly supported sub-solutions.

In the sequel, we denote by U the travelling wave associated with the speed of the limit interface c λ = λ + λ -1 and by d(t, x) the cut-off signed distance function associated with Γ c λ the solution of the free boundary problem (P c λ ). We also consider V the travelling wave associated with the speed c ε := c λ -ε| ln ε|.

From Lemma 2.2, we see that for U (whose speed is c λ = λ + λ -1 ), the µ that appears in (2.6) is actually equal to λ. Therefore, we collect

re -η|z| ≤ 1 -U (z) ≤ Re -η|z| for z ≤ 0 , (3.5) re -λz ≤ U (z) ≤ Re -λz for z ≥ 0 . (3.6)
Moreover, since V which is slightly slower it will decay faster. More precisely, we deduce from Lemma 2.2 that

re -ηε|z| ≤ 1 -V (z) ≤ Re -ηε|z| for z ≤ 0 , (3.7) re -µεz ≤ V (z) ≤ Re -µεz for z ≥ 0 , (3.8)
with η ε ≥ η + γε| ln ε| and µ ε ≥ λ + γε| ln ε|, for some γ > 0. The estimates on the derivatives of U and V corresponding to (2.7) and (2.8) also hold.

We are looking for sub-solutions in the form

u -(t, x) := U d(t, x) + ε| ln ε|m 1 e m 2 t ε -εV d(t, x) + ε| ln ε|m 1 e m 2 t
ε .

(3.9) In the sequel we set z(t, x) := d(t, x) + ε| ln ε|m 1 e m 2 t ε .

(3.10) Lemma 3.3 (Ordering initial data). Let Assumptions 1.1 and 1.4 be satisfied. Then there exists m1 > 0 such that for all m 1 ≥ m1 , all m 2 > 0, all ε > 0 small enough, we have

u -(0, x) ≤ u ε (t ε , x) , (3.11)
for all x ∈ R N , with t ε = αε| ln ε|.

Proof. Choose k > 0 so that (3.3) holds and m 1 ≥ m1 := 3k. Note that to prove Lemma 3.3, it is sufficient to check that

u -(0, x) = U (z(0, x)) -εV (z(0, x)) ≤ u(t ε , x) , (3.12)
where u is the sub-solution for small times defined in (3.1). To prove this inequality we shall split our arguments into three parts according to the value of d(0, x).

If x is such that d(0, x) ≥ 0. Since z(0, x) ≥ 0, we deduce from (3.6) that, for ε > small enough,

u -(0, x) ≤ U (z(0, x)) ≤ Re -λ d(0,x) ε e -λm 1 | ln ε| ≤ me -λ |d(0,x)| ε ≤ u(t ε , x) .
If x is such that -kε| ln ε| ≤ d(0, x) ≤ 0. The choice of m 1 implies that z(0, x) ≥ 2k| ln ε| so that, for ε > small enough,

u -(0, x) ≤ Re -λk| ln ε| e -λk| ln ε| ≤ me -λk| ln ε| ≤ me -λ |d(0,x)| ε ≤ u(t ε , x) .
If x is such that -2d 0 ≤ d(0, x) ≤ -kε| ln ε|, which implies that z(0, x) ≥ -d 0 /ε. We claim that (see proof below), for ε > 0 small enough,

U ′ (z) -εV ′ (z) < 0 for all z ∈ R . (3.13)
Therefore, by using (3.5) and (3.7) we get

u -(0, x) ≤ (U -εV ) (-d 0 /ε) ≤ 1 -re -ηd 0 /ε -ε(1 -Re -ηεd 0 /ε ) = 1 -ε -e -ηd 0 /ε (r -εRe -(ηε-η)d 0 /ε ) ≤ 1 -ε -e -ηd 0 /ε (r -εR) ≤ 1 -ε ,
for ε > 0 small enough. In view of Corollary 3.2, this completes the proof of (3.11).

It remains to prove (3.13). Note that (U -εV )(-∞) = 1ε and (U -εV )(∞) = 0 and assume, by contradiction, that there exist ε 0 > 0 and a family {z ε } 0<ε<ε 0 such that

U ′ (z ε ) -εV ′ (z ε ) = 0 for each ε ∈ (0, ε 0 ) .
First assume that {z ε } is bounded. Then there exists a sequence {ε n } n≥0 tending to zero such that z εn → z 0 ∈ R when n → ∞ for some z 0 . Recall that V depends on ε > 0 and is uniformly bounded with respect to ε up to its second derivative. Passing to the limit n → ∞ leads us to U ′ (z 0 ) = 0, a contradiction. Next, assume that {z ε } is unbounded. Then there exists a sequence {ε n } n≥0 tending to zero such that z εn → ∞ or z εn → -∞ when n → ∞. Consider the case where z εn → ∞ then we obtain that

ε n = U ′ (z εn ) V ′ (z εn ) ≥ re -λzε n Re -µεzε n ≥ r R e (µε n -λ)zε n ≥ r R ,
a contradiction with the behavior of {ε n } when n → ∞. The case where z εn → -∞ is similar. The claim (3.13) is proved.

Lemma 3.4 (Sub-solutions for later times). Recall that u -was defined in (3.9) and assume that U (0) > 1 2 . Then there exists m2 > 0 such that for all m 1 ≥ m1 , all m 2 ≥ m2 , all ε > 0 small enough, we have

εL ε [u -] = ε∂ t u --ε 2 ∆u --u -(1 -u -) ≤ 0 in (0, ∞) × R N . (3.14)
Proof. By using straightforward computations we get

ε∂ t u -= (U ′ -εV ′ )(z) ∂ t d + m 2 ε| ln ε|m 1 e m 2 t ε 2 ∆u -= (U ′′ -εV ′′ )(z)|∇d| 2 + ε(U ′ -εV ′ )(z)∆d u -(1 -u -) = U (1 -U ) + εU V -εV (1 -U ) -ε 2 V 2 ,
where z = z(t, x) was defined in (3.10). Now, the ordinary differential equations

U ′′ + c λ U ′ + U (1 -U ) = 0 and V ′′ + (c λ -ε| ln ε|)V ′ + V (1 -V ) = 0 yield εL ε [u -] = E 1 + • • • + E 4 ,
with

E 1 := (U ′ -εV ′ )(z) ∂ t d + c λ + m 2 ε| ln ε|m 1 e m 2 t -ε∆d E 2 := ε 2 | ln ε|V ′ (z) E 3 := (U ′′ -εV ′′ )(z)(1 -|∇d| 2 ) E 4 := -εV (2U -V )(z) + ε 2 V 2 (z) .
Note that E 2 ≤ 0. We show below that the choice

m2 := 2A 2 m1 η + 1 ,
is enough to prove the lemma, with A > 0 the constant that appears in (2.14). To that purpose we distinguish four cases, namely (3.15), (3.17 Using the estimates for U ′ and V ′ we see that, for ε > 0 small enough,

|E 1 | ≤ C(e -η|z| + εe -ηε|z| ) ≤ Ce -η|z| ≤ Cε 2 ,
thanks to (3.16). Using similar arguments we see that

|E 3 | ≤ Cε 2 . At least note that z → -∞ as ε → 0 and that V (2U -V )(-∞) = 1. Therefore, if ε > 0 is small enough then E 4 ≤ -1 2 ε + Cε 2 . It follows that εL ε [u -] ≤ -1 2 ε + Cε 2 ≤ 0. Assume that - m 2 2A
ε| ln ε|m 1 e m 2 t ≤ d(t, x) ≤ -ε| ln ε|m 1 e m 2 t .

(3.17)

From (2.12) we deduce that E 3 = 0. From (2.13), we deduce that ∂ t d + c λ = 0. Since, for ε > 0 small enough, m 2 ε| ln ε|m 1 e m 2 t -ε∆d ≥ 0 we deduce from (3.13) that E 1 ≤ 0. Next, since (3.17) implies that z ≤ 0 we get

2U (z) -V (z) -εV (z) ≥ 2U (0) -1 -ε ≥ 0 , since U (0) > 1 2
. Hence we obtain that E 4 ≤ 0, so that we have εL ε [u -] ≤ 0. Assume that -ε| ln ε|m 1 e m 2 t ≤ d(t, x) ≤ d 0 .

(3.18)

Here, E 3 = 0 and ∂ t d + c λ = 0 also hold true. Note that, for ε > 0 small enough,

m 2 ε| ln ε|m 1 e m 2 t -ε∆d ≥ m 1 m 2 2 ε| ln ε| . (3.19)
Using that U ′ (z) -εV ′ (z) < 1 2 U ′ (z) for all z ∈ R, whose proof is similar to that of (3.13), we see that

E 1 ≤ 1 2 U ′ (z) m 1 m 2 2 ε| ln ε| ≤ - rm 1 m 2 4 ε| ln ε|e -λz , since (3.18) implies z ≥ 0. Next, we see that E 4 ≤ CεV (z) ≤ Cεe -µεz ≤ Cεe -λz . As a consequence we get εL ε [u -] ≤ εe -λz - rm 1 m 2 4 | ln ε| + C ≤ 0 , for ε > 0 small enough. Assume that d 0 ≤ d(t, x) ≤ 2d 0 . (3.20)
We rewrite εL ε [u -] ≤ F 1 + F 2 + F 3 where

F 1 := U ′ (z) (∂ t d + c λ ) + U ′′ (z)(1 -|∇d| 2 ) F 2 := U ′ (z)(m 2 ε| ln ε|m 1 e m 2 t -ε∆d) F 3 := -εV ′ (z)(∂ t d + c λ + m 2 ε| ln ε|m 1 e m 2 t -ε∆d) -εV ′′ (z)(1 -|∇d| 2 ) - εV (2U -V )(z) + ε 2 V 2 (z) . Since |F 3 | ≤ Cεe -µεz ≤ Cεe -λz , we deduce from (3.19) that, for ε > 0 small enough, F 2 + F 3 ≤ εe -λz - rm 1 m 2 2 | ln ε| + C ≤ 0 .
It remains to estimate the term F 1 . Since (3.20) implies that z ≥ d 0 /ε we have, for ε > 0 small enough, U (z) ≤ α with 0 < α < 1 to be selected below. Therefore it holds that

U ′′ (z) ≤ -c λ U ′ (z) -(1 -α)U (z).
Recall that (see subsection 2.3)

∂ t d = (∂ t d)ζ ′ = -c λ ζ ′ and |∇d| 2 = |∇ d| 2 (ζ ′ ) 2 = (ζ ′ ) 2 ,
where the function ζ ′ is evaluated at point d. It follows that

F 1 ≤ U ′ (z)(-c λ ζ ′ + c λ ) -c λ U ′ (z)(1 -(ζ ′ ) 2 ) -(1 -α)U (z)(1 -(ζ ′ ) 2 ) ≤ -(1 -ζ ′ ) [(1 -α)(1 + ζ ′ )U (z) + c λ ζ ′ U ′ (z)] .
Since, as ε → 0, U ′ (z) = -βe -λz (1 + o(1)) and U (z) = β λ e -λz (1 + o(1)) for some β > 0, we see that

(1 -α)(1 + ζ ′ )U (z) + c λ ζ ′ U ′ (z) = 1 -α λ (1 + ζ ′ ) -cζ ′ βe -λz (1 + o(1)) .
Recall that 0 ≤ ζ ′ ≤ 1 so that by selecting α ∈ (0, 1-λ 2 2 ) we see that

1-α λ (1 + ζ ′ ) -cζ ′ ≥ 0 so that, for ε > 0 small enough, F 1 ≤ 0. Hence εL ε [u -] ≤ 0.
The lemma is proved.

Super-solutions

This section is devoted to the construction of super-solutions which are efficient for the study of both the generation and the motion of interface.

Lemma 4.1 (Super-solutions). Let Assumptions 1.1 and 1.3 be satisfied. Then there exists a constant K 0 > 1 such that, for all K ≥ K 0 , the following holds. For all x 0 ∈ Γ 0 = ∂Ω 0 , for all ε > 0 small enough, we have

u ε (t, x) ≤ KU (x -x 0 ) • n 0 -c λ t ε for all (t, x) ∈ [0, ∞) × R N ,
wherein n 0 is the outward normal vector to Γ 0 = ∂Ω 0 at x 0 .

Before proving the lemma, for a given x ∈ R N , choose x 0 ∈ ∂Ω 0 as the projection of x on the convex Ω 0 . For such a choice we have (xx 0 ) • n 0 = d(0, x) , and the lemma yields, for some K > 1,

u ε (t, x) ≤ KU d(0, x) -c λ t ε , (4.1)
for all t ≥ 0 and all x ∈ R N . Next, we prove Lemma 4.1.

Proof. We recall that λ and M were defined in Assumption 1.1 (iii) and that U (z) ≥ re -λz for all z ≥ 0. Then we define

K 0 := max 1, M r , g ∞ + M U (0) .
Next, let K ≥ K 0 and x 0 ∈ Γ 0 = ∂Ω 0 be given. We consider the map u + (t, x) := KU (xx 0 ) • n 0c λ t ε .

Straightforward computations and equation U ′′ + c λ U ′ + U (1 -U ) = 0 for the travelling wave yield

εL ε [u + ](t, x) = K( K -1)(U ) 2 (x -x 0 ) • n 0 -c λ t ε ,
and therefore L ε [u + ] ≥ 0 in (0, ∞) × R N . Hence, to complete the proof of the lemma it remains to order the initial data, i.e.

u 0,ε (x) ≤ u + (0, x) = KU (x -x 0 ) • n 0 ε , ∀x ∈ R N . (4.2)
First, assume that x in the half plane {y ∈ R N : (yx 0 ) • n 0 ≤ 0}. Then since U is decreasing we have

U (x -x 0 ) • n 0 ε ≥ U (0) .
Therefore we obtain that

u 0,ε (x) ≤ g ∞ + M U (0) U (x -x 0 ) • n 0 ε ≤ KU (x -x 0 ) • n 0 ε ,
in view of the choice of K 0 . Next, we assume that x is in the half plane {y ∈ R N : (yx 0 ) • n 0 > 0}. Since Ω 0 is convex, we have x /

∈ Ω 0 and d(0, x) ≥ (xx 0 ) • n 0 > 0 so that, in view of the choice of K 0 , u 0,ε (x) = h ε (x) ≤ M e -λd(0,x)/ε ≤ Kre -λ(x-x 0 )•n 0 /ε ≤ KU (xx 0 ) • n 0 ε .

This completes the proof of Lemma 4.1.

As a consequence of the above construction of super-solutions, we deduce that, after a very short time, the solution u ε approaches 0 in most part of the complementary of the support of the initial data. The proof is an easy consequence of the upper bound (4.1) combined with the exponential decay (3.6) of U . Details are omitted. Corollary 4.2 (Generation of interface "from the outside"). Let Assumptions 1.1 and 1.3 be satisfied. For any p > 0, there exists k p > 0 such that, for all ε > 0 small enough, d(0, x) ≥ k p ε| ln ε| =⇒ 0 ≤ u ε (t ε , x) ≤ ε p , where we recall that t ε = αε| ln ε|.

Hence the choice of C implies that z(tt ε , x) ≤ -C 2 | ln ε|. Therefore, using (3.9) and (3.5), we see that, for ε > 0 small enough,

u ε (t, x) ≥ U -C 2 | ln ε| -εV -C 2 | ln ε| ≥ 1 -Re -η C 2 | ln ε| -ε ≥ 1 -2ε , since C > 2 η .
This completes the proof of Theorem 1.5.

(2. 4 )

 4 Define c * := 2. Then, for all c ≥ c * there exists a unique (up to a translation in z) travelling wave denoted by (c, U ). It is positive and monotone.

Lemma 2 . 2 (

 22 Behavior of U ). Let c > 2 = c * be arbitrary and consider the associated travelling wave (c, U ). Then there exist constants C > 0 and 0

2 2A ε| ln ε|m 1 e m 2

 22 ),(3.18) and(3.20). In the sequel we denote by C positive constants which do not depend on ε (and may change from places to places).Assume that -2d 0 ≤ d(t, x) ≤ -m

5 Proof of Theorem 1.5 We first claim that 0 ≤ u ε (t + t ε , x) ≤ 1 + ε , (

for all x ∈ R N and all t ≥ 0. Indeed, the map

Therefore the comparison principle yields

Thus Lemma 2.1 (v) applies and completes the proof of (5.1). Now, let Assumptions 1.1, 1.3 and 1.4 be satisfied. Choose k > 0, α > 0 as in Corollary 3.2 and K > 0 as in Lemma 4.1. According to Lemma 3.3, Lemma 3.4 and the comparison principle, there exist m 1 > 0 and m 2 > 0 such that, for ε > 0 small enough,

for all (t, x) ∈ [t ε , T ] × R N . We choose C such that

with η > 0 the constant that appears in (3.5). First, we take x ∈ (R N \ Ω c λ t ) \ N Cε| ln ε| (Γ c λ t ), i.e.

and prove below that u ε (t, x) ≤ ε, for t ε ≤ t ≤ T . Since

we deduce from (4.1), the decrease of U and (3.6) that, for ε > 0 small enough, for 0 ≤ t ≤ T ,

and prove below that u ε (t, x) ≥ 1 -2ε, for t ε ≤ t ≤ T . In view of (5.2) we have u ε (t, x) ≥ (U -εV )(z(tt ε , x)). Note that d(tt ε , x) = d(t, x) + c λ t ε .