An infrared high-brightness light source based on supercontinuum generation through a SF6 photonic crystal fiber seeded by a Cr :YAG femtosecond oscillator is developed for high resolution multiplex spectroscopy in the 1.5 µm region. Moreover, a multiplex high resolution approach based on a Cr :YAG frequency comb enables to probe large spectral domains, with simultaneous sensitive measurement of the absorption and the dispersion associated with all individual spectral features. 4+ 4+

1

Infrared frequency combs and supercontinua for multiplex high sensitivity spectroscopy

INTRODUCTION

Femtosecond (fs) mode-locked lasers and supercontinua represent the first versatile table-top coherent sources linking broad bandwidth and high brightness. Femtosecond frequency combs offer additional new features for high resolution spectroscopy as they exhibit a broad spectrum, made of equidistant narrow lines of stable and accurate individual positions. Their comb structure may be taken advantage of for improved spectroscopy. This new generation of light sources requires new spectrometric methodologies to be developed. In this article, our progress in the development of infrared supercontinua and frequency combs based methods is presented. Supercontinua are first being implemented for infrared absorption spectroscopy. A powerful method, femtosecond frequency comb spectrometry, is also being experimentally demonstrated. It is based on the exploitation of a frequency comb on its whole spectral domain is aimed at providing sensitivity, accuracy, resolution, broad spectral extension and rapid acquisition times. This multiplex approach enables to probe large spectral domains, with simultaneous measurement of the absorption and the dispersion associated with all individual spectral features. Purposely a femtosecond Cr 4+ :YAG frequency comb has been developed in the 1.5 µm range. In a previous paper [1], we used it as a bright source for high resolution absorption spectroscopy. Here, spectral broadening using highly non linear Photonic Crystal Fibers (PCF) is investigated. The Cr 4+ :YAG oscillator is also applied to 2 frequency comb spectrometry. As an illustration, the entire ν 1 +ν 3 vibration-rotation band region of acetylene is recorded around 6500 cm -1 .

FEMTOSECOND Cr 4+ :YAG OSCILLATOR BROADENED BY A PCF FIBER FOR BROADBAND SPECTROSCOPY

The femtosecond infrared oscillator, emitting in the 1.5 µm region, makes use of a 2 cm-long Brewster-cut Cr 4+ :YAG crystal, pumped by a 1.06 µm commercial Nd:YVO4 laser. Stable mode-locking is obtained by a SEmiconductor Saturable Absorber Mirror and the dispersion is compensated by chirped mirrors. The output power is about 100 mW and the repetition rate of the pulses is 150 MHz. Stable operation is obtained in the positive dispersion regime, where 1.5 ps chirped pulses are obtained. They may be compressed down to 100 fs. As shown on Fig. 1, the laser output spectrum extends from 6340 to 6790 cm -1 at 25 dB below the maximum. To broaden the available spectral domain, a highly non linear multimode PCF in SF6 glass, similar to the one described in [2,3], has been launched. Its core diameter is 4.5 µm, its length 40 cm and its non linear index is 2.2 x 10 -15 cm 2 .W -1 . At the PCF output, the accessible spectrum extends over 2000 cm -1 from 6010 to 7960 cm -1 at 25 dB below the maximum, as shown on Fig. 1. This experimental set-up has been successfully used for the realization of high resolution spectra, as illustrated on the upper right part of Fig. 1 which displays the region of the ν 2 +ν 3 +ν 4 band of NH 3 at 0.12 cm -1 resolution. Supercontinua prove to be a convenient and inexpensive way to perform broadband multiplex spectroscopy with table-top high brightness sources, as their spectral radiance is typically 10 5 higher than incoherent sources.

FEMTOSECOND FREQUENCY COMB SPECTROSCOPY

In order to enhance the sensitivity provided by broadband femtosecond light sources, a new method, femtosecond frequency comb spectroscopy, has been conceived [START_REF] Picqué | Femtosecond frequency combs : new trends for Fourier transform spectroscopy, Fourier Transform Spectroscopy/Hyperspectral Imaging and Sounding of the Environment Topical Meetings on CD-ROM[END_REF] and its first demonstration is given here. The frequency comb probes a cell containing the 3 molecular sample and is analyzed by a new kind of Fourier spectrometer characterized by the radio-frequency detection, at the comb repetition rate, of the interferogram. By performing in-phase and in-quadrature detection of the interferogram, the absorption and dispersion of the spectral features are measured simultaneously in the same experiment. Thanks to the synchronous detection performed in the radio-frequency domain, extremely high sensitivity is expected together with short acquisition time. Additionally, femtosecond frequency comb spectrometry provides broad spectral extension, high spectral resolution, and spatial resolution. The wavenumber scale may be self-calibrated by the frequency comb, with no need of molecular frequency standards. The method may be developed in any spectral domain.

As a first demonstration of our femtosecond frequency comb spectroscopy method, our homemade Cr 4+ :YAG mode-locked femtosecond laser has been used as a broadband comb source. The laser beam passes through a 80-cm cell filled with acetylene. It is analyzed by the high resolution Connes-type interferometer of Laboratoire de Photophysique Moléculaire and detected by a fast InGaAs detector. Synchronous inphase detection at 150 MHz frequency is performed by a lock-in amplifier. Figure 2 provides a restricted portion of the resulting absorption spectrum, exhibiting lines of the R-branch of the ν 1 +ν 3 band of C 2 H 2 . Signal to noise ratio is still limited because of the absence of appropriate dynamics for the interferogram's measurement. This experiment however clearly validates the capabilities of our method and especially the good quality of the retrieved lineshapes. Improvement of the electronics is presently underway.

Figure 1 .

 1 Figure 1. Low resolution spectra on a logarithmic vertical scale of the laser output (thin gray line) and the PCF output (bold black). Upper right part: portion of the ammonia spectrum recorded using the supercontinuum as an absorption source.

Figure 2 .

 2 Figure 2. Portion of the overtone spectrum of the acetylene molecule (pressure: 59 hPa) in the 1.5 µm region obtained from femtosecond frequency comb spectroscopy.


Sylvain Deville

Jérôme Chevalier

Hassan El Attaoui

ATOMIC FORCE MICROSCOPY STUDY AND QUALITATIVE ANALYSIS OF MARTENSITE RELIEF IN ZIRCONIA

Keywords: Atomic force microscopy, martensitic transformation, zirconia

A recent report [S. Deville et al., J. Am. Ceram

I. INTRODUCTION

The martensite transformation model, developed by Bain 1 , has now been the object of almost a century of investigations. Its relevance to different types of materials, running from metals to ceramics, has drawn a lot of attention and studies. If the characteristics and macroscopic features of the transformation are now well predicted and understood, the number of quantitative reports of surface relief changes resulting from phase martensitic transformation is still limited, which is not surprising considering the scale at which the transformation is occurring. Martensite relief has been investigated mainly by optical methods and scanning electron microscopy, though both methods provide a limited spatial resolution, and 3D quantitative informations are not accessible. Quite fortunately, the recent development of scanning tunneling microscopy (STM) and atomic force microscopy (AFM) [START_REF] Binnig | Surface studies by scanning tunneling microscopy[END_REF] provides the scientific community with powerful tools to investigate phenomenon's characterized by relief variations at a nanometer scale. Great progresses were accomplished in the last few years and a few reports might be found on steel based materials [START_REF] Yang | Surface relief accompanying martensitic transitions in an Fe-Ni-C alloy by atomic-force microscopy and phenomenological theory of martensitic crystallography[END_REF][START_REF] Bergeon | Atomic force microscopy study of stress-induced martensite formation and its reverse transformation in a thermomechanically treated Fe-Mn-Si-Cr-Ni alloy[END_REF][START_REF] Davenport | Ultrasonic and atomic force studies of the martensitic transformation induced by temperature and uniaxial stress in NiAl alloys[END_REF] .

The absence of specific sample preparation and the possibility of observing bulk non-conductive materials make it very attractive to study martensitic transformation in ceramics in particular.

The martensitic transformation of zirconia corresponds to the tetragonal to monoclinic phase transformation 6,[START_REF] Porter | Transformation-toughening in partially stabilized zirconia (PSZ)[END_REF] . Zirconia, when doped with yttria (Y 2 O 3 ) or ceria (CeO 2 ), is indeed retained in its metastable tetragonal structure after sintering. Upon the action of mechanical stresses or hydrothermal solicitations [START_REF] Sato | Transformation of yttria-doped tertragonal ZrO 2 polycrystals by annealing in water[END_REF][START_REF] Lange | Degradation during ageing of transformation toughened ZrO 2 -Y 2 O 3 materials at 250°C[END_REF][START_REF] Tsubakino | Tetragonal to monoclinic phase transformation during thermal cycling and isothermal ageing in yttria-partially stabilized zirconia[END_REF] (i.e. water vapor at 140°C), zirconia might transform to its stable monoclinic structure. This transformation, at the origin of the transformation toughening effect [START_REF] Garvie | Ceramic steel ?[END_REF][START_REF] Evans | Review -Transformation toughening in ceramics: martensitic transformation in crack-tip stress fields[END_REF] , has been the object of extensive studies over the last twenty years, and its martensitic nature is now widely recognized [START_REF] Kelly | The martensitic transformation in ceramics -its role in transformation toughening[END_REF] . Evidences of martensitic features were provided mainly by transmission electron microscopy and optical interferometry [START_REF] Hayakawa | Structural study on the tetragonal to monoclinic transformation in arc-melted ZrO 2 -2mol.%Y 2 O 3[END_REF] . However, very few quantitative reports [START_REF] Yamamoto | Scanning tunneling microscope study of surface relief induced by the tetragonal-tomonoclinic transformation in a zirconia-yttria alloy[END_REF][START_REF] Tsubakino | Surface relief associated with isothermal martensite in zirconia 3 mol% yttria ceramics observed by atomic force microscopy[END_REF][START_REF] Chen | The study of martensitic transformation and nanoscale surface relief in zirconia[END_REF] of the martensitic features might be found in the literature due to experimental difficulties, and less interest attached to these materials so far. Recent progresses [START_REF] Deville | Martensitic relief observation by atomic force microscopy in yttria stabilized zirconia[END_REF] in imaging resolution have shown that AFM could provide with very precise measurements of martensitic surface relief on zirconia samples. In this paper, AFM has been used to characterize surface relief resulting from martensitic transformation in ceria and yttria-doped zirconia, at a scale that was never reached before. These qualitative observations brought new insights on the transformation initiation and propagation mechanisms.

II. EXPERIMENTAL METHODS

Ceria stabilized zirconia (Ce-TZP) materials were processed by classical powder mixing processing route, using Zirconia Sales Ltd powders, with uniaxial pressing and sintering at 1550°C for two hours. Yttria stabilized zirconia (Y-TZP) samples were processed using (3 mol.% Y 2 O 3 )-TZP powders (Tosoh, Japan), and also uniaxial pressing and sintering for two hours at 1500°C.

Residual porosity was negligible. Samples were polished with standard diamond based products. Some samples were thermally etched for 12 min at 1350°C, in order to form grain boundary thermal grooves. The effect of a slight thermal etching on the ageing behaviour has been investigated, and it was shown it did not modify either the transformation mechanism or its kinetic. Thermal etching was performed to study the location of the transformation with respect to grain boundaries. Experiments were performed using both thermally etched and unetched samples.

AFM experiments were carried out with a D3100 nanoscope from Digital Instruments Inc., using oxide sharpened silicon nitride probes in contact mode, with an average scanning speed of 5 µm.s -1 . Since the t-m phase transformation is accompanied by a large strain (4 % vol. and 16 % shear), surface relief is modified by the formation of monoclinic phase. The vertical resolution (down to a few tenths of nanometers) of AFM allows following very precisely the transformation. Two types of images have been obtained from AFM experiments. The first one is the height image (see Fig. 1,2 or 10), where the height of every point of the scanned surface is measured. This allows relief 3D imaging, making the image analysis and interpretation easy. The second type is the so-called derivated image (see Fig. 6, 11 or 12), where the contrast is originating from the rate of relief variation, i.e. all the surfaces with the same orientation, related to the probe scanning path, will appear with the same contrast. This type of images is very convenient to discern planes with a constant angle, such as the ones forming the sides of self accommodating variant pair of martensite.

Either these two types of images are presented here. The vertical and lateral scales of AFM images are always different here so as to exaggerate the relief and see it more clearly.

Ageing treatments were conducted in autoclave at 140°C, in water vapor atmosphere, with a 2 bar pressure, in order to induce phase transformation at the surface of the samples with time.

III. RESULTS AND DISCUSSION

A. Martensite fundamental features

The phenomenological theory of martensitic crystallography [START_REF] Wechsler | On the theory of formation of martensite[END_REF][START_REF] Bowles | The crystallography of martensite transformations[END_REF] relies on the model of an invariant plane strain (IPS) phase transformation, i.e. the habit plane of martensite does not exhibit neither strain nor rotation. Experimental evidences for this were provided here by the observation of polishing scratches at samples surface. Upon transformation, a scratch lying at the surface of transformed grains remains continuous and straight. The direction of the scratch is slightly modified, according to the overall shear of the surface, but the scratch remains unbroken. This simple observation is shown in Fig. 1. Two pairs of self accommodating martensitic variants pairs lying side by side might be observed, and scratches running across the surface are observed. It is quite clear that these scratches remained still continuous and straight, providing thus strong evidences supporting the IPS phase transformation model.

One of the most characteristic features of PTMC is the formation of self accommodating variant pairs (SAMVP). Their apparition is related in a very straightforward way to the microscopic and macroscopic effects of local shear and stresses resulting from the transformation. In the PTMC, single martensite plates might appear, leading to an N-like shape of surface relief. If two plates are growing back to back or close enough, their habit planes might join themselves, and the overall surface adopts a triangular shape. It was thought [START_REF] Kelly | The martensitic transformation in ceramics -its role in transformation toughening[END_REF] the formation of SAMVP would be present only in the case were the transforming region was isolated and surrounded by untransformable material, e.g. zirconia grains in an alumina matrix, or tetragonal precipitates in MgO -partially stabilized zirconia. However, strain considerations must also be taken into account in the formation of the SAMVP. When two variants are growing back to back, their shape strain directions are opposite.

Considering the very large shear strain (16%) and volume increase (4%) accompanying the t-m phase transformation, very large stresses appear in the surrounding zones of transformed material.

Theses stresses might concentrate and build up to eventually stop the transformation, or they might also trigger the transformation of another neighboring system, providing certain crystallography relationships are respected. It is nevertheless worth noticing that the formation of SAMVP results in a very large reduction of long range overall shear strain, since shear in the variants of a pair are opposite and equal. This configuration is therefore very favorable from an energetical point of view.

In the case of zirconia, SAMVP are present all over the surface (Fig. 1). The orientation of the pairs will be discussed later on, but it is already worth noticing this mechanism seems to be the more favorable to accommodate stresses induced by the transformation. The different ways of accommodating stresses are discussed in the next part.

B. Martensite formation

It is worth noticing the first transformed zones present all the same relief after transformation, suggesting their orientation relationships are very similar. The junction planes of theses variants are all perpendicular to the surface (see Fig. 3, 4 or 5), so that the overall long range lateral stress is almost totally suppressed. Height variations are not restricted by the surface, so that these systems are the easiest to transform. When the transformation is propagating to the surrounding zones of the surface, due to higher stresses in the surrounding zones of the transformed regions, different crystallographical systems may be activated and transform. The relief change is consequently modified. Figure 6 provides an example of a very different orientation relationship to the surface, with two possible explanations for this. The first explanation could be related to a junction plane almost parallel to the surface, leading to a rippled surface, with much smaller height variations. However, higher residual stresses are expected in the surrounding areas in this case. The other possibility is the accommodation of deformation strain by slipping rather than twinning. It is not possible to conclude on this particular point without further local crystallographic informations.

The spatial distribution of the SAMVP at the surface is more complex. Several situations might be observed indeed. Either the SAMVP might run through the entire grain, as shown in Fig. 3, or they might also stop at the middle of the grain, and a system with a different orientation is activated, as shown in Fig. 4. Some more complex structures between these two situations might be found.

As far as the location of the variants is concerned, AFM allows the observation of very interesting features. The transformation was never initiated away from the grain boundaries, i.e. in the middle of a grain, as this would be energetically too highly unfavorable. SAMVP almost always appear at grains triple junction at first. It can be seen (Fig. 7), the transformation was indeed initiated at the triple junction before propagating to the rest of the grain. This might be interpreted by taking into account residual stress effects. It was shown [START_REF] Gremillard | Microstructural study of silica-doped zirconia ceramics[END_REF] that residual stresses resulting from material processing concentrate at grains triple junction. As compared to other regions, these sites will act as preferential nucleation sites.

The top shape of SAMVP is of prime interest. Differences are observed between Ce-TZP and Y-TZP. In the case of Y-TZP, the junction of variant parts of a pair is always very sharp (Fig. 3 and4). In the case of Ce-TZP, some large flat untransformed zones might be observed (Fig. 2, 5 and9) at the junction. Since the surface of theses zones seems to be unmodified, it is reasonable to suggest they are not transformed indeed, inasmuch as this effect may be explained by the PTMC. In fact, it was shown the formation of SAMVP was a sequential process. The variants did not form all at once, and even the formation of a single variant is a sequential process. If the two variants of the pair might grow back to back, with a symmetric relief with respect to the surface, a remaining part of tetragonal phase of triangular shape is left in-between, as schematically shown in Fig. 8. When the variants are growing, stresses might add up in these untransformed zones (depending on the crystallographic relationships) until everything is transformed (Fig. 3 and4). However, it is also possible theses stresses, if present, become so high that the transformation cannot proceed anymore [START_REF] Bateman | Tranverse twins in magnesia partially stabilized zirconia (Mg-PSZ)[END_REF][START_REF] Rhüle | TEM Studies on phases and phases stabilities of zirconia ceramics[END_REF] . The observed differences between Ce-TZP and Y-TZP could be explained by the differences in grain size and in crystallographic parameters.

The sequential growth of a SAMVP is illustrated in Fig. 10. The same zone of the grain was observed at two different stages of the transformation, and it might be seen the variant pair did indeed grew in height (about 10 nm) and in length. The two triangles indicate the end of the junction plane, and the distance in-between shows an increase of about 50 nm in length. This is another clear evidence that even a single pair is formed via a sequential progression.

Once some variants are formed, lots of stresses are accumulated, and the system will try to reduce its overall energy. Several strategies are possible for this. The first one is to trigger the transformation of a neighboring system, as previously mentioned. This is indeed the main mechanism observed for stress relaxation and accommodation in zirconia. However, the two systems must satisfy certain crystallographic relationships for the transformation to proceed. In the more favorable case, some coherency is found between two adjacent grains and SAMVP running from one grain to the other one might be observed, as shown in Fig. 11. Though the grain boundary thermal groove is disturbing the surface homogeneity of the pairs, the relationship between the SAMVP of the two adjacent grains is obvious. This is however a very rare occurrence in these materials, and very few transgranular martensite laths might be observed.

In a more general manner, if no specific crystallographic correspondences are found, the grain will have to accommodate all the strain when the transformation is propagating, by modifying the spatial arrangement of the SAMVP; this is particularly obvious (Fig. 5 and12) in Ce-TZP. A system of large SAMVP is usually formed in the grain, occupying almost its entire surface. To transform the remaining parts of the grain and accommodate the strain at the same time, some smaller systems of SAMVP could be formed around, so that the resulting stresses and strains are much lower than those of larger SAMVP. A lot of these small pairs might be observed along the grain boundaries.

Finally, if no correspondence is found between two grains or two parts of a single grain, the combination of the very limited plasticity of zirconia, and the apparition of very large shear strains and stresses might lead to the formation of microcracking at the end of SAMVP. This is illustrated in Fig. 13. Thermal etching was not performed on this sample, so that there is no risk for the observed microcrack to be mistaken with a grain boundary thermal groove. The S-shaped microcrack is running across the entire micrograph. Its shape also eliminates the possibility for this artifact of being a residual polishing scratch. In all the phenomenological models developed [START_REF] Yoshimura | Role of H 2 O on the degradation process of Y-TZP[END_REF][START_REF] Sato | Transformation of yttria-doped tertragonal ZrO2 polycrystals by annealing in water[END_REF] to explain the t-m phase transformation of zirconia, the formation of microcracks and macrocracks as a consequence of the transformation plays a major role in the propagation of the transformation.

However, these cracks were never clearly observed in the surroundings zones of transformed regions. The observations reported here provide therefore strong evidence supporting these models.

C. Relationships with the system crystallography

One of the great improvements of using AFM as compared to conventional observation methods is that it can provide 3D measurements at a nanometer scale. The lateral resolution (as low as 0.1 nm) and vertical resolution (0.01 nm) provide very reliable quantitative measurements of surface relief characteristics. For example, a precision better than 0.2° might be reached when measuring angles between planes, providing the image was acquired in good conditions, i.e. principally a probe with a radius of curvature [START_REF] Sedin | Influence of tip size on AFM roughness measurements[END_REF] as low as possible, typically 10 nm for the best probes used here. 3D information's are nevertheless not necessary to measure angle relationships between SAMVP junction planes. In all of the observations, junction planes were always found to be either parallel or perpendicular. In regards of the original crystallographic structure (tetragonal), this is an excellent agreement with the theory, since two planes of the tetragonal cell are crystallographically equivalent, so that they might equally transform.

IV. CONCLUSIONS

AFM has been used here for the first time to investigate precisely and qualitatively the surface characteristics of martensitic transformation in zirconia. It was shown that all the features observed here could be explained by the PTMC. The formation of SAMVP was observed. The different ways of accommodating locally the strain, i.e. SAMVP formation, system of small SAMVP formation and microcracking were observed and discussed. As far as SAMVP formation conditions are concerned, it was shown that grains triple junction appear as preferential nucleation sites.

Differences in martensitic surface relief between Ce-TZP and Y-TZP could be explained by differences in grain size.

With its unique lateral and vertical resolution, the possibility of observing bulk samples (as compared to thin foils used for transmission electron microscopy) and ease of image interpretation due to the absence of a specific interaction between the probe and the surface of zirconia, AFM appears as a unique and extremely powerful tool to investigate martensitic transformation.

FIG. 5 .FIG. 7 .FIG. 8 .

 578 FIG. 1. Image of polishing scratches shear (arrows) after martensitic transformation in Ce-TZP.

FIG. 9 .

 9 FIG. 9. Triangular untransformed zones in self accommodating martensitic variant pairs in Ce-TZP (left). A detailed zone is shown (right).

ACKNOWLEDGMENTS

The authors would like to thank the CLAMS for using the nanoscope. The authors are also indebted to Pr. Guenin and Pr. Morin for their very fertile discussions on the subject. ‡ Corresponding author: sylvain.deville@insa-lyon.fr, tel: +33 4 72 43 63 57, fax: +33 4 72 43 85 28.


Bertrand Chambion

Christophe Gaschet

Thibault Behaghel

Aurélie Vandeneynde

Stéphane Caplet

Stéphane Gétin

David Henry

Emmanuel Hugot

Wilfried Jahn

Simona Lombardo

Marc Ferrari

Curved sensors for compact high-resolution wide field designs: prototype demonstration and optical characterization

Keywords: Curved sensors, Detectors, Arrays, Imaging systems, Optical design, Petzval Field Curvature, High resolution, Compact, Photography, Mechanical limits, Aberrations, Field of view, Electro-optical characterization

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

In recent years, there has been an increasing interest and demand for curved focal plane for imaging systems. By using a curved focal plane, significant size and optical benefits have been demonstrated for multiple applications, as defense, military, astronomical, consumer applications. In this paper, we propose an entire methodology and development, from curved packaging process to prototype, equipped with a curved CMOS image sensor, including mechanical and optical modeling, electro-optical characterization, opto-mechanical design, assembly and test compared to a standard optical system. This new compact architecture, specifically designed for curved sensor, providing high resolution without aspheric surfaces and demonstrate the capacity of curved sensors to reduce the complexity of any optical system.

CURVED SENSORS: IMPROVED ABERRATION CORRECTION 2.1 History

Bioinspired optics is an emerging field for learning the strategies from nature and leading to better solutions. In optical imagery, the most famous natural strategy is to curve the optical focal plane. In fact, all animal eyes have a curved retina, to compare with no commercial camera with curved silicon sensor. The discovery of the Petzval Field curvature by Joseph Petzval, nearly 180 years ago, shows the first human interest for curved focal plane: an object plane through lenses gives a curved image surface, depending of refractive index and diopters curvatures. This aberration is called "Petzval Field Curvature", which can be expressed by the Petzval sum (1):

     i i i i i sum n n r n n Petzval 1 1 (1)
Where n is the refractive index of the incident and refractive medium, r is the radius of curvature of the considered diopter. Usually, the correction of this aberration is done by the use of divergent elements called "field flatteners", discovered by Charles Piazzi Smyth in 1875 [START_REF] Ray | Applied Photographic Optics[END_REF], which minimize drastically the Petzval sum to coincide with a flat sensor. The second interest was the discovery made by Thomas Sutton in 1860, with the monocentric system, or concentric system [START_REF] Sutton | Panoramic Photography[END_REF]. In this system, all optical surfaces are spherical and share the same center of curvature, and with this symmetry, multiple aberrations as the coma and astigmatism are cancelled out. This is an aberration free design and will be our optical design starting point (section 3). And the third technology with an interest for sensor's curvature was the Schmidt telescope which provide wide field of view, limited aberrations with a curved detector [START_REF] Lemaitre | Astronomical Optics and Elasticity Theory: Active Optics Methods[END_REF]. For all these discoveries, the use of curved sensors was possible but limited. In fact, the solid photographic plate used in the 19th centuries was too delicate for a commercial purpose. And with the patent of Hannibal Goodwin in 1887 [START_REF] Goodwin | Photographic pellicle and process of producing same[END_REF], flexible photographic films have been used. Since the launch of silicon industry, image sensors has been limited to flat and rigid. But some recent developments show a new interest for curved sensors. Firstly, there are several developments on the fabrication of curved sensors. For the monolithic approach, the fabrication has been demonstrated on uncooled and cooled infrared sensors, for very compact high-performance camera [START_REF] Dumas | Curved focal plane detector array for wide field cameras[END_REF], Charge Couple Device (CCD) [START_REF] Andanta | CCD product datasheet[END_REF], or Complementary Metal Oxide Semiconductor (CMOS) [START_REF] Itonaga | A Novel Curved CMOS Image Sensor Integrated with Imaging System[END_REF][START_REF] Guenter | Highly Curved Image Sensors: A Practical Approach for Improved Optical Performance[END_REF]. None are in industrial production. Secondly, there are also some developments on optical improvements of optical systems with curved sensors, on optical advantages, for instance on camera-phone [START_REF] Reshidko | Optical Analysis of Miniature Lenses with Curved Imaging Surfaces[END_REF], or astronomical applications [START_REF] Hugot | Flexible focal plane arrays for UVOIR wide field instrumentation[END_REF], and also on the simplification of optical systems by reducing weight, volume or number of lenses [START_REF] Stamenov | Optimization of Two-Glass Monocentric Lenses for Compact Panoramic Imagers: General Aberration Analysis and Specific Designs[END_REF]. A study on telescope combining free-form optics and curved detectors showed also a better field of view and f number [START_REF] Muslimov | Combining Freeform Optics and Curved Detectors for Wide Field Imaging: A Polynomial Approach over Squared Aperture[END_REF].

Curved packaging and process

This work is based on the commercial product 1/1.8'' format 1.3Mpx global shutter CMOS sensor (Teledyne EV76C560) [13]. The standard sensor structure basically consists of a silicon die (7.74 x 8.12 mm), glued on a ceramic package. Electrical connections are wire bonded from the die to the package surface and then, to the interconnection board thanks to a reflow process. On top, a glass cover is placed to prevent from mechanical or environment solicitations. This structure is shown in figure 1. In order to implement a spherically shaped CMOS sensor, changes are required to adapt this standard structure. First, the sensor is thinned with a grinding equipment to a targeted thickness in order to make the sensor mechanically "flexible". It can be followed by a Chemical Mechanical Polishing (CMP). In this work the targeted thickness is 100µm. The bendable capabilities of the CMOS sensor will be detailed in section 2.4. Then, that thinned chip is glued (structural attachment) onto a curved substrate. The CMOS final shape is drove by the substrate. Wire bonding process, developed for electrical connections, is also optimized in order to prevent damages on thinned dies. Figure 2 shows a schematic of the final packaging, curved into its commercial packaging. The radius of curvature is R=65mm.

Associated mechanical modeling

Mechanical considerations of the curved sensors are an important part to develop optical system design and find curving limitation for the sensor. For an analytical analysis, the shell theory has been used to model the mechanical behavior of the semiconductor die. This analytical model is presented in [START_REF] Timoshenko | Theory of Plates and Shells[END_REF]. The mechanical behavior has been also modeled, using ANSYS ® Finite Element Analysis (FEA) software. For this study, extensive simulation were conducted on 7.74 x 8.12 mm (100)-oriented silicon chip with specific quadrangle elements are used, defined by 4 nodes, 6 degrees of freedom each (SHELL 181 elements). Using these elements, the principle stress values on the bottom, middle and top surfaces of the plate are obtained. Based on a breakage ball on ring study and curved packaging work [START_REF] Guenter | Highly Curved Image Sensors: A Practical Approach for Improved Optical Performance[END_REF][START_REF] Zhao | Experimental evaluations of the strength of silicon die by 3-point-bend versus ball-on-ring tests[END_REF] on silicon square plates with different grinding, polishing, and sawing processes, two tensile failure strength criterions has been defined: S1max1 = 200MPa, which refers to a standard grinding and sawing, and S1max2= 500MPa, associated to CMP process and standard sawing.

The parameters are the thickness t of the plate with a range value from 25 to 125 µm and its radius of curvature. The die was discretized into approximately 5000 elements. For silicon mechanical data, the following reduced stiffness coefficient matrix is used, with only three independent elastic coefficients: where c11 = 165.7GPa, c12 = 63.9GPa, c44 = 79.6 GPa [START_REF] Mason | Physical Acoustics and the Properties of Solids[END_REF]. The minimum allowable radius of curvature are extracted from the FEA results for both tensile failure strength criterions. Results of the minimum allowable radius of curvature are plotted on figure 3.

                    
With this two failure criterions methodology, three areas are defined: the safe area without any breakage risk with a standard grinding and sawing (S1< S1max1), a forbidden area where the intrinsic silicon mechanical limits are over (S1> S1max2), and a in between zone for processes optimizations. With our targeted thickness of 100 µm, and considering our thinning process, we expect a minimum allowable radius of curvature Rc min=32 mm before silicon breakage. According to a progressive shaping of a flat plate onto a spherical surface with a free edge boundary conditions curving process, there are two die mechanical behavior: the bi-axial tensile stress is first established in all the die for low level of radius of curvature (+inf. <Rc<60mm), and then, tangential compressive stress zones appears at the edges of the die near the center of each of the four edges (Rc<60mm). This uniaxial compression field could be the origin of a buckling effect as shown in a previous study on cooled IR sensor [START_REF] Chambion | Tunable curvature of large visible CMOS image sensors : Towards new optical functions and system miniaturization[END_REF][START_REF] Tekaya | Mechanical behavior of flexible silicon devices curved in spherical configurations[END_REF] and due to a load-deflection response for thin-walled structures. While curving, these two behaviors are presented in figure 4a. For illustration, the tensile stress distribution (S1) of a 7.74 x 8.12 x 0.1 mm silicon plate, curved at Rc=65mm is presented in Figure 4b. For this level of curvature, all the die is in tensile stress with a maximum bi-axial stress at the die center (201MPa) and the middle of each edges at 45MPa.

Figure 4: a) Two mechanical behaviors illustration for compression stress field generation at the middle of each edges while curving. Results of the parametric study conducted for 7.74 x 8.12 mm (100)-oriented silicon chip in spherical shape Rc=65mm. Note that all the in plane stress is tensile, even the middle of each die edges.

Experimental assessment

In order to validate our simulation model accuracy, bendable capability tests have been conducted on 16 representative (100) bulk silicon samples, thinned at 100µm. The experimental setup is based on a 3D printed spherical molds (Rc from 90 to 20 mm with 5 mm steps), made up of two parts, one convex, concave for the other. The sample is placed in-between these 2-part mold and a 0.8 bar pressure is applied to force the shaping of the sample. The results is binary: breakage or not breakage of the sample. The results are summarized in Figure 5 and compared to simulated limits presented before in section 2.3 assuming S1max2. Considering an 80% cumulative frequency, a minimum allowable radius of curvature is experimentally found at Rc min = 35 mm. Figure 5: Experimental bendable capabilities conducted on 7.74 x 8.12 x 0.1 mm (100)-oriented silicon chip in spherical shape and associated tensile stress limit at S1max2= 500MPa. This study shows a minimum allowable radius of curvature at Rc min = 35 mm (80% of cumulative frequency).

We first show a good accordance between measured (Rcmin, exp= 35 mm) and model results (Rcmin, model= 32 mm). It illustrates that our FEM model gives a good prediction of the strains for silicon dies. Then, some sample broke below the simulated limit. It could be explained by a non-perfect shaping of the samples in the mold during experimental test. Another explanation could be the ultimate tensile strength value considered in the model. GENTER [START_REF] Guenter | Highly Curved Image Sensors: A Practical Approach for Improved Optical Performance[END_REF] has shown that for silicon plate, and for spherical shaping, the maximum ultimate tensile stress could be over 500MPa before breakage.

Electro-optical response

An important point to address is the curvature influence on the sensor functionality. Due to tensile or compressive stresses applied on the CMOS active layers, the electro-optical response of the CMOS stack could be modified. One of the most important parameter is the dark current: The dark current is the slope of the dark signal as a function of the integration time, in obscurity. Commercial flat sensors and curved one (Rc = 65mm) have been tested. For commercial sensors, and stabilized à 25°C, we recorded a dark current at 450 electrons per second (e -/s). We did the same for curved samples and a 458 e -/s is found. Dark noise (e -) and coefficient conversion (DN/e -) have been also measured. Values are summarized in table 1. Results on curved sensor show a standard response compared to flat sensor. In order to quantify the stress map onto the sensor response, dark current, noise, and conversion coefficient maps are plotted in table 2 for flat sensor and for curved sensor at Rc=65 mm. for each map, we calculated average values every 20x16 pixels clusters. No stresses maps signatures are visible. With all of these measurements, we can confirm that within (+inf.; 55mm) radius of curvature range, curving process has no significant impact on the Teledyne EV76C560 chip electro-optical response.

Measured on commercial sensor

Curved sensor at

PROTOTYPE CAMERA DESIGN DEVELOPEMENT

Monocentric lens optimization

In this part, the objective is to obtain an innovative simpler architecture specifically adapted to the curved technology. As presented in section 2.1, one architecture with curved sensor already exists: the monocentric system. This system combines compactness, wide Field of View (more than 120°), high resolution and large light collection [START_REF] Stamenov | Optimization of Two-Glass Monocentric Lenses for Compact Panoramic Imagers: General Aberration Analysis and Specific Designs[END_REF]. But the technical problem of this monocentric system is the highly curved focal plane. For example, in order to address an 80° FOV with a 2 glasses monocentric system, a sensor with a size of 15.4 mm and with a radius of curvature of 12 mm is required. According to mechanical limits presented 2.3, it is impossible to curve so much the sensor without breaking it, even if it is thinned down to 10 microns. We have studied modifications on this monocentric system to provide an optical system in accordance with the sensor mechanical limits. One possibility in order to have a feasible system is described as follows. Light emerging from the monocentric system can have a large chief ray angle when the system has a wide field of view. This large angle can be problem in order to have a less curved sensor. By placing convergent lenses after the monocentric block, we can control this angle, as we can see in the figure 6a. Divergent lenses (figure 6b) are placed after convergent lenses in order to correct aberrations like the Petzval field curvature of the system and also those added by convergent lenses and the loss of the optical symmetry. The loss of symmetry interacts with monocentric block and also the aperture position. For the aperture position, one of the best positions is in front of the lens (figure 7). In fact, placing the aperture stop after convergent lenses can reduce the field of view of the system. And the monocentric block is no longer symmetric, becoming just a convergent lens. In this way, we founded a new optical design based on this architecture. The first-order proprieties of this new optical architecture are as follow. We considered different designs with a focal length between 8 and 16mm, with a corresponding sensor format between 1/2"and 2/3". With these sensor's formats, we obtain a large Field of View (FOV), between 40° and 50°, for these equivalent focal lengths, around 50-60mm. These sensors are thinned down to 100 μm and curved at a radius of curvature between 50 and 86 mm compatible with the safe area presented in section 2.3. This new architecture provides a great compactness and a high resolution for a design without aspheric surfaces: 24 mm in axial length from stop aperture to the sensor. This architecture is made for low cost applications, when high resolution and compactness are needed.

Figure 7: Schematic representation of CEA-Leti unsymmetrical monocentric based optical system equipped with a spherically curved image sensor.

Final optical system performances

We specifically optimized a system with 12 mm focal length, a 1/1.8" sensor bended at -65mm, a 2.6 f/# and a FOV of 42°. In order to characterize optical performances of this optical system, the polychromatic Modulation Transfer Function (MTF) was calculated in Zemax lens design software for different fields and compared to an equivalent commercial design (Techspec® high resolution fixed focal length lens #63-779) with a flat sensor Teledyne EV76C560 with the same focal, field of view, resolution, and Working Distance (WD) of 2 meters.

As the final objective of the optical study is to show an important optical system size reduction of an existing one, our design shows at 0° field a very good performance with an MTF of about 73% at 100 cycles/mm, as commercial one performance. For the maximal field, the MTF is over 65% at 100 cycles/mm, compared to 55% for the commercial one. It shows that curved technology helps optical design to enhance image quality over the field. Optical performances comparisons (MTF) are plotted in figure 8.

PROTOTYPE DEMONSTRATION 4.1 Mechanical mounting

Opto-mechanical design is a key step in optical system development. It has to be easy to mount and align lenses, with high precision machining, within optical tolerances. As our prototype is a fixed focal system, we choose to design a 1part cylindrical mechanical holder with increasing diameter values along the optical axis to align and glue each lens, from L1 to L6. Several radial holes are drilled for each optical block to make the gluing step easier with standard optical glues. The material used is aluminum and the internal mechanical tolerance on diameters is +-5µm. Drawings are presented in figure 10.

Prototype specifications and comparison to existing system

The final prototype is built on the commercial 1/1.8" format Teledyne EV76C560 CMOS image sensor evaluation kit.

Basically, the standard flat sensor has been replaced by a curved-one, packaged as described in section 2.2. The radius of curvature of the sensor is R=65 mm and the opto-mechanical part is aligned and linked to the sensor thanks to a standard plug.

In order to make a performance comparison to an existing system, a Techspec® high resolution fixed focal length lens #63-779 commercial optical system has been mounted on the same evaluation kit with flat sensor. In figure 11, systems comparison views are proposed to highlight the high level of simplification we can reach by using a curved sensor. The main gain is the length reduction. Both design are the same optical performances (describes in figure 9), but the use of curved sensor allow to drastically simplify the optical part and bring technical advantages:

 Reduction of the total length of the system (x2.5)

 Saving lenses (40%)  Make the system easier to assemble (less lenses to align)

All of the optical and physical specifications are summarized in table 3. Table 3: Optical and physical characteristics comparison between commercial design and CEA-Leti Design with curved sensor.

Preliminary optical tests

In order to characterize the optical performances, images from both systems have been captured and data analysis is in progress to extract and compared optical key parameters such as MTF or relative illumination. Also, a demonstration mockup has been presented on CEA-LETI booth during Photonics West 2018 conference to demonstrate the huge interest of curved technology for imaging systems.

CONCLUSION

Curved sensor technology is a disruptive approach for a number of scientific fields including photography, videography, computer vision and automation, surveillance imaging, microscopes, and telescopes, among others. Using a curved sensor can improve performances: considering equivalent optical performances, curved technology can reduce the system size, remove lenses, and reduce cost and complexity of an existing system. In this paper, a fully functional prototype of optical design using curved sensor is presented with a detailed following methodology: curved packaging technology with a free edge bending process and sensor mechanical limits investigation, curved sensor integration in standard package, electro-optical characterization, and optical design using Zemax ® tool, opto mechanical design with lenses integration and optical performances comparison to an existing commercial design. Using our free edge bending process, we have created a prototypes of curved 1/1.8" format CMOS sensor bended at Rc=65mm and 55mm into its standard package, without any electro-optical response modifications. This process is compatible with any sensor size and large scale manufacturing processes. On a f/2.6 12 mm focal length system with a 1/1.8" format sensor (Teledyne EV76C560), using our curved technology, we demonstrate an impressive simplification of the optical system (-40% of lenses) and a huge reduction of the total length by 2.5 time for the same optical performances. The finality of this work was a functional prototype demonstration on the CEA-LETI booth during Photonics West 2018 conference.

Figure 1 :

 1 Figure 1: a) Commercial Teledyne EV76C560 flat sensor. b) Associated schematic view along A-A' axis.

Figure 2 :

 2 Figure 2: a) Curved Teledyne EV76C560 sensor (R=65mm). b) Associated schematic view along B-B'' axis.

Figure 3 :

 3 Figure 3: Modeling results on 7.74 x 8.12 mm (100)-oriented silicon chip in spherical shape, considering two failure criterions, S1max1 = 200MPa and S1max2= 500MPa.

Figure 6 :

 6 Figure 6: a) Control of the exiting light angle from the monocentric block with a convergent lens. b) Control of aberrations with a divergent lens.

Figure 8 :

 8 Figure 8: a) Simulated MTF of the CEA LETI Optical design. b) Simulated MTF of Techspec® lens #63-779.

Figure 10 :

 10 Figure 10: Schematic views of our opto-mechanical holder. a) Cross section. b) 3D view.

Figure 11 :

 11 Figure 11: Optical system comparison: a) commercial system and b) CEA-Leti equivalent performances prototype equipped with curved sensor. Curved sensor leads a x2.5 total length reduction.

Table 1 :

 1 Experimental tests on electro-optical response of flat and curved Teledyne EV76C560 CMOS image sensor at 25°C (considering +7.5%.°C -1 for dark current).

	=65mm	Rc	Difference

Table 2 :

 2 Response maps comparison on dark current, noise, and conversion coefficient. Average values every 20x16 pixels clusters. (Dark current values are extrapolated to 25°C considering +7.5%.°C -1 ).

AKNOWEDGMENTS

This activity was partially funded by the French Research Agency (ANR) under the LabEx FOCUS ANR-11-LABX-0013, and the European Research Council through the H2020-ERC-STG-2015-678777 ICARUS program.


Olivier Bernardi
email: olivier.bernardi@gmail.com

Marc Noy
email: marc.noy@upc.edu

Dominic Welsh
email: dwelsh@maths.ox.ac.uk

On the growth rate of minor-closed classes of graphs

 shows that for all minor-closed class G, there is a constant c such that g n ≤ c n n!. Our main results show that the growth rate of g n is far from arbitrary. For example, no minor-closed class G has g n = c n+o(n) n! with 0 < c < 1 or 1 < c < ξ ≈ 1.76.

Introduction

In 1994, Scheinerman and Zito [START_REF] Scheinerman | On the size of hereditary classes of graphs[END_REF] introduced the study of the possible growth rates of hereditary classes of graphs (that is, sets of graphs which are closed under isomorphism and induced subgraphs). Here we study the same problem for classes which are closed under taking minors. Clearly, being minor-closed is a much stronger property than to be hereditary. However, many of the more structured hereditary classes such as graphs embeddable in a fixed surface or graphs of tree width bounded by a fixed constant are minor-closed and the possible growth rates attainable are of independent interest.

A broad classification of possible growth rates for hereditary classes given by Scheinermann and Zito [START_REF] Scheinerman | On the size of hereditary classes of graphs[END_REF] is into four categories, namely constant, polynomial, exponential and factorial. This has been considerably extended in a series of papers by Balogh, Bollobas and Weinrich [START_REF] Bolagh | The speed of hereditary properties of graphs[END_REF][START_REF] Bolagh | The penultimate range of growth for graph properties[END_REF][START_REF] Bolagh | A jump to the Bell number for hereditary graph properties[END_REF] who use the term speed for what we call growth rate.

A first and important point to note is that if a class of graphs is minor-closed then it is hereditary. Hence, in what follows we are working within the confines described by the existing classifications of growth rates of hereditary classes. Working in this more restricted context, we obtain simpler characterization of the different categories of growth rate and simpler proofs. This is done in Section 2. In Section 3, we establish some results about the possible behaviour about classes in the most interesting range of growth rates, namely the factorial range. We conclude by listing some open questions in Section 4.

A significant difference between hereditary and minor-closed classes is due to the following recent result by Norine et al. A class is proper if it does not contain all graphs.

Theorem 1 (Norine et al. [START_REF] Norine | Proper minor-closed families are small[END_REF]). If G is a proper minor-closed class of graphs then g n ≤ c n n! for some constant c.

Remark. In contrast, a hereditary class such as the set of bipartite graphs can have growth rate of order 2 cn 2 with c > 0.

We close this introduction with some definitions and notations. We consider simple labelled graphs. The size of a graph is the number of vertices; graphs of size n are labelled with vertex set {1, 2, . . . , n}. A class of graphs is a family of labelled graphs closed under isomorphism. For a class of graphs G, we let G n be the graphs in G with n vertices, and we let g n = |G n |. The (exponential) generating function associated to a class G is G(z) = n≥0 gn n! z n . The relation H < G between graphs means H is a minor of G. A family G is minor-closed if G ∈ G and H < G implies H ∈ G. A class is proper if it does not contain all graphs. A graph H is a (minimal) excluded minor for a minor-closed family G if H ∈ G but every proper minor of H is in G. We write G = Ex(H 1 , H 2 , • • • ) if H 1 , H 2 , . . . are the excluded minors of G. By the theory of graph minors developed by Robertson and Seymour [START_REF] Robertson | Graph minors I-XX[END_REF], the number of excluded minors is always finite.

A classification theorem

Our classification theorem for the possible growth rate of minor-closed classes of graphs involves the following classes; it is easy to check that they are all minor-closed.

• P is the class of path forests: graphs whose connected components are paths.

• S is the class of star forests: graphs whose connected components are stars (this includes isolated vertices).

• M is the class of matchings: graphs whose connected components are edges and isolated vertices.

• X is the class of stars: graphs made of one star and some isolated vertices.

Theorem 2. Let G be a proper minor-closed family and let g n be the number of graphs in G with n vertices.

1. If G contains all the paths, then g n has factorial growth, that is, n! ≤ g n ≤ c n n ! for some c > 1;

2. else, if G contains all the star forests, then g n has almost-factorial growth, that is, B(n) ≤ g n ≤ ǫ n n! for all ǫ > 0, where B(n) is the n th Bell number;

3. else, if G contains all the matchings, then g n has semi-factorial growth, that is,

a n n (1-1/k)n ≤ g n ≤ b n n (1-1/k)n
for some integer k ≥ 2 and some a, b > 0;

4. else, if G contains all the stars, then g n has exponential growth, that is, 2 n-1 ≤ g n ≤ c n for some c > 2;

5. else, if G contains all the graphs with a single edge, then g n has polynomial growth, that is, g n = P (n) for some polynomial P (n) of degree at least 2 and n sufficiently large;

6. else, g n is constant, namely g n is equal to 0 or 1 for n sufficiently large.

Remark. As mentioned in the introduction, some of the results given by Theorem 2 follow from the previous work on hereditary classes. In particular, the classification of growth between pseudo factorial (this includes our categories factorial, almost-factorial and semifactorial), exponential, polynomial and constant was proved by Scheinerman and Zito in [START_REF] Scheinerman | On the size of hereditary classes of graphs[END_REF].

A refined description of the exponential growth category was also proved in this paper (we have not included this refinement in our statement of the classification Theorem 2 since we found no shorter proof of this result in the context of minor-closed classes). The refined descriptions of the semi-factorial and polynomial growth categories stated in Theorem 2 were established in [START_REF] Bolagh | The speed of hereditary properties of graphs[END_REF]. Finally, the jump between the semi-factorial growth category and the almost-factorial growth category was established in [START_REF] Bolagh | A jump to the Bell number for hereditary graph properties[END_REF]. The rest of this section is devoted to the proof of Theorem 2. This proof is self-contained and does not use the results from [START_REF] Scheinerman | On the size of hereditary classes of graphs[END_REF][START_REF] Bolagh | The speed of hereditary properties of graphs[END_REF][START_REF] Bolagh | The penultimate range of growth for graph properties[END_REF][START_REF] Bolagh | A jump to the Bell number for hereditary graph properties[END_REF]. We begin by the following easy estimates. We recall that log

(n!) = n log(n) + O(n), log B(n) = n log(n) -n log(log(n)) + O(n) and log(n!!) = n log(n)/2 + O(n).
Proof. 1. The number of path forests of size n ≥ 2 made of a single path is n!/2; the number of path forests of size n ≥ 2 made of an isolated vertex and a path is n!/2. 2. A star-forest defines a partition of [n] := {1, 2, . . . , n} (together with some marked vertices: the centers of the stars) and the partitions of [n] are counted by the Bell numbers B(n). 3. The vertex n of a matching of size n can be isolated or joined to any of the (n -1) other vertices, hence

|M n | ≥ |M n-1 | + n|M n-2 |. The property |M n | ≥ n!! follows by induction.
4. The number of stars for which 1 is the center of the star is 2 n-1 .

Proof of Theorem 2

• The lower bound for classes of graphs containing all paths follows from Lemma 3 while the upper bound follows from Theorem 1.

• The lower bound for classes of graphs containing all the star forests but not all the paths follows from Lemma 3. The upper bound is given by the following Claim (and the observation that if a class G does not contain a given path P , then G ⊆ Ex(P )). Claim 4. For any path P , the growth rate of Ex(P ) is bounded by ǫ n n n for all ǫ > 0.

The proof of Claim 4 use the notion of depth-first search spanning tree (or DFS tree for short) of a graph. A DFS tree of a connected graph G is a rooted spanning tree obtained by a depth-first search algorithm on G (see, for instance, [START_REF] Cormen | Introduction to algorithms[END_REF]). If G is not connected, a choice of a DFS tree on each component of G is a DFS spanning forest. We recall that if T is a DFS spanning forest of G, every edge of G which is not in T joins a vertex of T to one of its ancestors (see [START_REF] Cormen | Introduction to algorithms[END_REF]).

Proof. Let P be the path of size k. Let G be a graph in Ex(P ) and let T be a DFS spanning forest of G. We wish to bound the number of pairs (G, T ) of this kind.

• First, the height of T is at most k -1 (otherwise G contains P ). The number of (rooted labelled) forests of bounded height is at most ǫ n n n for all ǫ > 0; this is because the associated exponential generating function is analytic everywhere and hence has infinite radius of convergence (see Section III.8.2 in [START_REF] Flajolet | Analytic combinatorics[END_REF]).

• Second, since T is a DFS spanning forest, any edge in G which is not in T joins a vertex of T to one of its ancestors. Since the height of T is at most k -1, each vertex has at most k ancestors, so can be joined to its ancestors in at most 2 k different ways. This means that, given T , the graph G can be chosen in at most 2 kn ways, and so the upper bound ǫ n n n for all ǫ > 0 holds for the number of pairs (G, T ).

• We now consider minor-closed classes which do not contain all the paths nor all the star forests. Given two sequences (f n ) n∈N and (g n ) n∈N , we write f n ≍ exp g n if there exist a, b > 0 such that f n ≤ a n g n and g n ≤ b n f n . Observe that if G contains all the matchings, then g n ≥ n!! ≍ exp n n/2 by Lemma 3. We prove the following more precise result.

Claim 5. Let G be a minor-closed class containing all matchings but not containing all the paths nor all the star forests. Then, there exists an integer k ≥ 2 such that g n ≍ exp n (1-1/k)n .

Remark. For any integer k ≥ 2, there exists a minor-closed class of graphs G such that g n ≍ exp n (1-1/k)n . For instance, the class G in which the connected components have no more than k vertices satisfies this property (see Lemma 7 below).

Proof. Let G be a minor-closed class G containing all matchings but not a given path P nor a given star forest S. We denote by p and s the size of P and S respectively. Let F be set of graphs in G such that every vertex has degree at most s. The following lemma compares the growth rate of F and G. Lemma 6. The number f n of graphs of size n in F satisfies f n ≍ exp g n .

Proof. Clearly f n ≤ g n so we only have to prove that there exists b > 0 such that g n ≤ b n f n . Let c be the number of stars in the star forest S and let s 1 , . . . , s c be the respective number of edges of these stars (so that s = c + s 1 + . . . + s c ).

• We first prove that any graph in G has less than c vertices of degree greater than s. We suppose that a graph G ∈ G has c vertices v 1 , . . . , v c of degree at least s and we want to prove that G contains the forest S as a subgraph (hence as a minor; which is impossible). For i = 1 . . . , n, let V i be the set of vertices distinct from v 1 , . . . , v c which are adjacent to v i . In order to prove that G contains the forest S as a subgraph it suffices to show that there exist disjoint subsets S 1 ⊆ V 1 , . . . , S c ⊆ V c of respective size s 1 , . . . , s c . Suppose, by induction, that for a given k ≤ c there exist disjoint subsets

S 1 ⊆ V 1 , . . . , S k-1 ⊆ V k-1 of respective size s 1 , . . . , s k-1 . The set R k = V k -i≤k S i has size at least s -c -i<k s i ≥ s k , hence there is a subset S k ⊆ V k distinct from the S i , i < k of size s k . The induction follows. • We now prove that g n ≤ n c 2 cn f n .
For any graph in G one obtains a graph in F by deleting all the edges incident to the vertices of degree greater than s. Therefore, any graph of G n can be obtained from a graph of F n by choosing c vertices and adding some edges incident to these vertices. There are at most n c 2 cn f n graphs obtained in this way.

It remains to prove that f n ≍ exp n (1-1/k)n for some integer k ≥ 2. Let G be a graph in F and let T be a tree spanning of one of its connected components. The tree T has height less than p (otherwise G contains the path P as a minor) and vertex degree at most s. Hence, T has at most 1 + s + . . . + s p-1 ≤ s p vertices. Thus the connected components of the graphs in F have at most s p vertices. For a connected graph G, we denote by m(G) the maximum r such that F contains the graph consisting of r disjoint copies of G. We say that G has unbounded multiplicity if m(G) is not bounded. Note that the graph consisting of 1 edge has unbounded multiplicity since G contains all matchings. Lemma 7. Let k be the size of the largest connected graph in F having unbounded multiplicity. Then,

f n ≍ exp n (1-1/k)n .
Proof. • Let G be a connected graph in F of size k having unbounded multiplicity. The class of graphs consisting of disjoint copies of G and isolated vertices (these are included in order to avoid parity conditions) is contained in F and has exponential generating function exp(z + z k /a(G)), where a(G) is the number of automorphisms of G. Hence f n is of order at least n (1-1/k)n , up to an exponential factor (see Corollary VIII.2 in [START_REF] Flajolet | Analytic combinatorics[END_REF]).

• Let L be the class of graphs in which every connected component C appears at most m(C) times. Then clearly F ⊆ L. The exponential generating function for L is P (z) exp(Q(z)), where P (z) collects the connected graphs with bounded multiplicity, and Q(z) those with unbounded multiplicity. Since Q(z) has degree k, we have an upper bound of order n (1-1/k)n . This finishes the proof of Claim 5.

• We now consider the classes of graphs containing all the stars but not all the matchings. The lower bound for these classes follows from Lemma 3 while the upper bound is given by the following claim. Claim 8. Let M k be a perfect matching on 2k vertices. The growth rate of Ex(M k ) is at most exponential.

Proof. Let G be a graph of size n in Ex(M k ) and let M be a maximal matching of G. The matching M has no more than 2k -2 vertices (otherwise, M k < G). Moreover, the remaining vertices form an independent set (otherwise, M is not maximal). Hence G is a subgraph of the sum H n of the complete graph K 2k-2 and n -(2k -2) independent vertices. There are n 2k-2 ways of labeling the graph H n and 2 e(Hn) ways of taking a subgraph, where e(H n ) = 2k-2 2

+ (2k -2)(n -2k + 2
) is the number of edges of H n . Since n 2k-2 is polynomial and e(H n ) is linear, the number of graphs of size n in Ex(M k ) is bounded by an exponential.

• We now consider consider classes of graphs G containing neither all the matchings nor all the stars. If G does not contain all the graphs with a single edge, then either G contains all the graphs without edges and g n = 1 for n large enough or g n = 0 for n large enough. Observe that if G contains the graphs with a single edge, then g n ≥ n(n-1)

2

. It only remains to prove the following claim: Claim 9. Let G be a minor-closed class containing neither all the matching nor all the stars. Then, there exists an integer N and a polynomial P such that g n = P (n) for all n ≥ N .

Remark. For any integer k ≥ 2, there exists a minor-closed class of graphs G such that g n = P (n) where P is a polynomial of degree k. Indeed, we let the reader check that the class G of graphs made of one star of size at most k plus some isolated vertices satisfies this property.

Proof. Since G does not contain all matchings, one of the minimal excluded minors of G is a graph M which is made of a set of k independent edges plus l isolated vertices. Moreover, G does not contain all the stars, thus one of the minimal excluded minors of G is a graph S made of one star on s vertices plus r isolated vertices.

• We first prove that for every graph G in G having n ≥ max(s+r, 2k +l) vertices, the number of isolated vertices is at least n -2ks. Observe that for every graph G in G having at least s + r vertices, the degree of the vertices is less than s (otherwise, G contains the star S as a minor). Suppose now that a graph G in G has n ≥ max(s + r, 2k + l) vertices from which at least 2ks are not isolated. Then, one can perform a greedy algorithm in order to find k independent edges. In this case, G contains the graph M as a minor, which is impossible.

• Let M, S, H 1 , . . . , H h be the minimal excluded minors of G and let M ′ , S ′ , H ′ 1 , . . . , H ′ h be the same graphs after deletion of their isolated vertices. We prove that there exists N ∈ N such that G n = F n for all n ≥ N , where F = Ex(H ′ 1 , . . . , H ′ h ). Let m be the maximal number of isolated vertices in the excluded minors M, S, H 1 , . . . , H h and let N = max(s + r, 2k + l, 2ks + m). If G has at least N vertices, then G has at least m isolated vertices, hence G is in G if and only if it is in F.

• We now prove that there exists a polynomial P with rational coefficients such that f n ≡ |F n | = P (n). Let C be the set of graphs in F without isolated vertices; by convention we consider the graph of size 0 as being in C. The graphs in C have at most max(s + r, 2k + l, 2ks) vertices, hence C is a finite set. We say that a graph in G follows the pattern of a graph C ∈ C if C is the graph obtained from G by deleting the isolated vertices of G and reassigning the labels in {1, . . . , r} respecting the order of the labels in G. By the preceding points, any graph in F follows the pattern of a graph in C and, conversely, any graph following the pattern of a graph in C is in F (since the excluded minors M ′ , S ′ , H ′ 1 , . . . , H ′ h of F have no isolated vertices). The number of graphs of size n following the pattern of a given graph

C ∈ C is n |C| , where |C| is the number of vertices of C. Thus, f n = C∈C n |C| which is a polynomial.
This conclude the proof of Theorem 2.

Growth constants

We say that class G has growth constant γ if lim n→∞ (g n /n!) 1/n = γ, and we write γ(G) = γ.

Proposition 10. Let G be a minor-closed class such that all the excluded minors of G are 2-connected. Then, γ(G) exists.

Proof. In the terminology of [START_REF] Mcdiarmid | Random planar graphs[END_REF], the class G is small (because of Theorem 1), and it is addable because of the assumption on the forbidden minors. Hence, Theorem 3.3 from [START_REF] Mcdiarmid | Random planar graphs[END_REF] applies and there exists a growth constant.

We know state a theorem about the set Γ of growth constants of minor-closed classes. In what follows we denote by ξ ≈ 1.76 the inverse of the unique positive root of x exp(x) = 1.

Theorem 11. Let Γ be the set of real numbers which are growth constants of minor-closed classes of graphs.

1. The values 0, 1, ξ and e are in Γ.

If γ ∈ Γ then 2γ ∈ Γ.

3. There is no γ ∈ Γ with 0 < γ < 1.

4.

There is no γ ∈ Γ with 1 < γ < ξ.

Remarks. Before the proof of Theorem 11, we make the following remark. Let G be a minorclosed class, let C be the family of all connected members of G, and let G(z) and C(z) be the corresponding generating functions. Then if C has growth constant γ, so does G. This is because the generating functions G(z) is bounded by exp(C(z)) (they are equal if the forbidden minors for G are all connected), and both functions have the same dominant singularity.

Proof. 1) • All classes whose growth is not at least factorial have growth constant 0. In particular, γ(Ex(P )) = 0 for any path P .

• The number of labelled paths is n!/2. Hence, by the remark made before the proof, the growth constant of the class of path forests is 1.

• A caterpillar is a tree consisting of a path and vertices directly adjacent to (i.e. one edge away from) that path. Let C be the class of graphs whose connected components are caterpillars, which is clearly minor-closed. A rooted caterpillar can be considered as an ordered sequence of stars. Hence the associated generating function is 1/(1 -ze z ). The dominant singularity is the smallest positive root of 1 -ze z = 0, and γ(C) is the inverse ξ of this value.

• The growth constant of the class of acyclic graphs (forests) is the number e. This is because the number of labelled trees is n n-2 which, up to a sub-exponential factor, is asymptotic to ∼ e n n!.

2) This property follows from an idea by Colin McDiarmid. Suppose γ(G) = γ, and let AG be family of graphs G having a vertex v such that G -v is in G; in this case we say that v is an apex of G. It is easy to check that if G is minor-closed, so is AG. Now we have

2 n |G n | ≤ |AG n+1 | ≤ (n + 1)2 n |G n |.
The lower bound is obtained by taking a graph G ∈ G with vertices [n], adding n + 1 as a new vertex, and making n + 1 adjacent to any subset of [n]. The upper bound follows the same argument by considering which of the vertices 1, 2, . . . , n + 1 acts as an apex. Dividing by n! and taking n-th roots, we see that γ(AG) = 2γ(G).

3) This has been already shown during the proof of Theorem 2. Indeed, if a minor-closed class G contains all paths, then |G n | ≥ n!/2 and the growth constant is at least 1. Otherwise g n < ǫ n n n for all ǫ > 0 and γ(G) = 0. 4) We consider the graphs Cat l and Ap l represented in Figure 1. Remark. Claim 12 gives in fact a characterization of the minor-closed classes with growth constant 1. These are the classes containing all the paths but neither all the caterpillars nor all the graphs in the apex class of the path forests. For instance, the class of trees not containing a given caterpillar (as a minor) and the class of graphs not containing a given star (as a minor) both have growth constant 1.

Proof. Observe that the class Ex(Cat k , Ap l ) contains all paths as soon as k > 2 and l > 1. Hence, γ(Ex(Cat k , Ap l )) ≥ 1 (by Lemma 3) and we only need to prove that γ(Ex(Cat k , Ap l )) ≤ 1. We first prove a result about the simple paths of the graphs in Ex(Cat k , Ap l ).

Lemma 13. Let G be a graph in Ex(Cat k , Ap l ) and let P be a simple path in G. Then, there are less than kl + 4k 3 l vertices in P of degree greater than 2.

Proof. • We first prove that any vertex not in P is adjacent to less than l vertices of P and any vertex in P is adjacent to less than 2l vertices of P . Clearly, if G contains a vertex v not in P and adjacent to l vertices P , then G contains Ap l as a minor. Suppose now that there is a vertex v in P adjacent to 2l other vertices of P . In this case, v is adjacent to at least l vertices in one of the simple paths P 1 , P 2 obtained by removing the vertex v from the path P . Hence G contains Ap l as a minor.

• We now prove that there are less than kl vertices in P adjacent to at least one vertex not in P . We suppose the contrary and we prove that there exist k independent edges e i = (u i , v i ), i = 1 . . . k such that u i is in P and v i is not in P (thereby implying that Cat k is a minor of G). Let r < k and let e i = (u i , v i ), i ≤ r be independent edges with u i ∈ P and v i / ∈ P . The set of vertices in P adjacent to some vertices not in P but to none of the vertices v i , i ≤ r has size at least kl -rl > 0 (this is because each of the vertex v i is adjacent to less than l vertices of P ). Thus, there exists an edge e r+1 = (u r+1 , v r+1 ) independent of the edges e i , i ≤ r with u r+1 ∈ P and v r+1 / ∈ P . Thus, any set of r < k independent edges with one endpoint in P and one endpoint not in P can be increased.

• We now prove that there are no more than 4k 3 l vertices in P adjacent to another vertex in P beside its 2 neighbors in P . We suppose the contrary and we prove that either Cat k or Ap l is a minor of G. Let E P be the set of edges not in the path P but joining 2 vertices of P . We say that two independent edges e = (u, v) and e ′ = (u ′ , v ′ ) of E P cross if the vertices u, u ′ , v, v ′ appear in this order along the path P ; this situation is represented in Figure 2 (a).

-We first show that there is a subset E ′ P ⊆ E P of k 3 independent edges. Let S be any set of r < k 3 edges in E P . The number of edges in E P sharing a vertex with one of the edges in S is at most 2r × 2l < 4k 3 l (this is because any vertex in P is adjacent to less than 2l vertices in P ). Since |E P | ≥ 4k 3 l, any set of independent edges in E P of size less than k 3 can be increased.

-We now show that for any edge e in E ′ P there are at most k edges of E ′ P crossing e. Suppose that there is a set S ⊆ E ′ P of k edges crossing e. Let P ′ be the path obtained from P ∪ e by deleting the edges of P that are between the endpoints of e. The graph made of P ′ and the set of edges S contains the graph Cat l as a minor which is impossible.

-We now show that there exists a subset E ′′ P ⊆ E ′ P of k 2 non-crossing edges. Let S be any set of r < k 2 edges in E ′ P . By the preceding point, the number of edges in E ′ P crossing one of the edges in S is less than rk < k 3 . Since |E ′ P | ≥ k 3 , any set of non-crossing edges in E ′ P of size less than k 2 can be increased.

-Lastly, we show that the graph Cat k is a minor of G. We say that an edge e = (u, v) of E ′′ P is inside another edge e ′ = (u ′ , v ′ ) if u ′ , u, v, v ′ appear in this order along the path P ; this situation is represented in Figure 2 (b). We define the height of the edges in E ′′ P as follows: the height of an edge e is 1 plus the maximum height of edges of E ′′ P which are inside e (the height is 1 if there is no edge inside e). The height of edges have been indicated in Figure 2 (c). Suppose that there is an edge of height k in E ′′ P . Then there is a set S of k edges e 1 = (u 1 , v 1 ), . . . , e k = (u k , v k ) such that the vertices u 1 , u 2 , . . . , u k , v k , v k-1 , . . . , v 1 appear in this order along P . In this case, the subgraph made of S and the subpath of P between u 1 and u k contains Cat k as a minor. Suppose now that there is no edge of height k. Since there are k 2 edges in E ′′ P , there is a integer i < k such that the number of edges of height i is greater than k. Thus, there is a set S of k edges e 1 = (u 1 , v 1 ), . . . , e k = (u k , v k ) such that the vertices u 1 , v 1 , u 2 , v 2 , . . . , u k , v k appear in this order along P . In this case, the subgraph obtained from P ∪ {e 1 , . . . , e k } by deleting an edge of P between u i and v i for all i contains Cat k as a minor. For any integer N , we denote by G N T the set of pairs (G, T ) where G is a graph and T is a DFS spanning forest on G having height at most N (the definition of DFS spanning forest was given just after Claim 4).

(b) v e ′ u ′ u v ′ P 1 2 2 1 1 1 P 3 (c) u u ′ v v ′ e e ′ (a)
Lemma 14. For any graph G in Ex(Cat k , Ap l ), there exists a pair (G ′ , T ′ ) in G kl+4k 3 l T such that G is obtained from G ′ by subdividing some edges of T .

Proof. Let G be a graph in Ex(Cat k , Ap l ), let T be a DFS spanning forest of G and let R be the set of roots of T (one root for each connected components of G). One contracts a vertex v of degree 2 by deleting v and joining its two neighbors by an edge. Let G ′ and T ′ be the graphs and trees obtained from G and T by contracting the vertices v / ∈ R of degree 2 which are incident to 2 edges of T . We want to prove that (G ′ , T ′ ) is in G kl+4k 3 l T .

• Since T is a DFS spanning forest of G, every edge of G which is not in T connects a vertex to one of its ancestors [START_REF] Cormen | Introduction to algorithms[END_REF]. This property characterize the DFS spanning forests and is preserved by the contraction of the vertices of degree 2. Hence, T ′ is a DFS spanning forest of G ′ .

• By Lemma 13, the number of vertices which are not of degree 2 along a path of T from a root to a leaf is less than kl + 4k 3 l. Thus, the height of T ′ is at most kl + 4k 3 l.

We have already shown in the proof of Claim 4 that the radius of convergence of the generating function G N T (z) of the set G N T is infinite. Moreover, the generating function of the set of graphs that can be obtained from pairs (G ′ , T ′ ) in G N T by subdividing the tree T ′ is bounded (coefficient by coefficient) by G N T ( z 1-z ) (since a forest T ′ on a graph G ′ of size n has at most n -1 edges to be subdivided). Thus, Lemma 14 implies that the generating function of Ex(Cat k , Ap l ) is bounded by G kl+4k 3 l T ( z 1-z ) which has radius of convergence 1. Hence, the growth constant γ(Ex(Cat k , Ap l )) is at most 1.

This concludes the proof of Claim 12 and Theorem 11.

We now investigate the topological properties of the set Γ and in particular its limit points. First note that Γ is countable (as a consequence of the Minor Theorem of Robertson and Seymour [START_REF] Robertson | Graph minors I-XX[END_REF]).

Lemma 15. Let H 1 , H 2 , . . . H k be a family of 2-connected graphs, and let

H = Ex(H 1 , H 2 , . . . H k ). If G is a 2-connected graph in H, then γ(H ∩ Ex(G)) < γ(H).
Proof. The condition on 2-connectivity guarantees that the growth constants exist. By Theorem 4.1 from [START_REF] Mcdiarmid | Random planar graphs[END_REF], the probability that a random graph in H n contains G as a subgraph is a least 1 -e -αn for some α > 0. Hence the probability that a random graph in H n does not contain G as a minor is at most e -αn . If we denote G = H ∩ Ex(G), then we have

|G n | |H n | = |G n | n! n! |H n | ≤ e -αn .
Taking limits, this implies γ(G) γ(H) ≤ lim e -αn 1/n = e -α < 1.

We recall that given a set A of real numbers, a is a limit point of A if for every ǫ > 0 there exists x ∈ A -{a} such that |a -x| < ǫ.

Theorem 16. Let H 1 , . . . , H k be 2-connected graphs which are not cycles. Then, γ = γ(Ex(H 1 , . . . , H k )) is a limit point of Γ.

Proof. For k ≥ 3, let G k = G ∩ Ex(C k )
, where C k is the cycle of size k. Because of Proposition 10, the class G k has a growth constant γ k , and because of Lemma 15 the γ k are strictly increasing and γ k < γ for all k. It follows that γ ′ = lim k→∞ γ k exists and γ ′ ≤ γ. In order to show equality we proceed as follows.

Let

g n = |G n | and let g k,n = |(G k ) n |. Since γ = lim n→∞ (g n /n!) 1/n
, for all ǫ > 0 there exists N such that for n > N we have

(g n /n!) 1/n ≥ γ -ǫ. Now define f n = g n e 2 n! and f k,n = g k,n e 2 n!
. From [START_REF] Mcdiarmid | Random planar graphs[END_REF]Theorem 3], the sequence f n is supermultiplicative and γ = lim

n→∞ (f n ) 1/n = lim n→∞ (g n /n!) 1/n exists and equals sup n (f n ) 1/n . Similarly, γ k = lim n→∞ (f k,n ) 1/n = sup n (f k,n ) 1/n .
But since a graph on less than k vertices cannot contain C k as a minor, we have g k,n = g n for k > n. Equivalently, f k,n = f n for k > n. Combining all this, we have

γ k ≥ (f k,n ) 1/n ≥ (f n ) 1/n ≥ γ -ǫ for k > N . This implies γ ′ = lim γ k ≥ γ.
Notice that Theorem 16 applies to all the classes in Table 1 starting at the class of outerplanar graphs. However, it does not apply to the classes of of forests. In this case we offer an independent proof based on generating functions.

Lemma 17. The number e is a limit point of Γ.

Proof. Let F k be the class of forests whose trees are made of a path and rooted trees of height at most k attached to vertices of the path. Observe that the classes F k are minor-closed, that F k ⊂ F k+1 , and that ∪ k F k = F, where F is the class of forests. We prove that γ(F k ) is a strictly increasing sequence tending to e = γ(F).

Recall that the class F k and the class T k of its connected members have the same growth constant. Moreover, the class T k of trees with a distinguished oriented path to which rooted trees of height at most k are attached has the same growth constant as T k (this is because there are only n(n -1) of distinguishing and orienting a path in a tree of size n). The generating function associated to

T k is 1/(1 -F k (z)), where F k (z) of is the generating function of rooted trees of height at most k. Hence, γ(F k ) = γ( T k ) is the inverse of the unique positive root ρ k of F k (ρ k ) = 1.
Recall that the generating functions F k are obtained as follows; see Section III.8.2 in [START_REF] Flajolet | Analytic combinatorics[END_REF]).

F 0 (z) = z; F k+1 (z) = ze F k (z) for k > 0.
It is easy to check that the roots ρ k of F k (ρ k ) = 1 are strictly decreasing. Recall that the generating function F (z) of rooted trees has a singularity at 1/e and that F (1/e) = 1 (see [START_REF] Flajolet | Analytic combinatorics[END_REF]). Moreover, for all n, 0 ≤

[z n ]F k (z) ≤ [z n ]F (z) and lim k→∞ [z n ]F k (z) = [z n ]F (z), thus lim k→∞ F k (1/e) = F (1/e) = 1
. Furthermore, the functions F k (z) are convex and F ′ k (1/e) ≥ 1 (since the coefficients of F k are positive and [z 1 ]F k (z) = 1). Thus, F k (z) > F k (1/e)+ (z -1/e) which implies 1/e ≤ ρ k ≤ 1/e + (F k (1/e) -F (1/e)). Thus, the sequence ρ k tends to 1/e and the growth constants γ(F k ) = 1/ρ k tend to e.

Remark. The number ν ≈ 2.24, which is the inverse of the smallest positive root of z exp(z/(1 -z)) = 1, can be shown to be a limit point of Γ by similar methods. It is the smallest number which we know to be a limit point of Γ. It is the growth constant of the family whose connected components are made of a path P and any number of paths of any length attached to the vertices of P .

Remark. All our examples of limit points in Γ come from strictly increasing sequences of growth constants that converge to another growth constant. Is it possible to have an infinite strictly decreasing sequences of growth constants? As we see now, this is related to a classical problem. A quasi-ordering is a reflexive and transitive relation. A quasi-ordering ≤ in X is a well-quasi ordering if for every infinite sequence x 1 , x 2 , . . . in X there exist i < j such that x i ≤ x j . Now consider the set X of minor-closed classes of graphs ordered by inclusion. It is an open problem whether this is a well-quasi ordering [START_REF] Diestel | Graph minor hierarchies[END_REF]. Assuming this is the case, it is clear that an infinite decreasing sequence γ 1 > γ 2 > • • • of growth constants cannot exist. For consider the corresponding sequence of graph classes G 1 , G 2 , . . . . For some i < j we must have G i ⊆ G j , but this implies γ i ≤ γ j .

Conclusion: some open problems

We close by listing some of the open questions which have arisen in this work.

1) We know that a class G has a growth constant provided that all its excluded minor are 2-connected. The condition that the excluded-minors are 2-connected is certainly not necessary as is seen by noting that the apex family of any class which has a growth constant also has a growth constant. It is also easy to see that such an apex family is also minor-closed and that at least one of its excluded minors is disconnected.

Thus our first conjecture is that every minor-closed family has a growth constant, that is, lim gn n! 1/n exists for every minor-closed class G.

2) A minor-closed class is smooth if lim gn ng n-1 exists. It follows that this limit must be the growth constant and that a random member of G will have expected number of isolated vertices converging to 1/γ. Our second conjecture is that if every excluded minor of a minorclosed class is 2-connected then the class is smooth.

If true, then it would follow that a random member of the class would qualitatively exhibit all the Poisson type behaviour exhibited by the random planar graph. However proving smoothness for a class seems to be very difficult and the only cases which we know to be smooth are when the exponential generating function has been determined exactly.

3) We have shown that the intervals (0, 1) and (1, ξ) are "gaps" which contain no growth constant. We know of no other gap, though if there is no infinite decreasing sequence of growth constants they must exist. One particular question which we have been unable to settle is whether (ξ, 2) is also a gap.

4) We have shown that for each nonnegative integer k, 2 k is a growth constant. A natural question is whether any other integer is a growth constant. More generally, is there any algebraic number in Γ besides the powers of 2? 5) All our results concern labelled graphs. In unlabelled setting, the most important question to settle is whether there is an analogue of the theorem of Norine et al. More precisely, suppose G is a minor-closed class of graphs and that u n denotes the number of unlabelled members of G n . Does there exist a finite d such that u n is bounded above by d n ?

Aknowledgements. We are very grateful to Colin McDiarmid who suggested the apexconstruction, to Angelika Steger for useful discussions, and to Norbert Sauer and Paul Seymour for information on well quasi orders.

Lemma 3 . 1 .

 31 The number of path forests of size n satisfies |P n | ≥ n!. 2. The number of star forests of size n satisfies |S n | ≥ B(n). 3. The number of matchings of size n satisfies |M n | ≥ n!! = n(n -2)(n -4) . . .. 4. The number of stars of size n satisfies |X n | ≥ 2 n-1 .

Figure 1 :

 1 Figure 1: The graph Cat l (left) and the graph Ap l (right).

Figure 2 :

 2 Figure 2: (a) Two crossing edges. (b) An edge inside another. (c) A set of non-crossing edges.

Table 1 :

 1 • The property 1 of Theorem 11 can be extended with the growth constants of the minor-closed classes listed in table by table 1. • The properties 2, 3 and 4 of Theorem 11 remain valid if one replaces Γ by the set Γ ′ = {γ ′ = lim sup gn

	n!	1/n /G minor-closed}.
	Class of graphs	Growth constant Reference
	Ex(P k )	0 This paper
	Path forests	1 Standard
	Caterpillar forests	ξ ≈ 1.76 This paper
	Forests = Ex(K 3 )	e ≈ 2.71 Standard
	Ex(C 4 )	3.63 [9]
	Ex(K 4 -e)	4.18 [9]
	Ex(C 5 )	4.60 [9]
	Outerplanar = Ex(K 4 , K 2,3 )	7.320 [1]
	Ex(K 2,3 )	7.327 [1]
	Series parallel = Ex(K 4 )	9.07 [1]
	Ex(W 4 )	11.54 [9]
	Ex(K 5 -e)	12.96 [9]
	Ex(K 2 × K 3 )	14.13 [9]
	Planar	27.226 [13]
	Embeddable in a fixed surface	27.226 [10]
	Ex(K 3,3 )	27.229 [8]

A table of some known growth constants.