L Carteron
email: loic.carteron@ensta-bretagne.org

C Doudard

S Calloch

B Levieil

J Beaudet

F Bridier

Naval welded joints local stress assessment and fatigue cracks monitoring with quantitative thermoelastic stress analysis

Fatigue assessment of welded assemblies is a key challenge both for industrial and academic research. This paper assesses possibilities of thermoelastic coupling quantitative analysis for the comprehension of fatigue phenomena occurring with welded structures. A test protocol has been set up to measure temperature field on cruciform as-welded specimens under cyclic loading thanks to an infrared camera. Identification of temperature variations associated to thermoelastic coupling (order of magnitude of 0.1 K) allows to map temperature which are directly correlated to stress tensor first invariant. From this result, analysis of thermoelastic coupling gradient allows to determine the part of bending stress due to specimen distortion (up to 20% higher than nominal stress). Besides, thermal conduction influence when evaluating a local stress at weld toe is studied thanks to a numerical thermal model. In addition, infrared images posttreatment based on image segmentation is proposed for fatigue crack monitoring at weld toes (minimal crack size detection of 1 mm). Experimental validation is performed through analysis of marked fracture surface. Finally, fatigue crack growth rates are evaluated with this approach for different load amplitudes.

Introduction

Fatigue design of structures subjected to cyclic loading is a major concern for both industry and research since fatigue failure may represent up to 80% of in-service rupture cases [START_REF] Sangid | The physics of fatigue crack initiation[END_REF]. In welded structures, larger risk of fatigue failure is located at the weld toe because of stress concentration, complex microstructure and possible weld defects. Understanding the heterogeneous stress field in this area is therefore a major concern when developing or using models for fatigue design.

Several full field experimental techniques exist to assess stress field at weld joints. Thermoelastic Stress Analysis (TSA) has become a recognized advantageous method to assess stress amplitude field on a surface under cyclic loading. Indeed, specimen tested under low stress cyclic loading (level significantly lower than the material elastic limit) shows cyclic temperature variations with the same frequency than loading and the temperature amplitude can be linked to the stress amplitude. The beginning and early development of TSA has been reviewed by Stanley [2]. This technique has been successfully applied to both standard specimens and more complex structures such as pressure vessels [START_REF] Stanley | Applications and potential of thermoelastic stress analysis[END_REF], fighter jet fuselage [START_REF] Rajic | Thermoelastic stress analysis -emerging opportunities in structural health monitoring[END_REF], power station drain lines [START_REF] Tighe | Stress based nondestructive evaluation using thermographic approaches: From laboratory trials to on-site assessment[END_REF] or additively manufactured aerospace brackets [START_REF] Allevi | Qualification of additively manufactured aerospace brackets: A comparison between thermoelastic stress analysis and theoretical results[END_REF]. Other studies also have opened paths by experimenting this thermal approach on butt joints [START_REF] Ummenhofer | On the use of infrared thermography for the analysis of fatigue damage processes in welded joints[END_REF], thin steel sheet T-joint [START_REF] Chen | Crack growth analysis in welded and non-welded T-joints based on lock-in digital image correlation and thermoelastic stress analysis[END_REF] and more complex welded structures such as a car wishbone [START_REF] Florin | Determination of the first stress tensor invariant of a complex steel sheet structure from Thermoelastic Stress[END_REF]. Besides, temperature field study have also been used as a mean of fatigue crack monitoring [START_REF] Charles | Using the scanning infrared camera in experimental fatigue studies[END_REF] but only qualitative observations have been made. This paper aims to extract a maximum of quantitative informations from the temperature variation associated to thermoelastic coupling, on a specific configuration of joint, considered as a standard welded detail in naval industry.

This study faces several problematic and scientific challenges. On the one hand, the inherent stress heterogeneities implied around welded joints can be due to different aspects [START_REF] Hobbacher | Recommendations for Fatigue Design of Welded Joints and Components[END_REF] such as weld toes geometry, residual stresses or welding defects. On the other hand, the use of a thermal approach may be complex and require precocious experimental measurements. Indeed, special cares need to be taken to obtain a reliable signal and some hypothesis need to be made to model the observed phenomena. Besides, thermal conduction in the metal will add difficulties since it may act as a leveller filter. This paper introduces the test protocol developed to perform infrared measurement on the studied welded specimen. Temperature evolutions during a fatigue test are then presented. Finally, results of TSA are discussed following two axes: (i) the evaluation of local stresses, and (ii) the detection and monitoring of fatigue cracks along weld toes. This last section proposes an infrared film 1 post-treatment, an experimental validation and finally results comparison between two welded joint configurations. Conclusions and future insights end the paper.

Material and experimental set-up

This section introduces the specimens and the test protocol used during this study. Initial qualitative observations are then outlined through the analysis of thermal sequences during a fatigue test.

Studied specimens

Testing was carried out on cruciform non-load carrying welded joints (Fig. 1) made of DH36 naval grade steel (Yield stress of 360 MPa). Specimens were welded in Naval Group shipyard using Gas Metal Arc Welding (GMAW). Two types of specimen configurations were studied: as-welded joints and TIG-dressed specimen.

TIG dressing is based on remelting (with a TIG torch) the weld toes located between the main plate and the stiffeners. This process is used to increase fatigue life by enlarging weld toe radius and redistributing residual stresses around the weld area [START_REF] Yildirim | Review of fatigue data for welds improved by tungsten inert gas dressing[END_REF]. As-welded joints are the main focus of this article but TIG-dressed results will be introduced at some points in order to compare the two specimen configuration and identify differences in fatigue failure mechanism.

As a result of the welding procedure, all the studied samples have a slightly different degree of distortion (max +/-1 mm between middle profile of different free specimen). As previously observed in literature [START_REF] Hobbacher | Recommendations for Fatigue Design of Welded Joints and Components[END_REF], samples present one face with a concave shape (Fig. 2) which therefore presents a higher stress level than the convex face when subjected to a tensile load. All the temperature observations have been carried out on the concave faces. The bending moment induced by this geometric distortion can be taken into account using a structural (or geometrical) stress approach. The use of structural stress as defined by the International Institute of Welding [START_REF] Hobbacher | Recommendations for Fatigue Design of Welded Joints and Components[END_REF] allows to consider both the membrane and bending part of the stress applied to a welded joint. The structural stress is generally evaluated with finite element analysis or experimentally from interpolation of stress measurement performed with two strain gauges placed at 0.5 and 1.5 times the thickness from the weld toe [START_REF] Hobbacher | Recommendations for Fatigue Design of Welded Joints and Components[END_REF]. In Section 3.2 thermoelastic coupling is used to assess the bending stress induced by specimen distortion.

Test set-up and equipment

Experiments have been performed on MTS® 250 kN tensile test machine with hydraulic clamping jaws (Fig. 3a). Repeated tensile loading with load ratio R = F min /F max = 0.1 has been applied for different stress amplitude levels, with a maximum nominal applied force smaller than the yield stress. Temperature field has been recorded using an infrared camera FLIR® SC7600MB with a 640 × 512 pixels sensor (Fig. 3b). Several thermal precautions have been taken to improve temperature measurement quality:

-Mat black painting (JELT® 5771) was applied on specimens in order to maximize the emissivity coefficient. -A cooling system has been installed around clamping jaws to limit thermal drift during tests and to reduce the temperature gradient between the two clamps. -A thick sheet has been placed around specimen and camera (Fig. 3a) to lower environmental influences that are convection and reflection.

Short videos of 200 s every 600 s have been recorded during fatigue tests until specimen failure. Pixel size is approximately 160 μm. FLIR® compensated calibration has been applied to each and every pixels to take in account the initial sensor temperature [START_REF] Saux | Proposition of a compensated pixelwise calibration for photonic infrared cameras and comparison to classic calibration procedures: Case of thermoelastic stress analysis[END_REF]. The smallest measurable temperature variation, also referred as Noise Equivalent Temperature Difference (NETD), of this camera is in the range of 20 mK. Camera frequency has been set to 1 Hz whereas mechanical loading frequency has been set to 10.02 Hz in order to observe thermoelastic cycles with the stroboscopic effect [START_REF] Florin | Fast fatigue properties identification by self-heating method: Application to automotive welded joints[END_REF].

Temperature evolutions during fatigue test

As a first step, observation of the mean temperature (calculated over the framed part of the specimen) during a fatigue test (Fig. 3b) shows consistent results in terms of temperature evolution compared to observations reported in the literature on material specimen [START_REF] Blotny | A method for determining the heat energy of the fatigue process in metals under uniaxial stress: Part 1. Dtermination of the amount of heat liberated from a fatigue-tested specimen[END_REF]. Two types of temperature variations can be noticed:

1. The cyclic variation of the signal may be identified and associated to the thermoelastic coupling effect [START_REF] Stanley | A new experimental stress analysis technique of wide application[END_REF]. 2. The mean thermal evolution which may be divided into three phases [START_REF] Rosa | Thermographic methodology for rapid determination of the fatigue limit of materials and mechanical components[END_REF]: (i) a transient phase from 0 to 2⋅10 4 cycles where the global temperature increases, (ii) a steady-state phase from 2⋅10 4 cycles to 1.3⋅10 5 cycles where global temperature stays constant and (iii) a rapid increase prior to specimen failure from 1.3⋅10 5 cycles to the end of the test. Studies in the literature consider that the dissipation mechanism responsible for this temperature variation is microplasticity in the case of standard metal specimens [START_REF] Doudard | Identification of the scatter in high cycle fatigue from temperature measurements[END_REF]. In the case of welded structures, localized dissipation mechanisms may also be involved close to weld toes such as local plasticity or crack opening. This article focuses exclusively on the informations that can be extracted from the analysis of thermoelastic coupling. Identification of the temperature amplitude associated with thermoelastic coupling, Δθ the , and a phase shift, ϕ, has been carried out on infrared data by fitting (least square optimization method) a function built as the sum of a shifted sine and a linear drift [START_REF] Krapez | Compared performances of four algorithms used for modulation thermography[END_REF], such as:

F(t) = Δθ the sin(2πft + ϕ) + (At + B), (1)
with A and B constants to be determined, and f the stroboscopic frequency (0.02 Hz). This identification has been performed for each pixel of each image of each infrared films, allowing the composition of Δθ the maps (Fig. 4). Examination of the first Δθ the map on Fig. 4 highlights the non-homogeneous stress field in this type of structure and shows that the stiffener displays a temperature amplitude Δθ the close to zero as it is not directly submitted to the tensile load. Areas in red on Δθ the map (Fig. 4) highlight concentrated stress areas located at the weld toes. Application of quantitative TSA [START_REF] Stanley | A new experimental stress analysis technique of wide application[END_REF] for the studied welded detail is introduced Section 3. The evolution of Δθ the map during a fatigue test, mirrored with the averaged temperature evolution, is represented Fig. 4. Several interruptions of the red areas appear progressively during the test. These are indicators of fatigue cracks [START_REF] Ummenhofer | On the use of infrared thermography for the analysis of fatigue damage processes in welded joints[END_REF][START_REF] Charles | Using the scanning infrared camera in experimental fatigue studies[END_REF]. Quantitative analysis of this phenomena is proposed in Section 4. Fig. 4 highlights also that, for aswelded configuration, first cracks can be detected since the first third of the total life. By contrast, TIG dressed specimens show relatively short propagation phase (Fig. 5). This result supports the pertinence to consider the propagation phase in the total life estimation for as-welded joints whereas another approach is needed to model fatigue life of TIG dressed specimens. In the next sections, quantitative analysis of the experimental results will be proposed and discussed under two main axes: (i) quantification of local stresses at weld toes, and (ii) detection and monitoring of fatigue cracks along weld toes.

Local stresses quantification

This section introduces the benefits of the TSA method applied to the studied welded specimen. After underlining the equations of the thermoelastic phenomenon, the TSA is applied first to assess the bending stress induced by the specimen distortion and then to evaluate the local stress at the weld toes.

Thermoelastic stress analysis theory

The analysis of thermoelastic coupling is used as a technique to assess stress field on a surface. Indeed, under adiabatic hypothesis, the equation of thermoelasticity,links the amplitude of temperature variation associated to thermoelastic coupling heat source with the amplitude of stress tensor first invariant [START_REF] Biot | Thermoelasticity and irreversible thermodynamics[END_REF]. For an isotropic homogeneous material under a uniaxial loading, the heat source can be linked to the thermoelastic coupling such as, S the = -2πf s αT 0 I 1amp cos(2πf s t), [START_REF] Stanley | Beginnings and early development of thermoelastic stress analysis[END_REF] with f s the loading frequency, α the isotropic expansion coefficient, T 0 the initial temperature and I 1amp the stress tensor first invariant amplitude. Assuming adiabaticity, the following expression can be written [START_REF] Florin | Determination of the first stress tensor invariant of a complex steel sheet structure from Thermoelastic Stress[END_REF][START_REF] Pitarresi | A review of the general theory of thermoelastic stress[END_REF],

I 1amp = -Δθ the ρC ∊αT 0 , ( 3
)
where Δθ the is the measured amplitude of the cyclic temperature evolution and ∊ the paint emissivity. Validity of the adiabatic hypothesis is discussed together with the influence of heat conduction in the forthcoming paragraph 3.3.

Assessment of bending stress induced by specimen distortion

The studied cruciform specimens have overall symmetrical geometry but initial distortion due to the welding process induces an additional bending stress during tensile tests. The use of TSA to quantify this additional part of the stress is evaluated in this paragraph. To validate the experimental results, a first finite element model has been implemented with the commercial software Abaqus to simulate only the mechanical behaviour of the specimens. Assuming two symmetry planes, only one fourth of the specimen geometry is considered and a driving force is applied at one end (Fig. 6). Initial distortion is introduced by setting the weld detail center offset of clamp axes by 0.75 mm (Fig. 6). This value has been measured onto the mean specimen profile thanks to in situ digital image correlation measurements when both ends of the specimen were clamped. Averaged connecting radius at the weld toes (Fig. 6) has been determined from a 3D scan of the chosen specimen (Values are given in Fig. 9). Connecting circle radius has been measured within +/-0.1 mm confidence. Material behavior is supposed elastic Fig. 5. Δθ the map evolution monitored on TIG dressed specimen during fatigue test. Applied nominal stress amplitude is 150 MPa. and the specimen is meshed using C3D20R elements (20 nodes hexahedron with quadratic interpolation and reduced integration). The model uses 167080 elements including 60 elements located into the connecting radius of the studied weld toe. First stress invariant amplitude profile is extracted along the specimen central path and plotted in Fig. 7. For comparison purpose, experimental Δθ the maps are projected along y axis (Fig. 7) assuming a signal average over ten pixels in the specimen middle (≈ 1.6 mm). This value is a compromise between noise reduction by spatial average and side effects limitations. The coefficient ρC ∊αT0 introduced in Eq. ( 3) is calculated (1104 MPa • C -1 ) using the values in Table 1, a measured emissivity coefficient ∊ of 0.87, and a measured temperature T 0 of 293.15 K.

This coefficient is then applied to experimental temperature data (dots in Fig. 7)) to allow comparison with stress curve from the finite element model. Additional experimental points for validation have been obtained with four strain gauges (orange cross in Fig. 7). They have been positioned on the concave face, at approximatively once and twice the plate thickness from the weld toe. The strain gauge measure is then translated to stress measure under elastic hypothesis. Comparison between experimental data and mechanical finite element model result is shown Fig. 7. Fig. 7 highlights the good correlation between slopes of the experimental profile and the numerical model inside the intervals abs(y) ∈ [START_REF] Biot | Thermoelasticity and irreversible thermodynamics[END_REF]30] mm. This result confirms that thermoelastic coupling observations allow to capture and identify the influence of bending stress part caused here by the specimen distortion.

Furthermore, this infrared film analysis allows to define a custom structural stress from the Δθ the profile. Fig. 8a illustrate the method. Then, by applying this approach to the same specimen for different load levels, Fig. 8b shows a linear evolution of structural stress versus nominal stress. For high stress levels, the difference between nominal and structural stress increases and becomes important. In conclusion, this approach allows to evaluate structural stress on welded specimen for a better description of the stress state close to the weld toe area.

Local stress evaluation at weld toes

This paragraph focuses on how to evaluate the local stress at weld toe thanks to thermoelastic coupling analysis. Calculation of Fourier coefficient [START_REF] Biot | Thermoelasticity and irreversible thermodynamics[END_REF], defined as the ratio between conduction term and heating capacity, gives a value close to one in the local area of the weld toe. The heating capacity and the conduction part are thus of the same magnitude, meaning that the conduction of heat should be considered to increase the model quality. The stress field of the previous mechanical finite element model is thus reused in a second thermo-mechanical finite element model, with only the thermoelastic coupling as heat source. Stabilized temperature amplitude profile along specimen central path is extracted and represented on Fig. 9. A good correlation in the region of weld toes is obtained between experimental data and thermomechanical model curve. With this technique, the weld toe local stress analysis allows to catch the influence of the connecting radius over the stress concentration. Indeed, the smaller the radius, the higher the concentration stress. Therefore, this approach may also be used to evaluate an equivalent weld toe radius despite the difficulty to determine a unique radius. Besides, a perspective to increase the Δθ the peaks intensity might be to increase the loading frequency. However, the paint thickness influence would the have to be considered [START_REF] Florin | Determination of the first stress tensor invariant of a complex steel sheet structure from Thermoelastic Stress[END_REF].

Fatigue crack detection and monitoring

Observation of the thermoelastic coupling may also serve for damage evolution monitoring in composite materials [START_REF] Emery | Thermoelastic Stress Analysis of damage mechanisms in composite materials[END_REF] or fatigue crack monitoring [START_REF] Charles | Using the scanning infrared camera in experimental fatigue studies[END_REF]. Ummenhofer et al. have also explored the possibility to use this approach to monitor cracks on butt weld joints [START_REF] Ummenhofer | On the use of infrared thermography for the analysis of fatigue damage processes in welded joints[END_REF]. They have shown that Δθ the evolve towards zero where cracks appear which is logical as there is no material to support a stress. Quantification of the cracks size is proposed in this section thanks to a post-treatment based on image processing. A validation of the method is then outlined before further observations of crack growth rates.

Infrared films post-treatment

Firstly, selection of a smaller working area (4 × 40 mm) around studied weld toes is performed to reduce processing time. The next step is the application of a 3 by 3 pixels median filter in order to reduce white noise and to smooth the images (Fig. 10). Images from Fig. 10

Table 1

Measured thermomechanical constants for DH36 steel.

ρ [kg m -3 ] C [J kg -1 K -1 ] α [K -1 ] 7803 426 1.267.10 -5
this analysis and to allow quantitative monitoring of crack propagation along weld toes.

Histogram of images from Fig. 10 are overlayed in Fig. 11. These histograms show relatively low contrast. Observation of initial histogram, in blue, shows one main peak corresponding to main plate pixels. Pixels associated to the weld toe stress concentration area, located at the right hand side of the histogram, are not numerous. Comparison of the three histograms shows that image contrast is increasing during fatigue test. Indeed, crack propagation involve both darker pixels occurrence in cracked areas and stress increase in healthy areas.

Several segmentation algorithm have been experimented on Δθ the maps. Edges detection segmentation approaches don't supply satisfactory results because of low contrast images where no important gradient allows easy edges detection. Segmentation methods based on morphological operations also have been excluded because they may damage the data and affect crack size characterisation.

The chosen segmentation method is based on thresholding. Segmentation results of previous images from Fig. 10 are displayed in Fig. 12. Ostu's algorithm for automatic detection of optimal threshold [START_REF] Otsu | A Tlreshold Selection Method from Gray-Level Histograms C[END_REF] also have been experimented but doesn't give good results in this configuration because of no clear presence of second peak in the high intensity pixels. The threshold is here determined from the first Δθ the map of fatigue test and kept constant for all images. Its value is determined by calculating the average maximum pixel intensity and the position of main peak. Sensitivity of this threshold value is discussed in the next section.

The last step of the post-treatment consists in labelling the segmented images. Different values are given to each separated image areas. Quantification of the cracks size is then extracted thanks to the bounding box properties of the labelled areas. The output of one short infrared film is therefore a one dimension equivalent welded joint associated to a certain number of cycles. Fig. 13 shows the post-treatment output of the three initial images introduced in Fig. 10.

By vertically stacking these one dimension equivalent joints, a picture of the crack growth history during fatigue tests can be plotted. To illustrate this operation, the three images from Fig. 13 are highlighted with dashed lines in Fig. 14c. Fig. 14 introduces result of proposed posttreatment obtained for five different specimens loaded at different levels and a result obtained on a TIG dressed specimen for comparison. Analysis of these images allows some well-known observations and points out worth-noting facts:

-Cracks as small as 1 mm can accurately be detected and coalescence of cracks can be monitored. -Propagation represents at least half of the specimen fatigue life.

-When the stress is increased, the number of cracks increases too.

-This post-treatment may not detect small cracks located around the edges of the specimen due to side effect (Fig. 14e). -Some crack starts to propagate later than other, which might be explained by different weld toe geometrical criticality or different initial defects sizes (not detected by bleeding). -Fewer cracks are detected on TIG dressed specimens. Coalescence has therefore no time to impact fatigue life. Propagation phase represent a small fatigue life part of this specimen configuration.

Output sensitivity to threshold value

Sensitivity to threshold value has been studied to ensure approach reliability. Fig. 15 shows three segmentation results of the same initial image introduced in Fig. 4(c) with 10% variation of threshold value. These results emphasize a low sensibility to the threshold value.

Threshold sensitivity can also be observed onto complete fatigue test output. Fig. 16 allows comparison of output for three different threshold values. The three images show globally similar shapes. Three comparison criteria may be considered:

-First cracks detection: Threshold value has a non negligible influence on small crack detection capacity (see Table 2). In addition, when threshold is too high, artefacts appear with no physical significance (Fig. 16c) Therefore, cracks below 1 mm cannot be reliably detected with the proposed approach. Nevertheless, this information will not be used in the next section analysis. -Final cracks size: Final crack size differences are lower than 5% for cracks larger than 4 mm and less than 2% for cracks larger than 10 mm. Threshold value has therefore a very limited influence here. -Crack growth rate: Yellow shapes geometry appear comparable and crack growth rates estimated in Table 3 show low sensibility to threshold.

Post-treatment validation: fracture surface analysis

Experimental validation has been carried out by performing interrupted fatigue test on four specimens. After interruption, standard bleeding has not shown any evidence of cracks. Thus, specimens have been placed into a furnace at 500 • C during 30 min in order to mark all free surfaces including fatigue cracks. Specimen opening has then been carried out through cycling loading with through thickness pre-cut when needed (as can be seen, for example, on fracture surface in Fig. 17b). Cracks appear marked with black on fracture surfaces in Fig. 17. The crack position detected with infrared image processing correlate well with the marked surfaces. Moreover, a good correspondence is also found when observing coalescence locations. Crack width measurements have been performed thanks to numerical microscope.

These measures have been compared to the output of Δθ the maps processing in Fig. 18. Maximum differences are within 15% along the whole range of detected crack sizes.

Fracture surface analysis provided several justifications:

-Fatigue cracks evolve faster towards edges than through the thickness which can be explained by inhomogeneous stress field in specimen thickness, -Proposed infrared image processing allows good estimation of cracks position and width.

Crack growth rate observations

Representation of crack size evolutions before coalescence has been plotted in Fig. 19. Only one main crack size evolution per specimen and per stress level has been plotted to keep graph light and clear. Influence of stress level is in good agreement with expectations: the higher the stress level, the faster the crack propagates. In addition, the crack size evolution is mostly linear after 1 mm. Crack size growth rate may therefore be considered constant over time. Linear regression has been carried out to estimate crack growth rate as a single value for each nominal stress level (Fig. 20).

Representation of crack growth rate versus geometric stress is shown in logarithmic scale in Fig. 20. It underlines that points may be modelled with a slope of 4.1. Geometric stress amplitude is consider here to reduce variability induced by specimen distortion and is determined thanks to earlier introduced TSA approach (Section 3.2).

Initiation criterion for fatigue test campaign analysis

Conventional fatigue tests have been performed with additional use of infrared camera. The proposed post-treatment has then be used to determine an initiation criterion. Both failure criterion and 2 mm initiation criterion are used in Fig. 21 to analyse fatigue tests data. This figure highlights the fact that main fatigue life of the cruciform aswelded joints correspond to propagation phase. Besides, Basquin model has been identified to model traditional fatigue points. A slope of 3.9 is calculated for the mean curve. This value appears to be of the same magnitude order that the slope found in Fig. 20 (slope of 4.1). This observation adds another argument to the fact that crack propagation correspond to the main part of fatigue mechanism for the studied type of as-welded joints. In comparison, fatigue results of TIG dressed specimens show a different Basquin slope of 6 and considering the 2 mm initiation criteria doesn't affect the mean curve such as with as-welded configuration.

Conclusions

Experimental set-up has been developed to study naval grade steel welded joint under cyclic loading with an infrared camera. Cyclic temperature variations associated to thermoelastic coupling have been studied following two main axis:

1. The first one is the application of TSA approach. It offers a powerful tool for welded joint study as: (a) Stress gradient associated to bending stress induced by specimen distortion can be quantified (Geometric stress may be up to 20% higher than nominal stress). (b) A local stress at weld toe may be evaluated (Stress concentration factor between 2 and 3). (c) Influence of weld toe radius is visible even if heat conduction acts as a leveller filter. 2. Second axis is the development of an infrared image post-treatment, based on segmentation, for fatigue crack monitoring.

(a) This approach was first experimentally validated thanks to marked fracture surface observations. The following conclusions have been made: i. Proposed infrared images post-treatment shows good agreement with crack sizes measured on marked fracture surfaces.

ii. Threshold influences crack size detection within +/-0.3 mm precision range, whereas threshold does not significantly impact crack growth rate monitoring (b) Application of the proposed post-treatment to study as-welded and TIG dressed specimens allows several observations to be made: i. When the stress is increased, the number of cracks increases too (from 1 crack initiated at 70 MPa to 5 cracks initiated at 110 MPa) ii. When the stress is increased, the crack growth rate increases too. A slope of 4.1 is found between crack growth rate and the geometric stress iii. The crack growth rate does not significantly evolve with crack size iv. With as-welded joints, multi-site crack initiation are captured along weld toe, whereas TIG dressed specimens show in average only one crack propagation per weld seem.

v. Crack coalescences can be observed on as-welded joints. vi. For as-welded configuration, propagation phase corresponds to more than half of the fatigue life, whereas propagation phase represents only a short fatigue life part of TIG dressed specimens.

This database of observations, collected exclusively through thermoelastic coupling study, may potentially be used as an identification base for future modelling works. In addition, all the informations that can be extracted from the thermoelastic coupling is only one part of the data contained in the infrared films. Temperature raise associated to dissipation may also be studied allowing more informations to be collected.

Fig. 1 .

 1 Fig.1. Specimen geometry and dimensions.

Fig. 2 .

 2 Fig. 2. Representation of specimen distortion induced by welding process.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Test set-up and equipment.

  represent the evolution of Δθ the map on one specimen weld toe during fatigue test. First image 10(a) shows the initial state where the blue to green areas are associated to the base plate of the specimen and the red pixels are associated to the stress concentration at the weld toe. No cracks are significantly visible at this stage. Then, on the next image 10(b), several cracks can be easily detected by visual inspection. The last picture 10(c) finally shows the propagation of several cracks and coalescence of two close cracks. The goal of the proposed post-treatment is to automatize

Fig. 6 .

 6 Fig. 6. Finite elements model mesh and boundary conditions.

Fig. 7 .

 7 Fig. 7. Correlation between experimental results and mechanical finite element model.

Fig. 8 .

 8 Fig. 8. Structural stress assessment from infrared data analysis.

Fig. 10 .

 10 Fig. 9. Correlation between experimental results and thermomechanical model.

Fig. 11 .

 11 Fig. 11. Overlay of images histogram from Fig. 10.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Image segmentation of images from Fig. 10 using thresholding.

Fig. 14 .

 14 Fig. 14. Post-treatment output of five as-welded specimen loaded at different stress level and one TIG-dressed specimen. Horizontal dotted lines on Figure (c) correspond to 1D welds of Fig. 13.

Fig. 15 .

 15 Fig. 15. Segmentation sensitivity to threshold (Specimen No.3 at 500 kcycles).

Fig. 16 .

 16 Fig. 16. Final output sensitivity to threshold (Specimen No.3).

Fig. 17 .

 17 Fig. 17. Post-treatment output of five loaded at different stress level with juxtaposition of marked fracture surface.

Fig. 18 .

 18 Fig. 18. Experimental validation of post-treatment.

Fig. 19 .

 19 Fig. 19. Crack width evolution evaluated from Δθ the maps processing.

Fig. 20 .

 20 Fig. 20. Crack growth rate estimated from linear regression of Fig. 20 curves versus geometric stress determined by Δθ the 1D profil processing.

Fig. 21 .

 21 Fig. 21. Conventional fatigue tests results analysed with proposed post-treatment.

Table 2

 2 Crack size monitoring sensitivity to threshold considering only specimen No.3 leftmost crack propagation.

		Cycle count [kcycles]	300	350	400	450	500
	Crack size [mm]	Threshold -10% Threshold Threshold +10%	1.2 1.7 2.0	2.2 2.6 2.8	6.9 7.3 7.5	8.4 8.8 9.0	10.7 10.9 11.1

Table 3

 3 Crack growth rate estimated by finite differences from Table2.

		Cycle count [kcycles]	325	375	425	475 0
	Crack growth rate [mm/ cycles]	Threshold -10% Threshold Threshold +10%	2.e-5 1.8e-5 1.6e-5	9.4e-5 9.4e-5 9.4e-5	3e-5 3e-5 3e-5	4.6e-5 4.2e-5 4.2e-5

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.


Joachim Von Below

Gaëlle Pincet Mailly

Jean François

Rault Lmpa

ULCO Joseph Liouville

Growth order and blow up points for the parabolic Burger's equation under dynamical boundary conditions

Keywords: Nonlinear parabolic problems, dynamical boundary conditions, blow up AMS Subject Classification 2000: 35B05, 35B40, 35K55, 35K57, 35K65, 35R45

We investigate the blow up points of the one-dimensional parabolic Burger's equation ∂ t u = ∂ 2 x u -u∂ x u + u p under a dissipative dynamical boundary condition σ∂ t u + ∂ ν u = 0 for one bump initial data. A numerical example of a solution pertaining exactly two bumps stemming from its initial data is presented. Moreover, we discuss the growth order of the L ∞ -norm of the solutions when approaching the blow up time.

Introduction

This paper is devoted to the blow up phenomenon of the one-dimensional parabolic Burger's equation with a convection term changing sign under dynamical conditions on the time lateral boundary

   ∂ t u = ∂ 2
x u -u∂ x u + u p in Ω for t > 0, B σ (u) = σ∂ t u + ∂ ν u = 0 on ∂Ω for t > 0, u(•, 0) = ϕ ∈ C(Ω) [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF] with the interval Ω = (-a, a) and 1 < p ∈ R. The results presented here improve and extend those of Section 5 from [START_REF] Below | Blow up for some nonlinear parabolic problems with convection under dynamical boundary conditions[END_REF]. It is well known that the system defines a local flow, especially local existence results are well established, see [START_REF] Below | Blow up for some nonlinear parabolic problems with convection under dynamical boundary conditions[END_REF] and the references therein. The basic hypotheses on σ and ϕ are [START_REF] Below | Blow up for reaction diffusion equations under dynamical boundary conditions[END_REF] σ(-a) ≥ 0, σ(a) ≥ 0,

(3) ϕ ≥ 0, ϕ ∈ C 2 ([-a, a]) , ϕ -ϕϕ + ϕ p ≥ 0 in [-a, a].

Let T = T (σ, ϕ) denote the blow up time of the maximal solution u = u σ of Problem [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF], that is in our context the maximal existence time of u with respect to the L ∞ -norm:

T (σ, ϕ) = inf s > 0 lim t s sup{|u σ (x, t)| x ∈ Ω} = ∞ .
It has been shown in [START_REF] Below | Blow up for some nonlinear parabolic problems with convection under dynamical boundary conditions[END_REF] that for 1 < p ≤ 2, the solutions of Problem (1) exist globally, while for p > 2 they blow up in finite time if ϕ > 0 in Ω. In the present paper we improve the growth order result in [START_REF] Below | Blow up for some nonlinear parabolic problems with convection under dynamical boundary conditions[END_REF] and determine the blow up set for one bump initial data. The last section is devoted to a numerical example displaying a solution pertaining exactly two bumps stemming from its initial data.

Growth order

For p > 3 + 1 3 the solution grow like

1 (T -t) 1 p-1
when approaching the blow up time T = T (σ, ϕ), see [START_REF] Below | Blow up for some nonlinear parabolic problems with convection under dynamical boundary conditions[END_REF]. Here we shall show that the same holds for p > 3 with 4p(p -1)(p -3) > 1. 1 Recall the following basic Lemma 2.1 ([3]) Under ( 2) and (3), the solution

u σ ∈ C 2,1 Ω × [0, T (σ, ϕ)) of (1) satisfies ∂ t u σ ≥ 0 in Ω × [0, T (σ, ϕ)). If, in addition, ϕ is not identically vanishing on Ω, then ∂ t u σ > 0 in Ω × (0, T (σ, ϕ)).
First, we show that the lower growth order amounts always to -1 p-1 for any p > 2.

Lemma 2.2 Under the hypotheses (2) and (3), the maximal solution u of (1) satisfies

u σ (•, t) ∞ ≥ 1 p -1 1 p-1 T (σ, ϕ) -t -1 p-1
for all t ∈ [0, T (σ, ϕ)). 1 Numerically this means that it is sufficient to choose ). By (3) and Lemma 2.1 we have ∂ t u ≥ 0 on [-a, a] × [0, T ). Thus, g is increasing and continuous on [0, T ), and, thereby, g is differentiable almost everywhere in [0, T ). Choose t ∈ [0, T ), 0 < h < t, x and x h such that g is differentiable at t and

p > 4 3 + 2 √ 7 3 cos 1 3 arccos 107 √ 7 392 ≈ 3.0403022002854636178438894434... Proof. Set g(t) = u(•, t) ∞ for t ∈ [0, T
u(•, t) ∞ = u(x, t) and u(•, t -h) ∞ = u(x h , t -h).
Then

g(t) -g(t -h) = u(x, t) -u(x h , t -h) ≤ u(x, t) -u(x, t -h),
and there exists θ ∈ (0, 1) such that

u(x, t) = u(x, t -h) + h∂ t u(x, t -θh).
We conclude

g(t) -g(t -h) h ≤ ∂ t u(x, t -θh).
and, letting h tend to 0,

g (t) ≤ ∂ t u(x, t).
By hypothesis on u and definition of g,

g (t) ≤ ∂ 2 x u(x, t) -u(x, t)∂ x u(x, t) + u(x, t) p ≤ u(x, t) p = g(t) p .
Integration between t > 0 and t < τ < T yields

g(t) 1-p -g(τ ) 1-p ≤ (p -1)(τ -t).
As τ tends to T , the function g(τ ) tends to ∞. This shows

g(t) 1-p ≤ (p -1)(T -t).
The growth order bound is optimal as the example of constant initial data ϕ > 0 under Neumann boundary conditions displays well. Theorem 2.3 Suppose conditions (2) and (3) to hold and that

(4) p > 3, p(p -1)(p -3) > 1 4 .
Then there is a constant C > 0 such that the maximal solution

u σ ∈ C 2,1 ([-a, a]× [0, T (σ, ϕ)) of (1) satisfies u σ (•, t) ≤ C (T (σ, ϕ) -t) 1 p-1 for all t ∈ [0, T (σ, ϕ)).
Proof. We can adopt and improve the proofs by Friedman & McLeod [4] and von Below & Pincet [START_REF] Below | Blow up for some nonlinear parabolic problems with convection under dynamical boundary conditions[END_REF]. For the reader's convenience we repeat some similar arguments here. Choose α > 1 such that

p(p -1)(p -3) ≥ α 2 4 > 1 4
.

We choose M > 1 et M > 1 6 (α -1) -2 p-3 . Suppose ξ ∈ ]0, t 0 2 ] with t 0 = ϕ 1-p ∞ p-1 .
We shall show that there exists δ > 0 such that (5)

∂ t u ≥ δe -M t (u p + u 3 ) in [-a, a] × [ξ, T (σ, ϕ)).
In the same way as in Corollary 2.7 from [START_REF] Below | Blow up for some nonlinear parabolic problems with convection under dynamical boundary conditions[END_REF], the strong minimum principle from [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF] yields that there exists a positive constant c such that (6)

y := ∂ t u ≥ c > 0 in [-a, a] × [ξ, T (σ, ϕ)).
Now, set d(t) = exp(-M t) with M > 1 sufficiently large to be determined later and k(u) = u p + u 3 and introduce

J = ∂ t u -δd(t)k(u),
where δ > 0 is sufficiently small such that

(7) J(•, ξ) ≥ 0 in [-a, a]
in view to [START_REF] Mailly | Explosion des solutions de problèmes paraboliques sous conditions au bord dynamiques, Thèse doctorale à l'Université du Littoral Côte d'Opale[END_REF]. By classical regularity results, J ∈ C 2,1 ([-a, a] × [ξ, T (σ, ϕ))), see e.g. [START_REF] Ladyzenskaya | Linear and quasilinear equations of parabolic type[END_REF], and J satisfies the boundary condition

B σ (J) = B σ (y) -δdk (u)B σ (u) -σδd k(u) = σδ exp(-M t)k(u) ≥ 0.
Moreover, J fulfills

∂ t J -∆J + u∂ x J -(pu p-1 -∂ x u)J = δdH(u) in [-a, a] × [ξ, T (σ, ϕ)),
where

H(u) := pu p-1 k(u) -k (u)u p + k (u)(∂ x u) 2 - d d k(u) -k(u)∂ x u.
In order to show that H(u) ≥ 0, we prove the inequality

|∂ x u|(u p + u 3 ) ≤ M (u p + u 3 ) + (p -3)u p+2 (8) + p(p -1)u p-2 + 6u (∂ x u) 2 .
It is obvious when |∂ x u| ≤ M . Now, we suppose that |∂ x u| > M . In the case where u 2 ≤ 6|∂ x u|, (8) is fulfilled because

u 3 |∂ x u| ≤ 6u(∂ x u) 2 and u p |∂ x u| ≤ p(p- 1)u p-2 (∂ x u) 2 since p > 3. If u 2 > 6|∂ x u|, then we have u > √ 6M = (α -1) -1
p-3 , and u p + u 3 ≤ αu p .

(8) is satisfied if

α|∂ x u|u p ≤ (p -3)u p+2 + p(p -1)u p-2 (∂ x u) 2
which is equivalent to

α|∂ x u|u 2 ≤ (p -3)u 4 + p(p -1)(∂ x u) 2 ≤ p -3u 2 -p(p -1)|∂ x u| 2 + 2 p(p -1)(p -3)u 2 |∂ x u|.
In other words, we just need

α ≤ 2 p(p -1)(p -3),
which is guaranteed by the definition of α and p. Thus, ( 5) is shown. Finally, for the growth order, it suffices to estimate u(

•, t) ∞ for t ∈ [ t 0 2 , T (σ, ϕ)). For each x ∈ [-a, a] the integral S t ∂ t u(x, s) u p (x, s) ds = u(x,S) u(x,t) 1 η p dη
converges as S T (σ, ϕ). We conclude

u 1-p (x, T (σ, ϕ)) -u 1-p (x, t) 1 -p ≥ δ (T (σ, ϕ) -t) , and
u(x, t) ≤ (p -1) 1 1-p max δ 1 1-p , 2T (σ, ϕ) t 0 -1 1 p-1 1 (T (σ, ϕ) -t) 1/p-1 ,
which holds especially at the blow up points.

Blow up points

Let p > 2 and suppose that σ is a constant satisfying (9) σ > 0.

For the initial values, we require in addition to condition (3)

(10) ϕ(x) ≥ ϕ(-x) in [0, a],
and the one bump condition

ϕ (x) > 0 in [-a, x 0 ), ϕ (x) < 0 in (x 0 , a] (11)
with some x 0 ∈ (-a, a). Set T = T (σ, ϕ). Following the proof of Lemma 5.2 of [START_REF] Below | Blow up for reaction diffusion equations under dynamical boundary conditions[END_REF], and using an argument by Friedman & McLeod, see Lemma 5.2 from [START_REF] Friedman | Blow up of positive solutions of semilinear heat equations[END_REF], in the case where h(u) = u p , we can state Lemma 3.1 There exists a continuous function x = s(t) such that for 0 < t < T

∂ x u(x, t) > 0 if -a ≤ x < s(t), ∂ x u(x, t) < 0 if s(t) < x ≤ a. Proof. By Lemma 2.1, ∂ t u > 0 on Ω × [0, T ). The boundary condition B σ (u) = 0 with σ > 0 shows ∂ ν u < 0 on ∂Ω × (0, T ), i.e. (12) ∂ x u > 0 on {-a} × (0, T ) and ∂ x u < 0 on {a} × (0, T ).
Moreover, (11) implies

∂ x u > 0 on [-a, x 0 ) × {0} and ∂ x u < 0 on (x 0 , a] × {0}.
First, by continuity of the solution u, there are two relatively open subsets A + and A -of Ω × [0, T ) such that 1. A + ⊆ {∂ x u > 0} and A -⊆ {∂ x u < 0}.

2.

A + and A -are connected.

3. the parabolic boundary Ω × {0} ∪ ∂Ω × (0, T ) belongs to ∂A + ∪ ∂A -∪ {x 0 }.

4.

A + and A -are maximal with respect to the properties 1. -3.

We shall show that A -= {∂ x u < 0} and

A + = {∂ x u > 0}. Recall that u ∈ C 3,1 (Ω × [0, T )), see [5]. Thus, y := ∂ x u ∈ C 2,1 (Ω × [0, T )) and    ∂ t y = ∆y -y 2 -u∂ x y + pu p-1 y in Ω × [0, T ), B σ (y) = 0 on ∂Ω × [0, T ), y(•, 0) = ϕ in Ω. For 0 < τ < T , set Ω τ := Ω × [0, τ ). Let Q -denote a connected component of {∂ x u < 0}∩Ω τ and prove that Q -⊆ A -.
We first show that ∂Q -and the parabolic boundary of Ω τ meet at least in one point different from {x 0 }. For that purpose, suppose that

∂Q -∩ Ω × {0} ∪ ∂Ω × [0, τ ) ⊆ {x 0 }.
It yields y ≡ 0 on ∂Q -∩ Ω τ . Moreover, by definition of Q -we have

∂ t y ≤ ∆y -u∂ x y in Q -, y ≤ 0 on ∂Q -.
Since y attains its maximum 0 on ∂Q -, the strong maximum principle from [START_REF] Walter | Differential and integral inequalities[END_REF] implies y ≡ 0 in Q -, which is impossible. Clearly,

Q -∩ A -= ∅, which implies A -∪ Q -= A -by maximality of A -. Now, for a connected component Q + of {∂ x u > 0} ∩ Ω τ , suppose that ∂Q + ∩ Ω × {0} ∪ ∂Ω × [0, τ ) ⊆ {x 0 }.
We still have y ≡ 0 on ∂Q + ∩ Ω τ , which implies that the interior of the set

P + := Q + \ {pu p-1 -y < 0} is not empty. Then y satisfies ∂ t y ≥ ∆y -u∂ x y + y(pu p-1 -y) ≥ ∆y -u∂ x y in P + , y ≥ 0 on ∂P + .
Since y attains its minimum 0 on ∂Q + ⊆ ∂P + , the strong minimum principle from [START_REF] Walter | Differential and integral inequalities[END_REF] again, leads to y ≡ 0 in P + , in contradiction with the definition of P + . Thus, we can conclude that {∂ x u > 0} = A + . Then, since {∂ x u > 0} and {∂ x u < 0} are connected, for (x + , t) ∈ {∂ x u > 0} and (x -, t) ∈ {∂ x u < 0} with 0 < t < T , we have x + < x -. Furthermore, we can prove that for all x such that (x, t) ∈ {∂ x u = 0}, x + < x < x -. Indeed, for x 1 < x 2 < x 3 and s ∈ (0, T ) with (x 1 , s) and (x 3 , s) belonging to {∂ x u > 0} and (x 2 , t) ∈ {∂ x u = 0}, we can choose x 1 , x 3 , s and r ∈ (0, s) such that [x 1 , x 3 ]×[r, s) ⊆ {∂ x u > 0}. For x 1 and x 3 sufficiently close to x 2 and r sufficiently close to s, we have pu p-1 -y ≥ 0, and we obtain

∂ t y ≥ ∆y -u∂ x y in [x 1 , x 3 ] × [r, s], y ≥ 0 on {x 1 , x 3 } × [r, s] ∪ [x 1 , x 3 ] × {r}.
Thus, y attains its minimum in (x 2 , s) and the strong minimum principle leads to y ≡ 0 in [x 1 , x 3 ] × [r, s], which is impossible. In the same way, points of the form (x 1 , s) and (x 3 , s) with x 1 < x 2 < x 3 and s ∈ (0, T ) with (x 1 , s) and (x 3 , s) belonging to {∂ x u < 0} and (x 2 , t) ∈ {∂ x u = 0} can be excluded. Finally, the analytic non linearity implies the analyticity of the function u(•, t), and, if we consider

x 1 , x 2 ∈ Ω and s ∈ [0, T ) such that ∂ x u(•, s) = 0 in [x 1 , x 2 ],
we obtain ∂ x u(•, s) = 0 in Ω, in contradiction with (12). Now, we can state the following Theorem 3.2 Under Conditions (9)-(11), for each (x, t) ∈ [0, a] × [0, T ) it holds u(x, t) ≥ u(-x, t).

Proof. Set v(x, t) := u(-x, t) in [0, a]×[0, T ) and introduce the function y defined by y(x, t) := u(x, t) -v(x, t). Then y is a solution belonging to

C([0, a] × [0, T )) ∩ C 2,1 ([0, a]×](0, T )) of the problem        ∂ t y = ∂ 2 x y + v∂ x y + δy -(u + v)∂ x u in [0, a] × (0, T ), y(x, 0) ≥ 0 in [0, a], B σ (y) = 0 on {a} × (0, T ), y = 0 on {0} × (0, T ), with δ(x, t) = u p (x, t) -u p (-x, t) u(x, t) -u(-x, t) .
Now, suppose that there exists a point (x, t) ∈ [0, a] × (0, T ) with (13) y(x, t) < 0, then y(•, t) attains a negative minimum at (x, t) ∈ [0, a] × (0, T ) such that

(14) u(x, t) < v(x, t) ∂ x u(x, t) = ∂ x v(x, t).
If x > s( t), then, by Lemma 3.1, ∂ x u(x, t) < 0. In a neighbourhood V of (x, t) in which ∂ x u < 0, we have

∂ t y -∂ 2 x y -v∂ x y -δy ≥ 0.
The comparison principle in [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF] leads to y ≥ 0, in contradiction with (14). On the other hand, if x = s( t) we have y(x, t) = u(x, t) -u(-x, t) ≥ 0, in contradiction with (13). Finally, for 0 ≤ x < s( t), we have ∂ x u(x, t) > 0 and ∂ x u(-x, t) > 0 since -s( t) < -x ≤ 0 < s( t). Then we conclude that

∂ x y(x, t) = ∂ x u(x, t) + ∂ x u(-x, t) > 0,
again, in contradiction with (14).

The last two results immediately yield the following. The two following theorems will show that blow up can only occur in the interval [s -, s + ].

Theorem 3.5 Under the aforementioned assumptions, no point in [-a, s -) is a blow up point.

Proof. By Corollary 3.3, s -≥ 0. Suppose β ∈ [-a, s -) and choose T 0 < T sufficiently close to T such that s(t) > β for

T 0 ≤ t < T . Introduce R = [-a, β] × (T 0 , T ),
and

J = ∂ x u -εdk with d(x) = (x -β) n , n ∈ N * even, k(u) = u q , q = p -1,
and ε > 0 sufficiently small such that

(15) J ≥ 0 in [-a, β] × {T 0 }, and (16)
u q + n(n -1) (x -β) 2 + n |x -β| u ≥ εu q-1 (x -β) n u + 2nq|x -β| n-1 .
Condition ( 15) is due to Lemma 3.1, where as ( 16) is a consequence of the assumptions on p, q and n. Moreover J(β, •) > 0 in [T 0 , T ) by Lemma 3.1, since d(β) = 0. Set f (u) := u p , (16) implies that H defined by

H(u) := f (u)k(u) -f (u)k (u) -ε dk 2 (u) -2d k(u)k (u) - d d k(u)u + d d k(u) + k (u)(∂ x u) 2 + 1 εd (∂ x u) 2 satisfies H(u) ≥ k (u)(∂ x u) 2 + 1 εd (∂ x u) 2
≥ 0 since u is strictly positive in R, as well as k for q > 1. Recall that u > 0 for t > 0 by the comparison principle of [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF] and by Lemma 2.1. Moreover, J satisfies on {-a} × (T 0 , T ),

B σ (J) = B σ (∂ x u) -εdk (u)B σ (u) -εd k(u) = -εn(-a -β) n-1 u q (-a, t)
since σ is a constant. As Ω is an interval of the real line, classical interior regularity results, see e.g. [START_REF] Ladyzenskaya | Linear and quasilinear equations of parabolic type[END_REF], imply that

u ∈ C 3,2 ([-a, β] × [T 0 , T )). Thus, J belongs to C 2,2 ([-a, β] × [T 0 , T )) and is a solution of        ∂ t J -∆J + u∂ x J + K(u)J = εdH(u) ≥ 0 in [-a, β) × (T 0 , T ), B σ (J) ≥ 0 on {-a} × (T 0 , T ), J(•, T 0 ) ≥ 0 in [-a, β], J ≥ 0 on {β} × (T 0 , T ),
where

K(u) = J -f (u) + 2εdk(u) -2εd k (u)
. By the comparison principle from [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF] we conclude that J ≥ 0 in [-a, β] × [T 0 , T ), in other words

∂ x u k(u) ≥ εd.
Integration between x and y with -a ≤ x < y < β and the parity of n yield

u 1-q (x, t) -u 1-q (y, t) ≥ ε q -1 n + 1 [(y -β) n+1 -(x -β) n+1 ] > 0.
Finally, suppose that x ∈ [-a, β) is a blow up point. Using 1 -q < 0, we conclude that u 1-q (y, t) < 0 for y ∈ (x, β), and t sufficiently close to T , which is impossible.

Theorem 3.6 Under the aforementioned assumptions, no point of (s + , a] is a blow up point.

Proof. We can follow the idea of the proof of Theorem 3.5. Suppose that s + < a and γ ∈ (s + , a]. Choose T 0 < T sufficiently close to T such that s(t) < γ for T 0 ≤ t < T . Set R = [γ, a] × (T 0 , T ) and

J = ∂ x u + εdk with d(x) = e 1 γ-x , k(u) = u q , 2 < q < p,
and ε > 0 sufficiently small such that

(17) J(•, T 0 ) ≤ 0 in [γ, a].
Condition (17) is possible by Lemma 3.1. Using f (u) := u p , set

H(u) = f (u)k(u) -f (u)k (u) + εdk 2 (u) -2εd k(u)k (u) - d d k(u)u + d d k(u) + (∂ x u) 2 k (u) = (p -q)u p+q-1 + u q+1 (γ -x) 2 + 1 (γ -x) 4 - 2 (γ -x) 3 u q +εe -1 γ-x 2qu 2q-1 (γ -x) 2 + u 2q + q(q -1)(∂ x u) 2 u q-2 .
Then H(u) ≥ 0 since p > q > 2. Moreover, J satisfies on {a} × (T 0 , T ) the dynamical boundary condition,

B σ (J) = B σ (∂ x u) + εdk (u)B σ (u) + εd k(u) = -ε (γ -a) 2 e 1 γ-a u q (a, t) since σ is a constant. Thus J ∈ C 2,2 ([γ, a] × [T 0 , T )) is a solution of        ∂ t J -∆J + u∂ x J + K(u)J = -εdH(u) ≤ 0 in (γ, a] × (T 0 , T ), B σ (J) ≤ 0 on {a} × (T 0 , T ). J(•, T 0 ) ≤ 0 on [γ, a], J(γ, •) ≤ 0 on (T 0 , T ),
where K(u) := J -f (u)-2εdk(u)+2εd k (u). By the comparison principle of [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF], J ≤ 0 in [γ, a]×[T 0 , T ). By integrating as above, we obtain u 1-q (y, t)-u 1-q (x, t) > 0 for γ < x < y ≤ a. Thus if y ∈ (γ, a] is a blow up point, u 1-q (x, t) < 0 for x ∈ (γ, y) and t sufficiently close to T , in contradiction to the positivity of u. Thus, u remains bounded in R.

In fact, it will be shown that s -= s + . In other words, blow up can only occur at a singleton.

Theorem 3.7 Under Conditions (3) (9) (10) (11), the blow up set of Problem (1) consists at most of a single point.

Proof. Theorem 3.5 and Theorem 3.6 imply that blow up can only occur in [s -, s + ]. It remains to show that s -= s + . Suppose that s + > s -and that u blows up at

z 1 ∈ [s -, s + ]. Set y 1 = s --ε, with (18) 0 < ε < s + -s - 2 .
By Theorem 3.5, there exists a constant C 0 > 0 such that

(19) u(y 1 , t) ≤ C 0 in [0, T ).
As u explodes at z 1 , there is τ 1 sufficiently close to T such that u(z 1 , t) > C 0 for any τ 1 < t < T . Moreover, by Lemma 3.1,

u(z 1 , t) ≤ max Ω u(•, t) = u(s(t), t) for all 0 < t < T.
Thus, by Definition 3.4 and Lemma 3.1, there exists τ ∈ (0, T ) with T -τ sufficiently small such that for y 2 = s(τ ) > s + -ε and for α = y 1 +y 2

2

we have

u(y 2 , τ ) > C 0 , u(x, τ ) ≤ u(2α -x, τ ) for x ∈ [y 1 , α], u(x, τ ) < u(2α -x, τ ) for x ∈ [y 1 , α).
Then (19) and Lemma 2.1 yield u(y 1 , t) < u(y 2 , t) for τ ≤ t < T.

Set v(x, t) = u(2α -x, t) in [y 1 , α] × [τ, T ) and w(x, t) = v(x, t) -u(x, t). Then w ∈ C 2,1 ([y 1 , α] × [τ, T )) is a solution of        ∂ t w = ∆w + v∂ x w + δw + (u + v)∂ x u in (y 1 , α) × (τ, T ), w(•, τ ) ≥ 0 in [y 1 , α], w > 0 on {y 1 } × (τ, T ), w = 0 on {α} × (τ, T ),
where we have set

δ(x, t) = v p (x, t) -u p (x, t) v(x, t) -u(x, t) .
Suppose that (20) w(x, t) < 0 at some (x, t) ∈ (y 1 , α) × (τ, T ). Then there exists a point (x, t) ∈ (y 1 , α) × (τ, T ) at which w(•, t) takes a negative minimum. Thus,

(21) v(x, t) < u(x, t), ∂ x v(x, t) = ∂ x u(x, t). If α > x > s( t) then ∂ x u(x, t) < 0 and ∂ x u(2α -x, t) < 0 since 2α -x > α > x > s( t). Thus, ∂ x w = -∂ x u(2α -x, t) -∂ x u(x, t) > 0,
in contradiction with (21). Next, recall that x is the unique zero of ∂ x u(•, t), by Lemma 3.1. Thus, α > x = s( t) would lead to another zero since 2α -x = x. Finally, suppose y 1 ≤ x < s( t), then ∂ x u(x, t) > 0. Let V a neighborhood of (x, t) in which ∂ x u > 0. In V , we have

∂ t w -∆w -v∂ x w -δw = (u + v)∂ x u ≥ 0,
and comparison principle of [START_REF] Below | A qualitative theory for parabolic problems under dynamical boundary conditions[END_REF] leads to w ≥ 0, in contradiction to (20). Thus, we have shown that w ≥ 0. For any t ∈ (τ, T ), the maximum of u(•, t) in [y 1 , y 2 ] can not be attained for x ∈ [y 1 , α). As ∂ x u vanishes at s(t) by Lemma 3.1, α ≤ s(t) for τ < t < T . Thus, by Definition 3.4

s -= lim inf t→T s(t) ≥ α = y 1 + y 2 2 ≥ s -+ s + 2 -ε
and s -≥ s + -2ε, in contradiction with (18). This permits to conclude that s -= s + .

Corollary 3 . 3

 33 Under the aforementioned hypotheses, s(t) ≥ 0 and∂ x u(x, t) > 0 in [-a, 0) × (0, T ).Definition 3.4 s -= lim inf t→T s(t) and s + = lim sup t→T s(t)

Figure 1 :

 1 Figure 1: Initial data ϕ and the bifurcation of local maxima

Figure 2 : 4 2 .

 242 Figure 2: Convergence to one bump for c = 10.7 and conservation of two bumps for c = 9


Sourav Chakraborty
email: sourav@cs.technion.ac.il

Eldar Fischer

Arie Matsliah
email: ariem@cwi.nl

Raphael Yuster

C S Chakraborty

HARDNESS AND ALGORITHMS FOR RAINBOW CONNECTIVITY

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connectivity of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In addition to being a natural combinatorial problem, the rainbow connectivity problem is motivated by applications in cellular networks. In this paper we give the first proof that computing rc(G) is NP-Hard. In fact, we prove that it is already NP-Complete to decide if rc(G) = 2, and also that it is NP-Complete to decide whether a given edge-colored (with an unbounded number of colors) graph is rainbow connected. On the positive side, we prove that for every ǫ > 0, a connected graph with minimum degree at least ǫn has bounded rainbow connectivity, where the bound depends only on ǫ, and the corresponding coloring can be constructed in polynomial time. Additional non-trivial upper bounds, as well as open problems and conjectures are also presented.

Introduction

Connectivity is perhaps the most fundamental graph-theoretic property, both in the combinatorial sense and the algorithmic sense. There are many ways to strengthen the connectivity property, such as requiring hamiltonicity, k-connectivity, imposing bounds on the diameter, requiring the existence of edge-disjoint spanning trees, and so on.

An interesting way to quantitavely strengthen the connectivity requirement was recently introduced by Chartrand et al. in [START_REF] Chartrand | Rainbow connection in graphs[END_REF]. An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. Clearly, if a graph is rainbow connected, then it is also connected. Conversely, any connected graph has a trivial edge coloring that makes it rainbow connected; just color each edge with a distinct color. Thus, one can properly define the rainbow connectivity of a connected graph G, denoted rc(G), as the smallest number of colors that are needed in order to make G rainbow connected. An easy observation is that if G is connected and has n vertices then rc(G) ≤ n -1, since one may color the edges of a given spanning tree with distinct colors. We note also the trivial fact that rc(G) = 1 if and only if G is a clique, the (almost) trivial fact that rc(G) = n -1 if and only if G is a tree, and the easy observation that a cycle with k > 3 vertices has rainbow connectivity ⌈k/2⌉. Also notice that, clearly, rc(G) ≥ diam(G) where diam(G) denotes the diameter of G.

Chartrand et al. computed the rainbow connectivity of several graph classes including complete multipartite graphs [START_REF] Chartrand | Rainbow connection in graphs[END_REF]. Caro et al. [START_REF] Caro | On rainbow connectivity[END_REF] considered the extremal graph-theoretic aspects of rainbow connectivity. They proved that if G is a connected graph with n vertices and with minimum degree 3 then rc(G) < 5n/6, and if the minimum degree is δ then rc(G) ≤ ln δ δ n(1+f (δ)) where f (δ) tends to zero as δ increases. They also determine the threshold function for a random graph G(n, p(n)) to have rc(G) = 2. In their paper, they conjecture that computing rc(G) is an NP-Hard problem, as well as conjecture that even deciding whether a graph has rc(G) = 2 in NP-Complete.

In this paper we address the computational aspects of rainbow connectivity. Our first set of results solve, and extend, the complexity conjectures from [START_REF] Caro | On rainbow connectivity[END_REF]. Indeed, it turns out that deciding whether rc(G) = 2 is an NP-Complete problem. Our proof is by a series of reductions, where on the way it is shown that 2-rainbow-colorability is computationally equivalent to the seemingly harder question of deciding the existence of a 2-edge-coloring that is required to rainbow-connect only vertex pairs from a prescribed set. Suppose we are given an edge coloring of the graph. Is it then easier to verify whether the colored graph is rainbow connected? Clearly, if the number of colors in constant then this problem becomes easy. However, if the coloring is arbitrary, the problem becomes NP-Complete: Theorem 1.2. The following problem is NP-Complete: Given an edge-colored graph G, check whether the given coloring makes G rainbow connected.

For the proof of Theorem 1.2, we first show that the st version of the problem is NP-Complete. That is, given two vertices s and t of an edge-colored graph, decide whether there is a rainbow path connecting them.

We now turn to positive algorithmic results. Our main positive result is that connected n-vertex graphs with minimum degree Θ(n) have bounded rainbow connectivity. More formally, we prove: Theorem 1.3. For every ǫ > 0 there is a constant C = C(ǫ) such that if G is a connected graph with n vertices and minimum degree at least ǫn, then rc(G) ≤ C. Furthermore, there is a polynomial time algorithm that constructs a corresponding coloring for a fixed ǫ.

The proof of Theorem 1.3 is based upon a modified degree-form version of Szemerédi's Regularity Lemma that we prove and that may be useful in other applications. From our algorithm it is also not hard to find a probabilistic polynomial time algorithm for finding this coloring with high probability (using on the way the algorithmic version of the Regularity Lemma from [START_REF] Alon | The algorithmic aspects of the Regularity Lemma[END_REF] or [START_REF] Fischer | Approximate Hypergraph Partitioning and Applications[END_REF]).

We note that connected graphs with minimum degree ǫn have bounded diameter, but the latter property by itself does not guarantee bounded rainbow connectivity. As an extreme example, a star with n vertices has diameter 2 but its rainbow connectivity is n -1. The following theorem asserts however that having diameter 2 and only logarithmic minimum degree suffices to guarantee rainbow connectivity 3.

Theorem 1.4. If G is an n-vertex graph with diameter 2 and minimum degree at least 8 log n then rc(G) ≤ 3. Furthermore, such a coloring is given with high probability by a uniformly random 3edge-coloring of the graph G, and can also be found by a polynomial time deterministic algorithm.

Since a graph with minimum degree n/2 is connected and has diameter 2, we have as an immediate corollary: Corollary 1.5. If G is an n-vertex graph with minimum degree at least n/2 then rc(G) ≤ 3.

The rest of this paper is organized as follows. The next section contains the hardness results, including the proofs of Theorem 1.1 and Theorem 1.2. Section 3 contains the proof of Theorem 1.3 and the proof of Theorem 1.4. At the end of the proof of each of the above theorems we explain how the algorithm can be derived -this mostly consists of using the conditional expectation method to derandomize the probabilistic parts of the proofs. The final Section 4 contains some open problems and conjectures. Due to space limitations, several proofs have been omitted from this write-up.

Hardness results

We first give an outline of our proof of Theorem 1.1. We begin by showing the computational equivalence of the problem of rainbow connectivity 2, that asks for a red-blue edge coloring in which all vertex pairs have a rainbow path connecting them, to the problem of subset rainbow connectivity 2, asking for a red-blue coloring in which every pair of vertices in a given subset of pairs has a rainbow path connecting them. This is proved in Lemma 2.1 below.

In the second step, we reduce the problem of extending to rainbow connectivity 2, asking whether a given partial red-blue coloring can be completed to a obtain a rainbow connected graph, to the subset rainbow connectivity 2 problem. This is proved in Lemma 2.2 below.

Finally, the proof of Theorem 1.1 is completed by reducing 3-SAT to the problem of extending to rainbow connectivity 2.

Lemma 2.1. The following problems are polynomially equivalent:

(1) Given a graph G decide whether rc(G) = 2.

(2) Given a graph G and a set of pairs P ⊆ V (G) × V (G), decide whether there is an edge coloring of G with 2 colors such that all pairs (u, v) ∈ P are rainbow connected.

Lemma 2.2. The first problem defined below is polynomially reducible to the second one:

(1) Given a graph G = (V, E) and a partial 2-edge-coloring χ : Ê → {0, 1} for Ê ⊂ E, decide whether χ can be extended to a complete 2 edge-coloring χ : E → {0, 1} that makes G rainbow connected.

(2) Given a graph G and a set of pairs P ⊆ V (G) × V (G) decide whether there is an edge coloring of G with 2 colors such that all pairs (u, v) ∈ P are rainbow connected.

We are unable to present the proofs of Lemma 2.1 and Lemma 2.2 due to space limitations.

Proof of Theorem 1.1 We show that Problem 1 of Lemma 2.2 is NP-hard, and then deduce that 2-rainbow-colorability is NP-Complete by applying Lemma 2.1 and Lemma 2.2 while observing that it clearly belongs to NP. We reduce 3-SAT to Problem 1 of Lemma 2.2. Given a 3CNF formula φ = m i=1 c i over variables x 1 , x 2 , . . . , x n , we construct a graph G φ and a partial 2-edge coloring χ ′ : E(G φ ) → {0, 1} such that there is an extension χ of χ ′ that makes G φ rainbow connected if and only if φ is satisfiable.

We define G φ as follows:

V (G φ ) = {c i : i ∈ [m]} ∪ {x i : i ∈ [n]} ∪ {a} E(G φ ) = {c i , x j } : x j ∈ c i in φ ∪ {x i , a} : i ∈ [n] ∪ {c i , c j } : i, j ∈ [m] ∪ {x i , x j } : i, j ∈ [n]
and we define the partial coloring χ ′ as follows:

∀ i,j∈[m] χ ′ ({c i , c j }) = 0 ∀ i,j∈[n] χ ′ ({x i , x j }) = 0 ∀ {x i ,c j }∈E(G φ ) χ ′ ({x i , c j }) = 0 if x i is positive in c j , 1 otherwise
while all the edges in {x i , a} : i ∈ [n] (and only they) are left uncolored.

Assuming without loss of generality that all variables in φ appear both as positive and as negative, one can verify that a 2-rainbow-coloring of the uncolored edges corresponds to a satisfying assignment of φ and vice versa.

The proof of Theorem 1.2 is based upon the proof of the following theorem.

Theorem 2.3. The following problem is NP-complete: Given an edge colored graph G and two vertices s, t of G, decide whether there is a rainbow path connecting s and t.

Proof. Clearly the problem is in NP. We prove that it is NP-Complete by reducing 3-SAT to it. Given a 3CNF formula φ = m i=1 c i over variables x 1 , x 2 , . . . , x n , we construct a graph G φ with two special vertices s, t and a coloring χ :

E(G φ ) → [|E(G φ )|] such
that there is a rainbow path connecting s and t in G φ if and only if φ is satisfiable.

We start by constructing an auxiliary graph G ′ from φ. The graph

G ′ has 3m + 2 vertices, that are partitioned into m + 2 layers V 0 , V 1 , . . . , V m , V m+1 , where V 0 = {s}, V m+1 = {t} and for each i ∈ [m]
, the layer V i contains the three vertices corresponding to the literals of c i (a clause in φ). The edges of G ′ connect between all pairs of vertices residing in consecutive layers. Formally,

E(G ′ ) = {u, v} : ∃i ∈ [m + 1] s.t. u ∈ V i-1 and v ∈ V i .
Intuitively, in our final colored graph G φ , every rainbow path from s to t will define a satisfying assignment of φ in a way that for every i ∈ [m], if the rainbow path contains a vertex v ∈ V i then the literal of c i that corresponds to v is satisfied, and hence c i is satisfied. Since any path from s to t must contain at least one vertex from every layer V i , this will yield a satisfying assignment for the whole formula φ. But we need to make sure that there are no contradictions in this assignment, that is, no opposite literals are satisfied together. For this we modify G ′ by replacing each literalvertex with a gadget, and we define an edge coloring for which rainbow paths yield only consistent assignments.

For every variable x j , j ∈ [n], let v j 1 , v j 2 , . . . , v j k be the vertices of G ′ corresponding to the positive literal x j , and let v j 1 , v j 2 , . . . , v j ℓ be the vertices corresponding to the negative literal x j . We can assume without loss of generality that both k ≥ 1 and ℓ ≥ 1, since otherwise the formula φ can be simplified. For every such variable x j we also introduce k × ℓ distinct colors α j 1,1 , . . . , α j k,ℓ . Next, we transform the auxiliary graph G ′ into the final graph G φ .

For every a ∈ [k] we replace the vertex v ja that resides in layer (say) V i with ℓ + 1 new vertices v 1 , v 2 , . . . , v ℓ+1 that form a path in that order. We also connect all vertices in V i-1 to v 1 and connect all vertices in V i+1 to v ℓ+1 . For every b ∈ [ℓ], we color the edge {v b , v b+1 } in the new path with the color α j a,b . Similarly, for every b ∈ [ℓ] we replace the vertex v j b from layer (say) V i ′ with k + 1 new vertices v 1 , v 2 , . . . , v k+1 that form a path, and connect all vertices in V i ′ -1 to v 1 and all vertices in V i ′ +1 to v k+1 . For every a ∈ [k], we color the edge {v a , v a+1 } with α j a,b . All other edges of G φ (which were the original edges of G ′ ) are colored with fresh distinct colors.

Clearly, any path from s to t in G φ must contain at least one of the newly built paths in each layer. On the other hand, it is not hard to verify that any two paths of opposite literals of the same variable have edges sharing the same color.

Proof of Theorem 1.2. We reduce from the problem in Theorem 2.3. Given an edge colored graph G = (V, E) with two special vertices s and t, we construct a graph G ′ = (V ′ , E ′ ) and define a coloring χ ′ : E ′ → [|E ′ |] of its edges such that s and t are rainbow connected in G if and only if the coloring of G ′ makes G ′ rainbow connected.

Let V = {v 1 = s, v 2 , . . . , v n = t} be the vertices of the original graph G. We set

V ′ = V ∪ {s ′ , t ′ , b} ∪ {s 1 , v 1 2 , v 2 2 , . . . , v 1 n-1 , v 2 n-1 , t 2 } and E ′ = E ∪ {s ′ , s}, {t ′ , t}, {s, s 1 }, {t, t 2 } ∪ {b, v i } : i ∈ [n] ∪ ∪ {v i , v j i } : i ∈ [n], j ∈ {1, 2} ∪ {v a i , v b j : i, j ∈ [n], a, b ∈ {1, 2} .
The coloring χ ′ is defined as follows:

• all edges e ∈ E retain the original color, that is χ ′ (e) = χ(e);

• the edges {t, t ′ }, {s, b} and

{v i , v 1 i } : i ∈ [n -1]
are colored with a special color c 1 ; • the edges {s, s ′ }, {t, b} and {v i , v 2 i } : i ∈ [2, n] are colored with a special color c 2 ; • the edges in {v i , b} : i ∈ [2, n -1] are colored with a special color c 3 ;

• the edges in {v a i , v b j } : i, j ∈ [n], a, b ∈ {1, 2}
are colored with a special color c 4 . One can verify that χ ′ makes G ′ rainbow connected if and only if there was a rainbow path from s to t in G.

Upper bounds and algorithms

The proof of our main Theorem 1.3 is based upon a modified degree-form version of Szemerédi's Regularity Lemma, that we prove here and that may be useful in other applications. We begin by introducing the Regularity Lemma and the already known degree-form version of it.

Regularity Lemma

The Regularity Lemma of Szemerédi [START_REF] Szönyi | Szemerédi Regular partitions of graphs[END_REF] is one of the most important results in graph theory and combinatorics, as it guarantees that every graph has an ǫ-approximation of constant descriptive size, namely a size that depends only on ǫ and not on the size of the graph. This approximation "breaks" the graph into a constant number of pseudo-random bipartite graphs. This is very useful in many applications since dealing with random-like graphs is much easier than dealing with arbitrary graphs. In particular, as we shall see, the Regularity Lemma allows us to prove that graphs with linear minimum degree have bounded rainbow connectivity.

We first state the lemma. For two nonempty disjoint vertex sets A and B of a graph G, we define E(A, B) to be the set of edges of G between A and B. The edge density of the pair is defined by

d(A, B) = |E(A, B)|/(|A||B|). Definition 3.1 (ǫ-regular pair). A pair (A, B) is ǫ-regular if for every A ′ ⊆ A and B ′ ⊆ B satisfying |A ′ | ≥ ǫ|A| and |B ′ | ≥ ǫ|B|, we have |d(A ′ , B ′ ) -d(A, B)| ≤ ǫ.
An ǫ-regular pair can be thought of as a pseudo-random bipartite graph in the sense that it behaves almost as we would expect from a random bipartite graph of the same density. Intuitively, in a random bipartite graph with edge density d, all large enough sub-pairs should have similar densities.

A partition V 1 , . . . , V k of the vertex set of a graph is called an equipartition if |V i | and |V j | differ by no more than 1 for all 1 ≤ i < j ≤ k (so in particular every V i has one of two possible sizes). The order of an equipartition denotes the number of partition classes (k above). An equipartition V 1 , . . . , V k of the vertex set of a graph is called ǫ-regular if all but at most ǫ k 2 of the pairs (V i , V j ) are ǫ-regular. Szemerédi's Regularity Lemma can be formulated as follows. [START_REF] Szönyi | Szemerédi Regular partitions of graphs[END_REF]). For every ǫ > 0 and positive integer K, there exists N = N 3.2 (ǫ, K), such that any graph with n ≥ N vertices has an ǫ-regular equipartition of order k, where K ≤ k ≤ N .

Lemma 3.2 (Regularity Lemma

As mentioned earlier, the following variation of the lemma comes useful in our context. Lemma 3.3 (Regularity Lemma -degree form [START_REF] Komlós | Szemerédis Regularity Lemma and its applications in graph theory[END_REF]). For every ǫ > 0 and positive integer K there is N = N 3.3 (ǫ, K) such that given any graph G = (V, E) with n > N vertices, there is a partition of the vertex-set V into k + 1 sets V ′ 0 , V ′ 1 , . . . , V ′ k , and there is a subgraph G ′ of G with the following properties:

(1) K ≤ k ≤ N , (2) s |V ′ 0 | ≤ ǫ 5 n and all other components V ′ i , i ∈ [k] are of size ℓ n-s k , (3) for all i ∈ [k], V ′ i induces an independent set in G ′ , (4) for all i, j ∈ [k], the pair (V ′ i , V ′ j ) is ǫ 5 -regular in G ′ , with density either 0 or at least ǫ 4 , ( 5
) for all v ∈ V , deg G ′ (v) > deg G (v) -ǫ 3
n. This form of the lemma (see e.g. [START_REF] Komlós | Szemerédis Regularity Lemma and its applications in graph theory[END_REF]) can be obtained by applying the original Regularity Lemma (with a smaller value of ǫ), and then "cleaning" the resulting partition. Namely, adding to the exceptional set V ′ 0 all components V i incident to many irregular pairs, deleting all edges between any other pairs of clusters that either do not form an ǫ-regular pair or they do but with density less than ǫ, and finally adding to V 0 also vertices whose degree decreased too much by this deletion of edges.

A modified degree form version of the Regularity Lemma

In order to prove that graphs with linear minimum degree have bounded rainbow connectivity number, we need a special version of the Regularity Lemma, which is stated next.

Lemma 3.4 (Regularity Lemma -new version).

For every ǫ > 0 and positive integer K there is N = N 3.4 (ǫ, K) so that the following holds: If G = (V, E) is a graph with n > N vertices and minimum degree at least ǫn then there is a subgraph G ′′ of G, and a partition of V into V ′′ 1 , . . . , V ′′ k with the following properties:

(1) K ≤ k ≤ N , ( 2
)
for all i ∈ [k], (1 -ǫ) n k ≤ |V ′′ i | ≤ (1 + ǫ 3 ) n k , (3) for all i ∈ [k], V ′′ i induces an independent set in G ′′ , (4) for all i, j ∈ [k], (V ′′ i , V ′′ j
) is an ǫ 3 -regular pair in G ′′ , with density either 0 or at least ǫ 16 , (5) for all i ∈ [k] and every v ∈ V ′′ i there is at least one other class V ′′ j so that the number of neighbors of v in G ′′ belonging to

V ′′ j is at least ǫ 2 |V ′′ j |.
We also note that the above a partition as guaranteed by our modified version of the Regularity Lemma can be found in polynomial time for a fixed ǫ (with somewhat worse constants), by using the exact same methods that were used in [START_REF] Alon | The algorithmic aspects of the Regularity Lemma[END_REF] for constructing an algorithmic version of the original Regularity Lemma. We are unable to give the complete proof of Lemma 3.4 due to space limitations.

Proof of Theorem 1.3

In this section we use our version of the Regularity Lemma to prove Theorem 1.3. First we need some definitions. Given a graph G = (V, E) and two subsets

V 1 , V 2 ⊆ V , let E(V 1 , V 2 )
denote the set of edges having one endpoint in V 1 and another endpoint in V 2 . Given a vertex v, let Γ(v) denote the set of v's neighbors, and for

W ⊆ V , let Γ W (v) denote the set W ∩ Γ(v).
For an edge coloring χ : E → C, let π χ denote the corresponding partition of E into (at most) |C| components. For two edge colorings χ and χ ′ , we say that χ ′ is a refinement of χ if π χ ′ is a refinement of π χ , which is equivalent to saying that χ ′ (e 1 ) = χ ′ (e 2 ) always implies χ(e 1 ) = χ(e 2 ). Observation 3.5. Let χ and χ ′ be two edge-colorings of a graph G, such that χ ′ is a refinement of χ. For any path P in G, if P is a rainbow path under χ, then P is a rainbow path under χ ′ . In particular, if χ makes G rainbow connected, then so does χ ′ .

We define a set of eight distinct colors

C = {a 1 , a 2 , a 3 , a 4 , b 1 , b 2 , b 3 , b 4 }.
Given a coloring χ : E → C we say that u, v ∈ V are a-rainbow connected if there is a rainbow path from u to v using only the colors a 1 , a 2 , a 3 , a 4 . We similarly define b-rainbow connected pairs. The following is a central lemma in the proof of Theorem 1.3. The proof of Lemma 3.6 is given in Section 3.4. Lemma 3.6. For any ǫ > 0, there is N = N 3.6 (ǫ) such that any connected graph G = (V, E) with n > N vertices and minimum degree at least ǫn satisfies the following. There is a partition

Π of V into k ≤ N components V 1 , V 2 , . . . , V k ,
and a coloring χ : E → C such that for every i ∈ [k] and every u, v ∈ V i , the pair u, v is both a-rainbow connected and b-rainbow connected under χ.

Using Lemma 3.6 we derive the proof of Theorem 1.3. For a given ǫ > 0, set N = N 3.6 (ǫ) and set C = 3 ǫ N + 8. Clearly, any connected graph G = (V, E) with n ≤ C vertices satisfies rc(G) ≤ C. So we assume that n > C ≥ N , and let Π = V 1 , . . . , V k be the partition of V from Lemma 3.6, while we know that k ≤ N .

First observe that since the minimal degree of G is ǫn, the diameter of G is bounded by 3/ǫ. This can be verified by e.g. by taking an arbitrary vertex r ∈ V and executing a BF S algorithm from it. Let L 1 , . . . , L t be the layers of vertices in this execution, where L i are all vertices at distance i from r. Observe that since the minimal degree is at least ǫn, the total number of vertices in every three consecutive layers must be at least ǫn, thus t ≤ 3/ǫ. Since the same claim holds for any r ∈ V , this implies that diam(G) Proof. Let u, v ∈ V be any pair of G's vertices. If u and v reside in the same component V i of the partition Π, then (by Lemma 3.6) they are connected by a path P of length at most four, which is a rainbow path under the the original coloring χ. Since χ ′ is a refinement of χ, the path P remains a rainbow path under χ ′ as well (see Observation 3.5).

≤ t ≤ 3/ǫ. Now let T = (V T , E T ) be a connected subtree of G on at most k • diam(G) ≤ 3 ǫ N vertices such that for every i ∈ [k], V T ∩ V i = ∅.
Otherwise, let u ∈ V i and v ∈ V j for i = j. Let t i and t j be vertices of the subtree T , residing in V i and V j respectively. By definition of χ ′ , there is a rainbow path from t i to t j using colors from H. Let P t denote this path. In addition, by Lemma 3.6 we know that for the original coloring χ, there is a rainbow path P a from u to t i using colors a 1 , . . . , a 4 and there is a rainbow path P b from v to t j using colors b 1 , . . . , b 4 . Based on the fact that χ ′ is a refinement of χ, it is now easy to verify that P t , P a and P b can be combined to form a rainbow path from u to v under χ ′ . This concludes the proof of Theorem 1.3, apart from the existence of a polynomial time algorithm for finding this coloring. We note that all arguments above apart from Lemma 3.6 admit polynomial algorithms for finding the corresponding structures. The algorithm for Lemma 3.6 will be given with its proof.

Proof of Lemma 3.6

First we state another auxiliary lemma, which is proved in the next section. Lemma 3.8. For every ǫ > 0 there exists N = N 3.8 (ǫ) such that any graph G = (V, E) with n > N vertices and minimum degree at least ǫn satisfies the following: There exists a partition Π = V 1 , . . . , V k of V such that for every i ∈ [k] and every u, v ∈ V i , the number of edge disjoint paths of length at most four from u to v is larger than 8 5 log n. Moreover, these sets can be found using a polynomial time algorithm for a fixed ǫ.

Proof. (of Lemma 3.6) First we apply Lemma 3.8 to get the partition Π. Now the proof follows by a simple probabilistic argument. Namely, we color every edge e ∈ E by choosing one of the colors in C = {a 1 , . . . , a 4 , b 1 , . . . , b 4 } uniformly and independently at random. Observe that a fixed path P of length at most four is an a-rainbow path with probability at least 8 -4 . Similarly, P is a b-rainbow path with probability at least 8 -4 . So any fixed pair u, v ∈ V i is not both a-rainbowconnected and b-rainbow-connected with probability at most 2(1-8 -4 ) 8 5 log n < n -2 , and therefore the probability that all such pairs are both a-rainbow connected and b-rainbow connected is strictly positive. Hence the desired coloring must exist.

To find the coloring algorithmically, we note that for every partial coloring of the edges of the graph it is easy to calculate the conditional probability that the fixed pair of vertices u, v is not both a-rainbow-connected and b-rainbow-connected. Therefore we can calculate the conditional expectation of the number of pairs that are not so connected for any partial coloring. Now we can derandomize the random selection of the coloring above by using the conditional expectation method (cf. [START_REF] Alon | The Probabilistic Method, Second Edition[END_REF]): In every stage we color one of the remaining edges in a way that does not increase the conditional expectation of the number of unconnected pairs. Since this expectation is smaller than 1 in the beginning, in the end we will have less than 1 unconnected pair, and so all pairs will be connected.

Proof of Lemma 3.8

Given ǫ > 0 let L = N 3.4 (ǫ, 1) and set N to be the smallest number that satisfies ǫ 4 N L > 8 5 log N . Now, given any graph G = (V, E) with n > N vertices and minimum degree at least ǫn, we apply Lemma 3.4 with parameters ǫ and 1. Let Π = V 1 , V 2 , . . . , V k be the partition of V obtained from Lemma 3.4, while as promised, k ≤ L = N 3.4 (ǫ).

Fix i ∈ [k] and u, v ∈ V i . From Lemma 3.4 we know that there is a component V a such that u has at least ǫ 3k n neighbors in V a . Similarly, there is a component V b such that v has at least ǫ 3k n neighbors in V b . Let Γ u,a denote the set of u's neighbors in V a , and similarly, let Γ v,b denote v's neighbors in V b . We assume in this proof that V a = V b , and at the end it will be clear that the case V a = V b can only benefit.

We say that a set W u = {w 1 , . . . , w t } ⊆ V i is distinctly reachable from u if there are distinct vertices w ′ 1 , . . . , w ′ t ∈ Γ u,a such that for every j ∈ [t], {w j , w ′ j } ∈ E. Notice that the collection of pairs {w j , w ′ j } corresponds to a matching in the graph G, where all edges of the matching have one endpoint in V i and the other endpoint in Γ u,a . Similarly, we say that W v ⊆ V i is distinctly reachable from v if there are distinct vertices w ′ 1 , . . . , w ′ t ∈ Γ v,b such that for every j ∈ [t], {w j , w ′ j } ∈ E.

Observe that it is enough to prove that there exists a set W ⊆ V i of size ǫ 4 N L > 8 5 log N which is distinctly reachable from both u and v. This will imply the existence of 8 5 log N edge disjoint paths of length four from u to v.

Our first goal is to bound from below the size of the maximal set W u as above. Since (by Lemma 3.4) V a and V i are ǫ 3 -regular pairs with density ≥ ǫ 16 and since ǫ 3 < ǫ/3, the number of edges between Γ u,a and V i is at least To prove that W = W u ∩ W a is large, we similarly use the regularity condition, but now on the pair (Γ v,b , W u ). We get,

|E(Γ v,b , W u )| ≥ ǫ 16 -ǫ 3 |Γ v,b ||W u |.
Here too, by Observation 3.9 we can bound from below the size of a maximal matching in the pair (Γ v,b , W u ) with

ǫ 16 -ǫ 3 |Γ v,b ||W u | |Γ v,b | + |W u | ≥ ǫ 16 -ǫ 3 ǫ 3k n ǫ 2 64k n ǫ 3k n + ǫ 2 64k n ≥ ǫ 4 n k ≥ ǫ 4 n L > 8 5 log N,
where the last inequality follows from our choice of N . Recall that the matching that we found defines the desired set W , concluding the proof. An algorithmic version of this lemma can be derived by simply using an algorithmic version of Lemma 3.4 in the selection of V 1 , . . . , V k above.

Graphs with diameter 2

Proof of Theorem 1.4. Consider a random 3-coloring of E, where every edge is colored with one of three possible colors uniformly and independently at random. It is enough to prove that for all pairs u, v ∈ V the probability that they are not rainbow connected is at most 1/n 2 . Then the proof follows by the union bound (cf. [START_REF] Alon | The Probabilistic Method, Second Edition[END_REF]). them. The rainbow diameter number, denoted rd(G) is the smallest number of colors used in such a coloring. Clearly, rd(G) ≥ rc(G) and obviously every connected graph with n vertices has rd(G) < n 2 . Unlike rainbow connectivity, which is a monotone graph property (adding edges never increases the rainbow connectivity number) this is not the case for the rainbow diameter (although we note that constructing an example that proves nonmonotonicity is not straightforward). Clearly, computing rd(G) is NP-Hard since rc(G) = 2 if and only if rd(G) = 2. It would be interesting to prove a version of Theorem 1.3 for rainbow diameter. We conjecture that, indeed, if G is a connected graph with minimum degree at least ǫn then it has a bounded rainbow diameter.

• Suppose that we are given a graph G for which we are told that rc(G) = 2. Can we rainbow-color it in polynomial time with o(n) colors? For the usual coloring problem, this version has been well studied. It is known that if a graph is 3-colorable (in the usual sense), then there is a polynomial time algorithm that colors it with Õ(n 3/14 ) colors [START_REF] Blum | An Õ(n 3/14 )-coloring algorithm for 3-colorable graphs[END_REF].

Theorem 1 . 1 .

 11 Given a graph G, deciding if rc(G) = 2 is NP-Complete. In particular, computing rc(G) is NP-Hard.

Lemma 3 . 7 .

 37 Such a subtree must exist in G since as observed earlier, diam(G) ≤ 3/ǫ. Let χ : E → C be the coloring from Lemma 3.6, and let H = {h 1 , h 2 , . . . , h |E T | } be a set of |E T | ≤ 3 ǫ N fresh colors. We refine χ by recoloring every e i ∈ E(T ) with color h i ∈ H. Let χ ′ : E → C ∪ H be the resulting coloring of G. The following lemma completes the proof of Theorem 1.3. The coloring χ ′ makes G rainbow connected. Consequently, rc(G) ≤ |E T | + 8 ≤ C.

  ǫ 16ǫ 3 |Γ u,a | • |V i |. Before proceeding, we make the following useful observation. Let H = (A, B) be a bipartite graph with γ|A||B| edges. Then H contains a matching M of size γ |A||B| |A|+|B| . Proof. Consider the following process that creates M . Initially M 0 = ∅. Then in step i, we pick an arbitrary edge {a, b} ∈ E(H), set M i+1 = M i ∪ {a, b} and remove from E(H) all the edges incident with either a or b. Clearly, in each step the number of removed edges is bounded by |A| + |B|, so the process continues for at least E(H) |A|+|B| = γ |A||B| |A|+|B| steps. Hence |M| = | i M i | ≥ γ |A||B| |A|+|B| .Returning to the proof of Lemma 3.8, by Observation 3.9 the size of a maximal set W u as above is at least

	Observation 3.9. ǫ 16	-ǫ 3	|Γ u,a ||V i | |Γ u,a | + |V i |	≥	ǫ 16	-ǫ 3	ǫn/(3k) (n/k) ǫn/(3k) + n/k	≥	ǫ 2 64k	n.

This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/3.0/.

Acknowledgment

We thank Van Bang Le and Zsolt Tuza for pointing out an error in one of our concluding remarks in an earlier version of this paper.

Let us fix a pair u, v ∈ V , and bound from above the probability that this pair is not rainbow connected. We know that both Γ(u) and Γ(v) (the neighborhoods of u and v) contain at least 8 log n vertices.

(1) If {u, v} ∈ E then we are done.

(2) If |Γ(u) ∩ Γ(v)| ≥ 2 log n then there are at least 2 log n edge-disjoint paths of length two from u to v. In this case, the probability that none of these paths is a rainbow path is bounded by (1/3) 2 log n < 1/n 2 , and we are done.

and in addition, since the first two cases do not hold and the diameter of G is two, all the (length two) shortest paths from A's vertices to v go through the vertices in B. This implies that every vertex x ∈ A has a neighbor b(x) ∈ B (b(x) need not be a one-one function). Let us consider the set of at least 6 log n edge-disjoint paths P = {u, x, b(x) : x ∈ A}. For each x ∈ A, the probability that u, x, b(x), v is a rainbow path (given the color of the edge

Moreover, this event is independent of the corresponding events for all other members of A, because this proabablity does not change even with full knowledge of the colors of all edges incident with v. Therefore, the probability that none of the paths in P extends to a rainbow path from u to v is at most (7/9) 6 log n ≤ 1/n 2 , as required.

The above proof immediately implies a probabilistic polynomial expected time randomized algorithm with zero error probability (since we can also efficiently check if the coloring indeed makes G 3-rainbow connected). The algorithm can be derandomized and converted to a polynomial time probabilistic algorithm using the method of conditional expectations (cf. [START_REF] Alon | The Probabilistic Method, Second Edition[END_REF]) similarly to the proof of Lemma 3.6: For every partial coloring of the edges we can efficiently bound the conditional probability that a fixed pair u, v is not rainbow-connected, using the relevant one of the three cases concerning u and v that were analyzed above. Now we can color the edges one by one, at each time taking care not to increase the bound on the conditional expectation of unconnected pairs that results from the above probability bound for every u and v. Since the bound on the expectation was smaller than 1 before the beginning of the process, in the end we would get a valid 3-rainbow-coloring of G.

Concluding remarks and open problems

• Theorem 1.3 asserts that a connected graph with minimum degree at least ǫn has bounded rainbow connectivity. However, the bound obtained is huge as it follows from the Regularity Lemma. It would be interesting to find the "correct" bound. It is even possible that rc(G) ≤ C/ǫ for some absolute constant C. • The proof of Theorem 1.1 shows that deciding whether rc(G) = 2 is NP-Complete. Although this suffices to deduce that computing rc(G) is NP-Hard, we still do not have a proof that deciding whether rc(G) ≤ k is NP-Complete for every fixed k. It is tempting to conjecture that for every k it is NP-Hard even to distinguish between 2-rainbow-colorable graphs and graphs that are not even k-rainbow-colorable. • A parameter related to rainbow connectivity is the rainbow diameter. In this case we ask for an edge coloring so that for any two vertices, there is a rainbow shortest path connecting