text:
# Theory of measuring the “Luttinger-g” of a one-dimensional quantum dot

One dimensional (1D) electron systems are important paradigms for studying the effects of impurities and interactions in condensed matter. Here, electron-electron interaction can be treated by the bosonization technique using the Tomonaga-Luttinger liquid (TLL) model. The energetically lowest excitations are collective charge- and spin-density waves . Correlation functions can be exactly obtained. As a function of temperature, frequency and/or bias voltage, non-analytic power laws of the form $`C(\tau )\tau ^{\nu (g)}`$ have been predicted, where $`\nu (g)`$ is a non-rational exponent that contains the interaction parameter $`g`$. Since TLL appears to be of fundamental importance in modern condensed matter physics, experimentally confirming such behavior is very important.

The search for “Tomonaga-Luttinger behavior” has been very intense during recent years. In tunable semiconductor quantum wires contacted to nearly adiabatic funnels  conductance quantization was found to be weakly affected by electron correlations. It was argued that in these systems the conductance of the leads (assumed as Fermi liquids) is measured . Non-universal conductance quantization was detected in semiconductor cleaved-edge-overgrowth (CEO) quantum wires . This was assigned to electron backscattering in the contacts . Theoretical approaches considered contacts and impurity scattering . In recent CEO-experiments, a 1D quantum dot was fabricated between two impurities . The dependence on temperature $`T`$ of Coulomb blockade peaks was cleanly analyzed within the TLL model . Most strikingly, interaction parameters deduced from different measured quantities were found to be inconsistent: from the charging energy $`E_\mathrm{c}`$, $`g`$ was estimated to be a factor of two smaller than the value obtained from the temperature dependence of the conductance peaks. Similar inconsistencies were observed in the temperature behavior of the conductance of a carbon nanotube (CN) SET-transistor formed between two buckles .

In this paper, we consider a 1D quantum dot in a TLL with an inhomogeneity induced either by a non-uniform interaction parameter or by the presence of contacts modeled by tunnel resistances. First, in view of the CEO-system, we determine the conductance for $`g(x)`$ interpolating smoothly between $`g_{\mathrm{}}=g(|x|\mathrm{})`$ and $`g_\mathrm{b}=g(x_\mathrm{b})`$ in the dot. We find that the interaction in different regions of the system can be probed. While $`E_\mathrm{c}`$ and the level spacing $`\epsilon `$ in the dot are determined by the interaction near $`x_\mathrm{b}`$, the temperature behavior of the conductance peaks show crossovers between $`g_{\mathrm{}}`$ (low $`T`$) and $`g_\mathrm{b}`$ (high $`T`$). Second, we determine the conductance of a quantum dot embedded in a TLL with $`g=\mathrm{const}`$ but attached to metallic contacts. This is appropriate for CNs. We show that the temperature behavior of the Coulomb peaks can be entirely determined by the non-analytic powers laws induced by the contacts though the Coulomb blockade peaks remain perfectly intact. Quite generally, the crossovers can be traced back to the competing energy scales associated with the quantum dot and the inhomogeneity. Our results not only put earlier theoretical findings into a general frame but also explain quantitatively the — at the first sight — discrepant findings in the recent experiments which seems to us of outstanding importance after the intense search for TLL-behavior during more than three decades.

We consider the Hamiltonian $`H=H_0+H_\mathrm{b}`$ with

$$H_0=\frac{\mathrm{}v_\mathrm{F}}{2}dx\left\{\mathrm{\Pi }^2(x)+\frac{1}{g^2(x)}[_x\vartheta (x)]^2\right\}$$
(1)
describing the clean TLL-system with the conjugate Boson fields $`[\mathrm{\Pi }(x),\vartheta (x^{})]=i\delta (xx^{})`$ and a local inhomogeneous density-density interaction

$$\frac{1}{g^2(x)}=\frac{1}{g_{\mathrm{}}^2}+\frac{\phi (x)}{\pi \mathrm{}v_\mathrm{F}}.$$
(2)
We assume $`\phi `$ as smooth, with a maximum of width $`L^{}a`$ near the impurities, and $`\phi (x)0`$ when $`|x|\mathrm{}`$.

The contribution of the impurities located at $`x_\mathrm{b}^\pm =x_\mathrm{b}\pm a/2`$ is $`H_\mathrm{b}=U_\mathrm{b}\mathrm{cos}(\pi N_+)\mathrm{cos}[\pi (n_0+N_{})]`$ where $`N_\pm =[\vartheta (x_\mathrm{b}^+)\pm \vartheta (x_\mathrm{b}^{})]/\sqrt{\pi }`$. The quantity $`N_+`$ and $`N_{}`$ are associated with the unbalanced particles between left and right leads, and the fluctuations of the particle number in the dot with respect to the mean value $`n_0=k_\mathrm{F}a/\pi `$, respectively ($`k_\mathrm{F}`$ Fermi wave number). The charge modes of the inhomogeneous TLL act on $`N_\pm `$ as an external Bosonic bath. Their influence can be exactly evaluated in terms of a dissipative impedance . For $`L^{}>a`$, such that near the quantum dot $`g(x)g_\mathrm{b}`$, the resulting Euclidean effective action is

$$S_{\mathrm{eff}}[N_+,N_{}]=\frac{k_\mathrm{B}T}{2}\underset{r=\pm ,n}{}N_r(\omega _n)K_r(\omega _n)N_r(\omega _n).$$
(3)
The Fourier transforms of the dissipative kernels $`K_r`$, at Matsubara frequencies $`\mathrm{}\omega _n=2k_\mathrm{B}T\pi n`$, are

$$K_\pm (\omega _n)=\frac{\pi }{2}\left[𝒢(\omega _n;x_\mathrm{b},x_\mathrm{b})\pm 𝒢(\omega _n;x_\mathrm{b}^+,x_\mathrm{b}^{})\right]^1.$$
(4)
The zero-frequency limit of $`K_{}`$ gives the charging energy, $`E_\mathrm{c}=\mathrm{}K_{}(\omega _n0)/2`$. The dissipative effects of the collective modes are described by the spectral density

$$J_{\mathrm{tot}}(\omega )=\frac{1}{\pi }\mathrm{Im}[K_{}(\omega _n+i\omega )+K_+(\omega _n+i\omega )].$$
(5)
These quantities depend on the time ordered propagator $`𝒢(\tau ;x,x^{})𝐓_\tau \vartheta (x,\tau )\vartheta (x^{},0)`$ defined with respect to $`H_0`$ via the resolvent equation

$$\left[\frac{\omega _n^2}{v_\mathrm{F}}\frac{}{x}\frac{v_\mathrm{F}}{g^2(x)}\frac{}{x}\right]𝒢(\omega _n;x,x^{})=\delta (xx^{}).$$
(6)
We solve (6) linearly in $`\phi (x)`$ ($`x>x^{}`$, $`\omega _n>0`$),

$`𝒢(\omega _n;x,x^{})`$ $`=`$ $`{\displaystyle \frac{g_{\mathrm{}}}{2\omega _n}}\{e^{\eta |xx^{}|}C[e^{\eta (x+x^{})}\times .`$ (9)
$`\times {\displaystyle _{\mathrm{}}^x^{}}\mathrm{d}y\phi (y)e^{2\eta y}.+e^{\eta (x+x^{})}{\displaystyle _x^{\mathrm{}}}\mathrm{d}y\phi (y)e^{2\eta y}`$
$`..e^{\eta (xx^{})}{\displaystyle _x^{}^x}\mathrm{d}y\phi (y)]\}`$
with the constants $`\eta =g_{\mathrm{}}\omega _n/v_\mathrm{F}`$ and $`C=g_{\mathrm{}}^3\omega _n/2\pi \mathrm{}v_\mathrm{F}^2`$.

Without impurities, one obtains from the above Green function the linear dc-conductance $`G_0=2e^2\omega _n𝒢(\omega _n0)/h=g_{\mathrm{}}e^2/h`$, consistent with earlier work , and indicating that the linear conductance is a global probe. For the quantum dot, the results are more complex. On the one hand, by expanding (4) and (9) consistently to the order $`a/L^{}1`$, the charging energy turns out to be $`E_\mathrm{c}=\pi \mathrm{}v_\mathrm{F}/2ag_\mathrm{b}^2`$. It is determined by the interaction at the position of the quantum dot and is a local probe. On the other hand, the spectral density (5) can be decomposed in two parts that describe the influences of the leads, and of the energy discretization in the dot, $`J_{\mathrm{tot}}(\omega )=J_\mathrm{l}(\omega )+J_\mathrm{d}(\omega )=J(\omega )[1+\epsilon _{n=1}^{\mathrm{}}\delta (\mathrm{}\omega n\epsilon )]`$, where $`J(\omega )=\mathrm{Im}[𝒢^1(i\omega ;x_\mathrm{b},x_\mathrm{b})]/2`$ and $`\epsilon 2g_\mathrm{b}E_\mathrm{c}`$ the discretization energy of the plasmon modes in the quantum dot. The function $`J(\omega )`$ is shown in Fig. 1 for $`\phi (x)=\mathrm{exp}[(2x/L^{})^2]`$; $`[1+(2x/L^{})^2]^1`$; and $`[1+\mathrm{cos}(\pi x/L^{})]/2`$, $`|x|<L^{}`$. There is a crossover between low- and high-frequency behavior, independently of the particular interaction, namely $`J(\omega \omega ^{})=\omega /g_{\mathrm{}}`$ and $`J(\omega \omega ^{})=\omega /g_\mathrm{b}`$, where $`\omega ^{}=v_\mathrm{F}/g_{\mathrm{}}L^{}`$ is the crossover frequency corresponding to the characteristic length scale of the inhomogeneity.

The conductance $`G_\mathrm{d}`$ in the region of the Coulomb blockade is calculated by using sequential tunneling through high barriers in the presence of an external gate voltage $`V_\mathrm{g}`$ . The latter defines the reference particle number in the dot. We consider $`k_\mathrm{B}T\epsilon `$. The dependence on the gate energy $`\mu =e(V_\mathrm{g}V_\mathrm{g}^{\mathrm{res}})`$, that measures the shift with respect to the resonance value $`eV_\mathrm{g}^{\mathrm{res}}=E_\mathrm{c}[2(nn_0)+1]`$, and the temperature is

$$G_\mathrm{d}=\frac{e^2e^{\mu /2k_\mathrm{B}T}}{4k_\mathrm{B}T\mathrm{cosh}(\mu /2k_\mathrm{B}T)}w_0(\epsilon ,T)\gamma (\mu ,T).$$
(10)
Here $`\gamma (\mu ,T)=(\mathrm{\Delta }^2/4)dt\mathrm{exp}[i\mu t/\mathrm{}W_\mathrm{l}(t)]`$ is a tunneling rate through a single impurity with tunneling frequency $`\mathrm{\Delta }`$. The temperature and time dependent dissipative kernel $`W_\mathrm{l}(t)`$ is given as an integral that contains the above spectral density $`J(\omega )`$, with a frequency cutoff $`\omega _\mathrm{c}`$. The weight $`w_0(\epsilon ,T)=(\epsilon /h)_0^{h/\epsilon }dt\mathrm{exp}[W_\mathrm{d}(t)]`$ is the time average of the periodic kernel of the dot $`W_\mathrm{d}(t)`$ . Higher components that exhibit the excitation spectra do not contribute in the linear regime since $`k_\mathrm{B}T<\epsilon `$. Below we present numerical results obtained for the Lorentzian inhomogeneity (Fig. 1).

The conductance for a single Coulomb blockade peak as a function of temperature and gate energy is shown in Fig. 2 for $`g_{\mathrm{}}=0.6`$ and $`g_\mathrm{b}=0.3`$. Independently of the inhomogeneity, the width $`w`$ of the peak increases linearly with temperature. This implies that even in the inhomogeneous case the area $`A`$ under the peak and the peak height are connected by $`ATG_\mathrm{d}^{\mathrm{max}}`$. The maximum of the peak has a non-monotonous behavior in temperature with a minimum around the crossover that corresponds to the saddle in the 3D plot. The temperature dependence of the maximum can be written as $`G_\mathrm{d}^{\mathrm{max}}(T)T^{1/\stackrel{~}{g}(T)2}`$ where $`\stackrel{~}{g}(T)`$ shows a crossover between $`\stackrel{~}{g}(TT^{})=g_{\mathrm{}}`$ and $`\stackrel{~}{g}(TT^{})=g_\mathrm{b}`$ with $`k_\mathrm{B}T^{}=\mathrm{}\omega ^{}`$. The non-monotonous behavior of the conductance is due to the particular choice of the interaction parameters $`g_\mathrm{b}<1/2<g_{\mathrm{}}`$. If both are larger or smaller than the critical value $`1/2`$ the conductance decreases or increases monotonously with temperature, respectively. However, independently of the details near the crossover, the high- and low-temperature behaviors of the peaks are always dominated by the local and global properties of the interaction represented by $`g_\mathrm{b}`$ and $`g_{\mathrm{}}`$, respectively. This means that a measurement of the linear conductance of the 1D quantum dot at low temperatures reflects the interaction far away from the barrier, and therefore is a global probe. On the other hand, when measuring the Coulomb peak at higher temperatures, $`T^{}<T`$, the interaction close to the dot will dominate. In this region, the experiment is a local probe for the interaction.

That contacts may become crucial when interpreting experimental data can also be seen by considering a TLL model with homogeneous interaction, $`g(x)=g`$, but its ends connected to a normal metallic lead via point like tunnel contacts. The temperature dependence of the contact conductance is

$$G_\mathrm{c}(T)=\frac{1}{R_\mathrm{c}}\left(\frac{k_\mathrm{B}T}{\epsilon }\right)^\alpha ,\alpha =g^11$$
(11)
with the prefactor $`R_\mathrm{c}^1`$ containing the tunneling resistance between the lead and the TLL. For later comparison with the dot conductance we have chosen the discretization energy $`\epsilon `$ as the energy scale, including in $`R_\mathrm{c}`$ the rescaling between $`\omega _\mathrm{c}`$ and $`\epsilon `$. If a quantum dot is embedded into the TLL with complete momentum randomization in the contacts, the total resistance can be obtained by adding the resistances of the contacts (11), and that of the quantum dot (10) with $`g=\mathrm{const}`$: $`G^1(T)R(T)=G_\mathrm{c}^1(T)+G_\mathrm{d}^1(T)`$. This can still yield Coulomb blockade oscillations (Fig. 3) but with a crossover in the temperature behavior. Near the maximum of a Coulomb peak the dot conductance scales as

$$G_\mathrm{d}^{\mathrm{max}}(T)=\frac{1}{R_\mathrm{d}}\left(\frac{k_\mathrm{B}T}{\epsilon }\right)^{\alpha 1}.$$
(12)
In this region, the $`G(T)`$ will be determined by $`G_\mathrm{c}(T)`$ for temperatures lower than a crossover value that depends on the ratio $`R_\mathrm{c}/R_\mathrm{d}`$. On the other hand, in the tails of the peak, the $`G_\mathrm{d}(T)`$ always dominates, since there in any case $`G_\mathrm{d}(T)G_\mathrm{c}(T)`$. The peak height $`G^{\mathrm{max}}(T)`$ shows a crossover between global (small $`T`$) and local (large $`T`$) power laws. For $`\alpha <1`$, it has a maximum near the crossover temperature is $`T^{}=2R_\mathrm{c}\epsilon /R_\mathrm{d}k_\mathrm{B}`$. For $`R_\mathrm{c}=0`$ (no contact) only the power law behavior of the dot is obtained (black curve in Fig. 3).

The above results suggest that inhomogeneities cannot be neglected when deducing the interaction parameter in experimental data, especially in the presence of backscattering impurities. In  the charging energy of a 1D dot embedded in a CEO-quantum wire has been determined from the distance between Coulomb peaks, $`E_\mathrm{c}=2.2`$meV with an estimate of $`a100\mathrm{}200`$nm. It has been found that $`g_\mathrm{b}0.4`$ . Measuring the temperature dependence of two conductance peaks in the range $`T0.2\mathrm{}2`$K, a value $`g_{\mathrm{exp}}0.8`$ has been estimated (without spin) . Taking into account the spin reduces the latter value slightly to $`0.7`$ but does not solve the inconsistency. Given the good fit of the experimental data for $`T<2`$K to the power law with a single value for $`g_{\mathrm{exp}}>g_\mathrm{b}`$ we conclude $`g_{\mathrm{exp}}g_{\mathrm{}}`$, and that $`T^{}`$ should be larger than $`2`$K. By inspection of Fig. 2 we estimate $`T^{}10`$K. This value certainly depends on the shape of the inhomogeneity, but should be of the correct order. With $`v_\mathrm{F}10^5`$m/s we find $`L^{}100`$nm. This is not larger than the estimated length of the 1D quantum dot. But in view of the above idealized model assumptions, we can conclude that the temperature dependence of the conductance peaks are described by $`g_{\mathrm{}}`$, and not by $`g_\mathrm{b}`$. Our result could be further experimentally addressed by changing the parameters of the CEO-quantum wires, which should influence especially $`L^{}`$.

The influence of the contacts must also be present in the temperature behavior of the Coulomb blockade peaks of a quantum dot created by two buckles in a CN. In the absence of the dot a CN with ends attached to Au-wires shows the contact conductance $`G_\mathrm{c}(T)`$ of (11) with $`\alpha =(g_{\mathrm{nano}}^11)/4`$ and $`g_{\mathrm{nano}}0.28`$ . The different relation between $`\alpha `$ and $`g_{\mathrm{nano}}`$ from the one given in (11) is due to the presence of further three non-interacting modes. In the presence of the dot, with the experimental value $`\alpha =0.68`$ (corresponding to $`g_{\mathrm{nano}}=0.27`$ ) we obtain from (12) that $`G_\mathrm{d}^{\mathrm{max}}(T)`$ increases with decreasing $`T`$ (black curve in Fig. 3). On the other hand, the maximum $`G^{\mathrm{max}}`$ of the total conductance including the contacts decreases with decreasing $`T`$ according to the power law of the contact conductance for $`T<T^{}`$ and for a suitable ratio $`R_\mathrm{c}/R_\mathrm{d}`$. This is consistent with the experimental data and explains the discrepant behavior between the observed $`G_{\mathrm{max}}(T)`$ and the dot conductance in the sequential tunneling regime .

In conclusion, we have investigated transport in a 1D quantum dot embedded in a TLL with an inhomogeneity either due to non-uniform interaction or to the presence of contacts. We have identified quantities that measure the interaction locally and globally. We predict a crossover in the temperature behavior of Coulomb blockade peaks between regions that probe the interaction far away from and close to the dot for $`TT^{}`$, and $`TT^{}`$, respectively, though the Coulomb blockade remains intact. For the non-homogeneous interaction, the crossover is determined by the characteristic length of the region where $`g(x)\mathrm{const}g(x_\mathrm{b})`$. When assuming a homogeneous interaction strength, the crossover is determined by the ratio between contact and dot resistances. Quite generally, the behavior can be understood by considering the energy scales set by the quantum dot and the inhomogeneity: if $`E_\mathrm{c}k_\mathrm{B}T^{}`$ one may fulfill the condition $`k_\mathrm{B}TE_\mathrm{c}`$ necessary for getting Coulomb blockade and nevertheless observe a crossover from global to local behavior in the non-analytic power law dependence of the conductance peaks which is governed by the energy scale of the inhomogeneity. The results are used to understand consistently and quantitatively recent, fundamentally important experiments done on semiconductor CEO-quantum wires and CNs.

We acknowledge discussions with M. Grifoni, F. Napoli and J. Stockburger, and support by the EU within TMR (FMRX-CT98-0180), RTN (HPRN-CT2000-00144), italian MURST via PRIN00, and the DFG via SFB 508 “Quantenmaterialien” of the Universität Hamburg.


format: text

text:
# A photometric monitoring of bright high-amplitude 𝛿 Scuti stars

## 1 Introduction

High-amplitude $`\delta `$ Scuti stars (hereafter HADS) form an interesting subgroup of short-period pulsators located inside the classical instability strip near the main-sequence. Their light variation is characterized by relatively large amplitudes (a conventional limit is $`A_\mathrm{V}0\stackrel{m}{.}30`$) which is associated with one or two stable frequencies. The variability of these stars has been interpreted as caused by radial pulsation in fundamental or low-order radial overtone pulsation (Rodríguez et al. 1996, Petersen & Christensen-Dalsgaard 1996), although some empirical evidence is present for microvariability due to weakly excited high-order radial or non-radial modes of pulsation (Garrido & Rodríguez 1996). It also appears that they exhibit a period-luminosity relation which has been studied by several authors (e.g. McNamara 1997, Petersen & Høg 1998). Previous studies based on bright field stars have recently been supplemented by analyses of tens of objects discovered by the MACHO and OGLE projects (Alcock et al. 2000, Poretti 2001).

Breger & Pamyatnykh (1998) tried to infer evolutionary conclusions from long-term observational records of selected HADS. Although they found evidence of period changes in a significant fraction of HADS, it was not possible to relate them to stellar evolution. The detected period changing behaviours range from continuous period decrease to continuous period increase, and period jumps might also be present in several stars. Furthermore, cyclic period variations due to possible binary light-time effect were inferred in a few cases (see references in Breger & Pamyatnykh 1998). However, despite the large amplitudes, short periods and moderate brightnesses of the stars studied, many of them need period updates as the latest observations in the literature were obtained almost two decades ago. That is why we started a photometric monitoring of bright northern HADS. Our target stars include all HADS brigther than $`V11^\mathrm{m}`$ situated in favourable positions in the northern sky (our sample is partially overlapping with that of Breger & Pamyatnikh). The observations started in 1995 (Kiss & Szatmáry 1995), and since then we have obtained unfiltered (one star), Johnson (eight stars) and Strömgren (one star) photometric observations for ten stars in order to get an updated view of their period changes (some early results have already been published in Kiss & Szatmáry 1995 and Kiss & Derekas 2000). Here we report on results for V567 Ophiuchi, which is the only one that clearly shows double-mode pulsation. The period changes of the remaining stars will be discussed in a companion paper.

The light variations of V567 Oph (=BD+13547, $`V11\stackrel{m}{.}2`$, $`A_\mathrm{V}=0\stackrel{m}{.}34`$, $`P=0.1495`$ d, spectral type A6–F1, Powell et al. 1990) were discovered by Hoffmeister (1943) giving a period ($`1/8`$ d) that was an alias of the true one ($`1/7`$ d). De Bruyn (1972) was the first who determined the period accurately. The observational record until 1990 is quite numerous and has been summarized in Powell et al. (1990). These authors carried out a detailed photometric and spectroscopic study of V567 Oph, which was based on Strömgren photometry and medium-resolution optical spectroscopy. Besides determining the fundamental physical parameters of the star, Powell et al. (1990) suspected the existence of a secondary period, although they could not draw a firm conclusion on it. In the same year, Poretti et al. (1990) presented Fourier decomposition of three HADS. The true period of 0.149 d was established for V567 Oph and they concluded that it was monoperiodic. This conclusion was based on four nights of observations distributed in two separate years (1984 and 1986). Rodríguez et al. (1996) studied the phase shifts and amplitude ratios for a large set of stars, including V567 Oph. The radial nature of its pulsation was deduced. Hintz & Joner (1997) and McNamara (1997), adopting the suggestion by Powell et al. (1990), mentioned the star in their studies as double-mode variable. Contrary to this, Petersen & Høg (1998) listed V567 Oph as oscillating in fundamental mode only. Musazzi et al. (1998) went farther, as they refused the secondary periodicity of the star. It was claimed that the stability of the light curve found by Poretti et al. (1990) clearly proves the monoperiodic nature. The final argument so far was presented by Schwendiman & Hintz (1999), who gave information on the existence of a second period of V567 Oph. Unfortunately, in their poster abstract they did not go into any further details (neither the period value nor its amplitude was specified).

Other studies dealing at least partly with V567 Oph include Kinman (1998), who presented an analysis of local space densities of HADS. He noted that for four stars (DY Her, V567 Oph, ZZ Mic and EH Lib) it is likely that they are old disk members instead of belonging to the young galactic disk or the halo, as other HADS do. Balona & Evers (1999) discussed the mode identification of well-observed $`\delta `$ Scuti stars with the use of multicolour photometry. The applied procedure failed to infer plausible mode identification in three HADS (DY Her, RS Gru, V567 Oph). The single frequency in each case was identified with an $`l=1`$ g-mode. Balona & Evers (1999) concluded that the most likely explanation of their result is that these stars are evolved radially-pulsating stars outside the range of the models applied. Although the models show unstable g-modes for main-sequence stars, these are unlikely to attain the high amplitudes which are observed.

In this paper, we present new Johnson $`V`$ photometry of V567 Oph which revealed the secondary period unambiguously. The observations are described in Sect. 2, while the period analysis is discussed in Sect. 3. An interpretation and possible implications are given in Sect. 4.

## 2 Observations

Single-filtered Johnson $`V`$ observations were carried out at Szeged Observatory on 15 nights during 2001 and 2002. We used the 0.4m Cassegrain-telescope equipped with an ST–9E CCD camera (512$`\times `$512 pixels). In order to attain better time resolution we used the CCD in 2$`\times `$2 binned mode thus giving an angular resolution of 1.4′′/pixel (the field of view is 6$`{}_{}{}^{}\times 6^{}`$). The exposure time was between 20 and 40 seconds depending on the weather conditions and the frames were obtained almost uninterruptedly enabling a very good light curve coverage during every cycle. The full log of observations is given in Table 1.

The data were reduced with standard tasks in IRAF111IRAF is distributed by the National Optical Astronomy Observatories, which are operated by the Association of Universities for Research in Astronomy, Inc., under cooperative agreement with the National Science Foundation.. The flat-field correction utilized sky-flat images taken during the evening or morning twillight. Differential magnitudes222Corresponding data files can be found at CDS via anonymous ftp to cdsarc.u-strasbg.fr (130.79.128.5) or via http://cdsweb.u-strasbg.fr/cgi-bin/qcat?J/A+A/.../... were calculated with aperture photometry using two comparison stars of similar brightnesses ($`C_1`$ and $`C_4`$ in Powell et al 1990, who gave the following magnitudes: $`C_1`$$`y_{\mathrm{mag}}=11\stackrel{m}{.}261`$, $`by=0\stackrel{m}{.}489`$; $`C_4`$$`y_{\mathrm{mag}}=11\stackrel{m}{.}412`$, $`by=0\stackrel{m}{.}431`$). Since V567 Oph has very similar colour to the applied comparisons (Table 5 in Powell et al. gives a $`by=0\stackrel{m}{.}44`$), the standard transformations are negligible corrections, therefore, the use of only one filter is not expected to introduce large systematic differences.

The estimated photometric accuracy varied between $`\pm 0\stackrel{m}{.}007`$ and $`\pm 0\stackrel{m}{.}020`$ as judged from the rms scatter of the comparison minus check data. Although we have tried to reduce the data as careful as possible, some instrumental drifts of order of a few millimags cannot be excluded. Due to the small field of view, the variable and comparison stars were located at the edge of the frames which may introduces some additional photometric uncertainty. The nightly mean values of the comp–check magnitudes were stable to $`\pm 0\stackrel{m}{.}004`$ with a mean value of $`\mathrm{\Delta }V=0\stackrel{m}{.}193`$ with a slight tendency for the 2002 data to be fainter by $`0\stackrel{m}{.}002`$ in average. This is below the range in which we are interested but might be important when a much larger and longer dataset becomes available. We also noted the 0$`\stackrel{m}{.}`$04 difference between the $`\mathrm{\Delta }V`$ and $`\mathrm{\Delta }y_{\mathrm{mag}}`$ values of the comparisons (the latter difference is $`0\stackrel{m}{.}15`$, taking the magnitudes in Powell et al. 1990), which we attribute to the difference between the Strömgren $`y`$ and Johnson $`V`$ filters.

## 3 Period analysis

### 3.1 The $`OC`$ diagram

First, we wanted to refine the period of V567 Oph by the traditional method of the $`OC`$ diagram. For this, we have collected all times of maximum from the literature. The data sources were the following works: early data were taken from the compilation of Powell et al. (1990); since then, Agerer & Hübscher (1996, 1997, 1998) and Agerer et al. (2001) published times of maximum quite regularly. We have determined 13 new epochs from our own light curves with the best phase coverages around maximum (see Table 2.). This was done by fitting low-order (3-5) polynomials to the parts of the light curves around maximum light. The whole collection consists of 46 times of maximum between JD 2429785 (1940) and JD 2452453 (2002). We have calculated the $`OC`$ values plotted in the top panel of Fig. 1 with the following ephemeris (GCVS):

$$Hel.JD_{\mathrm{max}}=2438592.4048+0.1495230E$$

As can be seen in Fig. 1, the global trend is linear, and can easily be subtracted. The bottom panel shows the residuals, which were calculated with the improved period of $`P=0.149523644\pm 0.000000024`$ days. This agrees very well with the period in Powell et al (1990), as they gave $`P=0.149523641\pm 0.000000043`$ days. We conclude, that the global picture of the period constancy is not changed when another 15 years are added to the previous $`OC`$ diagram by Powell et al. (1990). It means that any relative change of the main period (expressed as $`(1/P)dP/dt`$, Breger & Pamyatnykh 1998) is smaller than $`2.610^9`$ year-1.

However, as has been already discussed by Powell et al. (1990), the $`OC`$ diagram shows such large scatter (about $`\pm 0.01`$ days, i.e. $`\pm `$15 minutes!) which cannot be observational noise. Furthermore, our light curves alone showed such cycle-to-cycle variations which enforced us to reject the assumption of monoperiodicity. Fortunately, the amount of data enabled a more detailed analysis with the Fourier method.

### 3.2 Frequency analysis

The frequency analysis was performed by means of standard Fourier-analysis with subsequent prewhitening steps. For this we have used Period98 of Sperl (1998) which also includes multifrequency least squares fitting of the parameters. To test our results, we have also re-analysed other datasets in the literature (Poretti el al. 1990, Powell et al. 1990 and Hipparcos Epoch Photometry, ESA 1997).

The calculated amplitude spectra are shown in Fig. 2. The primary peak at $`f_1=6.687901`$ d-1 is in very good agreement with the period determined from the $`OC`$ analysis (6.6879055 d-1). In every step of the prewhitening procedure we allowed all parameters to vary to get the optimal Fourier-fit of the light curve. The first four prewhitening steps resulted in peaks in the subsequent frequency spectra with S/N ratios (Breger et al. 1993) larger than 10. The fifth step yielded a low-frequency component at 3.008 d-1 with S/N of 5. However, we did not accept it because this frequency range is especially sensitive to instrumental effects. This has been tested by a Fourier-analysis of the magnitude differences between the comparison stars. As expected, besides a very low-frequency component (approximately equal to 1/2$`\mathrm{\Delta }T`$, our time span) we could detect another component at 2.8 d-1 with an amplitude of 3.5 mmag. Therefore, we stopped the analysis of V567 Oph at the fourth prewhitening step.

As expected from the asymmetric light curve shape, some of the frequencies are integer harmonics of the primary one. In fact, we have detected $`f_1`$, $`2f_1`$ and $`3f_1`$ with amplitudes of 0$`\stackrel{m}{.}`$154, 0$`\stackrel{m}{.}`$035 and 0$`\stackrel{m}{.}`$011. The third frequency was the only one independent of $`f_1`$ at 11.82658 d-1 with an amplitude of 0$`\stackrel{m}{.}`$014. Therefore, we decided to repeat the whole analysis by fixing $`f_1`$=6.6879055 d-1 and its two integer harmonics. After fitting their amplitudes and phases only one prewhitening step yielded the secondary frequency of V567 Oph, hereafter referred to as $`f_2`$. The parameters of the adopted frequencies are summarized in Table 3, while the Fourier-fit of the individual light curves are presented in Fig. 3.

We have separately re-analysed previous data in the literature to draw some constraints on the stability of the secondary period. The dataset of Poretti et al. (1990) allowed the detection of $`f_1`$ and $`2f_1`$ and some low-frequency noise between 3 and 4 d-1 (it has been already noted in that paper that zero-point shifts affected the data). The Hipparcos Epoch Photometry, consisting of 190 data points, yielded only $`f_1`$, though quite accurately (6.687967 d-1). The strongest pieces of evidence came from the re-analysis of the Powell et al. (1990) dataset. Besides $`f_1`$, $`2f_1`$ and $`3f_1`$, the subsequent prewhitening steps resulted in $`f_2`$=11.77 d-1 with an amplitude of 0$`\stackrel{m}{.}`$014. Although $`3f_1`$ and $`f_2`$ have low S/N ratio in that dataset, their values strongly support our results (note, that the amplitude of the secondary frequency is very close to ours). Therefore, we conclude that the light curve of of V567 Oph is doubly periodic and consequently, the star is a double-mode pulsator.

## 4 Discussion

What can be said about the nature of this double-mode pulsation? To draw some constraints on mode identification, we have inspected the period ratio and $`Q`$ values.

The frequency ratio has an intriguing value of $`f_1/f_2=0.565`$ which is far from the usually found 0.75–0.79 associated with radial fundamental and first overtone pulsation (see Petersen & Christensen-Dalsgaard (1996) for a parameter study, while Alcock et al. (2000) for a larger sample of double-mode HADS). As pointed out by McNamara (2000), several candidates for higher overtone pulsation can be found in $`\omega `$ Cen, for which recent linear nonadiabatic models (Gilliland et al. 1998) predict $`f_0/f_2=0.63`$ and $`f_0/f_3=0.53`$. However, neither of these two values fits the observed one which is fairly accurate (its error is less than $`\pm `$0.001). From the observational point of view, it is interesting that there is no other double-mode HADS with similar frequency ratio. Therefore, we searched the literature to find similar stars among the lower amplitude $`\delta `$ Scuti stars. Close resemblance was found for AN Lyn (0.565, Rodríguez et al. 1997, Zhou 2002), V663 Cas (0.591, Mantegazza & Poretti 1990) and 63 Her (0.564, Breger et al. 1994). In all cases the authors arrived to the conclusion that a mixture of radial and non-radial modes is needed to explain the “non-standard” frequency ratios. Adopting their argumentations, it is reasonable to accept this consideration in the case of V567 Oph, too. Recent theoretical models also support this idea (Bono et al. 1997, Gilliland et al. 1998).

We have calculated the pulsation constant $`Q`$ for both frequencies with the formula

$$\mathrm{log}Q=6.456+\mathrm{log}P+0.5\mathrm{log}g+0.1M_{\mathrm{bol}}+\mathrm{log}T_{\mathrm{eff}}$$

in terms of four observables (Breger et al. 1993). The physical parameters of V567 Oph were determined by Powell et al. (1990), McNamara (1997) and Balona & Evers (1999). We list the corresponding $`Q`$ values in Table 4.

While the first two sets of parameters are in good agreement, the last two are fairly contradictory. Balona & Evers (1999) used different calibrations. For V567 Oph, they applied calibrations by Balona (1994) and Moon & Dworetsky (1985) – the latter one produced that deviant $`\mathrm{log}g`$=3.26 resulting in hardly acceptable $`Q`$ values. If we keep the first set of parameters of Balona & Evers, it still results in uncomfortably high $`Q_1`$. However, this is likely caused by a systematic error in their Strömgren calibrations, an error that was pointed out by Rodríguez & Breger (2001). From a comparison of photometric and geometric parallaxes they found that for slowly rotating stars Strömgren calibrations underestimate the absolute magnitude by 0$`\stackrel{m}{.}`$5 in average. Since V567 Oph is a typical slowly rotating HADS ($`v\mathrm{sin}i<18`$ km s-1, McNamara 1985), its absolute magnitude is likely to be affected by this systematic error. A correction by $`\mathrm{\Delta }M_\mathrm{V}=0\stackrel{m}{.}5`$ shifts $`Q_1`$ to 0.036 and $`Q_2`$ to 0.020, being in good agreement with the other two calibrations.

Assuming 20% uncertainty in $`Q`$ values (that is $`\pm 0.007`$ and $`\pm 0.004`$ for $`Q_1`$ and $`Q_2`$, respectively) we conclude that the dominant period indeed corresponds to the radial fundamental mode, as assumed for the overwhelming majority of HADS. On the other hand, the secondary period can be identified with a non-radial mode of radial order $`n=2`$ or 3 (Bono et al. 1997, Gilliland et al. 1998). Presently nothing can be specified unambiguously about the non-radial degree $`l`$, for which the simpliest assumption is 1 or 2.

In order to perform more secure mode identification, accurate multicolour photometry would be of great importance. Unfortunately, the relative faintness of the star does not make it favourable target object for photoelectric photometry. Therefore, CCD observers with proper instrumentation are expected to gain more insights into the peculiar pulsation pattern of V567 Oph by taking follow-up observations of this interesting HADS.

###### Acknowledgements.

This work has been supported by the Hungarian OTKA Grants #T032258 and #T034615, the “Bolyai János” Research Scholarship to LLK from the Hungarian Academy of Sciences, the Hungarian Eötvös Fellowship to LLK, FKFP Grant 0010/2001, Pro Renovanda Cultura Hungariae Foundation and Szeged Observatory Foundation. LLK thanks the kind hospitality of the Instituto de Astrofísica de Andalucía, where the analysis has been finished. Useful comments and suggestions by E. Rodríguez are also acknowledged. The NASA ADS Abstract Service was used to access data and references. This research has made use of the SIMBAD database, operated at CDS-Strasbourg, France.


text:
# Coloring random graphs

## Abstract

We study the graph coloring problem over random graphs of finite average connectivity $`c`$. Given a number $`q`$ of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on $`q`$, we find the precise value of the critical average connectivity $`c_q`$. Moreover, we show that below $`c_q`$ there exist a clustering phase $`c[c_d,c_q]`$ in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.

The Graph Coloring problem (COL) is a very basic and famous problems in combinatorics GaJo  and in statistical physics WU . Given a graph, or a lattice, and given a number $`q`$ of available colors, the problem consists in finding a coloring of vertices such that no two neighboring vertices have the same color. The minimally needed number of colors is the chromatic number of the graph.

For planar graphs there exists a famous theorem four\_colors  showing that four colors are sufficient, and that a coloring can be found by an efficient algorithm. On the contrary, for general graphs the problem is computationally hard to solve: already in 1972 it was shown that Graph Coloring is NP-complete Karp72  which means, roughly speaking, that the time required for determining the existence of a proper coloring grows exponentially with the graph size.

In modern computer science, graph coloring is taken as one of the most widely used benchmarks for the evaluation of algorithm performance satlib . The interest in coloring stems from the fact that many real-world combinatorial optimization problems have component sub-problems which can be easily represented as coloring problems. For instance, a classical application is the scheduling of registers in the central processing unit of computers. All variables manipulated by the program are characterized by ranges of times during which their values are left unchanged. Any two variables that change during the same time interval cannot be stored in the same register. One may represent the overall computation by constructing a graph where each variable is associated with a vertex and edges are placed between any two vertices whose corresponding variables change during the same time interval. A proper coloring with a minimal number of colors of this graph provides an optimal scheduling for registers: two variables with the same color will not be connected by an edge and so can be assigned to the same register (since they change in different time intervals).

The $`q`$-coloring problem of random graphs represents a very active field of research in discrete mathematics which constitutes the natural evolution of the percolation theory initiated by Erdös and Rènyi in the 50’s Erdos\_Renyi . One point of contact between computer science and random graph theory arises from the observation that, for large random graphs, there exists a critical average connectivity beyond which the graphs become uncolorable with probability tending to one as the graph size goes to infinity. This transition will be called the $`q`$-COL/UNCOL transition throughout this paper. The precise value of the critical connectivity depends of course on the number $`q`$ of allowed colors and on the ensemble of random graphs under consideration. Graphs generated close to their critical connectivity are extraordinarily hard to color and therefore the study of critical instances is at the same time a well posed mathematical question as well as an algorithmic challenge for the understanding of the onset of computational complexity AI ; TCS . The notion of computational complexity refers to worst-case instances and therefore results for a given ensemble of problems might not be of direct relevance. However, on the more practical side, algorithms which are used to solve real-world problems display a huge variability of running times and a theory for their typical-case behavior, on classes of non-trivial random instances, constitutes the natural complement to the worst-case analysis. Similarly to what happens for other famous combinatorial problem, e.g. the satisfiability problem of Boolean formulae, critical random instances of $`q`$-coloring (or polynomial mappings to other NP-complete problems) are a popular test-bed for the performance of search algorithms satlib .

In physics $`q`$-coloring has a direct interpretation as a spin-glass model. A proper coloring of a graph is a zero-energy ground state configuration of a Potts anti-ferromagnet with $`q`$-state variables. For most lattices this system is frustrated and displays many equilibrium and out-of-equilibrium features of glasses (‘Potts glass’).

Here we focus on the $`q`$-coloring problem (or Potts anti-ferromagnet) over random graphs of finite average connectivity, given by the $`𝒢_{N,p}`$ ensemble (graphs composed of $`N`$ vertices with edge probability $`p`$ for every pair of vertices). In the relevant limit of finite connectivity we have to take $`p=c/N`$ which leads to random graphs with a Poissonian connectivity distribution of mean $`c`$.

Two types of questions can be asked. One type is algorithmic, i.e. finding an algorithm that decides whether a given graph is colorable. The other type is more theoretical and amounts to asking whether a typical problem instance is colorable or not and what is the typical structure of the solution space. Here we address the latter question using the so called cavity method MePa .

Let us start with reviewing some known results on the $`q`$-COL/UNCOL transition on random graphs. One of the first important finite-connectivity results was obtained by Luczak about one decade ago Lu . He proved that the threshold asymptotically grows like $`c_q2q\mathrm{ln}q`$ for large numbers of colors, a result, which up to a pre-factor coincides with the outcome of a replica calculation on highly connected graphs KaSo  ($`p=𝒪(1)`$ for large $`N`$). For fixed number $`q`$ of colors, all vertices with less than $`q`$ neighbors, i.e. of degree smaller $`q`$, can be colored for sure. The hardest to color structure is thus given by the maximal subgraph having minimal degree at least $`q`$, the so-called $`q`$-core. Pittel, Spencer and Wormald PiSpWo  showed that the emergence of a 2-core coincides with random graph percolation at $`c=1`$ Erdos\_Renyi , and is continuous. For $`q3`$, however, the $`q`$-core arises discontinuously: For $`q=3`$ they found, e.g., that the core emerges at $`c3.35`$ and immediately contains about 27% of all vertices. The existence of this core is, however, not sufficient for uncolorability: The best lower bound for the 3-COL/UNCOL transition is 4.03 AcMo1 , numerical results predict a threshold of about 4.7 Numerical . The currently best rigorous upper bound is 4.99 AcMo2 . Most recently, a replica symmetric analysis of the problem has been performed MoSa . The resulting threshold 5.1 exceeds, however, the rigorous bound, and one has to go beyond replica symmetry. At the level of one-step replica-symmetry breaking (1RSB) we are able to calculate a threshold value $`c_34.69`$ which we believe to be exact note:rsb . We also describe the solution space structure which undergoes a clustering transition at $`c_d4.42`$.

As stated above, the question if a given graph is $`q`$-colorable is equivalent to the question if there are zero-energy ground states of the anti-ferromagnetic $`q`$-state Potts model defined on the same graph. Denoting the set of all edges by $`E`$, the problem can thus be described by the Hamiltonian

$$H=\underset{(i,j)E}{}\delta (\sigma _i,\sigma _j)$$
(1)
with $`\delta (,)`$ denoting the Kronecker symbol. The spins $`\sigma _i,i=1,\mathrm{},N,`$ are allowed to take the $`q`$ values $`\{1,\mathrm{},q\}`$. This Hamiltonian counts the number of edges being colored equally on both extremities, a proper coloring of the graph thus has energy zero. In this letter we apply the cavity method in a variant recently developed for finite-connectivity graphs directly at zero temperature MePaZe ; MePa2 ; MeZe . This approach consists of a self-consistent iterative scheme which is believed to be exact over locally tree-like graphs, like the ones we consider here. It includes the possibility of dealing with the existence of many pure states. One has to first evaluate the energy shift of the system due to the addition of a new new spin $`\sigma _0`$. Let us assume for a moment that the new spin is only connected to a single spin, say $`\sigma _1`$, in the pre-existing graph. Before adding the new site 0, the ground-state energy of the system with fixed $`\sigma _1`$ can be expressed as

$$E_0(\sigma _1)=A\underset{\tau =1}{\overset{q}{}}h_\tau ^1\delta (\tau ,\sigma _1)$$
(2)
where we have introduced the effective field $`\stackrel{}{h}^1=(h_1^1,\mathrm{},h_q^1)`$. Note that a $`(q1)`$-dimensional field would be sufficient since one of the $`q`$ fields above can be absorbed in $`A`$. We, however, prefer to work with $`q`$ field components in order to keep evident the global color symmetry. Connecting $`\sigma _0`$ to $`\sigma _1`$, and calculating the minimal energy of the enlarged graph with fixed $`\sigma _0`$, this reads

$`E(\sigma _0)`$ $`=`$ $`\underset{\sigma _1}{\mathrm{min}}\left(A{\displaystyle \underset{\tau =1}{\overset{q}{}}}h_\tau ^1\delta (\tau ,\sigma _1)+\delta (\sigma _0,\sigma _1)\right)`$ (3)
$`=`$ $`A\omega (\stackrel{}{h}^1){\displaystyle \underset{\tau =1}{\overset{q}{}}}u_\tau (\stackrel{}{h}^1)\delta (\tau ,\sigma _0)`$
with

$`\omega (\stackrel{}{h})`$ $`=`$ $`\mathrm{min}(h_1,\mathrm{},h_q)`$ (4)
$`u_\tau (\stackrel{}{h})`$ $`=`$ $`\{\begin{array}{cc}\hfill 1& \text{if}h_\tau <h_1,..,h_{\tau 1},h_{\tau +1},..,h_q\hfill \\ \hfill 0& \text{else}\hfill \end{array}`$ (7)
The field $`\stackrel{}{u}(\stackrel{}{h}^1)`$ has at most one non-zero component, which takes the value $`1`$, i.e. $`\stackrel{}{u}(\stackrel{}{h}^1)\{\stackrel{}{0},\stackrel{}{e}_1,\mathrm{},\stackrel{}{e}_q\}`$ with $`\stackrel{}{e}_\tau `$ denoting a unit vector in direction $`\tau `$.

If the new spin $`\sigma _0`$ is connected to $`d`$ sites with fields $`\stackrel{}{h}^1,\mathrm{},\stackrel{}{h}^d`$, and if these spins were previously uncorrelated (which is the case inside one pure state, cf. the discussion in MePa ), the propagated fields can be linearly superposed, $`\stackrel{}{h}^0=_{i=1}^d\stackrel{}{u}(\stackrel{}{h}^i)`$. Note that the fields never become positive, which reflects the anti-ferromagnetic character of the model. Colors are suppressed by neighbors carrying this color, they can be favored only by suppressing all other colors. If there would be a single state (replica symmetry), every link $`(i,j)`$ would carry two propagated fields $`\stackrel{}{u}_{ij}`$ and $`\stackrel{}{u}_{ji}`$ which are determined self-consistently. In case of multiple states, these fields fluctuate from state to state and have to be characterized by a full distribution $`Q_{ij}(\stackrel{}{u})`$, cf. MePa ; MeZe . Due to the global color symmetry, each of these takes the form

$$Q_{ij}(\stackrel{}{u})=(1q\eta _{ij})\delta (\stackrel{}{u})+\eta _{ij}\underset{\tau =1}{\overset{q}{}}\delta (\stackrel{}{u}+\stackrel{}{e}_\tau )$$
(8)
and can thus be fully described by the probability $`\eta _{ij}`$ that any of the colors of vertex $`j`$ is forbidden by edge $`(i,j)`$. Denoting the histogram of all $`\eta _{ij}`$ by $`\rho (\eta )`$, the self-consistency equation for the distribution of the $`Q_{ij}(\stackrel{}{u})`$ can be reduced to a simple equation for $`\rho (\eta )`$ note ,

$`\rho (\eta )`$ $`=`$ $`e^c{\displaystyle \underset{d=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c^d}{d!}}{\displaystyle _0^{1/q}}𝑑\eta _1\mathrm{}𝑑\eta _d\rho (\eta _1)\mathrm{}\rho (\eta _d)`$ (9)
$`\times \delta (\eta f_d(\eta _1,\mathrm{},\eta _d))`$
where $`f_d`$ is simply given by

$$f_d(\eta _1,\mathrm{},\eta _d)=\frac{_{l=0}^{q1}(1)^l\left(\genfrac{}{}{0pt}{}{q1}{l}\right)_{i=1}^d[1(l+1)\eta _i]}{_{l=0}^{q1}(1)^l\left(\genfrac{}{}{0pt}{}{q}{l+1}\right)_{i=1}^d[1(l+1)\eta _i]}$$
(10)
This equation resembles a replica-symmetric self-consistent equation and can be solved numerically using a population dynamical algorithm: We start with an initial population $`\eta _1,\mathrm{},\eta _𝒩`$ of size $`𝒩`$ which can be easily chosen to be as large as $`10^6`$ to generate high-precision data. This population is updated by iterating the following steps until convergence: (I) Randomly draw a number $`d`$ from the Poisson distribution $`e^cc^d/d!`$; (II) Randomly select $`d+1`$ indices $`i_0,i_1,\mathrm{},i_d`$ from $`\{1,\mathrm{},𝒩\}`$; (III) Update the population by replacing $`\eta _{i_0}`$ by $`f_d(\eta _{i_1},\mathrm{},\eta _{i_d})`$.

One obvious solution of Eq. (10) is the paramagnetic solution $`\delta (\eta )`$. For small average connectivities $`c`$ it is even the only one. The appearance of a non-trivial solution coincides with a clustering transition of ground states into an exponentially large number of extensively separated clusters. In spin-glass theory, this transition is called dynamical. Still, $`\rho (\eta )`$ will contain a non-trivial peak in $`\eta =0`$ due to small disconnected subgraphs, dangling ends etc. The weight $`t`$ of this peak can be computed self-consistently from

$$t=e^{(1t)c}\underset{l=0}{\overset{q2}{}}\frac{(1t)^lc^l}{l!}.$$
(11)
This equation is quite interesting, since a non-trivial solution forms a necessary condition for Eq. (9) to have a non-trivial solution. In fact PiSpWo , the fraction of edges in the $`q`$-core is given by $`(1t_{min})`$ with $`t_{min}`$ being the smallest positive solution of Eq. (11). Thus, we also find that the existence of an extensive $`q`$-core is necessary for a non-trivial $`\rho (\eta )`$, and forms a lower bound for the $`q`$-COL/UNCOL transition.

Unlike in the case of finite-connectivity $`p`$-spin-glasses or, equivalently, random XOR-SAT problems RiWeZe ; CoDuMo ; MeRiZe , the existence of a solution $`t<1`$ is not sufficient for a non-trivial $`\rho (\eta )`$ to exist. The latter appears suddenly at the dynamical transition $`c_d`$, which can be determined to high precision using the population dynamical algorithm. This solution does not imply uncolorability, but the set of solutions is separated into an exponentially large number of clusters. The logarithm of their number, divided by the graph size $`N`$, is called the complexity $`\mathrm{\Sigma }(c)`$ and can be calculated from $`\rho (\eta )`$, cf. MeZe

$`\mathrm{\Sigma }(c)`$ $`=`$ $`e^c{\displaystyle \underset{d=1}{\overset{\mathrm{}}{}}}{\displaystyle \frac{c^d}{d!}}{\displaystyle 𝑑\eta _1\mathrm{}𝑑\eta _d\rho (\eta _1)\mathrm{}\rho (\eta _d)}`$ (12)
$`\times \mathrm{ln}\left({\displaystyle \underset{l=0}{\overset{q1}{}}}(1)^l\left({\displaystyle \genfrac{}{}{0pt}{}{q}{l+1}}\right){\displaystyle \underset{i=1}{\overset{d}{}}}[1(l+1)\eta _i]\right)`$
$`{\displaystyle \frac{c}{2}}{\displaystyle 𝑑\eta _1𝑑\eta _2\rho (\eta _1)\rho (\eta _2)\mathrm{ln}(1q\eta _1\eta _2)}.`$
The full derivation will be given in ColoringAlgo . At the dynamical threshold, this complexity starts discontinuously with a positive value, see Fig. 1, and decreases when $`c`$ is increased. The static RSB transition, and thus the $`q`$-COL/UNCOL threshold $`c_q`$, are given by the point of vanishing complexity. At this point the number of clusters becomes sub-exponential, and disappears beyond $`c_q`$.

In the following table, we present the results for $`q=3,4,`$ and 5. For the dynamical transition we show the corresponding values of $`c_d`$, of the entropy $`s(c_d)=\mathrm{ln}q+\frac{c}{2}\mathrm{ln}\frac{q1}{q}`$ and the complexity $`\mathrm{\Sigma }(c_d)`$. For the $`q`$-COL/UNCOL transition, the critical connectivity $`c_q`$ and the solution entropy are given. Like in random 3-satisfiability MoZe  and vertex covering WeHa , this entropy is found to be finite at the transition point.

| q | $`c_d`$ | $`s(c_d)`$ | $`\mathrm{\Sigma }(c_d)`$ | $`c_q`$ | $`s(c_q)`$ |
| --- | --- | --- | --- | --- | --- |
| 3 | 4.42 | 0.203 | 0.0223 | 4.69 | 0.148 |
| 4 | 8.27 | 0.197 | 0.0553 | 8.90 | 0.106 |
| 5 | 12.67 | 0.196 | 0.0794 | 13.69 | 0.082 |

One can see that the complexity at the dynamical threshold grows strongly with $`q`$, whereas the total entropy decreases slowly. This means that the clustering phenomenon becomes more and more pronounced, the number of clusters increases, their internal entropy $`s(c)\mathrm{\Sigma }(c)`$ becomes smaller. It also becomes more relevant for small systems. At $`N=100`$ and the dynamical threshold, we would predict only around 10 clusters for $`q=3`$, for $`q=4`$ this number would already be close to 250, and grow to about 2800 for 5 colors.

The dynamical transition is not only characterized by a sudden clustering of ground states, at the same point an exponential number of meta-stable states of positive energy appears MeZe . Such states are expected to act as traps for local search algorithms causing an exponential slowing down of the search process. Well known examples of search processes that are overwhelmed by the presence of excited states are simulated annealing or greedy algorithms based on local information.

To test this prediction, we have applied several of the best solvers for COL and SAT problems available in the net satlib ; Culberson\_HP . The best results could be obtained using the complete smallk program Culberson\_HP  which may need exponential time to find a proper minimal coloring. Using a cutoff time (we probed with 10 seconds, 1 minute and 2 minutes without substantial changes for $`N=10^3`$), the algorithm can be restricted to sub-exponential times, i.e. only the underlying polynomial-time heuristic is applied. The results in Fig. 1 were obtained in the following way: We first tried to color a random graph ($`N=10^3`$) with a small number of colors (here $`q=3`$). If, after the cutoff time, smallk did not find a coloring, we stopped and retried with larger $`q`$. For each connectivity we averaged over 100 samples. As it can be clearly seen, the algorithm fails with $`q`$ colors slightly below the dynamical transition, confirming our expectations. Only a perfect local heuristic should reach this threshold.

We conclude by noticing that, in similarity to the 3-SAT problem MeZe , we expect the assumptions underlying the cavity approach to hold for single instances of COL. The equations for the order parameter on single instances provide the full histogram of the N probability distributions of the effective fields, one for each variable, which describe the fluctuations of the polarization of each Potts variable in the ground states. On the physics side, this information allows to develop a single sample statistical mechanics analysis whereas on the algorithmic side it allows develop new algorithms ColoringAlgo .

###### Acknowledgements.

We are grateful to A. Braunstein, J. Culberson and F. Ricci-Tersenghi for interesting discussions.


text:
# Disorder effects in diluted ferromagnetic semiconductors.

After the recent discovery by Ohno et al. that by doping GaAs  with only $`5\%`$ of magnetic impurities Mn2+, the Curie temperature $`T_C`$ could already exceed 100 K and because of all the possible technological applications, the interest for the III-V diluted magnetic semiconductors (DMS) has increased considerably. In spite of the apparent success of different methods (mean field, first-principle, random-phase approximation (RPA)) where disorder is either neglected or treated at the lowest order to reproduce the Curie temperature, there is still some shadow region concerning the effect of disorder on magnetism. Indeed only few works, mainly based on numerical simulations, are including the effect of positional disorder  within a mean field treatment (multi-scattering effects are not included). Recently, in order to provide a simultaneous and self-consistent treatment of the itinerant carrier and magnetic impurity an approach based on the equation of motion method was proposed . However, as a consequence of the RPA decoupling the self-energy of the itinerant carriers Green’s function (GF) is reduced to the lowest order term $`\mathrm{\Sigma }_\sigma =\frac{z_\sigma }{2}J_{pd}c\widehat{𝐒}^z`$ (where $`z_\sigma =\pm 1`$ and c is Mn2+ concentration). Because of the difficulty to include within this formalism, higher order scattering terms, we follow in this paper a slightly different approach and focus first on the effect of the disorder on the itinerant carriers. First, we calculate the itinerant carrier GF by treating the effect of disorder in the full coherent-potential approximation (CPA) approximation, which means that all single site multi-scattering processes are properly included. In the second step we calculate the exchange integrals between spin impurities using the projected GF on the Mn sites. The difficulty is to perform properly the averaged T-matrix calculation since the holes/electrons scattering depends on the impurity spin operator. For that purpose we follow the procedure described in . It should be added that in this work, spin impurities are treated fully quantum mechanically.

We consider the following minimal Hamiltonian which is the good starting point to study DMS,

$$H=\underset{ij,\sigma }{}t_{ij}c_{i\sigma }^{}c_{j\sigma }+\underset{i}{}J_i𝐒_i𝐬_i$$
(1)
$`t_{ij}=t`$ for $`i`$ and $`j`$ nearest neighbors and zero otherwise. In the exchange between localized impurities spin and itinerant electron gas $`J_i`$ is a random variable: $`J_i=J`$ ($`J0`$ means antiferromagnetic coupling) if the site $`i`$ is occupied by a magnetic impurity, and zero otherwise. $`𝐒_i`$ is the magnetic impurity spin operator at site $`i`$ and $`𝐬_i=c_{i\alpha }^{}(1/2𝝈_{\alpha \beta })c_{i\beta }`$ is the spin operator at site $`i`$ of the itinerant electron gas.

The T-matrix associated to the multi-scattering of a single magnetic impurity (at site $`m`$) embedded in the effective medium is,

$$\widehat{𝐭}_m=\widehat{𝐕}_m(\mathrm{𝟏}\widehat{\overline{𝐆}}\widehat{𝐕}_m)^1$$
(2)
where,

$`\widehat{𝐕}_m^{\text{Mn}}=\left(\begin{array}{cc}\frac{1}{2}J𝐒_m^z\mathrm{\Sigma }_{}& \frac{1}{2}J𝐒_m^{}\\ \frac{1}{2}J𝐒_m^+& \frac{1}{2}J𝐒_m^z\mathrm{\Sigma }_{}\end{array}\right)`$ (5)
Respectively, for Ga at site $`m`$, $`\widehat{𝐕}_m^{\text{Ga}}`$ is obtained by taking $`J=0`$ in the previous equation.

The $`2\times 2`$ averaged Green’s function matrix $`\widehat{\overline{𝐆}}`$ is,

$`\widehat{\overline{𝐆}}=\left(\begin{array}{cc}\widehat{\overline{𝐆}}_{}& 0\\ 0& \widehat{\overline{𝐆}}_{}\end{array}\right)`$ (8)
with $`\widehat{\overline{𝐆}}_\sigma =(\omega 𝐈\widehat{\overline{𝐊}}_\sigma )^1`$ where, $`\widehat{\overline{𝐊}}_\sigma =_𝐤(ϵ_𝐤\mathrm{\Sigma }_\sigma )c_{𝐤\sigma }^{}c_{𝐤\sigma }`$.

In the following, we omit the site index $`m`$. The self-energy $`\mathrm{\Sigma }_\sigma `$ is obtained by solving the coupled self-consistent equations.

$`t_{\sigma \sigma }_{\text{dis},T}=(1c)t_{\sigma \sigma }^{\text{Ga}}_T+ct_{\sigma \sigma }^{\text{Mn}}_T=0`$ (9)
$`\mathrm{}_{\text{dis},T}`$ denotes configuration average and thermal average at temperature $`T`$ for the spin operator, $`c`$ is the concentration of Mn impurities.

After lengthy calculations we get,

$`\mathrm{\Sigma }_\sigma ={\displaystyle \frac{_\lambda x_\lambda \widehat{𝐜}_\sigma ^\lambda (\widehat{𝐝}_\sigma ^\lambda )^1_T}{_\lambda x_\lambda (\widehat{𝐝}_\sigma ^\lambda )^1_T}}`$ (10)
The sum runs over all constituents, in our binary system $`x_{\text{Mn}}=c`$ (resp. $`x_{\text{Ga}}=1c`$).

$`\widehat{𝐜}_\sigma ^{\text{Mn}}`$ $`=`$ $`z_\sigma {\displaystyle \frac{J}{2}}\widehat{𝐒}^z+({\displaystyle \frac{J^2}{4}}[S(S+1)(\widehat{𝐒}^z)^2z_\sigma \widehat{𝐒}^z]`$ (12)
$`+[z_\sigma {\displaystyle \frac{J}{2}}\widehat{𝐒}^z+\mathrm{\Sigma }_\sigma ][{\displaystyle \frac{J}{2}}(z_\sigma \widehat{𝐒}^z1)\mathrm{\Sigma }_\sigma ])G_\sigma `$
and,

$`\widehat{𝐝}_\sigma ^{\text{Mn}}`$ $`=`$ $`1G_\sigma [{\displaystyle \frac{J}{2}}(z_\sigma \widehat{𝐒}^z1)\mathrm{\Sigma }_\sigma ]`$ (14)
$`G_\sigma [\widehat{𝐜}_\sigma ^{\text{Mn}}z_\sigma {\displaystyle \frac{J}{2}}\widehat{𝐒}^z]`$
with $`z_\sigma =1`$ (resp.$`1`$) for spin $``$ (resp.$``$). $`\overline{G}_\sigma =\frac{1}{N}_𝐪\overline{G}_\sigma (𝐪,\omega )`$ where $`\overline{G}_\sigma (𝐪,\omega )=\left(\omega ϵ_𝐪\mathrm{\Sigma }_\sigma (\omega )\right)^1`$ denotes the averaged GF. Similarly, one gets $`\widehat{𝐜}_\sigma ^{\text{Ga}}`$ and $`\widehat{𝐝}_\sigma ^{\text{Ga}}`$ after setting $`J=0`$ in the previous equations.

Note that since impurity spins are treated quantum mechanically, the thermal averaged quantities are evaluated using the following decomposition, $`\widehat{𝐎}(\widehat{𝐒}^z)_T=_{i=0}^{2S}a_i(\widehat{𝐒}^z)^i_T`$ where $`\widehat{𝐎}`$ denotes a general operator which depends in a non trivial manner on $`(\widehat{𝐒}^z)^i`$. Additionally, as it was shown by Callen-Strikman, $`(\widehat{𝐒}^z)^i_T`$, and hence $`\widehat{𝐎}(\widehat{𝐒}^z)_T`$, are universal functions of $`\widehat{𝐒}^z_T`$ only . After solving the coupled set of equations (Eq. (10) with $`\sigma =\pm 1`$) one gets the total averaged GF of the itinerant carriers.

The next step consists in calculating the long-range exchange integrals $`J_{ij}^{\text{eff}}`$ between magnetic impurities for the effective Heisenberg Hamiltonian,

$`H^{\text{Heis}}={\displaystyle \frac{1}{2}}{\displaystyle \underset{ij}{}}J_{ij}^{\text{eff}}𝐒_i𝐒_j`$ (15)
The exchange integrals between two impurities separated by a distance $`𝐑`$ is given by the generalized RKKY formula,

$`J^{\text{eff}}(𝐑)={\displaystyle \frac{1}{2}}J^2[{\displaystyle \frac{1}{\pi }}\mathrm{Im}\chi (𝐑)]`$ (16)
where the susceptibility is,

$$\chi (𝐑)=\underset{𝐤,𝐪}{}𝑑\omega f(\omega )\overline{G}_{}^{\text{Mn}}(𝐤,\omega )\overline{G}_{}^{\text{Mn}}(𝐤+𝐪,\omega )e^{i𝐪𝐑}$$
(17)
The chemical potential $`\mu `$ entering the Fermi-Dirac function $`f(\omega )`$ is determined at each temperature by fixing the itinerant carrier density. Note that the exchange integrals are $`T`$-dependent through the averaged GF. When replacing $`\overline{G}_\sigma `$ by the free particle GF the exchange integrals reduce to the standard RKKY. Additionally, it is important to stress that to calculate $`J_{ij}^{\text{eff}}`$, one has to take into account that both site $`i`$ and $`j`$ should be occupied by Mn atom. Thus the non local GF which enters Eq.17 should be the Mn-resolved GF but not the full averaged one.

To derive the projected GF on Mn sites, we essentially follow the procedure described in Ref., which gives,

$`\overline{G}_\sigma ^{\text{Mn}}(𝐤,\omega )`$ $`=`$ $`F_\sigma (\omega )(1F_\sigma (\omega ))\overline{G}_\sigma (\omega )`$ (19)
$`+F_\sigma ^2(\omega )\overline{G}_\sigma (𝐤,\omega )`$
where $`\overline{G}_\sigma (\omega )=\frac{1}{N}_𝐤\overline{G}_\sigma (𝐤,\omega )`$ and $`F_\sigma (\omega )=\left(1\overline{G}_\sigma (\omega )(V_{\text{eff},\sigma }^{\text{Mn}}\mathrm{\Sigma }_\sigma )\right)^1`$. The determination of the effective potential $`V_{\text{eff},\sigma }^{\text{Mn}}`$ leads to,

$`V_{eff,\sigma }^{Mn}=\mathrm{\Sigma }_\sigma {\displaystyle \frac{1+\mathrm{\Sigma }_\sigma \overline{G}_\sigma }{c+\mathrm{\Sigma }_\sigma \overline{G}_\sigma }}`$ (20)
As a final step we can evaluate the Curie temperature, by using mean-field theory for the effective Heisenberg model:

$`k_BT_C={\displaystyle \frac{2}{3}}S(S+1)c{\displaystyle \frac{1}{N}}{\displaystyle \underset{𝐪}{}}E(𝐪)`$ (21)
$`E(𝐪)`$ is the $`T`$-dependent magnon spectrum: $`E(𝐪)=\stackrel{~}{J}^{\text{eff}}(\mathrm{𝟎})\stackrel{~}{J}^{\text{eff}}(𝐪)`$where $`\stackrel{~}{J}^{\text{eff}}(𝐪)`$ denotes the Fourier transform of the exchange integrals.

In the following we discuss the numerical results. In Fig. 1 we have plotted the total density of states (DOS) and the projected one on Mn site as a function of energy, for different values of the parameter $`J/t`$. We observe that in the weak coupling regime($`J/t=0.86`$) the total spin-resolved DOS is almost identical to the unperturbed one although the Mn-projected DOS is already strongly affected by disorder. By increasing further $`J/t`$, we observe at low energy the impurity band formation. Note that the impurity band splits first at $`E0`$, and the position of the peaks in the Mn-DOS are not symmetric with respect to 0. This can be easily understood by analyzing the atomic limit ($`J/t\mathrm{}`$) which is properly described. In the paramagnetic phase, we get a peak at $`E_{\text{high}}=+\frac{1}{2}JS`$ and another at $`E_{\text{low}}=\frac{1}{2}J(S+1)`$ with respective weights $`\frac{S+1}{2S+1}c`$ and $`\frac{S}{2S+1}c`$ .

In Fig. 2, the dependence of $`T_C`$ on $`\gamma =n_h/c`$ ($`n_h`$ is the hole concentration) is discussed. At fixed $`\gamma `$, the Curie temperature increases significantly with $`J/t`$ and large value are reached when approaching the split-band regime. In the intermediate regime ($`J/t2`$), $`T_c`$ appears to be very sensitive to $`J/t`$, a maximum at $`\gamma 0.10`$ is observed before $`T_C`$ decrease and eventually vanishes at $`\gamma _c`$ which is $`J/t`$ dependent. These results are qualitatively comparable to those of ref., although we obtain Curie temperature significantly larger. Additionally, in comparable regime the maximum of $`T_c`$ in ref. corresponds to half-filled impurity band ($`\gamma 0.50`$) and $`T_c`$ is symmetric with respect to this point (it vanishes at $`\gamma =1`$). Later it will be shown that the sign of $`J`$ which is irrelevant in most of the model calculations, plays in fact an important role. As it will be discussed in the next section, the value of $`\gamma _c`$ for which $`T_C`$ vanishes depends on both the sign and amplitude of $`J/t`$.

In Fig. 3, $`T_C`$ as a function of $`J/t`$ is shown for both antiferromagnetic and ferromagnetic coupling for different carrier density. First, the sign of $`J/t`$ appears to be relevant. Indeed, $`T_C`$ is strongly asymmetric with respect to $`J/t=0`$. In the case of ferromagnetic coupling the maximum of $`T_C`$ is much smaller that for antiferromagnetic coupling. However, as expected, for $`|J|/t1`$ they are comparable and reduce to the standard RKKY calculations ($`T_CJ^2`$). For both, ferromagnetic and antiferromagnetic coupling, the position of the maximum depends on the hole concentration. However, the maximum occurs earlier in the ferromagnetic case. Note that in the intermediate regime $`1J/t3`$, $`T_C^{\text{RKKY}}`$ is much smaller than $`T_C^{\text{CPA}}`$: for $`J/t=2`$, $`T_C^{\text{CPA}}3T_C^{\text{RKKY}}`$ for $`n_h=0.015`$. Additionally, after the maximum is reached, $`T_C`$ drops rapidly, and vanishes at a $`n_h`$-dependent value of $`J/t`$. We observe that in the split-band regime $`J/t3.5`$ no ferromagnetic ordering is possible. In contrast to other approaches, our theory appears to be more suitable to describe the large coupling regime.

Let us discuss briefly, the relevance of our results with respect to experimental data of GacMn1-cAs. Our model is based on a one-band model, as done in Ref., we fix $`t`$ by assuming a hole effective mass $`m^{}=0.5m_e`$. This leads to a value $`t=0.58`$ eV . We assume that the $`5.3\%`$-doped sample (highest $`T_C=110`$ K) contains $`n_h0.2c`$. Using Fig.4, we obtain $`J=1.12`$ eV to get the same Curie temperature. Surprisingly, although our calculations are done within a one-band model, this value agrees perfectly with the estimate $`J=1.1\pm 0.2`$ eV .

In Fig. 4 we analyze the dependence of $`T_C`$ on the impurity concentration $`c`$, for different values of $`\gamma `$. For a given $`c`$, we observe that, $`T_C`$ is non monotonic with respect to $`\gamma `$. However it is clear, that even at large concentration the low hole density is more favorable to get a high Curie temperature. More precisely $`T_C`$ is larger when $`\gamma 0.1`$. For instance, when $`c=0.15`$ we get $`T_C240`$ K. Additionally, we see that when increasing $`c`$, for sufficiently large $`\gamma `$, $`T_C`$ shows a maximum and decreases till it vanishes. It is expected that $`T_C`$ will first vanish for larger itinerant carrier density.Indeed, the localization effect is stronger at higher carrier density.

To conclude, we have presented a theory to study ferromagnetism in DMS, which consists (i) in treating the itinerant carrier within the best single site approximation (CPA) and (ii) performing the susceptibility calculation with the disordered Green’s functions to get the Curie temperature. We have shown that the role of disorder is important and leads to significantly higher values of the Curie temperature with respect to a standard RKKY calculation. Additionally, it is shown that an antiferromagnetic coupling favors a higher $`T_C`$ in the hole doped materials. We believe that this approach is more suitable to analyze ferromagnetism in diluted semiconductors.

One of us (J.K.) acknowledges the financial support provided by the Grant Agency of the Czech Republic (No. 202/00/0122) and the Grant Agency of the Academy of Sciences of the Czech Republic ((No. A1010203).