K Fritsch

E Kermarrec

K A Ross

Y Qiu

J R D Copley

D Pomaranski

J B Kycia

H A Dabkowska

B D Gaulin

Temperature and Magnetic Field Dependence of Spin Ice Correlations in the Pyrochlore Magnet Tb 2 Ti 2 O 7

Keywords: numbers: 75, 25, -j 75, 10, Kt 75, 40, Gb 75, 40, -s

We present a parametric study of the diffuse magnetic scattering at 1 2 , 1 2 , 1 2 positions in reciprocal space, ascribed to a frozen antiferromagnetic spin ice state in single crystalline Tb2Ti2O7. Our highresolution neutron scattering measurements show that the elastic (-0.02 meV < E < 0.02 meV) 1 2 , 1 2 , 1 2 scattering develops strongly below ∼ 275 mK, and correlates with the opening of a spin gap of ∼ 0.06 -0.08 meV over most of the Brillouin zone. The concomitant low-lying magnetic spin excitations are weakly dispersive and appear to soften near the 1 2 , 1 2 , 1 2 wave vector at 80 mK. The nature of the transition at 275 mK has many characteristics of spin glass behavior, consistent with ac-susceptibility measurements. The application of a magnetic field of 0.075 T applied along the [1-10] direction destroys the 1 2 , 1 2 , 1 2 elastic scattering, revealing the fragility of this short-range ordered ground state. We construct a refined H-T phase diagram for Tb2Ti2O7 and [1-10] fields which incorporates this frozen spin ice regime and the antiferromagnetic long-range order previously known to be induced in relatively large fields. Specific heat measurements on the same crystal reveal a sharp anomaly at Tc ∼ 450 mK and no indication of a transition near ∼ 275 mK. We conclude that the higher temperature specific heat peak is not related to the magnetic ordering but is likely a signal of other, nonmagnetic, correlations.

I. INTRODUCTION

The search for experimental realizations of quantum spin liquid (QSL) and quantum spin ice (QSI) states is of great current interest 1,2 due to the potential for exotic physics within these systems. Geometrically frustrated magnetic materials are central to the discovery of such exotic states. [START_REF] Lacroix | Introduction to frustrated magnetism[END_REF] Besides materials based on quasi two-dimensional (2D) lattices such as herbertsmithite 4,5 or the organic spin liquid candidate κ-(BEDT-TTF) 2 Cu 2 (CN) 3 , 6,7 the three-dimensional (3D) pyrochlore lattice consisting of networks of cornersharing tetrahedra, has been the focus of significant and sustained research efforts. 1,2,[8][9][10] The family of rare earth-based titanate pyrochlores has played a prominent role in these studies as many members of this family can be grown as large and pristine single crystals. [11][12][13][14] Within this family, Tb 2 Ti 2 O 7 stands out as perhaps the least well understood, despite having been studied in this context for well over a decade. 15 In this material, the Tb 3+ magnetic moments that decorate the pyrochlore lattice are expected to display Ising-like easy axis anisotropy with spins pointing along the local 111 axes, either into or out of the tetrahedra, as a consequence of them being non-Kramers ions and their crystal field (CF) doublet ground state. [16][17][18] Based on a negative Curie-Weiss temperature (Θ CW ∼ -14 K) and this Ising-like anisotropy, mean-field theory predicts the classical ground state of Tb 2 Ti 2 O 7 to not be frustrated, and Tb 2 Ti 2 O 7 is, on the basis of Monte Carlo simulations, 19 expected to order into an antiferromagnetic (AF) Q = 0 Néel ordered state around ∼ 1 K. 16 Yet, this material fails to exhibit conventional long-range order (LRO) down to at least 50 mK as shown in very early studies by Gardner et al. 15,20 This puzzle has motivated two vigorously debated [21][22][23][24] theoretical scenarios to account for Tb 2 Ti 2 O 7 's disordered ground state: a quantum spin ice (QSI) scenario 21,22,25 and a nonmagnetic singlet ground state. 26 The QSI proposal introduces quantum dynamics to the problem through virtual fluctuations of the Tb 3+ ions between their ground state and excited CF doublets. These quantum fluctuations reposition Tb 2 Ti 2 O 7 into the nearby spin ice regime within a generalized phase diagram appropriate to Ising-like pyrochlore magnets. 19 The nonmagnetic singlet scenario assumes a splitting of the accidental CF doublet ground state of the Tb 3+ ions (J = 6, non-Kramers) into two non-magnetic singlets through a Jahn-Teller-like symmetry lowering of the CF environment, thus producing a non-magnetic ground state. The latter scenario implies a non-cubic structure at low but finite temperatures in Tb 2 Ti 2 O 7 . To date, evidence for such a static structural distortion is lacking at all but very large magnetic fields. 27,28 Recent experiments on Tb 2 Ti 2 O 7 have shown signatures of the proposed QSI state, most notably pinch point scattering 29 indicative of Coulombic correlations in spin ice, and signs of a magnetization plateau for magnetic fields along [111] theoretically proposed by Molavian et al., 25 although there is a diversity in the interpretation of this latter evidence. [30][31][32][33][34][35] Our recent neutron scattering measurements 36 on single-crystalline Tb 2 Ti 2 O 7 at 70 mK have revealed short-range spin ice correlations at 1 2 , 1 2 , 1 2 wave vectors which can be ascribed to a shortrange antiferromagnetically ordered spin ice state with spin canting at an angle of ∼12 • from the local 111 axes. These static correlations observed in the elastic scattering channel were shown to be very sensitive to both applied magnetic field and temperature, although parametric studies of the field and temperature dependence of this scattering were not performed. The static 1 2 , 1 2 , 1 2 correlations were separated from low-lying inelastic magnetic excitations by a spin gap of ∼0.06-0.08 meV. Other neutron studies also observed diffuse scattering intensity at 1 2 , 1 2 , 1 2 positions, however, these studies did not relate the scattering to a short-range antiferromagnetically ordered spin ice state. 29,37 A subsequent study of nonstoichiometric Tb 2+x Ti 2-x O 7+y by Taniguchi et al. 38 also observed the appearance of a Bragg-like peak associated with quasi-long-range order at low temperatures in a polycrystalline sample which was lightly "stuffed", Tb 2+x Ti 2-x O 7+y (x = 0.005).

In this paper, we report a detailed study of the temperature and field dependence of the previously observed elastic 1 2 , 1 2 , 1 2 and associated low-lying inelastic scattering in Tb 2 Ti 2 O 7 . We show that the elastic scattering appears upon lowering the temperature below ∼ 275 mK and that its appearance correlates with the opening of a spin gap within the low-lying magnetic spectral weight over most of the Brillouin zone. This magnetic spectral weight and its associated spin excitations exhibit weak dispersion and appear to soften somewhat at the "quasi"-ordering wave vector 1 2 , 1 2 , 1 2 and at the lowest temperature measured, T = 80 mK. The application of a magnetic field along [ 1-10 ] leads to a destruction of the short-range ordered ground state by µ 0 H = 0.075 T. We construct a new H-T phase diagram for Tb 2 Ti 2 O 7 in a [ 1-10 ] magnetic field, which encompasses both this new frozen spin ice state at very low fields and temperature, and the previously known long-range ordered, antiferromagnetic state which exists at relatively high fields and over a much larger range of temperatures.

II. EXPERIMENTAL DETAILS

The single crystal sample of Tb 2 Ti 2 O 7 used for the neutron scattering measurements we present here is the same sample used in earlier studies 36,39 and was grown using the optical floating zone technique at Mc-Master University. [START_REF] Dabkowska | Crystal growth of oxides by optical floating zone technique. experimental approach to defects determination[END_REF][START_REF] Gardner | [END_REF] Time-of-flight neutron scattering measurements were performed using the disk-chopper spectrometer DCS 42 at the NIST Center for Neutron Research. Two different incident energies were employed; for lower energy-resolution measurements we used E i =3.27 meV, giving an energy resolution of 0.1 meV, while the higher energy-resolution measurements we report used E i =1.28 meV with a resulting resolution of 0.02 meV. The sample was carefully aligned with the [ 1-10 ] direction vertical to within 0.5 • , such that the (H,H,L) plane was coincident with the horizontal scattering plane. Measurements were performed in a temperature range of ∼ 80 mK < T 650 mK and at magnetic fields ≤ 0.2 T.

Specific heat measurements were performed with a 3 He/ 4 He dilution refrigerator at the University of Waterloo. The crystal used for neutron scattering measurements was sectioned into a 33.8 mg mass with dimension 2.6 x 2.6 x 1.3 mm 3 and this smaller single crystal was used in the heat capacity study. The relaxation method was employed with a thermal weak link of manganin wire, with conductance 5.0 x 10 -7 J/K/s at 0.80 K. The resulting time constant was greater than 600 seconds at the highest temperature measured. The average step size for the relaxation measurement was 3.5% of the nominal temperature, with a minimum equilibration time window of five times the thermal relaxation constant.

III. MAGNETIC FIELD DEPENDENCE

Figure 1 shows a series of elastic scattering maps in the (H,H,L) plane for different magnetic fields applied along [ 1-10 ] in panels (a) through (e). Here, elastic scattering integrates over -0.1 meV < E < 0.1 meV in energy. Figure 1(f) shows a cut of this elastic scattering, along the [111] high-symmetry direction covering the (-0.5, -0.5, 1.5), (0.5, 0.5, 2.5) as well as the (0, 0, 2) and (1, 1, 3) Bragg positions, as indicated by the yellow dashed line in Fig. 1(e). As the applied magnetic field is increased to 0.05 T, the previously observed strong diffuse scattering at the 1 2 , 1 2 , 1 2 positions in zero field (panel (a)) gets suppressed substantially (panel (b)) and is much reduced by 0.075 T (panel (c)).

Simultaneous to the suppression of the 1 2 , 1 2 , 1 2 diffuse scattering intensity in fields up to 0.075 T, we observe a strong build-up in magnetic elastic intensity at the structurally forbidden (0, 0, 2) Bragg peak. As the field is increased further (panels (d) and (e)), most of the remaining diffuse scattering condenses into the Bragg position at (0, 0, 2). The intensity scale is linear for Fig. through (0, 0, 2) in Fig. 1(f) is plotted on a logarithmic intensity scale. Note that the highest applied field here, 0.2 T, is still far below the critical [ 1-10 ] field ∼ 2 T, above which Tb 2 Ti 2 O 7 is found in a field-induced antiferromagnetic long-range ordered state, characterized by the appearance of resolution-limited spin waves and a strong (1, 1, 2) magnetic Bragg peak. 39 A further feature in the elastic scattering maps are weak rods of scattering along both the 00L and 111 directions that can be identified as evidence for significant anisotropic exchange in Tb 2 Ti 2 O 7 . 29 Rods of magnetic scattering have been identified in other rare-earth titanate pyrochlores, such as Yb 2 Ti 2 O 7 , 43 where anisotropic exchange is well established. 12,44,45 Anisotropic exchange in Tb 2 Ti 2 O 7 has recently been investigated in papers by Bonville et al. 24 and by Curnoe, 46 the latter of which related an effective S = 1/2 spin Hamiltonian to diffuse magnetic neutron scattering.

1(a)-(e). In contrast, the cut along the [111] direction

One can integrate up the elastic scattering data in a relatively small region around the 1 2 , 1 2 , 1 2 or (0, 0, 2) positions in reciprocal space, and look at its explicit [ 1-10 ] magnetic field dependence. This is what is shown in Fig. 2, with relatively small integration ranges of ±0.2 r.l.u. in [H,H,H], and ±0.15 r.l.u. perpendicular to [H,H,H] for 1 2 , 1 2 , 1 2 , and ±0.1 r.l.u. in [H,H,H] and ±0.15 r.l.u. perpendicular to [H,H,H] for (0, 0, 2). We identify the inflection point in the field dependence of positions is seen to extend out to (0.5,0.5,2) and (-0.5,-0.5,2) below 0.075 T; above this field, the diffuse scattering increases in intensity and narrows considerably at the (0,0,2) position. An empty can background subtraction and correction for detector efficiency were performed for all data shown. Error bars are ±1σ.

µ 0 H ∼ 0.075 T, as well as the leveling off of the (0, 0, 2) elastic intensity for fields beyond 0.075 T with the T ∼ 0 phase boundary to the frozen, antiferromagnetic spin ice state in Tb 2 Ti 2 O 7 . The inset to Fig. 2 shows a color map of the diffuse elastic scattering around the (0,0,2) position. This color map is made of a series of scans along [H,H,2], integrating over L= [1.9, 2.1] r.l.u.. The resolution limited weak scattering at (0,0,2) in zero magnetic field has been fit and removed from the scattered intensity shown in this inset. As evident from this map and consistent with the integrated elastic intensity shown in Fig. 2, strong diffuse scattering at the 1 2 , 1 2 , 1 2 positions is present below µ 0 H = 0.075 T, and this extends across these [H,H,2] scans, that is to (0.5,0.5,2) and (-0.5,-0.5,2). For fields above µ 0 H = 0.075 T, this diffuse scattering collapses into the (0,0,2) position.

The field dependence of the elastic magnetic scattering, and in particular the rapid fall-off of the 1 2 , 1 2 , 1 2 frozen spin ice elastic scattering near 0.075 T is in qualitative agreement with recent work by Yin et al.. 33 They have proposed a low-temperature low-field phase diagram for Tb 2 Ti 2 O 7 based on magnetization and ac-susceptibility data. These measurements reveal two magnetic phases, the first one of which appears below 140 mK and for fields µ 0 H < 0.067 T, while another phase is found at very low temperatures T < 40 mK and higher fields 0.067 < µ 0 H < 0.6 T. From the observation of a weak magnetization plateau in the presence of a [111] magnetic field, theoretically predicted by Molavian et al., 25 these authors conclude that a quantum kagome spin ice state exists at higher fields, with a QSI state at low and zero magnetic fields. Although these Yin et al. 33 measurements were performed in a [111] applied magnetic field, we note that anisotropy in the magnetization of Tb 2 Ti 2 O 7 is only observed for field strengths exceeding 0.3 T, 35 well above the range of applied field strengths which we report here in our neutron scattering measurements. For that reason, we consider the phase diagram presented in Ref. 32 to be germane to our findings, reinforcing our assertion that the 1 2 , 1 2 , 1 2 elastic scattering is associated with a QSI state.

IV. TEMPERATURE DEPENDENCE

The temperature dependence of the integrated elastic intensity of the 1 2 , 1 2 , 1 2 peaks in zero field is presented in Fig. 3. We determined the elastic integrated intensity (-0.1 meV <E< 0.1 meV) at the four 1 2 , 1 2 , 1 2 positions in our field of view in Fig. 3(a) and average the integrated intensities at each temperature. The corresponding background signal for each T was obtained by integrating over a region of low intensity in reciprocal space around (1, 1, 2). This background term was subsequently subtracted from the averaged 1 2 , 1 2 , 1 2 integrated elastic intensity.

The results of these integrations are shown in Fig. 3(b) for individual heating and cooling runs labeled in the order of the measurements. Two prominent features become apparent in Fig. 3. First, the temperature dependence of the 1 2 , 1 2 , 1 2 peaks behaves in an order parameter-like fashion with a distinctive drop in integrated intensity around 275 mK. Second, the ground state below 275 mK has some history dependence to it, with the elastic 1 2 , 1 2 , 1 2 peak intensity variable from one thermal history to the next. History dependence is a common feature of spin glass states. [START_REF] Mydosh | Spin Glasses: An Experimental Introduction[END_REF][START_REF] Binder | [END_REF] We first discuss the second observation. Data points were collected in three temperature sweeps; heating A, cooling B and heating B. Representative elastic reciprocal space maps for the two runs obtained during heating are shown in Fig. 3(a) for the low temperature short-range ordered ground state (80 mK or 100 mK) and for the higher temperature disordered state (400 mK or 600 mK, respectively). We observe that the absolute intensity of the ( 12 , 1 2 , 1 2 ) elastic peaks in the second heating run is a factor of ∼2 smaller, and that the overall diffuse elastic scattering background is somewhat larger compared to the first heating run. This indicates that a complex freezing process with several metastable states is likely at play at low temperatures. This is not so surprising, as the ( 12 , 1 2 , 1 2 ) elastic scattering does not correspond to long-range order, but rather is known to be characterized by a relatively short and isotropic correlation length and L= [2.4, 2.6] r.l.u.) at the four 1 2 , 1 2 , 1 2 -like positions is presented as a function of temperature for different heating and cooling cycles in panel (b). Please see text for details. Representative reciprocal space maps for the two heating cycles are shown in panel (a). Panel (c) shows the integrated intensity from (b) scaled to the difference between the low-temperature phase at 100 mK and the high-temperature phase at 600 mK (heating B) or 400 mK (heating A), placing the transition below which 1 2 , 1 2 , 1 2 peaks appear at a temperature of ∼ 275 mK. In addition, the temperature dependence of the elastic (0, 0, 2) scattering, normalized to the intensity at the lowest temperatures, is shown on the same plot, indicating no obvious temperature dependence. Various reports of this glassy transition from ac-susceptibility measurements 20,30,47,48 are encompassed by the hatched area. The specific heat anomaly found for our crystal at TCp ∼ 450 mK is indicated by a dotted vertical line. This anomaly appears at considerably higher temperature than the onset of the short-range magnetic ordering. Dashed lines serve as guide to the eyes. 4. Shift of the ac-susceptibility peaks per decade frequency for polycrystal and single crystalline samples from different groups. 30,47,51 For these three measurements, the slope ∆T T ∆(log T ) <0.1, consistent with expectations for insulating spin glasses. [START_REF] Mydosh | Spin Glasses: An Experimental Introduction[END_REF] The extrapolation of the ac-susceptibility peak to frequencies of the order 0.01 THz ∼ 0.04 meV energies, at which our measurements probe the system, shows that the expected transition occurs between 210-335 mK. The transition temperature we determine falls right within that range and is thus consistent with these measurements.

of ∼ 8 Å, again typical of spin glasses. Despite this, a common feature in all three heating and cooling runs is the appearance of the ( 12 , 1 2 , 1 2 ) peaks below 275 mK. To make that point, we scaled and normalized the integrated elastic intensities at ( 1 2 , 1 2 , 1 2 ) from Fig. 3(b) to the difference in intensity between the low-temperature state at 100 mK or below and that of the high-temperature state (400 mK or 600 mK, respectively). The result is shown in Fig. 3(c), which shows a glass-like transition to occur around ∼275 mK, independent of the detailed history dependence. We also note here that, in contrast to the elastic scattering at ( 1 2 , 1 2 , 1 2 ), the elastic scattering at (0,0,2) does not show any significant temperature dependence as shown in Figure 3(c).

The spin glass transition as measured with the ( 12 , 1 2 , 1 2 ) elastic magnetic scattering is consistent with that observed by several groups using ac-susceptibility measurements. 20,30,47,51 This data is summarized in Fig. 4, and peaks found in χ , the real part of the acsusceptibility, lie in the temperature range from ∼150-250 mK. This temperature regime is indicated with an orange hatched area in Fig. 3(b) and (c), so that the results from elastic neutron scattering and ac-susceptibility can be compared. As neutron scattering measurements are performed at relatively high frequencies compared with ac-susceptibility, it is typical for neutron scattering to measure spin freezing associated with spin glass transitions at higher temperatures than are observed in ac-susceptibility. This is illustrated in Fig. 4, in which we show the linearly extrapolated peak-shift per decade fre-quency, a phenomenological parameter used to describe the temperature dependence of the χ peak in spin glasses as a function of frequency, to the frequency appropriate to our neutron measurements, ∼0.01 THz. Thus, a transition between 210-335 mK would be consistent with the range of previously reported AC susceptibility peaks for different samples, which is in good agreement with our observations. This frequency dependence may indeed play a role here, although as seen in Fig. 3(b) and (c), this does not seem to be a large effect as the agreement between the two techniques is quite good. We also note that Lhotel et al. 30 report a distinction between between the glassy behavior observed in Tb 2 Ti 2 O 7 and canonical spin glass behavior based on the frequency dependence of their ac-susceptibility data.

Based on the temperature and field dependence of the 39 Note that both temperature and field axes are on a logarithmic scale. [1-10] field extracted from neutron scattering measurements in the low field and low temperature region presented in this work and from high field and higher temperature measurements by Rule et al.. 39 The magnetic phase transitions measured by Yin et al. 33 from ac-susceptibility with fields along [111] are also shown.

FIG. 5. H-T phase diagram for Tb2Ti2O7 in

Higher energy resolution neutron scattering measurements with E i = 1.28 meV were performed to investigate the temperature and Q-dependence of the low-lying spin excitations in Tb 2 Ti 2 O 7 in zero magnetic field. Figure 6(a) shows a plot of intensity vs energy transfer obtained by integrating over the two ( 12 , 1 2 , 1 2 ) positions in reciprocal space shown as the black squares in the inset to Fig. 6(a). Data is shown for three different temperatures, in the ground state (T = 80 mK), near the spin glass transition (T = 275 mK) and well above the transition (T = 600 mK). As the temperature is lowered through the transition at 275 mK, spectral weight is transferred from the 12 , 1 2 , 1 2 ) peak intensity averaged over two peaks as a function of temperature. Note the logarithmic intensity scale. The Q-integration range (H= [±0.3, ±0.7], L = [1.2, 1.8] r.l.u.) is shown in the inset by the two black squares. Panel (b) shows the intensity vs energy transfer plot for the averaged ( 1 2 , 1 2 , 1 2 ) (on-peak) positions compared to other averaged (off-peak) positions at a temperature of 80 mK. The integration ranges for the averaging and extraction of the energy dependence is depicted in the inset by the black and magenta squares. low-energy inelastic channel into the resolution-limited elastic channel (-0.02 meV < E <0.02 meV), opening up a gap of ∼ 0.06-0.08 meV. The low-lying spin excitation spectrum above the gap extends ∼0.2meV. This collapse of the magnetic spectral weight over much of the magnetic Brillouin zone into the elastic channel is a canonical signature of spin freezing behavior, as observed in spin glasses such as, for example, Y 2 Mo 2 O 7 . 52 µSR measurements 15,48 in zero field have consistently reported persistent dynamics in the spin lattice relaxation rate down to very low temperatures in Tb 2 Ti 2 O 7 , which may suggest that either the elastic scattering itself is not truly elastic on the lower frequency scale probed by µSR, or that the depletion of spectral weight in the spin gap is not complete.

Weak Q-dependence is observed to the inelastic magnetic spectral weight at low temperatures, as shown in Fig. 6(b). This plot compares intensity vs energy transfer over small regions of reciprocal space centered on Q= 1 2 , 1 2 , 1 2 wave vectors, and positions in reciprocal space far-removed from 1 2 , 1 2 , 1 2 positions (referred to in Fig. 6(b) as "on-peak" and "off-peak" positions, which are shown in the black and magenta boxes, respectively, in the inset to Fig. 6(b)). The low-energy inelastic scattering appears to be gapped over the entire Brillouin zone, the spectral weight extends ∼ 0.03 meV lower in energy at the Q= 1 2 , 1 2 , 1 2 frozen spin ice zone center as compared with Q-positions in the middle of the zone. While Tb 2 Ti 2 O 7 in H = 0 does not display conventional long-range order at any temperature and therefore does not exhibit well defined spin wave excitations, this observation is consistent with a dispersion of a sort in the small lifetime spin excitations, softening somewhat at the Q= 1 2 , 1 2 , 1 2 frozen spin ice zone center. Taken together, our new neutron scattering data is fully consistent with a spin glass transition near T g ∼ 275 mK in H = 0. This (cluster) spin glass state builds upon short-range antiferromagnetic spin ice correlations, as opposed to either primarily short-range antiferromagnetic (e.g. La 2-x Sr x CuO 4 53 ) or ferromagnetic correlations (e.g. Eu x Sr 1-x S 54 ), and has a low temperature isotropic correlation length of ∼ 8 Å, as previously reported. The collapse of the low energy magnetic spectral weight across the magnetic zone into short-range ordered elastic scattering at Q= 1 2 , 1 2 , 1 2 wave vectors is a necessary component to this picture, informing on the magnetism in the frequency or time domain. It is also inconsistent with the singlet ground state scenario proposed theoretically for Tb 2 Ti 2 O 7 at low temperatures, as the inelastic magnetic intensity which forms the gap is transferred to elastic magnetic scattering, as opposed to being transferred above the gap leaving a nonmagnetic ground state and an absence of elastic magnetic scattering. The magnetic spin glass ground state based on antiferromagnetic spin ice is also consistent with ac-susceptibility measurements which also show canonical signatures for spin glass ground states in a variety of Tb 2 Ti 2 O 7 samples, both in polycrystalline and single crystal form. While there is some sample variation observed in the precise temperature at which a signature for a spin glass state is seen in Tb 2 Ti 2 O 7 , all samples reported to date show such a signature in the approximate temperature range of 150-275 mK, consistent with the neutron scattering measurements we present in this work.

V. SPECIFIC HEAT

Significant sample variability has, however, been reported in anomalies, and the lack thereof, in the low temperature heat capacity measured on different samples of Tb 2 Ti 2 O 7 . We note that sample variability in the position and sharpness of heat capacity anomalies at low temperature in Yb 2 Ti 2 O 7 have also been reported, 55 and these have been ascribed to the relative role of weak "stuffing" (excess Yb ions substituting on the Ti sublattice at the ∼ 2% level). In particular, Taniguchi and coworkers studied a family of polycrystalline samples of the form Tb 2+x Ti 2-x O 7 for very small non-stoichiomtery, |x| < 0.005. 38 They report very significant variability in both the temperature at which the heat capacity anomaly is observed, as well as in the amplitude of the anomaly. These anomalies in C p are typically observed in the 400 mK to 500 mK regime in zero field, and these results present two important questions for our study. 7. Specific heat versus temperature for different samples of Tb2Ti2O7 in zero magnetic field. Measurements from a single crystal cut from the neutron scattering sample which we report on, is shown in black. The feature at 450 mK does not coincide with the glass-like transition at 275 mK indicated by our neutron scattering measurements. For comparison, we also show Cp data taken from the literature. 38,47 To address these questions we performed specific heat measurements down to a temperature of 220 mK on a 33.8 mg single crystal sample, cut from the neutron scattering sample which was the focus of this paper and, as already mentioned, that of a previous study. 39 Figure 7 shows the measured specific heat of our single crystal sample of Tb 2 Ti 2 O 7 , compared with several other samples, both single crystals and polycrystals, taken from the literature. 38,47 can be seen from Fig. 7, we observe a relatively large anomaly in C p at ∼ 450 mK, almost twice the T g associated with the frozen spin ice state characterized in this paper with neutron scattering. For reference, we have indicated the location of the C p anomaly in zero field in Fig. 3(c), which also shows the temperature dependence of the Q= 1 2 , 1 2 , 1 2 elastic scattering. Clearly, the temperature scales associated with the results of these measurements are distinct. As this ∼ 450 mK temperature scale is not present in either our neutron scattering results or ac-susceptibility results on Tb 2 Ti 2 O 7 taken from the literature, we conclude that while this heat capacity anomaly and its associated sample dependence are intriguing and potentially important phenomena, they do not seem to originate from magnetic dipole degrees of freedom in Tb 2 Ti 2 O 7 , similarly to what has recently been suggested in Yb 2 Ti 2 O 7 . 56

VI. CONCLUSION

In conclusion, our neutron scattering data on Tb 2 Ti 2 O 7 in a magnetic field show that a small field of ∼ 0.075 T applied along [1-10] is sufficient to destroy the short-range antiferromagnetically ordered spin ice state characterized by diffuse elastic scattering at ( 1 2 , 1 2 , 1 2 ) positions. This field range is consistent with a µ 0 H C ∼ 0.067 T for fields along [111] reported by Yin et al., 33 who also suggest that the zero-field ground state of Tb 2 Ti 2 O 7 is a quantum spin ice. The temperature dependence of the elastic diffuse scattering reveals a spin glass-like freezing at T g ∼ 275 mK. The details of the neutron signatures associated with the ( 1 2 , 1 2 , 1 2 ) elastic scattering display some history-dependence. The appearance of the elastic diffuse scattering below 275 mK correlates with the opening of a spin gap of 0.06-0.08 meV over most of reciprocal space and concomitant weakly dispersive spin excitations extending out to ∼0.2 meV. These excitations appear to go soft at the short-range ordering positions of ( 12 , 1 2 , 1 2 ). Specific heat measurements on a piece of the same single crystal show an anomaly at 450 mK, consistent with other reports by Hamaguchi et al. and Taniguchi et al.. We observe no signs for an anomaly near 275 mK, indicating that different degrees of freedom are involved in the ordering process responsible for this specific heat anomaly in Tb 2 Ti 2 O 7 . The new neutron measurements we report on the temperature and magnetic field parametrics allow us to complete the H-T magnetic phase diagram for Tb 2 Ti 2 O 7 in a [1-10] magnetic field. We find the dynamic and disordered, cooperative paramagnetic phase, which generated much of the original interest in Tb 2 Ti 2 O 7 , to be bracketed by a low-field frozen spin ice state, and a field-induced, long-range ordered antiferromagnetic state at high fields.

ment No. DMR-0944772, and was supported by NSERC of Canada. The DAVE software package 57 was used for data reduction and analysis of DCS data.

FIG. 1 . 2 , 1 2 , 1 2

 121 FIG. 1. Elastic neutron scattering data within the (H,H,L) plane of Tb2Ti2O7 at T = 80 mK for different values of applied magnetic field (H [ 1-10 ]). The energy is integrated from -0.1 meV < E < 0.1 meV. Panels (a) through (e) show the evolution of the elastic scattering for an applied magnetic field of 0, 0.05, 0.075, 0.1 and 0.2 T, respectively. Panel (f) shows the magnetic field dependence of the elastic scattering along the [111] direction cutting through the (0, 0, 2) Bragg position as indicated by the yellow arrow in panel (e). The 1 2 , 1 2 , 1 2 peaks vanish around µ0H ∼ 0.075 T. All data have an empty can background subtracted. The error bars are ±1σ.

1 2

 1 FIG. 2. Integrated elastic scattering at the 1 2 , 1 2 , 1 2 and (0, 0, 2) positions as a function of magnetic field. The 1 2 , 1 2 , 1 2 scattering gets clearly suppressed at ∼ 0.075 T. The inset shows a color contour map of the diffuse elastic scattering around the (0, 0, 2) Bragg peak made of line scans along [H,H,2] on a logarithmic intensity scale. The binning ranges for this cut were L= [1.9, 2.1] r.l.u.. The intensity of the resolution-limited weak elastic scattering at (0,0,2) in zero field has been subtracted off. Diffuse scattering from the 1 2 , 1 2 , 1

2

 2

  FIG.3. Temperature dependence of the elastic1 2 , 1 2 , 1 2 scattering in zero field. The integrated elastic scattering intensity (-0.1 meV < E < 0.1 meV, H= ± [0.4, 0.6] r.l.u., L=[1.4, 1.6] and L= [2.4, 2.6] r.l.u.) at the four1 2 , 1 2 , 1 2 -like positions is presented as a function of temperature for different heating and cooling cycles in panel (b). Please see text for details. Representative reciprocal space maps for the two heating cycles are shown in panel (a). Panel (c) shows the integrated intensity from (b) scaled to the difference between the low-temperature phase at 100 mK and the high-temperature phase at 600 mK (heating B) or 400 mK (heating A), placing the transition below which1 2 , 1 2 , 1

  FIG.4. Shift of the ac-susceptibility peaks per decade frequency for polycrystal and single crystalline samples from different groups.30,47,51 For these three measurements, the slope

1 2

 1 elastic scattering, we can construct an H-T phase diagram for Tb 2 Ti 2 O 7 in [1-10] field, shown in Figure 5, including the high-field and high-temperature regions determined by Rule et al.'s work.

  FIG.6. High-resolution neutron scattering data of Tb2Ti2O7 in zero field. Panel (a) shows a plot of intensity vs energy transfer of the (12 , 1 2 , 1 2 ) peak intensity averaged over two peaks as a function of temperature. Note the logarithmic intensity scale. The Q-integration range (H= [±0.3, ±0.7], L = [1.2, 1.8] r.l.u.) is shown in the inset by the two black squares. Panel (b) shows the intensity vs energy transfer plot for the averaged (12 , 1 2 , 1 2 ) (on-peak) positions compared to other averaged (off-peak) positions at a temperature of 80 mK. The integration ranges for the averaging and extraction of the energy dependence is depicted in the inset by the black and magenta squares.

  First, does our neutron scattering single crystal sample of Tb 2 Ti 2 O 7 display such a C p anomaly; if so how strong and at what temperature? Second, what is the relation between these sample dependent C p anomalies in zero field in Tb 2 Ti 2 O 7 and the transition to the frozen spin ice state we observe in our neutron scattering sample at T g ∼ 275 mK?

		6				single crystal, this work Hamaguchi et al.,
	Speci c heat C (J/K/mol-Tb)	2 3 4 5				single crystal Taniguchi et al., polycrystalline x=0.000 Taniguchi et al., polycrystalline x=0.005 Takatsu/Taniguchi et al., polycrystalline x'=0.000
		1 0.1	0.2	0.3	0.4 0.5	0.6	0.7	0.8 0.9	1.0
					Temperature (K)
	FIG.

ACKNOWLEDGMENTS

The authors acknowledge useful contributions from M. J. P. Gingras. This work utilized facilities supported in part by the National Science Foundation under Agree-


Julien Bensmail

Toughness Properties of Arbitrarily Partitionable Graphs

Keywords: arbitrarily partitionable graph, toughness, Hamiltonicity, split graph

Drawing inspiration from a well-known conjecture of Chvátal on a toughness threshold guaranteeing graph Hamiltonicity, we investigate toughness properties of so-called arbitrarily partitionable (AP) graphs, which are those graphs that can be partitioned into arbitrarily many connected graphs with arbitrary orders, and can be perceived as a weakening of Hamiltonian and traceable graphs. In particular, we provide constructions of non-AP graphs with toughness about 5 4 , i.e., in which, when removing the vertices of any cut-set S, the number of resulting connected components is at most about 4 5 |S|. We also consider side related questions on graphs that can be partitioned arbitrarily into only a few connected graphs (with arbitrary orders). Among other things, we prove that not all 1-tough graphs can always be partitioned into four connected graphs this way. As going along, we also raise several other questions and problems of interest on the topic.

Introduction

We start with some definitions. For an n ≥ 1, we refer to a graph of order n as an n-graph, and to a partition π = (λ 1 , . . . , λ p ) of n (i.e., λ 1 + ⋅ ⋅ ⋅ + λ p = n) as an n-partition. Now, a realisation (V 1 , . . . , V p ) of an n-partition π = (λ 1 , . . . , λ p ) in an n-graph G is a partition of the vertex set V (G) of G into p parts V 1 , . . . , V p where V i is a connected part (i.e., G[V i ] is connected) of size λ i for every i ∈ {1, . . . , p}. We now say G is arbitrarily partitionable (AP for short) if all n-partitions are realisable in G, or, in other words, if G can be partitioned into arbitrarily many connected graphs, regardless of their orders.

AP graphs have been introduced independently by Barth, Baudon, and Puech in [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF], and by Horňák and Woźniak in [START_REF] Horňák | On arbitrarily vertex decomposable trees[END_REF]. Since then, several aspects of AP graphs have been investigated in literature, covering structural aspects, algorithmic aspects, and several variants. For more details, we refer the interested reader to several works on the topic, see e.g. [START_REF] Barth | A degree bound on decomposable trees[END_REF][START_REF] Bensmail | A σ 3 condition for arbitrarily partitionable graphs[END_REF][START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF][START_REF] Buchanan | Toughness of recursively partitionable graphs[END_REF][START_REF] Kalinowski | Dense arbitrarily partitionable graphs[END_REF][START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF], and, in particular, to the more recent of these investigations.

Among others, an interesting aspect lies in that AP graphs are quite connected to other fundamental notions of graph theory. For instance, it can be noted that any realisation of an n-partition (2, . . . , 2) or (1, 2, . . . , 2) in an n-graph forms a perfect matching or a quasi-perfect matching (i.e., a set of ⌊n/2⌋ pairwise disjoint edges). Another illustration arises from the facts that every path is obviously AP and that adding edges to an AP graph preserves APness, from which we deduce that any Hamiltonian or traceable graph (i.e., admitting a cycle or a path traversing all vertices exactly once) is AP. This latter fact is actually one of the main motivations behind our investigations in the current work. Indeed, put differently, APness can be perceived as a weaker form of Hamiltonicity and traceability, and, as such, an interesting direction is wondering whether known sufficient conditions for Hamiltonicity/traceability can be weakened to APness. A perfect illustration is the pioneer result by Marczyk in [START_REF] Marczyk | A note on arbitrarily vertex decomposable graphs[END_REF], stating that the AP property holds in any connected n-graph admitting a (quasi-)perfect matching and satisfying that the degree sum of any two non-adjacent vertices is at least n -2 (thereby weakening to APness a famous result of Ore from [START_REF] Ore | Note on hamilton circuits[END_REF], stating that this last quantity being at least n -1 guarantees traceability, and that it guarantees even Hamiltonicity if it is at least n). Since this result, several authors have provided such positive and negative results, showing that some sufficient conditions for Hamiltonicity and traceability weaken to APness, while some others do not. For instance, Marczyk's original result was improved (to decreased bounds on the degree sums) by Marczyk in [START_REF] Marczyk | An Ore-type condition for arbitrarily vertex decomposable graphs[END_REF], and by Horňák, Marczyk, Schiermeyer, and Woźniak in [START_REF] Horňák | Dense arbitrarily vertex decomposable graphs[END_REF]. In [START_REF] Bensmail | A σ 3 condition for arbitrarily partitionable graphs[END_REF], Bensmail provided a similar condition for APness in graphs where the degree sum of any three pairwise non-adjacent vertices is large enough. On a different line, Kalinowski, Pilśniak, Schiermeyer, and Woźniak proved in [START_REF] Kalinowski | Dense arbitrarily partitionable graphs[END_REF] that graphs with sufficiently many edges are AP, thereby weakening another condition for Hamiltonicity and traceability. In [START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF], Bensmail and Li considered other various conditions for Hamiltonicity and traceability, including the square operation and forbidden induced patterns.

In this work, we explore, in the context of AP graphs, another studied aspect of Hamiltonian and traceable graphs, being the notion of graph toughness, which is a refinement over the fundamental notion of graph connectivity. In brief, the toughness is a measure of how disconnected (in terms of number of resulting connected components) a graph may become upon removing some of its vertices. More formally, for a graph G, we denote by c(G) the number of connected components of G. Now, a cut-set S ⊂ V (G) of G is a set of vertices such that c(G -S) > 1, or, in other words, whose removal leaves G not connected. Assuming now S is a cut-set of G, we define as τ (S) the quantity |S| c(G-S) , and as τ (G) the toughness of G, being the smallest value of τ (S) over all cut-sets S of G. In particular, a tough cut-set of G is a cut-set S such that τ (S) = τ (G). Last, we say G is t-tough for some t ≥ 0 if we have t ≤ τ (G). Note that the toughness of every non-complete graph is well defined (since the definitions above apply only for graphs admitting cut-sets), and that a t-tough graph is also t ′ -tough for all t ′ ≤ t. Also, a graph has toughness 0 if and only if it is not connected; this apart, the toughness of a graph can be arbitrarily large.

The notion of graph toughness, as mentioned earlier, was introduced to express sufficient conditions for Hamiltonicity and traceability. More precisely, it is Chvátal whom considered this notion first, and raised that, perhaps, all tough enough graphs are Hamiltonian.

Conjecture 1.1 (Chvátal [START_REF]Tough graphs and Hamiltonian circuits[END_REF]). There is some t 0 > 0 such that every t 0 -tough graph is Hamiltonian.

As a first guess towards Conjecture 1.1, Chvátal asked whether all graphs with toughness more than 3 2 are Hamiltonian, which was first disproved by Thomassen (see [START_REF] Bermond | Hamiltonian graphs[END_REF]). After that, as Enomoto, Jackson, Katerinis, and Saito [START_REF] Enomoto | Toughness and the existence of kfactors[END_REF] proved that every 2-tough graph admits a 2-factor (i.e., disjoint cycles covering all vertices) and that, for every ε > 0, there is a (2-ε)-tough graph without this property, it was believed that, perhaps, 2-tough graphs are all Hamiltonian. Again, this was refuted by Bauer, Broersma, and Veldman, who proved in [START_REF] Bauer | Not every 2-tough graph is Hamiltonian[END_REF] that for every ε > 0 there is a ( 9 4ε)-tough graph that is not traceable. This is where the main investigations towards Conjecture 1.1 stand to date, although many related results (some of which will be recalled later on in this work, to guide our investigations) can be found in literature, in particular for restricted graph classes.

Although graph toughness has not been considered as such in the context of AP graphs, a few results and investigations actually deal with connectivity properties of these graphs, and, as such, are not so distant from that field. In particular, since investigations on AP trees (see e.g. [START_REF] Barth | A degree bound on decomposable trees[END_REF]), it is known that removing a cut-vertex (i.e., a cut-set of size 1) from an AP graph results in at most four connected components. This contrasts with more general, larger cut-sets, as Baudon, Foucaud, Przybyło, and Woźniak proved that removing a cutset of size at least 2 from an AP graph might result in a graph with arbitrarily many connected components [START_REF] Baudon | On the structure of arbitrarily partitionable graphs with given connectivity[END_REF]. In the language of graph toughness, this implies τ (G) can be arbitrarily close to 0, for an AP graph G. It was proved, however, that if one strengthens the definition of AP graphs by a bit, then some of these phenomena do not hold any more [START_REF] Baudon | Structural properties of recursively partitionable graphs with connectivity 2[END_REF]. This very concern was studied further by other authors in the recent work [START_REF] Buchanan | Toughness of recursively partitionable graphs[END_REF].

In this work, we thus initiate the study of graph toughness in the very context of AP graphs, regarding these graphs as a weaker form of Hamiltonian graphs. We start in Section 2 by raising a few remarks on a well-known theorem of Tutte on perfect matchings, from which we get to explaining why the most common proof arguments for proving non-APness cannot be applied to construct non-AP graphs with "large" toughness. In that section, we also get to introducing other results and problems related to Tutte's Theorem, which we think are of independent interest. From Section 3 on, we then focus on the following straight analogue of Chvátal's Conjecture 1.1: Conjecture 1.2. There is some t * > 0 such that every t * -tough graph is AP.

Of course, if Conjecture 1.1 was to be proved, then it would imply Conjecture 1.2 holds too, since Hamiltonicity implies APness. In the same line as in the work [START_REF] Kratsch | Toughness, hamiltonicity and split graphs[END_REF] of Kratsch, Lehel, and Müller, in Section 3 we start by investigating Conjecture 1.2 for split graphs. In particular, we get to constructing non-AP split graphs with toughness tending to 5 4 . Using that construction, we then get to exhibiting non-AP graphs with slightly larger toughness in Section 4, through exploiting ideas of Bauer, Broersma, and Veldman from [START_REF] Bauer | Not every 2-tough graph is Hamiltonian[END_REF], that allowed them to establish, assuming it holds, the best known lower bound on t 0 in Conjecture 1.1 to date. On the way, we also observe that the very construction of Bauer, Broersma, and Veldman of non-traceable graphs with toughness about 9 4 provides AP graphs. In Section 5, we move to a slightly different problem, where all these questions are investigated in graphs that are, in some sense, AP only for partitions into a few connected graphs. We finish off in Section 6 with a few more questions and directions for further work on the topic.

Around Tutte's Theorem for perfect matchings

Previous studies on AP graphs have shown that, in general, graphs are more likely to not be AP because of partitions with spectrum1 of size 1, and in particular because of partitions of the form (λ, . . . , λ) for λ ≥ 2 being small. A notable case is thus when λ = 2, corresponding to perfect matchings. Although there are non-AP graphs having perfect matchings, still, for these reasons, building non-AP graphs with certain properties is more easily done through building graphs with these properties admitting no perfect matchings.

Unfortunately, this approach is not quite promising in our context, in which we strive to build non-AP graphs with large toughness. This can e.g. be seen through the following famous condition, due to Tutte, for graphs to admit perfect matchings.

Theorem 2.1 (Tutte [START_REF] Tutte | The factorization of locally finite graphs[END_REF]). A graph G with even order has a perfect matching if and only if for every S ⊆ V (G) the graph G-S has at most |S| connected components with odd order. From Tutte's Theorem, we directly get that every graph of even order with sufficiently large toughness admits perfect matchings. More precisely, note that a particular toughness value is 1, as 1-tough graphs can more simply be perceived and defined as those graphs in which, when removing any k ≥ 1 vertices, we end up with a graph having at most k connected components. In conjunction with Tutte's Theorem, this yields: Observation 2.2. Every 1-tough graph of even order admits a perfect matching.

Regarding earlier remarks, we thus get that, if one aims to build non-AP graphs with large toughness, i.e., more than 1, then one has to consider graphs that are not AP because of partitions different from (2, . . . , 2), while, generally speaking, admitting no realisation of (2, . . . , 2) is a common reason why a non-AP graph is not AP.

Let us also add that Observation 2.2 is best possible, in the sense that, for every ε > 0, there are (1ε)-tough graphs of even order with no perfect matchings [START_REF] Enomoto | Toughness and the existence of kfactors[END_REF].

In the next sections, we will exhibit non-AP graphs with toughness more than 1, and this will be done by making sure there is some λ ≥ 3 such that these graphs cannot be partitioned following (λ, . . . , λ). The main reasons why we focus on such partitions generalise concerns raised above. In particular, note that, intuitively to the least, when partitioning a graph following some partition π, there are more partition possibilities, and thus more chances that a realisation exists, 1) the more distinct values π contains, and 2) the larger the values of π are. For these reasons, we will give a special focus to partitions (λ, . . . , λ) for some λ ≥ 3 being small (λ = 3 being thus the most promising case).

Due to these concerns, we wonder whether there is a way to generalise Tutte's Theorem from perfect matchings, thus to partition (2, . . . , 2), to any partition (λ, . . . , λ) with λ ≥ 3. A problem is that building a realisation of (2, . . . , 2) is much more constrained and different from building one of (λ, . . . , λ) for some λ ≥ 3, which makes unclear how a proper generalisation should read. An attempt we suggest is based on the following interpretation of one direction of Tutte's Theorem. Let G be a graph and S be a cut-set of G. If C is a connected component of G -S with odd order, then, in a perfect matching of G, it must be that at least one vertex of C is matched to a vertex outside C, and, more precisely, by the definition of a cut-set, this outside vertex must belong to S. From this, we get right away that |S| must be at least the number of connected components with odd order of G -S.

For the sake of simplicity, let us focus on λ = 3 throughout the following explanations. When considering realisations of (3, . . . , 3) in G, note that, if |V (C)| is not a multiple of 3, then there must be at least one part X of size 3 containing both vertices in C and vertices outside C. And this part X can be of multiple forms: These arguments generalise naturally to any partition (λ, . . . , λ) with λ ≥ 3, though, obviously, the possibilities increase as λ rises, and a general description as above, involving the order of C modulo λ, gets more and more tedious to establish properly (in particular, note that, for large values of λ, any part containing vertices of C can contain multiple vertices of S, and, for each connected component

• if |X ∩ V (C)| = 1,
C ′ of G -S different from C, multiple vertices of C ′ ).
Still, there is an obvious, strong way of generalising one direction of Tutte's Theorem to partitions of the form (λ, . . . , λ) for any λ ≥ 2, which reads as follows.

Set λ ≥ 2. For a graph G with a cut-set S, let C(G, S, λ) be the following graph:

• for every connected component C of G -S, if |V (C)| / ≡ 0 mod λ, then we add a clique K C of order |V (C)| mod λ to the graph;

• we add a clique K of order |S| to the graph;

• we make all vertices of K universal; that is, for every connected component C of G -S with |V (C)| / ≡ 0 mod λ, we add to the graph all possible edges between vertices of K and vertices of

K C . Note that |V (G)| ≡ |V (C(G, S, λ))| mod λ; in particular, if |V (G)| is divisible by λ, then so is |V (C(G, S, λ))|. Now,
by arguments above, it should be clear that the following generalisation of one direction of Tutte's Theorem holds:

Observation 2.3. Let λ ≥ 2,
and G be a graph with order multiple of λ. If, for some cut-set S of G, graph C(G, S, λ) admits no realisation of (λ, . . . , λ), then so does not G.

At this point, it remains unclear, however, whether the other direction of Tutte's Theorem can be generalised the same way. That is, we wonder whether, assuming a graph G admits no realisation of some partition (λ, . . . , λ) for some λ ≥ 3, there is necessarily a cutset S of G such that C(G, S, λ) shares the same property. Although we were able to check this for small graphs, proving this seems more demanding than proving Tutte's Theorem.

Due to these thoughts, in the next sections we will also wonder about toughness thresholds guaranteeing a graph admits a realisation of (λ, . . . , λ) for any λ ≥ 3. Indeed, as a weaker version of Conjecture 1.2 one could also wonder about the following: Conjecture 2.4. For every λ ≥ 3, there is some t - λ > 0 such that every t - λ -tough graph admits a realisation of (λ, . . . , λ).

On the toughness of AP and non-AP split graphs

Recall that a graph G is a split graph if its vertex set can be partitioned into two sets K, I such that K is a clique (i.e., G[K] is complete) and I is an independent set (i.e., G[I] is empty). For convenience, we say the vertices of K are black and those of I are white.

In this section, we wonder about the toughness of AP split graphs. In particular, we wonder about the maximum toughness of a non-AP split graph, and about a toughness threshold above which a split graph is necessarily AP. These concerns are primarily motivated by the work [START_REF] Kratsch | Toughness, hamiltonicity and split graphs[END_REF] of Kratsch, Lehel, and Müller, in which they answered these questions for Hamiltonicity (thereby understanding Conjecture 1.1 completely for split graphs). In particular, they proved that every 3 2 -tough split graph is Hamiltonian, and that, for every ε > 0, there exist non-Hamiltonian split graphs with toughness 3 2ε. The former of these two results directly implies the following in our context. Corollary 3.1. Every 3 2 -tough split graph is AP. Regarding the latter result of Kratsch et al., it turns out that the construction of split graphs they provide yields graphs that are traceable. Thus, contrarily to their former result, their latter one does not hold as is for non-APness, and we thus have to come up with another construction of non-AP split graphs with "large" toughness.

As mentioned in previous Section 2, one of the most common reasons why a graph is not AP is because it admits no perfect matchings. However, as seen through previous Observation 2.2, having toughness at least 1 guarantees the existence of perfect matchings. Thus, the main difficulty here is that we have to come up with graphs that are not AP because of partitions different from (2, . . . , 2), which, in general, are easier to realise.

Before proceeding, let us mention en passant that, in the context of split graphs, the toughness threshold of 1 for perfect matchings is actually best possible. For that, we first need to consider the split graph depicted in Figure 1, which can be used as follows: Observation 3.2. Any split graph G of even order containing the graph H in Figure 1 (so that the white vertices remain of degree 2) admits no perfect matching.

Proof. This follows from Theorem 2.1 since removing the six black vertices of H results in seven connected components, all of which have odd order, namely 1. This implies G has a cut-set S such that G -S has strictly more than |S| connected components of odd order; by Tutte's Theorem, we thus get that G has no perfect matching. Now, for any k ≥ 1, consider the following construction of a split graph W k . Start from k + 2 disjoint copies H 1 , . . . , H k+2 of the graph H in Figure 1, then add all possible edges joining black vertices from two distinct H i 's, and, last, just add k universal (black) vertices to the graph to get W k . Let us denote by Q the clique formed by these k new vertices. Note that Q and the black vertices of H 1 , . . . , H k+2 form a clique on k + 6(k + 2) vertices. Actually, W k is a split graph, the clique K containing Q and the 6(k + 2) black vertices of H 1 , . . . , H k+2 , and the independent set I containing the 7(k + 2) white (degree-2) vertices of H 1 , . . . , H k+2 . In particular, note that

|V (W k )| = 13(k + 2) + k = 14k + 26 is even.
This construction has the following properties:

Theorem 3.3. For every k ≥ 1, graph W k admits no perfect matching, and thus is not AP. Furthermore, τ (W k ) is non-decreasing and tends to 1 as k grows to infinity.

Proof. Assume, towards a contradiction, that, for some k ≥ 1, graph G = W k admits a perfect matching M . Since |Q| = k and W k contains k + 2 copies H 1 , . . . , H k+2 of H (the graph depicted in Figure 1), there must be i, j ∈ {1, . . . , k + 2} with i ≠ j such that no edge of M consists both of a vertex of Q and of a vertex of H i or H j . So the graph G ′ induced by the vertices covered by the edges of M containing at least one vertex of H i or H j is a split graph with even order, containing exactly two copies of H, namely H i and H j , in which all white vertices have degree 2. In particular, this means the restriction of M to G ′ is a perfect matching of G ′ . This stands as a clear contradiction to Observation 3.2; thus, M cannot exist, and G cannot admit perfect matchings, a contradiction. Now, for any k ≥ 1, consider a tough cut-set S of G = W k . Since the vertices of Q are universal, clearly S must contain Q. Now, focus on any copy H i of H in G -Q. Since H i contains six black vertices all of which have degree at least 7 (in G -Q), while all white vertices have degree 2, and only black vertices are connected to the rest of G -Q, it should be clear that, besides Q, set S must contain black vertices of H i only. Now, from H i 's point of view, it can be observed that removing any black vertex cannot isolate any white vertex, removing any two black vertices isolates at most one white vertex, removing any three black vertices isolates at most three white vertices, removing any four black vertices isolates at most four white vertices, removing any five black vertices isolates at most five white vertices, and removing all six black vertices isolates all seven white vertices. Besides, in any case but the last one, some black vertices of H i are not removed. Also, note that it is not possible to remove black vertices so that exactly six white vertices get isolated.

We now get to distinguishing whether S contains all black vertices of G.

• If S contains all black vertices, then G -S contains all white vertices. Then

τ (S) = |S| c(G -S) = k + 6(k + 2) 7(k + 2) = 7k + 12 7k + 14
which tends to 1 as k grows to infinity.

• If S does not contain all black vertices, then G -S necessarily contains a connected component over all black vertices (and all white vertices adjacent to these) not in S. For every i ∈ {0, . . . , 6}, we denote by n i the number of H i 's of which S contains exactly i black vertices. Then |S| = k + n 1 + 2n 2 + 3n 3 + 4n 4 + 5n 5 + 6n 6 , and by arguments above we have

τ (S) = |S| c(G -S) ≥ k + n 1 + 2n 2 + 3n 3 + 4n 4 + 5n 5 + 6n 6 n 2 + 3n 3 + 4n 4 + 5n 5 + 7n 6 + 1 .
If the right-hand term of the inequality is at least 1, then we have our conclusion. Otherwise, it means n 6 > k + n 1 + n 2 + 1, implying, since there are k + 2 H i 's, that S must actually contain all black vertices of G. This is a contradiction.

This concludes the proof.

We now consider split graphs that are not AP because of partitions different from (2, . . . , 2). This is done through the following construction of a graph G k . For any k ≥ 1, start from 4k + 3 (black) vertices v 1 , . . . , v 4k+3 forming a clique, and, to each v i of these 4k + 3 vertices, attach a pendant (white) vertex w i . Last, add k universal (black) vertices u 1 , . . . , u k to the graph (being our G k ), forming a clique Q on k vertices. Note that

|V (G k )| = 2(4k + 3) + k = 9k + 6 is a multiple of 3.
Also, G k is a split graph with clique K containing Q and all v i 's, and with independent set I containing all w i 's. Theorem 3.4. For every k ≥ 1, graph G k admits no realisation of (3, . . . , 3), and thus is not AP. Furthermore, τ (G k ) is non-decreasing and tends to 5 4 = 1.25 as k grows to infinity.

Proof. We claim that, for any k ≥ 1, graph G = G k admits no realisation of π = (3, . . . , 3). Indeed, towards a contradiction, assume this is wrong, and let R be a realisation of π in G. Note that any part of R containing some u i can contain at most two v i 's and w i 's.

Similarly any part containing some v i can contain at most two other v i 's, and at most one pair {v j , w j } for some j ≠ i. Since there are only k u i 's but 4k + 3 v i 's and w i 's, we deduce there are at least 2k + 3 pairs {v i , w i } such that v i and w i do not belong to the same part X as some vertex of Q. In particular, any such part X is of the {w i , v i , v j }, where j ≠ i, since, in G -Q, vertex w i is only adjacent to v i , while v i is only adjacent to w i and all other v i 's. For the same reasons, since N (w j ) = Q ∪ {v j }, this implies w j must be covered by a part containing a vertex of Q. Since there are at least 2k + 3 parts X of the form above, and the parts containing the vertices of Q cover only 3k vertices of G (k of which being those in Q), we deduce there must be at least one particular part X = {w i , v i , v j } such that the part Y containing w j does not contain any vertex of Q. Thus, G[Y ] cannot be connected, which contradicts that R is a realisation of π. Thus, G is not AP. Let now S be any tough cut-set of G = G k , for some k ≥ 1. Note that S must contain Q, since the u i 's are universal. Now, since the w i 's have degree 1 in G -Q, note that S cannot contain any w i , and so, besides u i 's, set S contains only v i 's.

• If S contains x ∈ {1, . . . , 4k + 2} vertices in {v 1 , . . . , v 4k+3 }, then note that c(G -S) =

x + 1 since G -S has a connected component containing all v i 's (and their adjacent w i 's) not in S. Precisely, we have

τ (S) = |S| c(G -S) = k + x x + 1 ,
which function, regardless of k, is non-increasing and thus reaches its minimum for x = 4k + 2, for which value we have

τ (S) = k + (4k + 2) (4k + 2) + 1 = 5k + 2 4k + 3
which tends to 5 4 as k grows to infinity. • If S contains all 4k + 3 v i 's, then G -S consists in all w i 's being isolated, and thus c(G -S) = 4k + 3. Hence,

τ (S) = k + (4k + 3) 4k + 3 = 5k + 3 4k + 3
which, again, tends to 5 4 as k grows to infinity.

This concludes the proof.

General graphs, and the construction of Bauer, Broersma, and Veldman

Before proceeding with with our main concern in this section, we first observe we can generalise previous Theorem 3.4 to get a similar result (for non-split graphs) regarding other partitions with spectrum of size 1, i.e., of the form (λ, . . . , λ) for any λ ≥ 3. In particular, upcoming Theorem 4.1 provides a little step towards Conjecture 2.4.

For some fixed λ ≥ 3 and any k ≥ 1, consider the following graph G λ k . Start from 2k(λ -1) + λ vertices v 1 , . . . , v 2k(λ-1)+λ forming a clique, and, to each v i , attach a new clique W i on λ -2 vertices (that is, W i is a clique of order λ -2, and we have all possible edges between v i and vertices of W i ). Last, add k universal vertices u 1 , . . . , u k to the graph, forming a clique Q, to achieve the construction of G λ k . Note that

|V (G λ k )| = (λ -1)(2k(λ -1) + λ) + k = λ(2k(λ -1) + λ -2k -1) + 3k.
In particular, |V (G λ k )| is divisible by λ whenever k is.

Theorem 4.1. For every λ ≥ 3 and k ≡ 0 mod λ, graph G λ k admits no realisation of (λ, . . . , λ), and thus is not AP. Furthermore, τ (G λ k ) is non-increasing and tends to 2λ-1 2λ-2 > 1 as k grows to infinity.

Proof. The proof is essentially the same as that of Theorem 3.4. For k being a multiple of λ, the order of any G = G λ k is a multiple of λ. Suppose a realisation of (λ, . . . , λ) in G exists. Then at most k connected parts can contain the u i 's, and these at most k parts can contain vertices of at most k(λ -1) sets of the form W i ∪ {v i } for some i ∈ {1, . . . , 2k(λ -1) + λ}. Assume, w.l.o.g., this is the case for all such W i ∪ {v i }'s with index in {1, . . . , k(λ -1)}. Then, there can be at most k(λ -1) indexes i / ∈ {1, . . . , k(λ -1)} such that vertices of W i ∪ {v i } belong to some connected part together with some v j with j ∈ {1, . . . , k(λ -1)}. Indeed, note that for every such i, we have that all vertices of W i must belong to the same part as v i (since v i is a cut-vertex in G -Q), and thus, apart from vertices in W i ∪ {v i }, the part must contain exactly one other vertex, being some other v j . Still, w.l.o.g., we can assume all i's with this property lie in {k(λ -1) + 1, . . . , 2k(λ -1)}. We now deduce that the graph G ′ induced by the W i 's and the v i 's with index i ≥ 2k(λ -1) + 1 admits a realisation of (λ, . . . , λ), which is impossible since all v i 's are cut-vertices in G ′ , and the W i 's have size λ -2. So G cannot admit a realisation of (λ, . . . , λ), and thus cannot be AP.

Regarding the toughness of G = G λ k (for some λ ≥ 3 and k ≡ 0 mod λ), again we have that any cut-set S must contain the k vertices of Q. Now, regarding G -Q, again if we assume S is tough, then there is not point having any vertex of some W i in S. So, besides Q, we have that S only contains v i 's. If S contains all v i 's, then

τ (S) = k + 2k(λ -1) + λ 2k(λ -1) + λ = k(2λ -1) + λ k(2λ -2) + λ ,
which tends to 2λ-1 2λ-2 as k grows to infinity. Now, if S contains only x v i 's for some x ∈ {1, . . . , 2k(λ -1) + λ -1}, then, again, the worst-case scenario is when x = 2k(λ -1) + λ -1, in which case

τ (S) = k + 2k(λ -1) + λ -1 2k(λ -1) + λ = k(2λ -1) + λ -1 k(2λ -2) + λ
which again tends to 2λ-1 2λ-2 as k grows to infinity. We now move to our main concern in this section. Namely, we consider, in our context, the following construction introduced in [8] by Bauer, Broersma, and Veldman (building upon previous ideas from [START_REF] Bauer | On Hamiltonian properties of 2-tough graphs[END_REF]), from which they established one of the most significant results towards Conjecture 1.1 to date. Let ℓ ≥ 1 and m ≥ 1 be two positive integers. For a graph H with two vertices x and y, the graph G(H, x, y, ℓ, m) is obtained as follows:

• start from m disjoint copies H 1 , . . . , H m of H;

• then, assuming that, for every i ∈ {1, . . . , m}, the copies of vertices x and y in H i are denoted x i and y i , add all possible edges between x i 's and y i 's (that is, any x i becomes adjacent to every other x j and every y j , including y i , and vice versa);

• last, add ℓ universal vertices to obtain G(H, x, y, ℓ, m).

Bauer et al. proved that, provided H, x, y, ℓ, and m satisfy some properties, we can infer that G(H, x, y, ℓ, m) is not Hamiltonian, and sometimes not even traceable, all the while having large toughness. In particular, for the graph L depicted in Figure 2 (a) (for which, throughout, we deal with its vertices using the terminology from the figure), they proved: Figure 2: Two graphs introduced in [START_REF] Bauer | Not every 2-tough graph is Hamiltonian[END_REF]. One of their main properties of interest is that, for each of the two graphs, there is no Hamiltonian path starting and ending in the two white vertices x and y.

Theorem 4.2 (Bauer, Broersma, Veldman [START_REF] Bauer | Not every 2-tough graph is Hamiltonian[END_REF]). For every ℓ ≥ 2 and m ≥ 1, we have

τ (G(L, x, y, ℓ, m)) = ℓ + 4m 2m + 1 . If m ≥ 2ℓ + 3 then G(L, x, y, ℓ, m) is not traceable, while if m ≥ 2ℓ + 1 then G(L, x, y, ℓ, m)
is not Hamiltonian. So, there are non-traceable graphs with toughness tending to 9 4 . It seems legitimate to wonder whether the construction of Bauer et al. brings something in the context of AP graphs. We prove it is not the case as is; indeed: Theorem 4.3. For every ℓ, m ≥ 1, graph G(L, x, y, ℓ, m) is AP.

Proof. Assume ℓ and m are fixed, and set G = G(L, x, y, ℓ, m). We denote by L 1 , . . . , L m the m copies of L in G, and, for every i ∈ {1, . . . , m}, we denote by x i , a i , b i , c i , d i , e i , f i , y i the copies of x, a, b, c, d, e, f, y, respectively, in L i . Also, we denote by K the clique formed by the ℓ universal vertices of G. Last, we set n = |V (G)|.

Let π be an n-partition. Our goal is to build a realisation R of π in G. For that, we will proceed along the following ideas. First, we will pick consecutive connected parts along L 1 , . . . , L m following that order, in the sense that if, when treating some L i , we miss vertices to form a connected part, then we will also pick vertices from the next copy L i+1 . To that aim, we will make sure, when adding the last vertices of L i and the first ones of L i+1 to a part S, that the vertices of L i in S induce a connected graph, the vertices of L i+1 in S induce a connected graph, and that S contains both y i and x i+1 to guarantee the vertices of both L i and L i+1 in S, altogether, induce a connected graph. Eventually, once all vertices of L 1 , . . . , L m are exhausted, we will then use freely the vertices of K to form connected parts, which can be done at will since K is a clique of universal vertices.

For technical reasons, we first need to take care of the possible connected parts of size 4 of R, which we do as follows. Note that L admits realisations of (4, 4); for instance, one can consider the two connected parts {x, b, a, c} and {d, e, f, y}. Starting from i = 1, as long as R requires at least two more connected parts of size 4, we then pick two connected parts of size 4 in L i this way, and then proceed with L i+1 . Thus, we can assume we get to the point where all vertices of L 1 , . . . , L i-1 are covered by connected parts of size 4, and either i -1 = m and it now suffices to partition K arbitrarily to get the desired R, or it remains to partition L i , . . . , L m and at most one connected part of size 4 must be picked.

When starting dealing with L i , the last part S we have built when treating L i-1 might be missing vertices. We denote by δ ≥ 0 the number of such vertices missing in S (to reach the desired size). As described above, in case δ ≥ 1 we assume that S contains y i-1 so that L i contains a vertex, x i , adjacent to a vertex in S. In case δ = 0, we set S = {}.

We now consider a few cases:

• If δ = 0, then every connected part built earlier on has reached its desired size. Note that P = (a i , c i , b i , x i , d i , f i , e i , y i ) is a Hamiltonian path of L i . In that case, we then pick as many remaining connected parts as possible following P , with the additional care that if there remains exactly one connected part of size 4 to be picked, then we pick it first. This apart, we can pick any remaining connected parts along P .

In particular, the last vertices of P might be part of a partial connected part S, that contains y i as desired, missing δ ≥ 1 vertices. In case the last connected part is actually complete, when treating L i+1 , we would thus have S = {} and δ = 0.

• If δ ≥ 1, then we add the following vertices to S.

-If δ = 1, then we add x i to S, thereby forming a connected part (due to the edge y i-1 x i and the fact that S -{x i } induces a connected graph by hypothesis) with the desired size. Note then that P = (a i , c i , b i , d i , f i , e i , y i ) forms a Hamiltonian path of what remains of L i . We can then pick remaining connected parts along P , with the last part, containing y i , being possibly partial.

-If δ = 2, then we add x i and b i to S to complete the part. We now consider the other connected parts that remain to be picked; in particular, note that it is not possible, since δ = 2, that there remains one of size 4 to pick. * If there remains at least one part of size 1 to be picked, then we pick {a i }. Then P = (d i , f i , e i , c i , y i ) is a Hamiltonian path in what remains to be picked in L i , and we can again pick remaining connected parts along P , the last one, containing y i , being possible partial. * If there remains at least one part of size 2 to be picked, then we pick {a i , c i }.

Then P = (d i , f i , e i , y i ) is a Hamiltonian path of what remains of L i , and we can proceed as in the previous case. * If there remains at least one part of size 3 to be picked, then we pick {d i , e i , f i }. Then P = (a i , c i , y i ) is a Hamiltonian path covering the other vertices of L i , and again we can be done. * If there remains at least one part of size x at least 5 to be picked, then we pick the first x vertices of (a i , c i , d i , e i , f i , y i ) to form a connected part. In case we had x = 5, then we start picking another remaining connected part from S = {y i } and proceed as earlier. If we had x = 6, then, actually, the connected part has reached the desired size, and we continue the process with L i+1 from an empty part. If we had x ≥ 7, then the resulting connected part is partial, and will be completed later on.

-If δ ≥ 3, then we add to S the first vertices of (x i , b i , a i , d i , f i , e i , c i , y i ), following that order, until either S reaches the desired size, in which case we then continue picking remaining connected parts along the ordering, or we attain a connected part containing y i , which, if partial, will be completed later on. In all cases, it can be checked that all parts built along that process in L i are indeed connected.

When adding y m to a connected part S, we can then add, if necessary, any vertices of K to S so that it reaches the desired size. If, then, other connected parts remain to be picked, then it suffices to pick arbitrary parts with the desired sizes covering the remaining vertices of K, to achieve the construction of R. Thus, π is indeed realisable in G, and from this we can conclude that G is indeed AP. Bauer, Broersma, and Veldman also employed the previous construction G(H, x, y, ℓ, m) with the building block in Figure 2 (b) as H to establish that, for every ε > 0, there exist chordal non-traceable graphs with toughness 7 4 -ε (see [START_REF] Bauer | Not every 2-tough graph is Hamiltonian[END_REF]). Through a similar proof scheme as in the proof of Theorem 4.3, similarly we can prove these graphs are always AP. Thus, here as well, unfortunately we do not get anything new regarding our concerns. Despite Theorem 4.3, it is possible to use the construction of Bauer, Broersma, and Veldman, together with one of our constructions from Section 3, to improve Theorem 3.4 by a bit. Our upcoming result relies on the following: Lemma 4.4. Let H be a graph with |V (H)| ≡ 0 mod 3 admitting no realisation of (3, . . . , 3). Then, for every ℓ ≡ 0 mod 3 and m ≥ 2ℓ + 1, and any two vertices x and y of H, graph G(H, x, y, ℓ, m) admits no realisation of (3, . . . , 3), and thus is not AP.

Proof. Set G = G(H, x, y, ℓ, m) for some ℓ ≡ 0 mod 3, m ≥ 2ℓ + 1, and any two vertices x and y of H. As in the definition, we denote by H 1 , . . . , H m the m copies of H in G, by z i the copy of any vertex z of H in the ith copy H i in G, and by K the clique of G formed by the ℓ universal vertices. Note that we have |V (G)| ≡ 0 mod 3.

Towards a contradiction to the claim, assume G admits a realisation R of (3, . . . , 3). Since m ≥ 2ℓ + 1, all parts of R contain three vertices each, and |K| = ℓ, note that there is necessarily an i ∈ {1, . . . , m} such that no vertex of H i belongs to a connected part together with a vertex of K. Since H i admits no realisation of (3, . . . , 3) but the order of H i is a multiple of 3, this means there must be two distinct connected parts, X and Y , of R, such that x i ∈ X and y i ∈ Y , and X contains one or two vertices (not in K) outside H i , while similarly Y contains one or two vertices (not in K) outside H i . More precisely, since |V (H i )| ≡ 0 mod 3, it must be, say, that x i is the only vertex of H i in X, while Y contains two vertices of H i , one being y i and the second one being some y ′ i with y ′ i / ∈ {x i , y i }, such that y i y ′ i is an edge (since Y is a connected part, and the unique vertex of Y outside H i cannot be a neighbour of y ′ i by construction). Then, due to the edge x i y i , we have that {x i , y i , y ′ i } is a connected part of size 3, and, together with the other parts of R covering the other vertices of H i , we get that H i , and thus H, admits a realisation of (3, . . . , 3), a contradiction. Thus, G cannot admit a realisation of (3, . . . , 3). Now, we have:

Theorem 4.5. If ℓ ≥ 3 with ℓ ≡ 0 mod 3, then G(H, w 1 , w 2 , ℓ, 2ℓ + 1)
, where H denotes the graph G ℓ from Theorem 3.4, admits no realisation of (3, . . . , 3), and thus is not AP. Furthermore, we have

τ (G(H, w 1 , w 2 , ℓ, 2ℓ + 1)) = 10ℓ 2 + 8ℓ + 1 8ℓ 2 + 6ℓ + 2 > 5 4 .
Proof. Set G = G(H, w 1 , w 2 , ℓ, 2ℓ + 1), where, in H, recall w 1 and w 2 are two vertices of degree 1 in the graph obtained upon removing all ℓ universal vertices of H. The first part of the statement follows directly from Lemma 4.4, since, by Theorem 3.4, there is no realisation of (3, . . . , 3) in H, as ℓ ≡ 0 mod 3 and m is basically 2ℓ + 1 in the current case. Thus, we can now focus on proving the second part of the statement. We denote by K the clique formed by the ℓ universal vertices of G. Also, for every i ∈ {1, . . . , 2ℓ + 1}, we denote by H i the ith copy of H in G, and by K i the clique formed by the ℓ universal vertices of H i . For every vertex z of H (being either some u j , v j , or w j ), we here denote by z i its copy in H i for every i ∈ {1, . . . , 2ℓ + 1}.

Let S be a tough cut-set of G. Clearly, K ⊂ S. For every i ∈ {1, . . . , 2ℓ + 1}, we set S i = S ∩ V (H i ) and s i = |S i |. For every i ∈ {1, . . . , 2ℓ + 1}, we also denote by C i the set of the connected components of G -S that contain only vertices of V (H i ) ∖ {w i 1 , w i 2 } (i.e., containing neither w i 1 nor w i 2 ) and set

c i = |C i |. Then τ (G) = τ (S) = ℓ + 2ℓ+1 ∑ i=1 s i r + 2ℓ+1 ∑ i=1 c i
, where r = 0 if w i 1 , w i 2 ∈ S for every i ∈ {1, . . . , 2ℓ + 1}, and r = 1 otherwise. In particular,

τ (G) = τ (S) ≥ ℓ + 2ℓ+1 ∑ i=1 s i 1 + 2ℓ+1 ∑ i=1 c i .
Recall that H contains exactly 4ℓ + 3 v i 's and w i 's. In particular, since, for every i ∈ {1, . . . , 2ℓ + 1}, the largest independent set of H i -{w i 1 , w i 2 } has size 4ℓ + 2 (achieved by the set containing w i 3 , . . . , w i 4ℓ+3 and, say, v i 1 ), then c i ≤ 4ℓ + 2. Now, for similar arguments as in the proof of Theorem 3.4, it can be noted that, if c i ≥ 1, then s i ≥ ℓ + c i . Indeed, recall that any cut-set of H must contain the ℓ universal vertices, and that, essentially, having any v i in the cut-set yields a connected component containing w i only (assuming w i is not also part of the cut-set). A particular case here is when c i = 4ℓ + 2, which requires S i to contain K i , {v i 3 , . . . , v i 4ℓ+3 }, and {w i 1 , w i 2 }; hence, even in that case, s i ≥ ℓ + 4ℓ + 3 > ℓ + 4ℓ + 2 = ℓ + c i . However, we note that if there is an i such that c i = 4ℓ + 2 (and thus s i ≥ 5ℓ + 3), then we can obtain a cut-set of G tougher than S, a contradiction, by, locally, just replacing S i with another cut-set S i of H i achieving s i = 5ℓ + 1 and c i = 4ℓ + 1. For these reasons, we can actually assume further all c i 's are at most 4ℓ + 1. Now, since s i ≥ ℓ + c i for every i ∈ {1, . . . , 2ℓ + 1}, we have

τ (G) = τ (S) ≥ ℓ + 2ℓ+1 ∑ i=1 s i 1 + 2ℓ+1 ∑ i=1 c i ≥ ℓ + ℓ(2ℓ + 1) + 2ℓ+1 ∑ i=1 c i 1 + 2ℓ+1 ∑ i=1 c i .
Since ℓ ≥ 3, note that this lower bound on τ (S) is a non-increasing function of 2ℓ+1 ∑ i=1 c i and thus it reaches its miminum when c i = 4ℓ + 1 for every i ∈ {1, . . . , 2ℓ + 1}. Thus

τ (G) = τ (S) ≥ ℓ + ℓ(2ℓ + 1) + (2ℓ + 1)(4ℓ + 1) 1 + (2ℓ + 1)(4ℓ + 1) = 10ℓ 2 + 8ℓ + 1 8ℓ 2 + 6ℓ + 2 .
Let now S * be the set of vertices of G containing K, all K i 's, and, for every i ∈ {1, . . . , 2ℓ + 1} and j ∈ {3, . . . , 4ℓ + 3}, vertex v i j . Then, it can be checked that G -S * contains a connected component containing all w i 1 's, all w i 2 's, all v i 1 's, and all v i 2 's, while vertex w i j is isolated for every i ∈ {1, . . . , 2ℓ + 1} and j ∈ {3, . . . , 4ℓ + 3}. Thus, |S * | = ℓ + ℓ(2ℓ + 1) + (2ℓ + 1)(4ℓ + 1), while c(G -S * ) = 1 + (2ℓ + 1)(4ℓ + 1). So,

τ (G) ≤ τ (S * ) = ℓ + ℓ(2ℓ + 1) + (2ℓ + 1)(4ℓ + 1) 1 + (2ℓ + 1)(4ℓ + 1) = 10ℓ 2 + 8ℓ + 1 8ℓ 2 + 6ℓ + 2 ,
and we hence have τ (G) = 10ℓ 2 + 8ℓ + 1 8ℓ 2 + 6ℓ + 2 as claimed. Since ℓ ≥ 3, this is more than 5 4 .

Partitioning into few connected parts

For any k ≥ 1, we say an n-graph G is k-AP if every n-partition (λ 1 , . . . , λ k ) containing exactly k elements is realisable in G. Now, still for any k ≥ 1, we say G is AP+k if for any set (v 1 , . . . , v k ) of k distinct vertices of G, and for any n-partition π = (λ 1 , . . . , λ p ) into p ≥ k parts, there is a realisation

(V 1 , . . . , V p ) of π in G such that v i ∈ V i for every i ∈ {1, . . . , k}. Last, for any k, k ′ ≥ 1 with k ≥ k ′ , we say G is k-AP+k ′ if, for any set (v 1 , . . . , v k ′ ) of k ′ distinct
vertices of G, and for any n-partition π = (λ 1 , . . . , λ k ) into k parts, there is a realisation

(V 1 , . . . , V k ) of π in G such that v i ∈ V i for every i ∈ {1, . . . , k ′ }.
In brief, k-APness means we can partition a graph into k connected graphs (regardless of their orders), AP+kness means we can partition into at least k connected graphs even under the requirement that k of these must each contain a given vertex, and k-AP+k ′ ness is a combination of these two properties (we can partition a graph into a fixed number k of connected graphs, a fixed number k ′ of which must each contain one particular vertex).

The introduction of these notions was mostly motivated by perhaps one of the most fundamental results when it comes to connected partitions, being the following result proved independently by Győri and Lovász, which, following our terminology, reads as follows:

Theorem 5.1 (Győri [START_REF] Győri | On division of graphs to connected subgraphs[END_REF], and Lovász [START_REF] Lovász | A homology theory for spanning trees of a graph[END_REF]). For every k ≥ 1, k-connectedness and k-AP+kness are equivalent notions.

Note that k-AP+k ′ ness is a particular case of k-APness and of AP+k ′ ness. AP+kness was introduced and studied more recently in a few works [START_REF] Baudon | Partitioning powers of traceable or Hamiltonian graphs[END_REF][START_REF] Baudon | Partitioning Harary graphs into connected subgraphs containing prescribed vertices[END_REF], and similarly for k-APness [START_REF] Diwan | Partitioning 2-connected graphs into connected subgraphs[END_REF]. Complexity aspects behind all these notions were also investigated e.g. in [START_REF] Bensmail | On the complexity of partitioning a graph into a few connected subgraphs[END_REF].

k-APness being a weaker form of APness, one could as well wonder about Conjecture 1.2 for this notion. This yields the following refinement: Conjecture 5.2. For every k ≥ 1, there is some t * k > 0 such that every t * k -tough graph is k-AP.

Note that, similarly as for Conjecture 1.2, even for more restricted Conjecture 5.2, we mainly get into the problem of constructing non-AP graphs with toughness more than 1, which, again, is not so obvious, recall our arguments from Section 2. Still, in the context of Conjecture 5.2, Theorem 5.1 here yields a positive answer for all values of k: Observation 5.3. Conjecture 5.2 holds for every k ≥ 1.

Proof. We claim that, for any k ≥ 1, Conjecture 5.2 holds for t * k = k 2 . Indeed, let G be a k 2 -tough graph. It is well-known that, for any t > 0, any t-tough graph is 2t-connected (as the existence of any cut-set of size at most 2t -1 would imply the toughness is at most 2t-1 2 < t, a contradiction). Thus, G is k-connected, and, by Theorem 5.1, we have that G is k-AP (and even k-AP+k), as desired.

Given that Conjecture 5.2 actually holds, a next question could be to determine, for any k ≥ 1, the smallest t * k > 0 such that every t * k -tough graph is k-AP. Due to the nature of the next results below, we choose to state that question formally as follows.

So, we must have, say, that V 1 contains u 1 and u 2 , that V 2 contains u 3 , that V 3 contains u 4 , and that V 4 contains u 5 . Then, since |V 2 | = |V 3 | = |V 4 | = 5k + 4 > 4k + 3, and because each of V 2 , V 3 , and V 4 contains only one distinct of the u i 's, we deduce that v must belong to all of V 2 , V 3 , and V 4 , which is another contradiction. Indeed, note that any V i containing only one of the u i 's must contain v, which does not comply with the fact that, in the present case, all of V 2 , V 3 , and V 4 have this property.

Thus, G cannot admit any realisation of π, and G is not 4-AP.

It remains to prove that G is 1-tough. Consider S, any tough cut-set of G. Since v is universal, we must have v in S. Now, since the independence number of Gv is 5, we have c(G-S) ≤ 5. For every x ∈ {2, 3, 4, 5}, clearly the minimum number of vertices of G-v that must be removed from Gv to get x connected components is x -1 (one should remove exactly x -1 of the u i 's). Thus, regardless of x, we have τ (G) = τ (S) = 1+(x-1) x = 1.

Conclusions and perspectives

In this work, we have initiated the study of the toughness of AP and non-AP graphs, being motivated mainly by Chvátal's Conjecture 1.1 and by the fact that AP graphs can be perceived as a weakening of Hamiltonian graphs. In a natural way, we thus raised Conjecture 1.2 as an adapted version of Conjecture 1.1. As a first step towards that conjecture, we proved Theorems 3.4 and 4.5, stating, in brief, that the threshold t * hypothesised in Conjecture 1.2, if it exists, is at least 5 4 . We also studied side questions throughout, for instance generalisations of Tutte's Theorem in Section 2, and, in Section 5, through Conjecture 5.2 and Question 5.4, a restriction of Conjecture 1.2 to graph partitions into a limited, constant number of connected parts only.

Most of the results we provided in the current work actually stand as very first steps towards more general questions. In particular, there remain many aspects of interest which could deserve to be studied further; for instance:

• One of our main results, Theorem 4.5, relies on a construction of Bauer, Broersma, and Veldman from [START_REF] Bauer | Not every 2-tough graph is Hamiltonian[END_REF], combined together with a graph with certain properties we exhibited through Theorem 3.4. More precisely, the main properties of interest of the latter graph is that it admits no realisation of (3, . . . , 3) and has "large" toughness. Through the same ideas, it would probably be possible to improve upon Theorem 4.5 by coming up with examples of graphs admitting no realisation of (3, . . . , 3) and having larger toughness. Let us mention that, using computer programs, we were not able to spot any small graph (with at most 12 vertices or so) having these properties. These concerns could thus be investigated further on.

• Quite similarly, it can be noticed that Lemma 4.4 could be generalised to graphs admitting no realisation of some (λ, . . . , λ) for any λ ≥ 3. While we feel confident, for the reasons exposed in Sections 2 and 3, that, towards improving upon Theorem 4.5, one should consider graphs that cannot be partitioned following (3, . . . , 3), perhaps this refinement could be worth investigating further too. Recall that this would also improve upon Theorem 4.1 we provided. On a different note, although constructing graphs with no perfect matchings and large toughness is not interesting enough for our concerns, as explained in Section 2, perhaps one way to go could be to consider partitioning graphs following partitions with spectrum of size more than 1. Regarding all the arguments we provided, perhaps one should consider partitions with spectrum {2, 3}, or, in other words, partitions into paths of order 2 and 3.

• Regarding split graphs, note that we are still far from understanding Conjecture 1.2 for these. For now, we roughly know that, for these graphs, the lowest t * lies somewhere in between about 5 4 (Theorem 3.4) and 3 2 (Corollary 3.1). We believe tightening these bounds closer could be an interesting challenge. Perhaps a significant result one could invoke here, is the fact that the APness of split graphs relies solely on the realisability of partitions with spectrum lying in {1, 2, 3}, as proved by Broersma, Kratsch, and Woeginger [START_REF] Broersma | Fully decomposable split graphs[END_REF]. That is, if a split n-graph G is not AP, then there is an n-partition containing only 1's, 2's, and 3's that is not realisable in G.

• To progress towards Conjecture 1.2, one could also consider other classes of graphs that have been considered in the context of Conjecture 1.1. For instance, [START_REF] Gao | Hamiltonian cycles in 7-tough (P 3 ∪ 2P 1 )-free graphs[END_REF] is a recent reference with an up-to-date listing of classes of graphs for which Conjecture 1.1 is known to hold. Although this means Conjecture 1.2 also holds for these classes of graphs, one could wonder whether these results can be improved even further in our context. Following our investigations in Section 3, one could more particularly wonder about superclasses of split graphs, such as chordal graphs and 2K 2 -free graphs, which have received quite some attention in this context.

• Note that an interesting aspect behind the constructions provided by Kratsch, Lehel, and Müller in [START_REF] Kratsch | Toughness, hamiltonicity and split graphs[END_REF] and by Bauer, Broersma, and Veldman in [START_REF] Bauer | Not every 2-tough graph is Hamiltonian[END_REF], which we also got to employ in ours, is the use of universal vertices, which are very important in the definition of graph toughness since these vertices necessarily belong to all cut-sets. In the context of AP graphs, the behaviour of universal vertices has also been investigated, notably in [START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF], wherein it was proved, among other things, that deciding whether an n-partition is realisable in an n-graph with about a third universal vertices is NPcomplete. This leads to the more general question of whether this problem remains NP-complete for graphs with "large" toughness. Note that this general problem was indeed proved to be NP-complete when restricted to several classes of graphs, see e.g. [START_REF] Bensmail | On the complexity of partitioning a graph into a few connected subgraphs[END_REF] and the pointers there, all of which seem to have very low toughness.

• Regarding the thoughts from Section 2, we wonder whether the way we proposed to generalise Tutte's Theorem from perfect matchings to partitions of the form (λ, . . . , λ) is plausible. Recall that, in Observation 2.3, we indeed proposed one generalisation of one of the two directions. Although the other direction might seem a bit strong, we were not able to come up with any counterexample. So we wonder whether it also holds, or, more generally speaking, whether Tutte's Theorem indeed generalises to this setting. If this were to be the case, then it is likely that this could have implications on the study of AP graphs, for the reasons provided in Sections 2 and 3 (in particular, due to the fact that, very generally speaking, if a graph is not AP, then it is likely that it is because of a non-realisable partition with spectrum of size 1).

Let us, here, also remind about Conjecture 2.4.

• Last, we think our related investigations in Section 5 are of interest, in particular due to their connection with Theorem 5.1 of Győri and Lovász. One appealing question is Conjecture 5.6, which we believe might be true. This apart, more general Question 5.4 could also be worth studying further.

  then either -X contains one vertex of C and two vertices of S, or -X contains one vertex of C, one vertex of S, and one vertex from a connected component of G -S different from C; • if |X ∩ V (C)| = 2, then X contains two vertices of C and one vertex of S.

Figure 1 :

 1 Figure 1: A split graph used to prove Theorem 3.3. The clique contains the black vertices, while the independent set contains the white ones.

Following works of Ravaux on AP graphs[START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF], the spectrum of a partition is the set of its values.

. In a private communication, Woźniak suggested that, perhaps, all 1-tough graphs are 3-AP, and thus that t * 3 < 1 (see [START_REF] Bensmail | Partitions and decompositions of graphs[END_REF] for an earlier mention), which, we think, is an interesting question on its own. Conjecture 5.6 (Woźniak, see e.g. [START_REF] Bensmail | Partitions and decompositions of graphs[END_REF]). All 1-tough graphs are 3-AP; that is, t * 3 < 1. We are not able to come up with arguments answering Conjecture 5.6 in this work, but, in the same line as some results we provided earlier, we can prove that, in general, 1-tough graphs are not 4-AP. Regarding Question 5.4 above, this is sort of similar to considering the other direction, being to wonder, for some t > 0, what is the largest k ≥ 1 such that t-tough graphs are k-AP. Thus, for all 1-tough graphs, we prove they are "at best" 3-AP.

Theorem 5.7. There are arbitrarily large 1-tough graphs that are not 4-AP; that is, t * 4 ≥ 1. Proof. For any k ≥ 0, consider the following construction. Start from five disjoint cliques K 1 , . . . , K 5 on 4k + 3 vertices. For every i ∈ {1, . . . , 5}, select any one vertex of K i , and denote it by u i . Now turn {u 1 , . . . , u 5 } into a clique, that is, add all possible edges between the u i 's. Last, add a universal vertex v, and let us call G the resulting graph.

Set n = |V (G)|; note that n = 5(4k+3)+1 = 20k+16. Thus, π = (5k+4, 5k+4, 5k+4, 5k+4) is an n-partition. We claim π is not realisable in G. Assume this is wrong, and suppose G admits a realisation R = (V 1 , V 2 , V 3 , V 4 ) of π. As a general observation, note that if some V i contains some u j , then, because |V i | = 5k + 4 > 4k + 3 (recall k ≥ 0), the vertices of K j must be covered by V i and the part containing v, which two parts might be the same. Now, since there are five u i 's, note that at least one part, say V 1 w.l.o.g., must contain at least two of the u i 's. If V 1 contains at least three u i 's, say u 1 , u 2 , and u 3 w.l.o.g., then, by a remark above, note that all vertices of K 1 , K 2 , and K 3 , must be covered by at most two V i 's (V 1 and another V i containing v). However, these at most two parts cover 2(5k + 4) = 10k + 8 vertices of G, while, in total, v and the vertices of K 1 , K 2 , and K 3 form a set of 3(4k + 3) + 1 = 12k + 10 > 10k + 8 vertices (recall k ≥ 0). Thus, this is impossible; so, the V i 's must contain at most two of the u i 's each.

We get a similar conclusion if two of the V i 's each contain two of the u i 's, say V 1 contains u 1 and u 2 while V 2 contains u 3 and u 4 without loss of generality. Indeed, then, all vertices of K 1 , K 2 , K 3 , and K 4 , and v, must be covered by at most three parts. At most three parts cover at most 3(5k + 4) = 15k + 12 vertices of G, while, here, they must cover at least 4(4k + 3) + 1 = 16k + 13 > 15k + 12 (recall k ≥ 0). Thus, again, this is impossible.