text:
# Molecular gas in the central regions of the latest-type spiral galaxies

## 1 Introduction

Spiral galaxies of the latest Hubble types (between Scd and Sm) are considered dynamically simple systems: they are “pure” disk galaxies, often with only weak spiral arm structure, ill-defined stellar bars, and no obvious central bulges. Their stellar disks often are extremely thin, as evidenced by a large ratio of radial to vertical disk scale lengths in edge-on images (Dalcanton & Bernstein 2000). In many cases the thin disks are embedded in a red stellar envelope that most plausibly formed before the thin disk (Dalcanton & Bernstein 2002). The undisturbed morphology of these systems indicates that they have not experienced any significant merger events after the formation of the red envelopes ($`6\mathrm{Gyr}`$ ago). Late-type spirals thus provide important constraints on galaxy formation scenarios that invoke hierarchical merging.

In addition, the featureless stellar disks, shallow surface brightness profiles, and lack of bulge-like structures apparent in optical images of many such galaxies (Matthews & Gallagher 1997; Böker et al. 2003) suggest an uneventful star formation history within their central few kpc. It is unclear whether this lack of past star formation activity in the central region is simply due to a lack of cold molecular gas (which provides the raw material for star formation), or whether dynamical effects prevent the gas from reaching a critical density. Unfortunately, late-type spirals are under-represented in many samples because of observational biases. This is especially true for surveys of their molecular gas content. For example, a literature compilation of the CO emission in 582 galaxies by Casoli et al. (1998) contains only 55 spirals with Hubble type Scd or later, only 26 of which have actual detections. With the data presented in this paper, we more than double the amount of available CO observations of late-type spirals. More specifically, we present spectra of the $`{}_{}{}^{12}\mathrm{CO}`$ emission from 47 objects in both the $`(10)`$ and $`(21)`$ lines, 30 of which have reliable detections in at least one of the CO lines.

Our study is further motivated by an apparent conundrum that has recently emerged from high-resolution images of this galaxy class. Over the last few years, Hubble Space Telescope (HST) images have revealed that the photocenter of many late-type spirals is occupied by a compact, luminous stellar cluster (Phillips et al. 1996; Carollo et al. 1998; Matthews et al. 1999). In a recent paper (Böker et al. 2002, hereafter paper I), we have shown that at least 75% of spiral galaxies with Hubble types later than Sc harbor such a nuclear star cluster. It thus appears that even in the most shallow disks, the nucleus is a well-defined location. This is difficult to explain, given the fact that the slowly rising rotation curves observed in most late-type spirals indicate a nearly homogenous mass distribution over much of the central disk (e.g. Matthews & Gallagher 1997), and hence gravity does not provide a strong force towards the nucleus.

Even more surprising is the fact that many of the nuclear clusters for which spectroscopic information exists are dominated by a relatively young ($`100\mathrm{Myr}`$) stellar population (Gordon et al. 1999; Böker et al. 1999, 2001; Davidge & Courteau 2002). The dynamical masses for these nuclear star clusters are in the range $`510^510^7\mathrm{M}_{}`$ (Kormendy & McClure 1993; Böker et al. 1999; Matthews & Gallagher 2002; Walcher et al. 2003), and it is unclear how the high gas densities required for the formation of such dense and massive star clusters could have been achieved in the centers of late-type spirals. One possible scenario is that the clusters are formed over time by a series of modest starburst events, rather than in a single, massive collapse. This model is difficult to confirm observationally, because the cluster spectrum is always dominated by the youngest stellar population which contains the most massive and brightest stars. The purpose of this paper is to provide a “sanity check” of this scenario by quantifying the amount of molecular material in the central few kpc of late-type spirals. Clearly, if repetitive starbursts are a viable model for nuclear cluster formation, one would expect to find a central reservoir of molecular gas from which gas can be transported into the central few pc.

In Sect. 2, we describe our galaxy sample, the details of the CO observations, and the data reduction procedure. The resulting CO spectra and their quantitative analysis are presented in Sect. 3. In Sect. 4, we compare the results for our sample to those derived for early-type disk galaxies. In addition, we use the HST images of paper I to investigate possible dependencies between the molecular gas content and galaxy parameters such as luminosity, bar class, or surface brightness, as well as the luminosity of the nuclear star clusters. We summarize and conclude in Sect. 5.

## 2 Sample Selection, Observations and Data Reduction

### 2.1 The galaxy sample

Our galaxy sample was selected according to the criteria described in paper I:

1. Hubble type between Scd and Sm ($`6T9`$).
2. Line-of-sight velocity $`v_{\mathrm{hel}}<2000\mathrm{km}\mathrm{s}^1`$.
3. Axis ratio parameter $`R_{25}\mathrm{log}(a/b)<0.2`$, i.e. inclination close to face-on.

The NASA Extragalactic Database, (NED) contains 120 galaxies that meet the above criteria. In this paper, we present new IRAM observations for a subset of 47 objects. The galaxy names and some selected properties of our IRAM sample are listed in Table 1.

We point out that the sample selection criteria are unbiased (within the limits of the catalogs that form the basis of NED) with respect to galaxy size, stellar or gaseous mass, total magnitude, star formation efficiency, or any other quantity that might reasonably be expected to favor or disfavor nuclear star formation. It should therefore be well suited to provide a representative measure of the molecular gas content in late-type galaxies in the local universe.

Of the 47 IRAM targets, all but 7 (MCG-1-3-85, NGC 4242, NGC 4395, NGC 4519, NGC 4534, NGC 4688, and NGC 5725) have HST I-band observations that were presented in paper I. We use these images to search for possible correlations of the molecular gas content both with the central surface brightness of the stellar disk and the luminosity of the nuclear star cluster (Sect. 4.2 and 4.3). The spatial resolution afforded by HST is essential for this purpose because the emission from the luminous central star cluster is difficult to separate from the underlying disk, even in the best seeing conditions.

### 2.2 Observations and data reduction

All objects were observed with the IRAM $`30\mathrm{m}`$ telescope on Pico Veleta, Spain between December 2001 and August 2002. We used dual polarization receivers at the (redshifted) frequencies of the $`{}_{}{}^{12}\mathrm{CO}(10)`$ and $`{}_{}{}^{12}\mathrm{CO}(21)`$ lines at 115 and $`230\mathrm{GHz}`$, respectively, employing the $`512\times 1\mathrm{MHz}`$ filterbanks for the $`(10)`$ line and the autocorrelator for the $`(21)`$ line. All observations were done in wobbler switching mode with a wobbler throw of $`200^{\prime \prime }`$ in azimuth. The galaxies were observed at their central positions listed in Table 1, with one beam position per galaxy. The telescope pointing accuracy was monitored on nearby quasars every 60 – 90 minutes, the rms offset being $`45^{\prime \prime }`$. Due to relatively poor weather conditions and anomalous refraction during most of our observations, the pointing accuracy is less than optimal. However, given the half-power beam width (HPBW) of the $`30\mathrm{m}`$ telescope of $`21^{\prime \prime }`$ at $`115\mathrm{GHz}`$ and $`11^{\prime \prime }`$ at $`230\mathrm{GHz}`$, this is adequate to measure the nuclear CO emission. At the median distance of our galaxy sample ($`16.7\mathrm{Mpc}`$), the beam size corresponds to $`1.7\mathrm{kpc}`$ ($`0.9\mathrm{kpc}`$) at $`115\mathrm{GHz}`$ ($`230\mathrm{GHz}`$).

Typical on-source integration times were 0.5–1 hours per object, divided in scans of 6 minutes. The individual scans were averaged after flagging of bad channels, and linear baselines were subtracted. Typical rms noise levels were in the range $`310\mathrm{mK}`$ for the $`(10)`$ line and $`538\mathrm{mK}`$ for the $`(21)`$ line (after smoothing to a velocity resolution of $`10\mathrm{km}\mathrm{s}^1`$). The reduced sensitivity of some of the $`(21)`$ observations is due to the fact that during part of the observations, only one of the two receivers was functional.

The data are calibrated to the scale of corrected antenna temperature, $`T_A^{}`$, by measuring loads at ambient and cold temperature, as in the conventional “chopper wheel” calibration for millimeter wavelength observations. A calibration measurement was carried out every 15-20 minutes during an integration and every time a new object was acquired. Typical system temperatures were in the range $`200300\mathrm{K}`$ at $`115\mathrm{GHz}`$ and $`250600\mathrm{K}`$ at $`230\mathrm{GHz}`$ on the $`T_A^{}`$ scale. The IRAM forward efficiency, $`F_{\mathrm{eff}}`$, was 0.95 and 0.91 at 115 and $`230\mathrm{GHz}`$ and the beam efficiency, $`B_{\mathrm{eff}}`$, was 0.75 and 0.50, respectively. All CO spectra and luminosities are presented in the main beam temperature scale ($`T_{\mathrm{mb}}`$) which is defined as $`T_{\mathrm{mb}}=(F_{\mathrm{eff}}/B_{\mathrm{eff}})\times T_A^{}`$. The conversion factor from main beam temperature to flux densities for the $`30\mathrm{m}`$ telescope is $`4.8\mathrm{Jy}/\mathrm{K}`$.

## 3 Results

### 3.1 CO spectra

In Fig. 1, we show the calibrated $`{}_{}{}^{12}\mathrm{CO}(10)`$ and $`(21)`$ spectra of all observed galaxies. The spectra were smoothed to a velocity resolution of $`10\mathrm{km}\mathrm{s}^1`$. We detect 29 galaxies in the $`{}_{}{}^{12}\mathrm{CO}(10)`$ line, 21 of which also show evidence for $`(21)`$ emission. One object (NGC 5584) is detected only in $`(21)`$. The $`{}_{}{}^{12}\mathrm{CO}(10)`$ detections for most galaxies are more than 5$`\sigma `$ above the noise, except for NGC 3906, NGC 4204 and NGC 4299 for which the detections are only at a level of $`3\sigma `$.

The quantitative analysis of the spectra is summarized in Table 2. For all detected galaxies, we list widths (at the 50% level) and central velocities of the $`(10)`$ emission as well as the integrated line intensities. Except for one case, the galaxies in our sample show no clear evidence for double-horn profiles. The CO lines are well-fitted by single Gaussians; both widths and central velocities listed in Table 2 are derived from these fits. The only exception is NGC 7741 for which these numbers were determined from the spectrum itself. For non-detections, we report upper limits for the CO intensities which were derived according to

$$I_{\mathrm{CO}}=3\sigma \sqrt{\mathrm{\Delta }V_{\mathrm{CO}}\delta V}[\mathrm{K}\mathrm{km}\mathrm{s}^1].$$
(1)
Here, $`\sigma `$ is the rms noise of the spectrum, $`\delta V`$ the spectral resolution, and $`\mathrm{\Delta }V_{\mathrm{CO}}`$ the total width of the detected CO line as indicated by the solid horizontal line in the spectra of Fig. 1. In cases for which no CO line was detected, we substitute $`\mathrm{\Delta }V_{\mathrm{CO}}`$ with the width of the HI $`21\mathrm{cm}`$ line, measured at the 20% level (Col. 7 in Table 1, dashed horizontal lines in Fig. 1).

For detections, both line intensities were integrated over the $`(10)`$ line width, except for NGC 5584 which was only detected in the $`(21)`$ line. In general, the CO line positions agree well with those of the $`21\mathrm{cm}`$ line. The errors for the line intensities were calculated as

$$\delta I_{\mathrm{CO}}=\sigma \sqrt{\mathrm{\Delta }V_{\mathrm{CO}}\delta V}[\mathrm{K}\mathrm{km}\mathrm{s}^1].$$
(2)
Fig.1 (cont.)

Fig.1 (cont.)

Fig.1 (cont.)

Fig.1 (cont.)

In Fig. 2a, we compare the velocity-integrated intensities of the two CO lines. Since the telescope beam size is different for the two CO lines, their respective intensities are averaged over different areas in the center of the galaxy. Under the assumption of optically thick molecular gas that extends at least as far as the (larger) $`(10)`$ beam, one would expect an intensity ratio $`I_{10}`$/$`I_{21}`$= $`1`$. If the CO emission were optically thick but more concentrated than the $`{}_{}{}^{12}\mathrm{CO}(10)`$ beam, one would expect $`I_{10}`$/$`I_{21}`$$`<1`$ because beam dilution would lower the observed $`{}_{}{}^{12}\mathrm{CO}(10)`$ beam temperature. The mean value for our sample is $`I_{10}`$/$`I_{21}`$ = $`0.95\pm 0.24`$, consistent with the assumption of optically thick, extended gas. This result is not atypical for spiral galaxies: Braine et al. (1993) found $`I_{10}`$/$`I_{21}`$ = $`0.89\pm 0.06`$ for a mixed sample of 81 galaxies. These authors mapped the $`{}_{}{}^{12}\mathrm{CO}(21)`$ emission in order to survey the same area as covered by the $`{}_{}{}^{12}\mathrm{CO}(10)`$ beam. Their result is therefore not affected by beam dilution and demonstrates that the assumption of optically thick gas is reasonable.

For our galaxy sample, the CO line width is systematically smaller than the HI line width, as demonstrated in Fig. 2b. This result differs from that obtained by Sakamoto et al. (1999) who find that the CO line width reaches about 95% of the $`W_{20}`$ value within $`1\mathrm{kpc}`$ from the center in a sample of 20 CO-luminous, mostly early- to intermediate-type spirals. However, given that the bulge-less, disk-dominated systems in our sample have slowly rising rotation curves, and the beam size of our observations only covers $`1.7\mathrm{kpc}`$ at the median distance of our galaxy sample ($`16.7\mathrm{Mpc}`$), this difference is not surprising. The smaller CO line width also argues against the presence of strong non-circular motion associated with prominent stellar bars in the inner $`2\mathrm{kpc}`$.

### 3.2 Molecular and atomic gas masses

The amount of molecular hydrogen in external galaxies can not be measured directly from $`\mathrm{H}_2`$ emission, but has to rely on indirect methods. The most common of these uses the $`{}_{}{}^{12}\mathrm{CO}(10)`$ line emission as a tracer for $`\mathrm{H}_2`$, assuming proportionality between the abundances of the two species. Driven mostly by the lack of a clear theoretical understanding of the relative abundances, many studies have assumed that the conversion factor $`XN(\mathrm{H}_2)/I(\mathrm{CO})`$ is universal, i.e. applies to all environments.

Keeping in mind the shortcomings of this approach, we can estimate111Here, we have adopted a Gaussian beam for which the solid angle is $`1.13\mathrm{\Theta }^2`$. For comparison, a circular beam (which is also used in the literature) covers a solid angle of $`\pi /4\mathrm{\Theta }^2`$, and hence yields $`M_{\mathrm{H}_2}=68D^2I_{10}\mathrm{\Theta }^2[\mathrm{M}_{}]`$.  the $`\mathrm{H}_2`$ mass within the central $`21^{\prime \prime }`$ by applying a generic conversion factor of $`X=2.310^{20}\mathrm{cm}^2(\mathrm{K}\mathrm{km}\mathrm{s}^1)^1`$ (Strong et al. 1988) which yields:

$$M_{\mathrm{H}_2}=97D^2I_{10}\mathrm{\Theta }^2[\mathrm{M}_{}]$$
(3)
where the galaxy distance $`D`$ is measured in Mpc, $`\mathrm{\Theta }`$, the half power beam width of the 30 m-telescope ($`21^{\prime \prime }`$) in seconds of arc, and $`I_{10}`$ the velocity integrated $`{}_{}{}^{12}\mathrm{CO}(10)`$ intensity in $`\mathrm{K}\mathrm{km}\mathrm{s}^1`$. The distance estimates for our sample are obtained by using the measured recession velocities, corrected for Virgo-centric infall (Sandage & Tammann 1990), and assuming $`\mathrm{H}_0=70\mathrm{km}\mathrm{s}^1\mathrm{Mpc}^1`$. In the case of NGC 5584, for which only the $`(21)`$ line was detected, we estimate $`I_{10}`$ by assuming that the $`(10)`$ measurement is affected by beam dilution, i.e. the CO emitting region is small compared to the $`(21)`$ beam. In this case, if the intrinsic $`I_{10}`$/$`I_{21}`$ ratio is unity, as appears to be the case for the rest of the sample, then $`I_{10}`$=$`I_{21}`$/4 in NGC 5584. This value is consistent with the upper limit derived from the $`(10)`$ spectrum itself.

The resulting molecular gas masses for the detected galaxies (Col. 6 of Table 2) span the range between $`1.2\times 10^6`$ and $`1.9\times 10^8`$ $`\mathrm{M}_{}`$. We emphasize that these mass estimates represent only lower limits to the total molecular gas content, since the galaxies were only observed at their center position (on average, the IRAM beam diameter is only about 10% of $`d_{25}`$).

There is general agreement, both from models (Maloney & Black 1988; Kaufman et al. 1999) and from observations that $`X`$ is not constant but in fact depends on environmental parameters such as metallicity, density, or the radiation environment. Unfortunately, observations have not yet yielded a unique prescription for these dependencies. Studies of nearby galaxies provide evidence for a strong dependence of $`X`$ on metallicity, but the various authors report different slopes (Wilson 1995; Arimoto et al. 1996; Israel 1997; Boselli et al. 2002).

In order to test the robustness of our analysis resulting from the use of Eq. (3), we also apply a galaxy-dependent $`X`$. Specifically, we use the relation suggested by Boselli et al. (2002) which was derived from a sample of 14 well-studied nearby galaxies. Their relation between $`X`$ and the metallicity agrees well with the result of Arimoto et al. (1996), with a slope that is stronger than the one found by Wilson (1995), and weaker than that derived by Israel (1997). For our purposes, we use the relation between $`X`$ and the blue magnitude of Boselli et al. (2002):

$$\mathrm{log}(X)=(0.18\pm 0.04)\mathrm{M}_\mathrm{B}+(23.77\pm 0.28)$$
(4)
The resulting $`\mathrm{H}_2`$ masses, $`M_{\mathrm{H}_2}`$(var) are also listed in Table 2 (Col. 7).

In order to compare the mass of the molecular gas component to that of the atomic one, we calculate the total HI mass for our galaxy sample from the 21 cm flux (as listed in LEDA) following the approach described in de Vaucouleurs et al. (1991), Eq. (74-77). The HI masses derived in this fashion represent the total HI mass of the galaxy, they are listed in Col. 8 of Table 2.

## 4 Analysis

### 4.1 Comparison to early-type galaxies

One of the goals of this program is to complement existing studies of the molecular gas content of spiral galaxies with a sample of “pure” disk galaxies with Hubble types around Sd. These galaxies are underrepresented in existing samples, and it is important to adress the question whether they follow the same trends as intermediate- to early-type spirals, or whether they might have intrinsically different gas properties. We have therefore compared our results to those obtained by Braine et al. (1993) for a sample of 81 predominantly early-type spiral galaxies. Their dataset is particularly suited for comparison with ours because both samples have nearly identical distance distributions (Fig. 3a) and were observed with the IRAM $`30\mathrm{m}`$ telescope. In particular, the $`{}_{}{}^{12}\mathrm{CO}(10)`$ intensities of the Braine et al. (1993) sample also refer to the central position of the galaxies only, and are therefore directly comparable to our data. The Braine et al. (1993) sample was selected to include nearby spiral galaxies with $`\mathrm{m}_\mathrm{B}<12\mathrm{mag}`$. In contrast, our sample mostly contains fainter galaxies (42 out of 47 galaxies have $`\mathrm{m}_\mathrm{B}>12\mathrm{mag}`$). Fig. 3b shows that the angular diameter of the major axis, $`d_{25}`$, of the Braine et al. (1993) galaxies is on average larger than for our targets, although both samples have nearly identical distance distributions. This is to be expected, because late-type spirals have on average lower total luminosities and lower surface brightness (Roberts & Haynes 1994), both of which likely reduce the isophotal diameter.

As evident from Fig. 3b, neither sample shows an obvious trend between the angular size of the galaxy disk and $`I_{10}`$. We have also verified that there is no correlation between the angular size and $`M_{\mathrm{H}_2}`$ or $`M_{\mathrm{H}_2}`$(var). This indicates that the CO observations are not significantly biased by the ratio of the optical disk size to the IRAM beam. Since the optical diameters in both samples are much larger than the IRAM $`(10)`$ beam of $`21^{\prime \prime }`$, it is likely that in both studies, the observations miss a non-negligible fraction of the total CO emission. This is confirmed for those 6 galaxies in our sample for which wide-beam data are listed in the GOLDMine database (Gavazzi et al. 2003). For these 6 objects, the IRAM beam detects only between 15 and 60% of the total $`I_{10}`$. In principle, the undetected CO fraction should increase with galaxy diameter because the size of the CO-emitting region and the diameter of the optical disk are correlated ($`d_{\mathrm{CO}}/d_{25}0.5`$ Young et al. 1995). However, the fact that the central $`I_{10}`$ is on average larger for the Braine et al. (1993) sample demonstrates that typically, early type spirals have more CO within their central few kpc than late type spirals.

In Fig. 4a, we add the results of our survey to the well-known relation between molecular gas mass (here calculated with the generic value for $`X`$, but using Eq. (4) yields equivalent results) and the far-infrared (FIR) luminosity (e.g. Young & Scoville 1991). The galaxies of our sample closely follow the relation defined by the earlier-type spirals, and extend it towards lower FIR-luminosities. The slope of the correlation is consistent with 1, indicating direct proportionality between the two quantitites. The average value of $`L_{\mathrm{FIR}}`$/$`M_{\mathrm{H}_2}`$ is about 40. This is higher than in nearby normal spirals ($`L_{\mathrm{FIR}}`$/$`M_{\mathrm{H}_2}`$$`5`$) and even starburst galaxies ($`L_{\mathrm{FIR}}`$/$`M_{\mathrm{H}_2}`$$`15`$) (Sanders & Mirabel 1996), another indication that measurements with a single IRAM pointing miss a substantial fraction of total molecular gas. It is interesting that after normalization of the two quantities to the optical diameter of the galaxy, the two samples overlap and cover a similar range (Fig. 4b). This suggests that the latest-type spirals follow the same physical processes that intimately link the molecular gas with star formation activity. At least in this context, the latest-type spirals are not a distinct class of objects, but rather constitute the low-luminosity end of the galaxy distribution.

A similar conclusion can be reached from the relation between $`\mathrm{H}_2`$ mass and total magnitude $`\mathrm{M}_\mathrm{B}`$ shown in Fig. 5: optically fainter galaxies have less molecular gas in their central regions. This result holds also when calculating the molecular mass according to Eq. (4), although this increases the scatter and reduces the dynamical range of $`M_{\mathrm{H}_2}`$. A similar, albeit weaker, correlation exists between optical luminosity and molecular-to-atomic gas mass ratio. Using Eq. (4) for $`X`$ again increases the scatter, so that only a weak trend remains (Fig. 5c, d). Here, as well as in Fig. 6c and d, we have excluded three galaxies (NGC 2681, NGC 4274, and NGC 4438) with anomalously222Specifically, we consider as HI-deficient those galaxies which deviate by more than $`3\sigma `$ from the relation between $`M_{\mathrm{HI}}`$ and linear diameter found by Haynes & Giovanelli (1984) (their Table V). low HI content from the Braine et al. (1993) sample.

We find that the latest-type spirals have on average less molecular gas and lower molecular gas mass fractions in their central regions than their early-type cousins. This is demonstrated in Fig. 6 which plots the $`\mathrm{H}_2`$ mass and $`M_{\mathrm{H}_2}`$/$`M_{\mathrm{HI}}`$ ratio versus Hubble-type. This result seems robust against variations in $`X`$, although using a luminosity-dependent conversion factor increases the scatter and decreases the slope of the correlations (Fig. 6b, d). The dependency of molecular gas mass fraction on Hubble-type and luminosity apparently contradicts the results of Boselli et al. (2002) who find that the fraction of molecular gas is independent of Hubble type or luminosity. It should be kept in mind that for our survey - as well as for the Braine et al. (1993) data - the IRAM beam is generally much smaller than the optical or HI disk of the galaxy. This probably explains the fact that typical gas mass fractions in Fig. 6c) and d) are only a few percent, much smaller than the $``$15% found by Boselli et al. (2002). However, effects related to beam size cannot explain the reduced $`\mathrm{H}_2`$ fraction at the late end of the Hubble sequence in Fig. 6c) and d) because both samples were observed in the same way with the same instrument and have similar distance distributions (Fig. 3a). Furthermore, Fig. 3b shows that the optical diameter $`d_{25}`$ is on average smaller for late-type spirals than for earlier Hubble types, and the $`21^{\prime \prime }`$ IRAM beam therefore covers a larger fraction of the optical disk. If the extent of molecular gas scales with the optical diameter in a way that is common to all galaxies, one would expect our sample to have a higher molecular gas fraction than the Braine et al. (1993) sample.

The fact that we observe the opposite result therefore indicates that the molecular gas in late-type spirals is less centrally concentrated relative to the HI distribution than in early-type spirals if indeed the overall $`\mathrm{H}_2`$/HI ratio is the same for all types of spirals, as indicated by the results of Boselli et al. (2002). This is in qualitative agreement with the result of Young et al. (1995) who find that the ratio between the CO and optical isophotal radius increases with Hubble type.

As discussed by Böker et al. (2003), one should not place too much emphasis on the exact Hubble classification in the range Scd-Sm because at arcsecond resolution, the prominent nuclear star cluster is easily mistaken as a compact “bulge”, and hence any morphological classification based on ground-based images is inaccurate at best. Nevertheless, it is clear from Fig. 6a) and b) that late-type galaxies are rather inefficient in accumulating molecular gas in their central regions. Similar results have been found by a number of earlier studies (e.g. Young & Knezek 1989; Sage 1993; Casoli et al. 1998). Young & Knezek (1989) have suggested that the deep gravitational well of a prominent bulge facilitates the formation and/or accumulation of molecular gas. While this might well be true, it is certainly not the whole story. Our sample has been selected to be devoid of stellar bulges, yet it shows a wide range of $`\mathrm{H}_2`$ masses. In the next section, we use the high-resolution HST images to investigate the impact of the shape of the stellar disk on the amount of molecular gas that accumulates in the center.

The results presented in this section depend to some degree on the assumptions made for $`X`$, in particular the variation with metallicity and/or luminosity which is still a matter of debate. For example, a much stronger dependence of $`X`$ on metallicity than the one derived by Boselli et al. (2002) has been suggested by Israel (1997). Using Fig. 2 of Boselli et al. (2002), we can infer that the variation in $`X`$ across the range of $`\mathrm{M}_\mathrm{B}`$ covered by the galaxies discussed here (-14 $``$ $`\mathrm{M}_\mathrm{B}`$ $``$ -21) is equivalent to that caused by metallicity differences of about 1 dex. According to Israel (1997), $`X`$ would vary by a factor of 500 over this metallicity range. While such a high variance in $`X`$ seems somewhat unlikely, it would eliminate (or even reverse) the trends of $`M_{\mathrm{H}_2}`$ or $`M_{\mathrm{H}_2}`$/$`M_{\mathrm{HI}}`$ with $`\mathrm{M}_\mathrm{B}`$ and Hubble type in Figs. 5 and 6.

### 4.2 CO and the stellar disk

In order to measure the central surface brightness of the galaxy disk underlying the nuclear cluster we have used the results of the elliptical isophote fits presented in paper I. Here, we have adopted the average of the two inward extrapolations of the disk shown in Fig. 3 of paper I. In Fig. 7, we compare the so-derived central disk surface brightness $`\mu _\mathrm{I}^0`$ which is directly proportional to the average molecular gas surface density $`I_{10}`$ within the beam. Both quantities are independent of galaxy distance, as long as the CO is more extended than the IRAM beam, which - based on the observed CO line ratio discussed in Sect. 3 \- is most likely true for the majority of our sample.

The most direct result of Fig. 7 is that there appears to be a threshold surface brightness for detection at the sensitivity limit of our observations: we detect all 25 galaxies with $`\mu _I^0<18.7\mathrm{mags}\mathrm{arcsec}^2`$, but only 1 out of 15 galaxies with $`\mu _I^0>18.7\mathrm{mags}\mathrm{arcsec}^2`$. This trend cannot plausibly be explained by anomalously high values of $`X`$ in the undetected galaxies, because their absolute magnitudes span a wide range (-14 $``$ $`\mathrm{M}_\mathrm{B}`$ $``$ -19.5). Figure 7 therefore indicates that the stellar density in the central regions of late-type spirals is intimately linked to the molecular gas abundance, even in the absence of a massive stellar bulge. It is difficult to assess whether there is a direct correlation between $`\mu _\mathrm{I}^0`$ and $`I_{10}`$. To address this issue, deeper CO observations for a larger galaxy sample which expands the range of surface brightness levels would be required. Nevertheless, this result might help to explain the low success rate in detecting molecular gas in low surface brightness (LSB) galaxies. This class of galaxies, defined to have $`\mu _\mathrm{B}^0>23\mathrm{mags}\mathrm{arcsec}^2`$ or $`\mu _\mathrm{I}^0>2122\mathrm{mags}\mathrm{arcsec}^2`$ for typical disk colors (de Jong 1996), has only been successfully detected in 3 out of 34 attempts (see compilation by O’Neil et al. 2003). The typical CO intensity of the detected LSB galaxies ($`1.2\mathrm{K}\mathrm{km}\mathrm{s}^1`$) is similar to that of our sample (both datasets were obtained with the $`30\mathrm{m}`$ telescope, and are thus directly comparable). However, the upper limits reported by O’Neil et al. (2003) for non-detections ($`<0.3\mathrm{K}\mathrm{km}\mathrm{s}^1`$) fall well below our sensitivity limit. It is therefore possible that LSB galaxies would extend the correlation between central surface brightness and CO intensity to fainter levels.

### 4.3 CO and nuclear star clusters

Our survey has shown that the latest-type spirals are not entirely devoid of molecular gas. With a median $`\mathrm{H}_2`$ mass of $`1.4\times 10^7\mathrm{M}_{}`$ inside the IRAM beam, there is enough raw material within the central kpc to support a number of modest ($`10^5\mathrm{M}_{}`$ in stars) starburst episodes assuming a star formation efficiency of 10%. This is an important result because recent spectroscopy of nuclear clusters has shown that the spectral energy distribution (SED) of a large fraction of these objects is dominated by a relatively young population of stars with an age of a few hundred Myrs (Walcher et al. 2003). Because it is unlikely that we witness the first nuclear starburst in such a large number of galaxies, it is reasonable to assume that star formation episodes within the central few pc occur repetitively. If true, there must be a reservoir of molecular gas to support these events. While it is comforting that our observations have demonstrated the presence of reasonable amounts of molecular gas in the central regions of late-type spirals, much has to be learned about the details of nuclear cluster formation. Recent high resolution ($`10\mathrm{pc}`$) CO observations of the barred late-type spiral IC 342 demonstrate that gas can indeed accumulate inside the central few pc (Schinnerer et al. 2003). In the case of IC 342, rough estimates of the gas inflow rates suggest that repetitive nuclear starbursts can be supported with duty cycles between $`100\mathrm{Myr}`$ and $`1\mathrm{Gyr}`$. However, IC 342 presents only a case study, and it is uncertain whether similar processes are common in late-type galaxies.

As we have discussed in the last section, the stellar density over the central kiloparsec appears tightly linked to the molecular gas abundance (or vice versa). On the other hand, the luminosity of the nuclear star cluster appears largely independent of $`\mathrm{M}_{\mathrm{H}_2}`$, as demonstrated in Fig. 8. Again, this result is independent on the exact recipe to calculate the $`\mathrm{H}_2`$ mass: using Eq. (4) for the $`X`$ does not significantly change Fig. 8. This result is not too surprising because the cluster luminosity is mostly determined by the age of the youngest population, and hence is not a reliable indicator of cluster mass (which one might expect to be more tightly correlated with CO luminosity).

However, it is interesting to note that $``$ 90% of the galaxies with nuclear clusters of $`\mathrm{M}_\mathrm{I}<11.5`$ are detected in CO, whereas the detection rate is about a factor of three lower for less luminous clusters. In addition, out of the 7 galaxies without a nuclear star cluster only one (NGC 7741) is detected in CO. This result underlines the notion that the lack of molecular gas is the main reason for the uneventful star formation history in the central regions of these galaxies. A more thorough study of the connection between molecular gas supply and nuclear starbursts requires reliable mass and age estimates for the nuclear clusters. Such measurements - which are now possible from high-resolution optical spectroscopy with large ground-based telescopes (Walcher et al. 2003) \- will undoubtedly provide new insights into the formation mechanism of nuclear clusters. In the meantime, it is not unreasonable to speculate that the frequency and efficiency of nuclear starbursts is governed by the supply of molecular gas which in turn is regulated, at least in part, by the gravitational potential of the host galaxy disk.

### 4.4 Are bars important?

As discussed so far, the gravitational potential of the stellar mass distribution appears to play an important role for the gas flow towards the nucleus. In this paragraph, we discuss whether our observations provide evidence that dynamical effects such as gas flow in a non-axisymmetric potential are also important. A way to gauge the impact of stellar bars on (circum)nuclear star formation is to measure the amount of molecular gas in the central kiloparsec in barred and unbarred galaxies. A number of studies have shown that the nuclear gas concentration in barred galaxies is indeed higher than in galaxies without bars (e.g. Sakamoto et al. 1999; Sheth 2001; Sheth et al. 2003), thus confirming the theoretical picture that bars drive molecular gas toward the galaxy center (e.g. Athanassoula 1992). However, the (few) galaxies with late Hubble types in these studies were selected to be luminous in the blue or the FIR, i.e. they are biased towards high star formation rates.

Our sample, on the other hand, has been selected only for Hubble type, inclination, and distance (see Sect. 2.1). It should therefore provide an unbiased look at the impact of stellar bars on the molecular gas abundance in the latest Hubble-type spirals. Our sample is evenly divided in barred, mixed, and unbarred galaxies following the RC3 (de Vaucouleurs et al. 1991) classification scheme (morphological type SB, SAB, or SA, respectively). In Table 3, we summarize the CO statistics for the three subsamples. We detect 80% of the barred galaxies in our sample, compared to 63% of mixed and 44% of unbarred galaxies. Taken at face value, this result supports the notion that bars are indeed an important factor for the transport of molecular gas towards the central few kiloparsec, even in very late Hubble types. However, we caution that the morphological classification of late-type galaxies is somewhat uncertain. For example, the bar classes reported in the LEDA database are different from those in the RC3 in about 20% (10 out of 47) of the cases. Using the LEDA classification scheme, we only find a slightly higher detection rate in barred galaxies (Table 3).

The average value of $`I_{10}`$ in barred galaxies appears slightly higher than in unbarred galaxies, but given the large standard deviations (Col. 7 of Table 3) in the respective subsamples, this is not significant. We have included upper limits for undetected galaxies in the averaging, but excluding these values does not change the result. For completeness, we point out that the median absolute galaxy magnitude ($`\mathrm{M}_\mathrm{B}`$) of the unbarred subsample is about 1 magnitude fainter than for the barred subsample (Col. 8 of Table 3) which potentially causes a bias towards lower molecular gas masses in the unbarred sample due to the correlation between $`\mathrm{M}_\mathrm{B}`$ and $`M_{\mathrm{H}_2}`$. To summarize, our observations provide little evidence for enhanced molecular gas masses in the centers of barred late-type spirals.

Whether stellar bars are a significant ingredient in the recipe to form compact stellar nuclei is an even more difficult question. Recent observations have not found much evidence for enhanced star formation in the very nuclei of barred galaxies (Ho et al. 1997), in apparent contradiction to the results from molecular gas surveys mentioned above. This notion is confirmed by the fact that nuclear clusters are found just as often in barred galaxies as in unbarred ones (paper I; Böker et al. 2003, in preparation). In addition, the topic is complicated by the fact that bars do not live forever. In fact, numerical simulations have shown that build-up of a central mass concentration (such as a supermassive black hole or a compact nuclear cluster) can dissolve stellar bars via dynamical instabilities (Norman et al. 1996). Because the bar destruction happens within just a few dynamical times, it is possible that a stellar bar might have been present in the past, leading to nuclear star formation until enough mass has been collected at the center to render the bar unstable. Without a more accurate isophotal analysis or even kinematic information on the central disks of late-type spirals, this question will remain open.

## 5 Summary

We have presented $`{}_{}{}^{12}\mathrm{CO}(10)`$ and $`{}_{}{}^{12}\mathrm{CO}(21)`$ spectra of the central $`12\mathrm{kpc}`$ in 47 spiral galaxies with Hubble-types between Scd and Sm. Of these, we detect 30 objects in at least one of the lines. Our survey thus significantly increases the number of available CO data for very late-type disk galaxies. The main results of our analysis can be summarized as follows:

1. The average $`\mathrm{H}_2`$ mass within the central kpc is $`1.4\times 10^7\mathrm{M}_{}`$. In principle, this amount is sufficient to support a number of modest ($`10^5\mathrm{M}_{}`$ in stars) starburst events. As recent high-resolution optical studies of Scd-Sm spirals have shown, star formation in these “pure” disk galaxies is almost exclusively found in the very nucleus, which is the location of a luminous, compact, and massive star cluster in at least 75% of the cases. In this context, our results are consistent with scenarios that invoke repeated nuclear starbursts to explain the fact that the SED of many clusters is dominated by a young (less than a few 100 Myrs) population of stars.
2. The latest-type spirals closely follow correlations between molecular gas content and galaxy luminosity - both at optical and far-infrared wavelengths - that have been established for more luminous, early- and intermediate-type spirals and extend them to lower luminosities. In particular, we find a lower ratio between the (central) $`M_{\mathrm{H}_2}`$ and the (total) $`M_{\mathrm{HI}}`$ for late type spirals for both prescriptions used to translate CO luminosity into molecular gas mass. This could either be due to a lower overall CO content (with respect to $`M_{\mathrm{HI}}`$) or a more extended distribution of the molecular gas in late-type galaxies. We favor the second scenario since the results of Boselli et al. (2002) obtained with a larger beam indicate that the overall $`M_{\mathrm{H}_2}`$/$`M_{\mathrm{HI}}`$ ratio is the same in all Hubble types.
3. We find a strong separation between our CO detections and non-detections in central surface brightness of the stellar disk, $`\mu _I^0`$. We detect 93% of galaxies with $`\mu _I^0<19\mathrm{mags}\mathrm{arcsec}^2`$, but only 8% of galaxies with $`\mu _I^0>19\mathrm{mags}\mathrm{arcsec}^2`$. While our observations are not sensitive enough to establish a direct correlation between the two quantities, our results fit in well with the detection rate of LSB galaxies which have even lower surface brightness disks than the galaxies in our sample. This suggests that the stellar mass distribution of the galaxy disk is an important indicator for the central accumulation of molecular gas.
4. While there is little evidence for a direct correlation between the luminosity of the nuclear star cluster and the $`\mathrm{H}_2`$ mass, we find a higher CO detection rate and higher average $`\mathrm{H}_2`$ mass in galaxies with the most luminous clusters. Although for young stellar populations luminosity is not a reliable indicator of mass, this suggests that the molecular gas supply is indeed an important parameter for the formation mechanism of nuclear star clusters.
5. Our observations provide only marginal support for an enhanced molecular gas mass in the centers of barred galaxies relative to unbarred ones.

###### Acknowledgements.

We would like to thank the referee, A. Boselli, for his helpful comments. UL ackowledges support from DGI Grant AYA2002-03338 and the Junta de Andalucía (Spain). This research has made use of the NASA/IPAC Infrared Science Archive and the NASA/IPAC Extragalactic Database (NED), both of which are operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. It has also benefited greatly from use of the Lyon-Meudon Extragalactic Database (LEDA, http://leda.univ-lyon1.fr).


format: text

text:
# Untitled Document

Thermoelectric power in between two plateaus in quantum Hall effect. Keshav N. Shrivastava School of Physics, University of Hyderabad,
Hyderabad 500046, India

We have considered the response at two energies corresponding to two plateaus in the quantum Hall effect. Since the thermoelectric power involves the derivative of conductivity with respect to energy, we introduce the concept of a line width and hence an activation energy. We then use the Hall conductivity to define the thermoelectric power at the centre of two plateaus, which is found to vary monotonically as T2 at low temperatures with fixed magnetic field. At elivated temperatures, the thermoelectric power varies as T exp(-$`\mathrm{\Delta }/k_B`$T). (Key words: Thermoelectric power, Hall effect, Mott’s formula.)
Corresponding author: keshav@mailaps.org
Fax: +91-40-2301 0145.Phone: 2301 0811.

1. Introduction

The phenomenon of quantum Hall effect has been described for a long time. The thermoelectric power involves the derivative of conductivity as a function of energy so that at the plateau in the Hall resistivity, where energy is fixed, it is not well defined. On the other hand, if we look at the centre of two plateaus, at a fixed magnetic field, we can define this derivative by using a relaxation process. The thermoelectric power can then give information about the relaxation mechanism in the quantum Hall effect away from the plateaus. In the transverse resistivity there are minima at the same magnetic fields where there are plateaus in the longitudinal resistivity. These fields are described by integers as well as fractions which are predicted by us.

In this communication, we obtain the thermoelectric power at the centre of two plateaus. This is an important point because the system becomes metallic just before the plateaus and hence there is a peak in the resistivity at a point in the centre of two plateaus. The system is some times referred to as “insulator” near the peak. Thus we are able to find the thermoelectric power in the insulating phase.

2. Theory

We consider a three level system in which the energies are labeled as Eo, E1 and E2. It absorbs energies E2-Eo and E1-$`E_o`$ so that there are two lines in the absorption as a function of energy. If these lines are far apart, there is no overlap and hence there is no region where the absorption depends on line width. We select a problem where there is a region in which the absorption depends on the line width. The width of the line at E1 is $`\delta \mathrm{\Omega }_1`$ and that at E2 is $`\delta \mathrm{\Omega }_2`$. The response function in this case is given by,

$$\chi ^\mathrm{"}=\frac{\delta \mathrm{\Omega }_1}{\{(EE_1)/\mathrm{}\}^2+(\delta \mathrm{\Omega }_1)^2}+\frac{\delta \mathrm{\Omega }_2}{\{(EE_2)/\mathrm{}\}^2+(\delta \mathrm{\Omega }_2)^2}.$$
(1)
If $`E_2E_1>>\mathrm{}\delta \mathrm{\Omega }_1`$, the lines are well resolved and peaked at well defined energies such as E1 and E2. On the other hand if $`E_2E_1<\mathrm{}\delta \mathrm{\Omega }_1`$, the lines overlap and there is absorption in the centre of two spectral lines. Since we are interested in the thermoelectric power in the centre of two lines, we consider the case of overlap between two lines. We suppose that the two lines are separated by $`\delta _1`$ such that $`\delta _1`$ is smaller than either $`\mathrm{\Omega }_1`$ or $`\mathrm{\Omega }_2`$, i.e.,

$$E_2E_1=\delta _1$$
(2)
$$\delta _1<<\delta \mathrm{\Omega }_1$$
(3)
$$\delta _1<<\delta \mathrm{\Omega }_2.$$
(4)
At $`E=E_1`$, the first term in the response function is peaked so that the response becomes,

$$\chi ^\mathrm{"}=\frac{1}{\delta \mathrm{\Omega }_1}+\frac{\delta \mathrm{\Omega }_2}{\{(E_1E_2)/\mathrm{}\}^2+(\delta \mathrm{\Omega }_2)^2}$$
(5)
but the line at $`E_2`$ is very near the one at $`E_1`$ so that the lines overlap. Substituting (2) in (5) we find,

$$\chi ^\mathrm{"}=\frac{1}{\delta \mathrm{\Omega }_1}+\frac{\delta \mathrm{\Omega }_2}{(\delta _1/\mathrm{})^2+(\delta \mathrm{\Omega }_2)^2}.$$
(6)
For convenience of algebra, we assume $`\delta \mathrm{\Omega }_1\delta \mathrm{\Omega }_2`$ so that the centre of the lines between $`E_1`$ and $`E_2`$ is located at $`E_1+\frac{1}{2}\delta _1`$. If the relaxation occurs due to interaction with phonons, the width depends on the phonon correlation function, $`2n+1`$, where $`n=[exp(\mathrm{\Delta }/k_BT)1]^1`$. It is also possible to say that $`nexp(\mathrm{\Delta }/k_BT)`$ at low temperatures so that $`\mathrm{\Delta }`$ becomes the activation energy,

$$\delta \mathrm{\Omega }_1=c_1(2n+1)2c_1exp(\mathrm{\Delta }/k_BT)$$
(7)
In the symmetric case,

$$\delta \mathrm{\Omega }_1=\delta _1.$$
(8)
Let us consider the old Hall effect. In the quantum Hall effect the conductivity is quantized as $`\sigma =ie^2/h`$ where $`i`$ may be an integer or a fraction. We believe that this fraction depends on spin. If there are two plateaus, they occur at $`i=\nu _1`$ and $`i=\nu _2`$. The conductivity is quantized at both $`\nu _1`$ as well as at $`\nu _2`$ but we are neither interested in quantization at $`\nu _1`$ nor at $`\nu _2`$. We are interested in the point which is exactly in the middle of $`\nu _1`$ and $`\nu _2`$ so that there is no quantization at this point.

The current is determined by $`j=nev`$ where $`n`$ is the concentration of electrons, $`e`$ the charge and $`v`$ the velocity. We replace the charge by energy $`E_cE_F+\frac{3}{2}k_BT`$ and devide the resulting expression by the current to define the Peltier coefficient,

$$\mathrm{\Pi }=\frac{E_cE_F+\frac{3}{2}k_BT}{e}$$
(9)
where $`E_c`$ is the electron energy in the conduction band. The negative sign in the above has come from the sign of the charge, -e. The thermoelectric power, S, may be defined as,

$$\mathrm{\Pi }=ST$$
(10)
where T is the temperature. If $`|\stackrel{}{E}|`$ is the electric field, another definition of the thermoelectric power is obtained by,

$$|\stackrel{}{E}|=SgradT$$
(11)
or

$$S=\frac{|\stackrel{}{E}|}{gradT}.$$
(12)
We can replace the $`grad`$ by $`d/dx`$ but then the temperature gradient has to be evaluated. Apparently, Mott has solved this problem by defining the thermoelectric power by using the energy derivative of the logarithm of the conductivity,

$$S=\frac{\pi ^2k_B^2T}{3e}\frac{d}{dE}ln\sigma |_{E=E_F}.$$
(13)
This means that we should know the conductivity as a function of energy, then only we can use the Mott formula. As we described above, we are interested in a point which is mid way between two quantized values, we use the old result according to which the Hall resistivity is $`\rho =nec/B`$ and hence the Hall conductivity is,

$$\sigma =\frac{nec}{B}$$
(14)
where $`n`$ is the electron concentration, $`e`$ is the charge, $`B`$ is the magnetic field and c is the velocity of light. The transition energies in the system described above are $`E_1=\frac{1}{2}g\mu _BB_1`$ and $`E_2=\frac{1}{2}g\mu _BB_2`$. Our transitions occur at $`E_1`$ and $`E_2`$ and the centre is at $`E_1+\frac{1}{2}\delta _1`$. Thus there is quantization at $`E_1`$ and at $`E_2`$ but not at $`E_1+\frac{1}{2}\delta _1`$. Therefore, the conductivity becomes,

$$\sigma =\frac{1}{2}g\mu _Bnec\frac{1}{E}$$
(15)
where $`E=\frac{1}{2}g\mu _BB`$. Taking the logarithm of conductivity, we obtain,

$$ln\sigma =ln(\frac{1}{2}g\mu _Bnec)lnE$$
(16)
so that

$$\frac{d}{dE}ln\sigma =\frac{d}{dE}lnE=\frac{1}{E}.$$
(17)
If the conductivity is thermally activated,

$$\sigma =\sigma _oexp(E/k_BT)$$
(18)
we obtain,

$$\frac{d}{dE}ln\sigma =\frac{1}{k_BT}.$$
(19)
In this case, the thermoelectric power will be independent of temperature. Therefore, we do not consider this case but we consider the thermally activated relaxation rate. We go back to the Mott formula to find the thermoelectric power as,

$$S=\frac{\pi ^2k_B^2T}{3e}\frac{1}{E}.$$
(20)
Where the negative sign means that power reduces as the energy is increased. When energy is either $`E_1`$ or $`E_2`$, the conductivity is quantized but at the mid point, $`E=E_1+\frac{1}{2}\delta _1`$, the conductivity is not quantized so that at this point,

$$S=\frac{\pi ^2k_B^2T}{3eE_1(1+\frac{1}{2}\frac{\delta _1}{E_1})}.$$
(21)
If $`\delta _1`$ is very small compared with $`E_1`$ we can write the term in the denominator as,

$$S=\frac{\delta _1\pi ^2k_B^2T}{6eE_1^2}\frac{\pi ^2k_B^2T}{3eE_1}.$$
(22)
Thus there is a large negative term which is linear in T and a small correction which depends on the relaxation. The distance $`\frac{1}{2}\delta _1`$ must be equal to half width so that,

$$\delta _1=\frac{1}{2\tau _1}=c_1(2n+1).$$
(23)
If the system is thermally activated, $`2n+12n2exp(\mathrm{\Delta }/k_BT)`$. Therefore, the first term in the thermoelectric power varies as,

$$S_1=\frac{\pi ^2k_B^2Tc_1(2n+1)}{6eE_1^2}\frac{\pi ^2k_B^2c_1Texp(\mathrm{\Delta }/k_BT)}{3eE_1^2}$$
(24)
in which the temperature dependence is determined by

$$S_1c_2Tcoth\frac{\mathrm{\Delta }}{2k_BT}$$
(25)
which at high temperatures varies as,

$$S_1\frac{2c_2k_BT^2}{\mathrm{\Delta }}.$$
(26)
There is also a large negative term,

$$S=S_1+S_2$$
(27)
$$S_2=\frac{\pi ^2k_B^2T}{3eE_1}.$$
(28)
Thus we have two terms in the thermoelectric power. One of these terms is negative and linear in temperature. This describes the emission of power under favourable conditions such as large relaxation times in the excited states. The other term is positive and depends approximately on $`T^2`$. It may be described as $`Tcoth(\mathrm{\Delta }/2k_BT)`$. It is known that relaxation in quantum Hall effect is thermally activated so that the thermopower may appear as $`Texp(\mathrm{\Delta }/k_BT)`$ as given by (24). In these results, the magnetic field is held constant so that there is no phase transition by varying temperature.

The variation of conductivity as a function of length or thickness of the sample is well known and it is related to a critical exponent. Polyakov and Shklovskii have treated $`\delta _1`$ or an equivalent quantity as if there is a phase transition with a critical temperature. In that case, the width is described by “scaling exponents”,

$$\delta _1T^\kappa $$
(29)
where $`\kappa `$ 0.4. It has been possible to correlate the exponent $`\kappa `$ with $`\gamma `$ which describes the coherence length. The band filling factor is called $`\nu `$ and the coherence length varies as,

$$\xi (\nu )=\xi (0)|\nu \nu _o|^\gamma $$
(30)
with $`\gamma `$ = 2.3 or $`\kappa =1/\gamma `$=0.435. Long time ago, the value of $`\kappa `$ was thought to be 0.5. We write the scaling width as,

$$\delta _1=c_2T^\kappa $$
(31)
which shows that the positive term of the thermoelectric power varies as,

$$S_1=\frac{\pi ^2k_B^2c_2}{6eE_1^2}T^{\kappa +1}$$
(32)
so that the exponent $`\kappa `$+1 can be determined from the thermoelectric power as a function of temperature. The critical exponents are a characteristic of a phase transition. When $`T_c`$0, $`(TT_c)^\kappa =T^\kappa `$ so that Polyakov’s result is applicable to a phase transition at zero temperature. When we go from one level to another, we call it a phase transition. However, if we keep the magnetic field a constant at the middle of two plateaus, then there is no phase transition and we need not expect any critical exponent.

Possanzini et al have measured the thermoelectric power for two different densities. In both the cases, the thermoelectric power monotonically increases with increasing temperature from 0.4 to 4 K. An effort is made to fit the data with $`S=\alpha T^{1/3}+\eta T^4`$ which is interpreted to arise from a variable range hopping model or from $`S_{xx}=\gamma +\eta T^4`$. Naturally, a term can be added in which the exponent has any value between 1/3 and 4 without disturbing the agreement between the model and the data. The expression (26) shows that the thermoelectric power varies as $`T^2`$. When the magnetic field is kept constant and the temperature is varied, it is reasonable to expect that there is no phase transition so the thermoelectric power varies as $`T^2`$. At a temperature of 0.32 K, the largest positive value of the diagonal thermoelectric power is about 5$`\mu `$V/K and at very small magnetic fields, the value is negative of the order of 10$`\mu `$V/K. Thus these observed features are in accord with the theoretical expressions.

3. Conclusions.

In conclusions,we find that when field is fixed in between two plateaus, the thermoelectric power varies as $`T^2`$ at low temperatures. At slightly elivated temperatures,we expect a thermally activated relaxation process so that $`Texp(\mathrm{\Delta }/k_BT)`$ type variation is predicted.

4. References

1. S. Das Sarma and A. Pinczuk, eds., Perspectives in quantum Hall effect, Wiley, New York 1997.
2. R. E. Prange and S. M. Girvin, eds., The quantum Hall effect, Springer-Verlag, New York 1987.
3. K. N. Shrivastava, Introduction to quantum Hall effect, Nova Science, New York 2002.(See also cond-mat/0303309).
4. N. F. Mott, J. Non-Cryst. Solids, 1, 1 (1968).
5. K. N. Shrivastava, Phys. Stat. Solidi (b)117,437(1983)
6. D. G. Polyakov and B. I. Shklovskii, Phys. Rev. B 48, 11167 (1993).
7. C. Possanzini, R. Fletcher, P. T. Coleridge, Y. Feng, R. L. Williams and J. C. Maan, Phys. Rev. Lett. 90, 176601(2003).


text:
# Frequency Content and Autocorrelation Function of Noisy Periodic Signals

## 1 Introduction

The computation of the autocorrelation function of a noisy signal usually requires the removal of a deterministic component often called trend or seasonal component. Motivated by the important problem of the statistical analysis of temperature data, we concentrate on the case of noisy periodic signals. For this particular application, we need to carry out the following steps. (i) First, we evaluate the frequencies of the embedded periodic components. (ii) Then, we fully identify the deterministic component by a variational principle restricted to the class of functions consistent with the results of part (i). (iii) Finally, the computation of the autocorrelation function of the residuals completes the analysis of the signal. We discuss the theoretical underpinnings of such a method in the special case of a signal with a single periodic component, and we demonstrate that this program is often spoiled by the subtle consequences of the possible incommensurability of the sampling frequency and the intrinsic frequency of the signal in question. See for example  for a discussion of the sampling theory of continuous signals. This paper quantifies one form of this undesirable effect, and proposes a remedy to the resulting ambiguity in the determination of the intrinsic frequency of a noisy periodic signal.

## 2 Fourier Spectrum

To establish notation, we begin by giving the explicit formula for the Discrete Fourier Transform (DFT for short) $`X_k`$ of a given vector $`x_j`$ of length $`N`$ :

$$X_k=\frac{1}{\sqrt{N}}\underset{j=1}{\overset{N}{}}x_je^{2\pi i\frac{j1}{N}(k1)},k=1,\mathrm{},N.$$
(1)
With this definition of the Fourier transform, it follows that:

$$x_j=\frac{1}{\sqrt{N}}\underset{k=1}{\overset{N}{}}X_ke^{2\pi i\frac{k1}{N}(j1)},$$
(2)
because of the orthogonality property

$$\frac{1}{N}\underset{j=1}{\overset{N}{}}e^{2\pi i\frac{nk}{N}j}=\delta _{nk}.$$
(3)
Here and in the following, $`\delta _{nk}`$ is the Kronecker delta. Let us consider a monochromatic signal:

$$x_j=Ae^{2\pi i\frac{m1}{N}j},j=1,\mathrm{},N,$$
(4)
where $`m`$ is a given positive integer between $`1`$ and $`N`$. For each integer $`1kN`$ we have:

$$X_k=A\sqrt{N}e^{2\pi i\frac{k1}{N}}\delta _{km},$$
(5)
and hence:

$$\left|X_k\right|=\left|A\right|\sqrt{N}\delta _{km}.$$
(6)
In other words, the spectrum results in all coefficients being zero apart from a peak for the value of $`k`$ equal to $`m`$. From the spectrum we can compute the frequency of the periodic signal given the length $`N`$ (i.e., $`\omega =\frac{m1}{N}`$). A difficulty arises when the monochromatic signal is of the form:

$$x_j=Ae^{2\pi i\frac{m1+ϵ}{N}j},j=1,\mathrm{},N,\frac{1}{2}ϵ<\frac{1}{2}.$$
(7)
In this case, the frequency cannot be expressed as a ratio of the form $`(m1)/N`$ and we say that we are facing an *incommensurate* lattice problem. Computing the spectrum, we get:

$$\left|X_k\right|=\left|A\right|\frac{1}{\sqrt{N}}\sqrt{\frac{1\mathrm{cos}2\pi \left(mk+ϵ\right)}{1\mathrm{cos}2\pi \frac{mk+ϵ}{N}}}.$$
(8)
It is now evident that an incommensurate frequency produces a spread of the peak (i.e., $`X_k0`$ for $`km`$). This is illustrated in Figure 1.

It is worth noting that for $`ϵ0`$ and $`N\mathrm{}`$, we obtain

$$\left|X_k\right|\left|A\right|\sqrt{N}\left|\frac{\mathrm{sin}\pi (mk)}{\pi (mk)}\right|\left\{1+\left[\pi \mathrm{cot}\pi (mk)\frac{1}{mk}\right]ϵ\right\}+O(N^{3/2}).$$
(9)
We recognize the zero order term as the Fraunhofer diffraction pattern for the single slit . This should not be surprising as the spread of the Fourier spectrum $`X_k`$ is due to the interaction of two wavelengths; one for the lattice and the other for the signal.

The previous analysis shows that the Fourier spectrum is widened even in the case of a noise free signal. In the case of a noisy signal the detection of the frequency is complicated by the spectrum asymmetries introduced by the noise.

## 3 The Case of Temperature Data

We now analyze the average temperature data for the case of Seattle-Tacoma international Airport from $`1/1/1960`$ to $`12/31/1999`$ (i.e., $`14,610`$ entries). First, we remove the mean value of $`52.20`$ Fahrenheit. Next, we determine the frequency of the embedded periodic signal by use of the Fourier paradigm. For any subset of the data, the Fourier spectrum gives a peak over a noisy background. However, each peak gives different estimates of the period, all inconsistent with the naive idea that the more points the better the estimate of the period. In Figure 2, we show the value of the estimated period $`\mathrm{\Lambda }`$ as a function of $`N`$. The $`\mathrm{\Lambda }`$’s were computed according to the following prescriptions. For each $`N14,610`$ we selected the first $`N`$ points of the data set and computed the period as

$$\mathrm{\Lambda }=\frac{N}{k_{\text{max}}1},$$
(10)
where $`k_{\text{max}}`$ is the index for which the absolute value of the spectrum is maximum. We always chose the integer $`k_{\text{max}}`$ to be in the range below the Nyquist frequency to avoid aliasing artifacts .

The uncertainty is dramatic. Even with as many points as $`7,9208,140`$ (more than $`20`$ times the ‘true’ period corresponding to the tropical year), the period takes values in the range $`360370`$ days. In experimental situations where the value is not foreseeable from the very beginning, such uncertainty would be disastrous for estimating statistical properties such as variance and autocorrelation function. Let us suppose that we are given only the first $`N_1=7,920`$ data points. We would find a peak at $`k_{\text{max}}=23`$, which corresponds to $`\mathrm{\Lambda }_1=360`$. If we had the first $`N_2=8,140`$ data, we would find a period of $`\mathrm{\Lambda }_2=370`$, even with the same $`k_{\text{max}}=23`$. In order to fully identify the deterministic component $`d_j`$ we use the ansatz

$$d_j=\underset{q=1}{\overset{Q}{}}\left[a_q\mathrm{cos}\frac{2\pi q}{\mathrm{\Lambda }}j+b_q\mathrm{sin}\frac{2\pi q}{\mathrm{\Lambda }}j\right],$$
(11)
where $`Q`$ is the number of harmonics used in the estimation. In each case we minimize the least square distance between the signal diminished by its mean and the expression in (11). For $`Q=3`$, we obtain:

|  |  | $`a_1`$ | $`b_1`$ | $`a_2`$ | $`b_2`$ | $`a_3`$ | $`b_3`$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $`\mathrm{\Lambda }_1=360`$ |  | -2.02 | -10.58 | -0.69 | -0.51 | -0.02 | -0.27 |
| $`\mathrm{\Lambda }_2=370`$ |  | -9.54 | 5.22 | 1.18 | -0.18 | 0.07 | 0.17 |

The variances of the residuals are $`\sigma _1^2=49.17`$ and $`\sigma _2^2=47.33`$ for $`\mathrm{\Lambda }_1`$ and $`\mathrm{\Lambda }_2`$. By using the tropical year estimate ($`\mathrm{\Lambda }_{\text{tr}}=365.2422`$), we get $`\sigma _{\text{tr}}^2=26.65`$ for $`N=7,920`$, and $`\sigma _{\text{tr}}^2=26.51`$ for $`N=8,140`$. It is evident that a wrong value of the period gives rise to an overestimated variance of the residuals.

In Figure 3, we show how dramatic the effect on the autocorrelation function is when a wrong period is used. Not only the residuals have an enlarged variance but they also show a spurious persistence. In the case of temperature time series, a large persistence would imply the possibility of forecasting the weather beyond any reasonable range. As discussed above, the determination of the ‘true’ frequency is paramount for an effective analysis of statistical properties of a signal. Here we provide a solution to this problem by analyzing the functional dependence of the peaks appearing in Figure 2. More than providing the solution, we want to stress that any time the DFT is performed on a finite sample data set a figure like Figure 2 should be generated. One should not seek the largest possible data set, but rather study the dependence of the estimated period as a function of the number of points. Our ansatz is that both the max and the min ‘peaks’ of each piecewise linear segment in Figure 2 lie on a curve of the type:

$$\mathrm{\Lambda }_{\text{max,min}}(x)=\frac{Ax}{B+x}.$$
(12)
By least square minimization, we find:

|  | $`A`$ | $`B`$ |
| --- | --- | --- |
| $`\mathrm{\Lambda }_{\text{min}}`$ | 365.70 | 194.26 |
| $`\mathrm{\Lambda }_{\text{max}}`$ | 366.19 | -165.67 |

In both cases the $`R^2`$ is $`1`$ apart from round off errors. This means that the function in (12) is not just a good guess, but rather the ‘true’ decay of the estimated period to its large $`N`$ limit (i.e., $`A`$). The results in the above table show that the estimates are fairly close to the ‘true’ period. Furthermore, the variance and the autocorrelation function are very close to those computed for the tropical year value, $`365.2422`$. To be more specific, the variance for $`N=8,140`$ is $`26.79`$ and $`27.54`$ for $`\mathrm{\Lambda }_{\text{min}}`$ and $`\mathrm{\Lambda }_{\text{max}}`$, respectively. In both cases, the autocorrelation function cannot be distinguished from the one obtained after using $`\mathrm{\Lambda }_{\text{tr}}`$.

It is worth pointing out that equation (8) is of some help for understanding a more fundamental reason for the functional dependence in equation (12). Adding a point to the data set is equivalent to changing the lattice or changing $`ϵ=ϵ(N)`$. The jumps appearing in Figure 2 will occur when $`ϵ`$ exceeds $`\frac{1}{2}`$, which occurs approximately after adding $`\mathrm{\Lambda }`$ points. By locating the minima and maxima in this way, one can obtain an expression for the decay of the form (12).

## 4 Conclusion

In conclusion, we have shown how to compute the autocorrelation function of noisy periodic signals in the case of a single frequency mode. Our scheme improves upon a naive application of the DFT. The main point is that more is not better when it comes to the DFT. The dependence on the number of points for the estimated frequency is more important than the position of the peak for a specific $`N`$. Our solution stems from building envelopes of minima and maxima of piecewise linear functions. This can certainly be improved; however there is no question that another solution has to be found by looking at the results in Figure 2.

Finally, our approach is applicable to signals with more than one frequency mode. This will be the subject of a future work.


text:
# Untitled Document

Supersymmetry, the Cosmological Constant, and a

Theory of Quantum Gravity in Our Universe

T. Banks

Department of Physics and Institute for Particle Physics

University of California, Santa Cruz, CA 95064

and

Department of Physics and Astronomy, NHETC

Rutgers University, Piscataway, NJ 08540

E-mail: banks@scipp.ucsc.edu

ABSTRACT

There are many theories of quantum gravity, depending on asymptotic boundary conditions, and the amount of supersymmetry. The cosmological constant is one of the fundamental parameters that characterize different theories. If it is positive, supersymmetry must be broken. A heuristic calculation shows that a cosmological constant of the observed size predicts superpartners in the TeV range. This mechanism for SUSY breaking also puts important constraints on low energy particle physics models. This essay was submitted to the Gravity Research Foundation Competition and is based on a longer article, which will be submitted in the near future.

Superstring Theory (ST) is our most successful attempt at constructing a quantum theory of gravitation. The advances of the Duality Revolution gave us detailed mathematical evidence for the nonperturbative existence and consistency of the theory. Ironically, they also told us that its name is misleading because it emphasizes particular asymptotic regions of a collection of continuous moduli spaces of theories. A better name would be Supersymmetric Quantum Theories of Gravity (SQUIGITS).

Indeed, the most cogent statement of the results of the Duality Revolution is that the principles of supersymmetry (SUSY) and quantum mechanics imply the existence of these moduli spaces of theories and of certain extended objects in them, whose tension can be calculated exactly. One then sees that in certain limiting regions of moduli space, strings of tension much less than the Planck scale exist, and one is led to expect a perturbative theory of strings. The existing formalism of perturbative superstring theory is a brilliant confirmation of these general arguments. Almost all known perturbative string expansions can be derived from arguments of this sort. The perturbation expansions allow us to calculate many quantities whose value does not follow from SUSY. More remarkably, in many cases, they can be used to obtain a completely nonperturbative formulation of the theory. The latter examples go under the names of Matrix Theory and the AdS/CFT correspondence.

Two points on a connected moduli space of such theories can be considered part of the same system because any physical observable of one can be recovered with arbitrary accuracy in terms of measurements done in the other. But this is no longer true if we try to compare theories on different moduli spaces. We seem to be presented with a plethora of different consistent theories of quantum gravity, all of which are exactly supersymmetric and none of which describe the real world. It behooves us to search for criteria, which would help us to understand how to construct a theory of the world, and to explain why our world is not described by a point on one of these moduli spaces of consistent theories.

An important general principle that emerges1 This principle could have been declared earlier, on the basis of black hole physics. However, only the mathematically rigorous formulation of the SUSic theories, particularly the AdS/CFT correspondence, gives us confidence that it is correct. from our rigorous understanding of supersymmetric theories of quantum gravity is the principle of Asymptotic Darkness: The high energy spectrum of a theory of quantum gravity is dominated by black holes. All scattering amplitudes at sufficiently large values of the kinematic invariants are dominated by black hole production. The famed UV/IR connection follows from this principle2 as does the even more famous Holographic Principle. One can attempt to probe short distances in order to demonstrate the volume extensive density of states we expect from quantum field theory (QFT). The production of black holes prevents us from doing this, and instead presents us with an area extensive spectrum of states. : high energy states take up large regions in space, and have low curvature external gravitational fields. This connection is the key to understanding that isolated vacuum states or theories with different values of the cosmological constant are not connected. The traditional notion of vacuum state in QFT is an infrared notion. Two vacua of the same QFT have identical high energy behavior, but this is false for states with different values of the cosmological constant.

For negative cosmological constant, the evidence for this statement comes from AdS/CFT. In these systems, the value of the cosmological constant in Planck units is determined by an integer $`N`$. $`N`$ determines the number of degrees of freedom of the conformal field theory whose boundary dynamics defines quantum gravity in the bulk of AdS space. For $`5`$ dimensional AdS spaces the relevant theories are conformally invariant supersymmetric gauge theories and $`N`$ is the rank of the gauge group. Large $`N`$ corresponds to small cosmological constant, $`\mathrm{\Lambda }`$. AdS/CFT shows us that the value of $`\mathrm{\Lambda }`$ is a discrete choice that we make in defining the theory, rather than a computable quantity in the low energy effective action. $`\mathrm{\Lambda }`$ determines the density of high energy states of the theory.

For positive $`\mathrm{\Lambda }`$ the evidence is less compelling since we do not yet have a mathematical quantum theory of de Sitter (dS) space. Fischler and the author suggested that the Bekenstein-Gibbons-Hawking entropy of dS space be interpreted as the logarithm of the number of quantum states in the Hilbert space defining quantum dS gravity. Evidently, $`\mathrm{\Lambda }`$ is then a discrete parameter chosen by the theorist, just as it is in the AdS systems. The existence of a maximal size black hole with entropy less than the dS entropy, together with the Bekenstein bound on the entropy of general localized systems by the entropy of black holes, then implies that a finite number of states suffices to describe any conceivable measurement in dS space.

The new role of $`\mathrm{\Lambda }`$ as a fundamental parameter, suggests that we give up the attempt to explain its value by other than anthropic means. Rather, we should attempt to calculate everything else in the theory, as a function of $`\mathrm{\Lambda }`$, in Planck units, and use one experiment to determine that pure number. The opportunity to explain the conundrum of vacuum selection now presents itself. A unitary quantum theory of dS space cannot be SUSic. Thus, the choice of a finite dimensional Hilbert space for the quantum theory, breaks SUSY. The question is by how much. Low energy field theory suggests a gravitino mass that scales like $`\mathrm{\Lambda }^{1/2}`$ in Planck units. I have presented a quantum calculation, which suggests an enhancement to

$$m_{3/2}\mathrm{\Lambda }^{1/4}.$$

The key to the calculation is the fact that the $`\mathrm{\Lambda }0`$ limit of the dS theory is a SUSic, R-symmetric theory . R symmetry violating terms are induced in the low energy effective Lagrangian by the dS background. These then lead to spontaneous violation of SUSY, and a gravitino mass. The leading contribution to these R violating terms comes from Feynman diagrams where a single gravitino line propagates out to the horizon and interacts with the large number of degenerate quantum states that a static observer sees there. The graph is suppressed by $`e^{cm_{3/2}R}`$ from the gravitino propagator, where $`R=\mathrm{\Lambda }^{\frac{1}{2}}`$ is the radius of the horizon. I argued that there was a compensating factor $`e^{\frac{b}{m_{3/2}}}`$ from the interaction with the large set of degenerate states on the horizon. Self consistency then leads to the scaling law $`m_{3/2}\mathrm{\Lambda }^{1/4}`$. If the two exponential terms don’t cancel exactly, leading to power law corrections, then the assumption of a small gravitino mass leads to a very large mass and vice versa. Of course, we really need a complete mathematical theory of the dS horizon to construct a reliable version of this argument.

The phenomenological consequences of the calculation are significant. The consistent SUSY vacua are banished from the theory of the world by the assumption that theory has a finite number of states. The dimension of the dS space is probably fixed to be $`4`$ because this is the only dimension in which Superstring Theory can have a low energy Lagrangian with small deformation that supports a dS solution. The limiting SUSY theory cannot have any moduli. The value of superpartner masses that solves the Standard Model hierarchy problem is predicted in terms of the cosmological constant. There are also more detailed constraints on the possible forms of the low energy supersymmetric Lagrangian.

One problem that remains to be solved is the construction of machinery for finding all possible isolated Super Poincare invariant theories of quantum gravity in four dimensions. A second is the development of a mathematical theory of horizon dynamics, which will provide a firm foundation for the calculation of supersymmetric mass splittings in terms the cosmological constant.

References

relax J. Schwarz, Lectures on Superstring and M-theory Dualities Given at ICTP Spring School and at TASI, Published in Nucl. Phys. Proc. Suppl. 55B,1,(1997), hep-th/9607201. relax T. Banks, W. Fischler, S. Shenker, L. Susskind M-theory as a Matrix Model: A Conjecture,Phys.Rev.D55:5112-5128,1997, hep-th/9610043 relax J. Maldacena, The Large N Limit of Superconformal Field Theories and Supergravity, Adv. Theor. Math. Phys. 2, 231, (1998), Int J. Theor. Phys. 38, (1999); S. Gubser, I. Klebanov, A. Polyakov, Gauge Theory Correlators From Non Critical String Theory  , Phys.Lett.B428:105-114,1998, hep-th/9802109 ;E. Witten, Anti-De Sitter Space and Holography , Adv.Theor.Math.Phys.2:253-291,1998, hep-th/9802150. relax T. Banks, On Isolated Vacua and Background Independence , hep-th/0011255; A Critique of Pure String Theory, Talk Given at Strings 2002, Cambridge, UK, July 2002; A Critique of Pure String Theory: Heterodox Opinions of Diverse Dimensions, manuscript in preparation. relax O. Aharony, T. Banks, Note On the Quantum Mechanics of M-theory, JHEP 9903:016, (1999), hep-th/9812237. relax R. Penrose unpublished 1974; P.D. d’Eath, P.N. Payne,Gravitational Radiation in High Speed Black Hole Collisions, 1,2,3 Phys. Rev. D46, (1992), 658, 675, 694; D. Amati, M. Ciafaloni, G. Veneziano, Classical and Quantum Gravity Effects from Planckian Energy Superstring Collisions, Int. J. Mod. Phys. A3, 1615, (1988), Can Space-Time Be Probed Below the String Size?, Phys. Lett. B216, 41, (1989). H-J. Matschull, Black Hole Creation in ($`2+1`$)-Dimensions, Class. Quant. Grav. 16, 1069, (1999); T. Banks, W. Fischler, A Model for High Energy Scattering in Quantum Gravity, hep-th/9906038; D. Eardley, S. Giddings, Classical Black Hole Production in High-Energy Collisions, Phys. Rev. D66, 044011, 2002, gr-qc/0201034. relax L .Susskind, E. Witten, The Holographic Bound in Anti de Sitter Space, hep-th/9805114. relax W. Fischler, Taking de Sitter Seriously. Talk given at The Role of Scaling Laws in Physics and Biology (Celebrating the 60th Birthday of Geoffrey West), Santa Fe Dec. 2000, and unpublished. relax T. Banks, QuantuMechanics and CosMology, Talk given at the festschrift for L. Susskind, Stanford University, May 2000; Cosmological Breaking of Supersymmetry?, Talk Given at Strings 2000, Ann Arbor, MI, Int. J. Mod. Phys. A16, 910, (2001), hep-th/0007146 relax T. Banks, Breaking SUSY at the Horizon, hep-th/0206117 relax T. Banks, The Phenomenology of Cosmological SUSY Breaking, hep-ph/0203066.


text:
# Integer and fractional packing of families of graphs

## 1 Introduction

All graphs considered here are finite and have no loops, multiple edges or isolated vertices. For the standard terminology used the reader is referred to . Let $``$ be any fixed finite or infinite family of graphs. For a graph $`G`$, the $``$-packing number, denoted $`\nu _{}(G)`$, is the maximum number of pairwise edge-disjoint copies of elements of $``$ in $`G`$. A function $`\psi `$ from the set of copies of elements of $``$ in $`G`$ to $`[0,1]`$ is a fractional $``$-packing of $`G`$ if $`_{eH}\psi (H)1`$ for each $`eE(G)`$. For a fractional $``$-packing $`\psi `$, let $`w(\psi )=_{H\left(\genfrac{}{}{0pt}{}{G}{}\right)}\psi (H)`$. The fractional $``$-packing number, denoted $`\nu _{}^{}(G)`$, is defined to be the maximum value of $`w(\psi )`$ over all fractional packings $`\psi `$. Notice that, trivially, $`\nu _{}^{}(G)\nu _{}(G)`$. If $``$ consists of a single graph $`H_0`$ we shall denote the parameters above by $`\nu _{H_0}(G)`$ and $`\nu _{H_0}^{}(G)`$.

Since computing $`\nu _{}^{}(G)`$ amounts to solving a linear program, it can be computed in polynomial time for every finite $``$. On the other hand, it was proved by Dor and Tarsi in  that computing $`\nu _{H_0}(G)`$ is NP-Hard for every $`H_0`$ with a component having at least three edges. Thus, it is interesting to determine when $`\nu _{}^{}(G)`$ and $`\nu _{}(G)`$ are “close”, thereby getting a polynomial time approximating algorithm for an NP-Hard problem. The following result was proved by Haxell and Rödl in .

###### Theorem 1.1

If $`H_0`$ is a fixed graph and $`G`$ is a graph with $`n`$ vertices, then $`\nu _{H_0}^{}(G)\nu _{H_0}(G)=o(n^2)`$.

The 25 page proof of Theorem 1.1 presented in  is very difficult. The major difficulty lies in the fact that their method requires proving that there is a fractional packing which is only slightly less than optimal, and which assigns to every copy of $`H_0`$ either $`0`$ or a value greater than $`\tau `$ for some $`\tau >0`$ which is only a function of $`H_0`$.

In this paper we present a significantly simpler proof of Theorem 1.1. Our proof method enables us to generalize Theorem 1.1 to the “family” case. There does not seem to be an easy way to generalize the proof in  to the family case.

###### Theorem 1.2

If $``$ is a fixed family of graphs and $`G`$ is a graph with $`n`$ vertices, then $`\nu _{}^{}(G)\nu _{}(G)=o(n^2)`$.

Notice that Theorem 1.2 immediately yields a polynomial time algorithm for approximating $`\nu _{}(G)`$ to within an additive term of $`ϵn^2`$ for every $`ϵ>0`$. Furthermore, if $``$ is finite, the degree of the polynomial depends only on $``$, and not on $`1/ϵ`$. Our proof also supplies a randomized polynomial time algorithm that finds a set of $`\nu _{}(G)o(n^2)`$ edge-disjoint copies of elements of $``$ in $`G`$.

## 2 Tools used in the main result

As in , a central ingredient in our proof of the main result is Szemerédi’s regularity lemma . Let $`G=(V,E)`$ be a graph, and let $`A`$ and $`B`$ be two disjoint subsets of $`V(G)`$. If $`A`$ and $`B`$ are non-empty, let $`E(A,B)`$ denote set of edges between them, and put $`e(A,B)=|E(A,B)|`$. The density of edges between $`A`$ and $`B`$ is defined as

$$d(A,B)=\frac{e(A,B)}{|A||B|}.$$

For $`\gamma >0`$ the pair $`(A,B)`$ is called $`\gamma `$-regular if for every $`XA`$ and $`YB`$ satisfying $`|X|>\gamma |A|`$ and $`|Y|>\gamma |B|`$ we have

$$|d(X,Y)d(A,B)|<\gamma .$$

An equitable partition of a set $`V`$ is a partition of $`V`$ into pairwise disjoint classes $`V_1,\mathrm{},V_m`$ whose sizes are as equal as possible. An equitable partition of the set of vertices $`V`$ of a graph $`G`$ into the classes $`V_1,\mathrm{},V_m`$ is called $`\gamma `$-regular if $`|V_i|<\gamma |V|`$ for every $`i`$ and all but at most $`\gamma \left(\genfrac{}{}{0pt}{}{m}{2}\right)`$ of the pairs $`(V_i,V_j)`$ are $`\gamma `$-regular. The regularity lemma states the following:

###### Lemma 2.1

For every $`\gamma >0`$, there is an integer $`M(\gamma )>0`$ such that for every graph $`G`$ of order $`n>M`$ there is a $`\gamma `$-regular partition of the vertex set of $`G`$ into $`m`$ classes, for some $`1/\gamma <m<M`$.

Let $`H_0`$ be a fixed graph with the vertices $`\{1,\mathrm{},k\}`$, $`k3`$. Let $`W`$ be a $`k`$-partite graph with vertex classes $`V_1,\mathrm{},V_k`$. A subgraph $`J`$ of $`W`$ with ordered vertex set $`v_1,\mathrm{},v_k`$ is partite-isomorphic to $`H_0`$ if $`v_iV_i`$ and the map $`v_ii`$ is an isomorphism from $`J`$ to $`H_0`$.

The following lemma is almost identical to the (2 page) proof of Lemma 15 in  and hence the proof is omitted.

###### Lemma 2.2

Let $`\delta `$ and $`\zeta `$ be positive reals. There exist $`\gamma =\gamma (\delta ,\zeta ,k)`$ and $`T=T(\delta ,\zeta ,k)`$ such that the following holds. Let $`W`$ be a $`k`$-partite graph with vertex classes $`V_1,\mathrm{},V_k`$ and $`|V_i|=t>T`$ for $`i=1,\mathrm{},k`$. Furthermore, for each $`(i,j)E(H_0)`$, $`(V_i,V_j)`$ is a $`\gamma `$-regular pair with density $`d(i,j)\delta `$ and for each $`(i,j)E(H_0)`$, $`E(V_i,V_j)=\mathrm{}`$. Then, there exists a spanning subgraph $`W^{}`$ of $`W`$, consisting of at least $`(1\zeta )|E(W)|`$ edges such that the following holds. For an edge $`eE(W^{})`$, let $`c(e)`$ denote the number of subgraphs of $`W^{}`$ that are partite isomorphic to $`H_0`$ and that contain $`e`$. Then, for all $`eE(W^{})`$, if $`eE(V_i,V_j)`$ then

$$\left|c(e)t^{k2}\frac{_{(s,p)E(H_0)}d(s,p)}{d(i,j)}\right|<\zeta t^{k2}.$$

Finally, we need to state the seminal result of Frankl and Rödl  on near perfect coverings and matchings of uniform hypergraphs. Recall that if $`x,y`$ are two vertices of a hypergraph then $`deg(x)`$ denotes the degree of $`x`$ and $`deg(x,y)`$ denotes the number of edges that contain both $`x`$ and $`y`$ (their co-degree). We use the version of the Frankl and Rödl Theorem due to Pippenger (see, e.g., ).

###### Lemma 2.3

For an integer $`r2`$ and a real $`\beta >0`$ there exists a real $`\mu >0`$ so that: If the $`r`$-uniform hypergraph $`L`$ on $`q`$ vertices has the following properties for some $`d`$:
(i) $`(1\mu )d<deg(x)<(1+\mu )d`$ holds for all vertices,
(ii) $`deg(x,y)<\mu d`$ for all distinct $`x`$ and $`y`$,
then $`L`$ has a matching of size at least $`(q/r)(1\beta )`$.

## 3 Proof of the main result

Let $``$ be a family of graphs, and let $`ϵ>0`$. To avoid the trivial case we assume $`K_2`$. We shall prove there exists $`N=N(,ϵ)`$ such that for all $`n>N`$, if $`G`$ is an $`n`$-vertex graph then $`\nu _{}^{}(G)\nu _{}(G)<ϵn^2`$.

Let $`k_{\mathrm{}}`$ denote the maximal order of a graph in $``$. Let $`k_0=\mathrm{min}\{k_{\mathrm{}},20/ϵ\}`$. Let $`\delta =\beta =ϵ/4`$. For all $`r=2,\mathrm{},k_{0}^{}{}_{}{}^{2}`$, let $`\mu _r=\mu (\beta ,r)`$ be as in Lemma 2.3, and put $`\mu =\mathrm{min}_{r=2}^{k_0^2}\{\mu _r\}`$. Let $`\zeta =\mu \delta ^{k_{0}^{}{}_{}{}^{2}}/2`$. For $`k=3,\mathrm{},k_0`$, let $`\gamma _k=\gamma (\delta ,\zeta ,k)`$ and $`T_k=T(\delta ,\zeta ,k)`$ be as in Lemma 2.2. Let $`\gamma =\mathrm{min}_{k=3}^{k_0}\{\gamma _k\}`$. Let $`M=M(\gamma ϵ/(25k_{0}^{}{}_{}{}^{2}))`$ be as in Lemma 2.1. Finally, we shall define $`N`$ to be a sufficiently large constant, depending on the above chosen parameters, and for which various conditions stated in the proof below hold (it will be obvious in the proof that all these conditions indeed hold for $`N`$ sufficiently large). Thus, indeed, $`N=N(,ϵ)`$.

Fix an $`n`$-vertex graph $`G`$ with $`n>N`$ vertices. Fix a fractional $``$-packing $`\psi `$ with $`w(\psi )=\nu _{}^{}(G)`$. We may assume that $`\psi `$ assigns a value to each labeled copy of an element of $``$ simply by dividing the value of $`\psi `$ on each nonlabeled copy by the size of the automorphism group of that element. If $`\nu _{}^{}(G)<ϵn^2`$ we are done. Hence, we assume $`\nu _{}^{}(G)=\alpha n^2ϵn^2`$.

We apply Lemma 2.1 to $`G`$ and obtain a $`\gamma ^{}`$-regular partition with $`m^{}`$ parts, where $`\gamma ^{}=\gamma ϵ/(25k_{0}^{}{}_{}{}^{2})`$ and $`1/\gamma ^{}<m^{}<M(\gamma ^{})`$. Denote the parts by $`U_1,\mathrm{},U_m^{}`$. Notice that the size of each part is either $`n/m^{}`$ or $`n/m^{}`$. For simplicity we may and will assume that $`n/m^{}`$ is an integer, as this assumption does not affect the asymptotic nature of our result. For the same reason we may and will assume that $`n/(25m^{}k_{0}^{}{}_{}{}^{2}/ϵ)`$ is an integer.

We randomly partition each $`U_i`$ into $`25k_{0}^{}{}_{}{}^{2}/ϵ`$ equal parts of size $`n/(25m^{}k_{0}^{}{}_{}{}^{2}/ϵ)`$ each. All $`m^{}`$ partitions are independent. We now have $`m=25m^{}k_{0}^{}{}_{}{}^{2}/ϵ`$ refined vertex classes, denoted $`V_1,\mathrm{},V_m`$. Suppose $`V_iU_s`$ and $`V_jU_t`$ where $`st`$. We claim that if $`(U_s,U_t)`$ is a $`\gamma ^{}`$-regular pair then $`(V_i,V_j)`$ is a $`\gamma `$-regular pair. Indeed, if $`XV_i`$ and $`YV_j`$ have $`|X|,|Y|>\gamma n/(25m^{}k_{0}^{}{}_{}{}^{2}/ϵ)`$ then $`|X|,|Y|>\gamma ^{}n/m^{}`$ and so $`|d(X,Y)d(U_s,U_t)|<\gamma ^{}`$. Also $`|d(V_i,V_j)d(U_s,U_t)|<\gamma ^{}`$. Thus, $`|d(X,Y)d(V_i,V_j)|<2\gamma ^{}<\gamma `$.

Let $`H`$ be a labeled copy of some $`H_0`$ in $`G`$. If $`H`$ has $`k`$ vertices and $`kk_0`$ then the expected number of pairs of vertices of $`H`$ that belong to the same vertex class in the refined partition is clearly at most $`\left(\genfrac{}{}{0pt}{}{k}{2}\right)ϵ/(25k_{0}^{}{}_{}{}^{2})<ϵ/50`$. Thus, the probability that $`H`$ has two vertices in the same vertex class is also at most $`ϵ/50`$. We call $`H`$ good if it has $`kk_0`$ vertices and its $`k`$ vertices belong to $`k`$ distinct vertex classes of the refined partition. By the definition of $`k_0`$, if $`H`$ has $`k>k_0`$ vertices and $`\psi (H)>0`$ then we must have $`k>20/ϵ`$. Since graphs with $`k`$ vertices have at least $`k/2`$ edges, the contribution of graphs with $`k>k_0`$ vertices to $`\nu _{}^{}(G)`$ is at most $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)/(10/ϵ)<ϵn^2/20`$. Hence, if $`\psi ^{}`$ is the restriction of $`\psi `$ to good copies (the bad copies having $`\psi ^{}(H)=0`$) then the expectation of $`w(\psi ^{})`$ is at least $`(\alpha ϵ/50ϵ/20)n^2`$. We therefore fix a partition $`V_1,\mathrm{},V_m`$ for which $`w(\psi ^{})(\alpha 0.07ϵ)n^2`$.

Let $`G^{}`$ be the spanning subgraph of $`G`$ consisting of the edges with endpoints in distinct vertex classes of the refined partition that form a $`\gamma `$-regular pair with density at least $`\delta `$ (thus, we discard edges inside classes, between non regular pairs, or between sparse pairs). Let $`\psi ^{}`$ be the restriction of $`\psi ^{}`$ to the labeled copies of elements of $``$ in $`G^{}`$. We claim that $`\nu _{}^{}(G^{})w(\psi ^{})>w(\psi ^{})0.72\delta n^2(\alpha 0.07ϵ0.72\delta )n^2=(\alpha \delta )n^2`$. Indeed, by considering the number of discarded edges we get (using $`m^{}>1/\gamma ^{}`$ and $`\delta >>\gamma ^{}`$)

$$w(\psi ^{})w(\psi ^{})|E(G)E(G^{})|<\gamma ^{}\left(\genfrac{}{}{0pt}{}{m^{}}{2}\right)\frac{n^2}{m_{}^{}{}_{}{}^{2}}+\left(\genfrac{}{}{0pt}{}{m^{}}{2}\right)(\delta +\gamma ^{})\frac{n^2}{m_{}^{}{}_{}{}^{2}}+m^{}\left(\genfrac{}{}{0pt}{}{n/m^{}}{2}\right)<0.72\delta n^2.$$

Let $`R`$ denote the $`m`$-vertex graph whose vertices are $`\{1,\mathrm{},m\}`$ and $`(i,j)E(R)`$ if and only if $`(V_i,V_j)`$ is a $`\gamma `$-regular pair with density at least $`\delta `$. We define a (labeled) fractional $``$-packing $`\psi ^{}`$ of $`R`$ as follows. Let $`H`$ be a labeled copy of some $`H_0`$ in $`R`$ and assume that the vertices of $`H`$ are $`\{u_1,\mathrm{},u_k\}`$ where $`u_i`$ plays the role of vertex $`i`$ in $`H_0`$. We define $`\psi ^{}(H)`$ to be the sum of the values of $`\psi ^{}`$ taken over all subgraphs of $`G^{}[V_{u_1},\mathrm{},V_{u_k}]`$ which are partite isomorphic to $`H_0`$, divided by $`n^2/m^2`$. Notice that by normalizing with $`n^2/m^2`$ we guarantee that $`\psi ^{}`$ is a proper fractional $``$-packing of $`R`$ and that $`\nu _{}^{}(R)w(\psi ^{})=m^2w(\psi ^{})/n^2m^2(\alpha \delta )`$.

We use $`\psi ^{}`$ to define a random coloring of the edges of $`G^{}`$. Our “colors” are the labeled copies of elements of $``$ in $`R`$. Let $`d(i,j)`$ denote the density of $`(V_i,V_j)`$ and notice that $`|E_G^{}(V_i,V_j)|=d(i,j)n^2/m^2`$. Let $`H`$ be a labeled copy of some $`H_0`$ in $`R`$, and assume that $`H`$ contains the edge $`(i,j)`$. Each $`eE(V_i,V_j)`$ is chosen to have the “color” $`H`$ with probability $`\psi ^{}(H)/d(i,j)`$. The choices made by distinct edges of $`G^{}`$ are independent. Notice that this random coloring is legal (in the sense that the sum of probabilities is at most one) since the sum of $`\psi ^{}(H)`$ taken over all labeled copies of elements of $``$ containing $`(i,j)`$ is at most $`d(i,j)1`$. Notice also that some edges might stay uncolored in our random coloring of the edges of $`G^{}`$.

Let $`H`$ be a labeled copy of some $`H_0`$ in $`R`$, and assume that $`\psi ^{}(H)>m^{1k_0}`$. Without loss of generality, assume that the vertices of $`H`$ are $`\{1,\mathrm{},k\}`$ where $`iV(H)`$ plays the role of $`iV(H_0)`$. Let $`r`$ denote the number of edges of $`H`$. Notice that $`r<k_0^2`$. Let $`W_H=G^{}[V_1,\mathrm{},V_k]`$ (in fact we only consider edges between pairs that correspond to edges of $`H_0`$). Notice that $`W_H`$ is a subgraph of $`G^{}`$ which satisfies the conditions in Lemma 2.2, since $`t=n/m>Nϵ/(25k_{0}^{}{}_{}{}^{2}M)>T_k`$ (here we assume $`N>25k_{0}^{}{}_{}{}^{2}MT_k/ϵ`$). Let $`W_H^{}`$ be the spanning subgraph of $`W_H`$ whose existence is guaranteed in Lemma 2.2. Let $`X_H`$ denote the spanning subgraph of $`W_H^{}`$ consisting only of the edges whose color is $`H`$. Notice that $`X_H`$ is a random subgraph of $`W_H^{}`$. For an edge $`eE(X_H)`$, let $`C_H(e)`$ denote the set of subgraphs of $`X_H`$ that contain $`e`$ and that are partite isomorphic to $`H_0`$. Put $`c_H(e)=|C_H(e)|`$. A crucial argument is the following:

###### Lemma 3.1

With probability at least $`1m^3/n`$, for all $`eE(X_H)`$,

$$\left|c_H(e)t^{k2}\psi ^{}(H)^{r1}\right|<\mu \psi ^{}(H)^{r1}t^{k2}.$$
(1)
Proof: Let $`C(e)`$ denote the set of subgraphs of $`W_H^{}`$ that contain $`e`$ and that are partite isomorphic to $`H_0`$. Put $`c(e)=|C(e)|`$. According to Lemma 2.2, if $`eE(V_i,V_j)`$ then

$$\left|c(e)t^{k2}\frac{_{(s,p)E(H_0)}d(s,p)}{d(i,j)}\right|<\zeta t^{k2}.$$
(2)
Fix an edge $`eE(X_H)`$ belonging to $`E(V_i,V_j)`$. The probability that an element of $`C(e)`$ also belongs to $`C_H(e)`$ is precisely

$$\rho =\psi ^{}(H)^{r1}\frac{d(i,j)}{_{(s,p)E(H_0)}d(s,p)}.$$

We say that two distinct elements $`Y,ZC(e)`$ are dependent if they share at least one edge other than $`e`$. Consider the dependency graph $`B`$ whose vertex set is $`C(e)`$ and the edges connect dependent pairs. Since two dependent elements share at least three vertices (including the two endpoints of $`e`$), we have that $`\mathrm{\Delta }(B)=O(t^{k3})`$. Hence, $`\chi (B)=O(t^{k3})`$. Put $`s=\chi (B)`$. Let $`C^1(e),\mathrm{},C^s(e)`$ denote a partition of $`C(e)`$ to independent sets. Let $`C_H^q(e)=C^q(e)C_H(e)`$, $`c^q(e)=|C^q(e)|`$ and $`c_H^q(e)=|C_H^q(e)|`$. Clearly, $`c^1(e)+\mathrm{}+c^s(e)=c(e)`$ and $`c_H^1(e)+\mathrm{}+c_H^s(e)=c_H(e)`$. The expectation of $`c_H^q(e)`$ is $`\rho c^q(e)`$. Consider some $`C^q(e)`$ with $`c^q(e)>\sqrt{t}`$. According to a large deviation inequality of Chernoff (cf.  Appendix A), for every $`\eta >0`$, and in particular for $`\eta =\mu /8`$, if $`n`$ (and hence $`t`$ and hence $`c^q(e)`$) is sufficiently large,

$$\mathrm{Pr}[|c_H^q(e)\rho c^q(e)|>\eta \rho c^q(e)]<e^{\frac{2(\eta \rho c^q(e))^2}{c^q(e)}}=e^{2\eta ^2\rho ^2c^q(e)}<<t^{k1}.$$

It follows that with probability at least $`1st^{k1}>1t^3`$, for all $`C^q(e)`$ with $`c^q(e)>\sqrt{t}`$, $`(1\eta )\rho c^q(e)c_H^q(e)(1+\eta )\rho c^q(e)`$ holds. Since the sum of $`c^q(e)`$ having $`c^q(e)\sqrt{t}`$ is $`O(t^{k2.5})`$ and since $`c(e)=\mathrm{\Theta }(t^{k2})`$ we have that this sum is much less than $`\rho \eta c(e)`$. Thus, together with (2) and the fact that $`\rho <\psi ^{}(H)^{r1}\delta ^r`$ we have

$$c_H(e)=\underset{q=1}{\overset{s}{}}c_H^q(e)\rho (1+\eta )(\underset{q=1}{\overset{s}{}}c^q(e))+\rho \eta c(e)=\rho (1+2\eta )c(e)$$
(3)
$$\rho (1+2\eta )t^{k2}(\zeta +\frac{_{(s,p)E(H_0)}d(s,p)}{d(i,j)})=(1+2\eta )t^{k2}(\psi ^{}(H)^{r1}+\zeta \rho )$$

$$t^{k2}\psi ^{}(H)^{r1}(1+2\eta )(1+\zeta \delta ^r)t^{k2}\psi ^{}(H)^{r1}(1+\mu /4)(1+\mu /2)(1+\mu )t^{k2}\psi ^{}(H)^{r1}.$$

Similarly,

$$c_H(e)\rho (1\eta )c(e)\rho \eta c(e)=\rho (12\eta )c(e)$$
(4)
$$\rho (12\eta )t^{k2}(\frac{_{(s,p)E(H_0)}d(s,p)}{d(i,j)}\zeta )=(12\eta )t^{k2}(\psi ^{}(H)^{r1}\zeta \rho )$$

$$t^{k2}\psi ^{}(H)^{r1}(12\eta )(1\zeta \delta ^r)t^{k2}\psi ^{}(H)^{r1}(1\mu /4)(1\mu /2)(1\mu )t^{k2}\psi ^{}(H)^{r1}.$$

Combining (3) and (4) we have that (1) holds for a fixed $`eE(X_H)`$ with probability at least $`1t^3`$. As $`E(X_H)<n^2`$ we have that (1) holds for all $`eE(X_H)`$ with probability at least $`1n^2/t^3=1m^3/n`$.

We also need the following lemma that gives a lower bound for the number of edges of $`X_H`$.

###### Lemma 3.2

With probability at least $`11/n`$,

$$|E(X_H)|>(12\zeta )r\frac{n^2}{m^2}\psi ^{}(H).$$

Proof: We use the notations from Lemma 3.1 and the paragraph preceding it. For $`(i,j)E(H_0)`$, the expected number of edges of $`E(V_i,V_j)`$ that received the color $`H`$ is precisely $`d(i,j)\frac{n^2}{m^2}\frac{\psi ^{}(H)}{d(i,j)}=\frac{n^2}{m^2}\psi ^{}(H)`$. Summing over all $`r`$ edges of $`H_0`$, the expected number of edges of $`W_H`$ that received the color $`H`$ is precisely $`r\frac{n^2}{m^2}\psi ^{}(H)`$. As at most $`\zeta |E(W_H)|`$ edges belong to $`W_H`$ and do not belong to $`W_H^{}`$ we have that the expectation of $`|E(X_H)|`$ is at least $`(1\zeta )r\frac{n^2}{m^2}\psi ^{}(H)`$. As $`\zeta `$, $`r`$, $`m`$ are constants and as $`\psi ^{}(H)`$ is bounded from below by the constant $`m^{1k_0}`$, we have, by the common large deviation inequality of Chernoff (cf.  Appendix A), that for $`n>N`$ sufficiently large, the probability that $`|E(X_H)|`$ deviates from its mean by more than $`\zeta r\frac{n^2}{m^2}\psi ^{}(H)`$ is exponentially small in $`n`$. In particular, the lemma follows.

Since $`R`$ contains at most $`O(m^{k_0})`$ labeled copies of elements of $``$ with at most $`k_0`$ vertices, we have that with probability at least $`1m^{k_0}/nm^{k_0+3}/n>0`$ (here we assume again that $`N`$ is sufficiently large) all labeled copies $`H`$ of elements of $``$ in $`R`$ with $`\psi ^{}(H)>m^{1k_0}`$ satisfy the statements of Lemma 3.1 and Lemma 3.2. We therefore fix a coloring for which Lemma 3.1 and Lemma 3.2 hold for all labeled copies $`H`$ of elements of $``$ in $`R`$ having $`\psi ^{}(H)>m^{1k_0}`$.

Let $`H`$ be a labeled copy of some $`H_0`$ in $`R`$ with $`\psi ^{}(H)>m^{1k_0}`$, and let $`r`$ denote the number of edges of $`H`$. We construct an $`r`$-uniform hypergraph $`L_H`$ as follows. The vertices of $`L_H`$ are the edges of the corresponding $`X_H`$ from Lemma 3.1. The edges of $`L_H`$ correspond to the edge sets of the subgraphs of $`X_H`$ that are partite isomorphic to $`H_0`$. We claim that our hypergraph satisfies the conditions of Lemma 2.3. Indeed, let $`q`$ denote he number of vertices of $`L_H`$. Notice that Lemma 3.2 provides a lower bound for $`q`$. Let $`d=t^{k2}\psi ^{}(H)^{r1}`$. Notice that by Lemma 3.1 all vertices of $`L_H`$ have their degrees between $`(1\mu )d`$ and $`(1+\mu )d`$. Also notice that the co-degree of any two vertices of $`L_H`$ is at most $`t^{k3}`$ as two edges cannot belong, together, to more than $`t^{k3}`$ subgraphs of $`X_H`$ that are partite isomorphic to $`H_0`$. In particular, for $`N`$ sufficiently large, $`\mu d>t^{k3}`$. By Lemma 2.3 we have at least $`(q/r)(1\beta )`$ edge-disjoint copies of $`H_0`$ in $`X_H`$. In particular, we have at least

$$(1\beta )(12\zeta )\frac{n^2}{m^2}\psi ^{}(H)>(12\beta )\psi ^{}(H)\frac{n^2}{m^2}$$

such copies. Recall that $`w(\psi ^{})m^2(\alpha \delta )`$. Since there are at most $`O(m^{k_0})`$ labeled copies $`H`$ of elements of $``$ in $`R`$ with $`0<\psi ^{}(H)m^{1k_0}`$, their total contribution to $`w(\psi ^{})`$ is at most $`O(m)`$. Hence, summing the last inequality over all $`H`$ with $`\psi ^{}(H)>m^{1k_0}`$ we have at least

$$(12\beta )m^2(\alpha \delta O(\frac{1}{m}))\frac{n^2}{m^2}>n^2(\alpha ϵ)$$

edge disjoint copies of elements of $``$ in $`G`$. It follows that $`\nu _{}(G)n^2(\alpha ϵ)`$. As $`\nu _{}^{}(G)=\alpha n^2`$, Theorem 1.2 follows.

The proof of Theorem 1.2 implies an $`O(n^{poly(k_0)})`$ time algorithm that produces a set of $`n^2(\alpha ϵ)`$ edge-disjoint copies of elements of $``$ in $`G`$ with probability at least, say, $`0.99`$. Indeed, Lemma 2.1 can be implemented in $`o(n^3)`$ time using the algorithm of Alon et. al. . Lemma 2.3 has a polynomial running time implementation due to Grable . Since we only need to compute $`\psi ^{}`$, rather than $`\psi `$, we can do this in $`O(n^{poly(k_0)})`$ time using any polynomial time algorithm for LP. The other ingredients of the proof are easily implemented in polynomial time.