text:
# Spin-density functional approach to thermodynamic and structural consistence in the charge and spin response of an electron gas

Abstract

We use spin-density functional theory to obtain novel expressions for the charge and spin local-field factors of an electron gas in terms of its electron-pair structure factors. These expressions (i) satisfy the compressibility and spin susceptibility sum rules; (ii) keep account of kinetic correlations by means of an integration over the coupling strength; and (iii) provide a practical self-consistent scheme for evaluating linear response and liquid structure. Numerical illustrations are given for the dielectric response of the paramagnetic electron gas in both three and two dimensions.

PACS numbers: 71.10.Ca - Electron gas

Key Words: C. Electron-electron interactions; C. Dielectric response; C. Spin dynamics

An interacting electron gas on a uniform neutralizing background is the reference system for many calculations of electronic structure in condensed matter systems . Its dielectric and spin susceptibilities provide key inputs in density functional theory  and in studies of quasi-particle properties such as the effective mass and the effective Landé g-factor . These properties are now known from experiment for carriers in semiconductor structures over a wide range of density . A great deal of relevant information has been coming from Quantum Monte Carlo (QMC) studies \[5 - 9\], but theoretical understanding continues to attract interest.

The issue of thermodynamic consistence in the theory of linear response for an electron gas, though raised in the early work of Vashishta and Singwi  through an ad hoc scheme to account for the compressibility sum rule, has not received much attention. In brief, thermodynamic consistence requires that the linear susceptibilities (at zero temperature) should reduce in the static, long-wavelength limit to the values obtained from the second derivatives of the (ground-state) energy. Of course, it is possible to model the susceptibilities by parametrized analytical expressions that embody these limiting behaviors as they are known from QMC data . In this Letter we propose instead a fully self-consistent theoretical scheme, which uses the mean particle and spin densities of the system as the only inputs for the calculation of the susceptibilities and of the electron-pair structure. Our approach is aimed at satisfying both the compressibility and the spin susceptibility sum rule: indeed, the QMC studies show that spin correlations and spin ordering are enhanced on increasing the coupling strength. Our starting point is the expression of the exchange-correlation energy $`E_{\mathrm{x}c}[n_{},n_{}]`$ as a functional of the spin densities $`n_{}(𝐫)`$ and $`n_{}(𝐫)`$ in an inhomogeneous $`d`$-dimensional electron gas with interaction potential $`v(r)=e^2/r`$,

$$E_{\mathrm{x}c}[n_{},n_{}]=\frac{1}{2e^2}_0^{e^2}𝑑\lambda \underset{\sigma ,\sigma ^{}}{}d^d𝐫d^d𝐫^{}v(|𝐫𝐫^{}|)\left[\mathrm{\Psi }_\lambda |\delta \widehat{n}_\sigma (𝐫)\delta \widehat{n}_\sigma ^{}(𝐫^{})|\mathrm{\Psi }_\lambda \delta _{\sigma \sigma ^{}}n_\sigma (𝐫)\delta (𝐫𝐫^{})\right]$$
(1)
where $`|\mathrm{\Psi }_\lambda `$ is the ground state of the gas with interaction potential $`v_\lambda (r)=\lambda /r`$ and $`\delta \widehat{n}_\sigma (𝐫)=\widehat{n}_\sigma (𝐫)n_\sigma (𝐫)`$. The spin-density operators $`\widehat{n}_\sigma (𝐫)`$ are given by $`\widehat{n}_\sigma (𝐫)=\psi _\sigma ^{}(𝐫)\psi _\sigma (𝐫)`$ in terms of Schrödinger field operators obeying canonical anticommutation relations. In deriving Eq. (1), which is obtained by an immediate extension of the treatment given by Dreizler and Gross  for the paramagnetic state, the technique of coupling-constant integration has been adapted to the context of density functional theory in order to account for kinetic correlations. Upon introducing as independent variables the total particle density $`n(𝐫)=n_{}(𝐫)+n_{}(𝐫)`$ and the spin magnetization density $`m(𝐫)=n_{}(𝐫)n_{}(𝐫)`$, Eq. (1) can be written in the more convenient form

$$E_{\mathrm{x}c}[n,m]=\frac{1}{2}d^d𝐫d^d𝐫^{}v(|𝐫𝐫^{}|)n(𝐫)n(𝐫^{})\left[\overline{g}(𝐫,𝐫^{})1\right]$$
(2)
where the coupling-averaged pair function $`\overline{g}(𝐫,𝐫^{})`$ is defined by

$$\overline{g}(𝐫,𝐫^{})=\frac{1}{e^2}_0^{e^2}𝑑\lambda g_\lambda (𝐫,𝐫^{}).$$
(3)
Here, $`g_\lambda (𝐫,𝐫^{})`$ is the pair distribution function in the gas with interaction potential $`v_\lambda (r)`$ of strength $`\lambda `$ and is, of course, a functional of $`n`$ and $`m`$.

We are in fact interested in the linear-response regime, where the inhomogeneity of the system is due to a weak static perturbation. We can then introduce the exchange-correlation kernels for the homogeneous electron gas as

$$K_{\mathrm{xc}}^{\sigma \sigma ^{}}(\overline{n},\overline{m};|𝐫𝐫^{}|)\frac{\delta ^2E_{\mathrm{x}c}}{\delta n_\sigma (𝐫)\delta n_\sigma ^{}(𝐫^{})}|_{\mathrm{hg}}$$
(4)
and the local field factors $`G_{\sigma \sigma ^{}}(q)`$ as

$$v_qG_{\sigma \sigma ^{}}(q)d^d𝐫K_{\mathrm{xc}}^{\sigma \sigma ^{}}(r)\mathrm{exp}(i𝐪𝐫),$$
(5)
with $`v_q`$ the Fourier transform of the electron-electron potential. In Eq. (4), after taking the second functional derivative the inhomogeneous spin densities are replaced by those of the homogeneous gas, corresponding to a particle density $`\overline{n}`$ and a magnetization density $`\overline{m}`$.

While the formulation given so far is quite general (within neglect of spin-orbit coupling), in the following we restrict ourselves for simplicity to the paramagnetic state (i.e. $`\overline{m}=0`$). In this case the matrices in Eqs. (4) and (5) can be diagonalized and expressed in terms of the charge and longitudinal-spin response kernels,

$$K_{\mathrm{x}c}^+(\overline{n};|𝐫𝐫^{}|)\frac{\delta ^2E_{\mathrm{x}c}}{\delta n(𝐫)\delta n(𝐫^{})}|_{\mathrm{hpg}}$$
(6)
and

$$K_{\mathrm{x}c}^{}(\overline{n};|𝐫𝐫^{}|)\frac{\delta ^2E_{\mathrm{x}c}}{\delta m(𝐫)\delta m(𝐫^{})}|_{\mathrm{hpg}}.$$
(7)
The corresponding local field factors are $`G_+(q)`$ and $`G_{}(q)`$, say. Notice that in the calculation of $`K_{\mathrm{x}c}^{}(\overline{n};r)`$ the functional derivatives in Eq. (7) must be evaluated on the spin-polarized gas before taking the paramagnetic limit.

The evaluation of the functional derivatives in Eqs. (6) and (7) can be explicitly carried out from Eqs. (1) and (2). The compressibility and spin susceptibility sum rules can be satisfied by making at this point a long-wavelength approximation. This involves, as an instance, the replacement $`\delta \overline{g}(𝐫_1,𝐫^{})/\delta n(𝐫)\delta (𝐫_1𝐫)\overline{g}(|𝐫𝐫^{}|)/n`$. Some straightforward algebra leads to the expressions

$$K_{\mathrm{x}c}^+(\overline{n};r)=\frac{e^2}{r}\left[\overline{g}(r)1+2\overline{n}\frac{\overline{g}(r)}{\overline{n}}+\frac{1}{2}\overline{n}^2\frac{^2\overline{g}(r)}{\overline{n}^2}\right]$$
(8)
and

$$K_{\mathrm{x}c}^{}(\overline{n};r)=\frac{e^2}{r}\left[\frac{1}{2}\overline{n}^2\frac{^2\overline{g}(r)}{\overline{m}^2}|_{\overline{m}=0}\right].$$
(9)
The local field factors are thus given in this approximation by

$$G_+(q)=\left(1+2\overline{n}\frac{}{\overline{n}}+\frac{1}{2}\overline{n}^2\frac{^2}{\overline{n}^2}\right)G(q)$$
(10)
and

$$G_{}(q)=\frac{1}{2}\overline{n}^2\frac{^2}{\overline{m}^2}G(q)|_{\overline{m}=0},$$
(11)
where we have defined

$$G(q)\frac{1}{\overline{n}e^2}_0^{e^2}𝑑\lambda \frac{d^d𝐪^{}}{(2\pi )^d}\frac{v_q^{}}{v_q}\left[S_\lambda (|𝐪𝐪^{}|)1\right].$$
(12)
Here, $`S_\lambda (q)`$ is the static structure factor of the electron gas with a pair potential $`v_\lambda (q)`$ given by $`4\pi \lambda /q^2`$ in $`d=3`$ and by $`2\pi \lambda /q`$ in $`d=2`$. That is,

$$S_\lambda (q)=1+\overline{n}d^d𝐫\left[g_\lambda (r)1\right]\mathrm{exp}(i𝐪𝐫).$$
(13)
Eqs. (10) - (12) are the main new results of the present work.

Let us pause at this point to explicitly show that Eqs. (10) - (13) satisfy the two thermodynamic sum rules. By taking the long-wavelength limit $`q0`$ inside the integral in Eq. (12) we find

$$\underset{q0}{lim}G(q)=\frac{2\epsilon _{xc}(\overline{n},\overline{m})}{\overline{n}v_q}$$
(14)
where

$$\epsilon _{xc}(\overline{n},\overline{m})=\frac{1}{2e^2}_0^{e^2}𝑑\lambda \frac{d^d𝐪^{}}{(2\pi )^d}v_q^{}\left[S_\lambda (q^{})1\right]$$
(15)
is the exchange-correlation energy in the homogeneous, spin-polarized electron gas. Since $`\epsilon _{xc}`$ is equal to the difference $`\epsilon _{gs}\epsilon _0`$ between the ground-state energies of the real and of the non-interacting electron gas, it follows from Eqs. (10) and (14) that

$$\underset{q0}{lim}G_+(q)=\frac{1}{\overline{n}^2v_q}\left(\frac{1}{K_0}\frac{1}{K}\right)$$
(16)
$`K`$ and $`K_0`$ being the corresponding compressibilities. Similarly, from Eqs. (11) and (14) we get

$$\underset{q0}{lim}G_{}(q)=\frac{1}{\overline{n}v_q}\frac{^2\epsilon _{\mathrm{x}c}(\overline{n},\xi )}{\xi ^2}|_{\xi =0}$$
(17)
with $`\xi =\overline{m}/\overline{n}`$ and hence

$$\underset{q0}{lim}G_{}(q)=\frac{\mu _B^2}{v_q}\left(\frac{1}{\chi _P}\frac{1}{\chi _s}\right)$$
(18)
where $`\mu _B`$ is the Bohr magneton, $`\chi _P`$ the Pauli susceptibility and $`\chi _s`$ the spin susceptibility of the interacting electron gas. Equations (16) and (18) are the correct relations between the long-wavelength limit of the static response of the paramagnetic electron gas and the second derivatives of its ground state energy .

Returning to Eqs. (10) - (12), they evidently need supplementing by a method for the evaluation of the electron-pair structure. Such a calculation can be carried out self-consistently by one of two alternative routes: (i) by using the static linear response functions to construct effective spin-dependent electron-electron interactions that yield the electron-pair distribution functions through the solution of an electron-electron scattering problem \[13 - 15\]; or (ii) by constructing dynamic susceptibilities from the static local-field factors and imposing that the fluctuation-dissipation formula relating the electron-pair distribution function to the van Hove dynamic structure factor is satisfied . The former method has already been tested to some extent and shown to yield accurate results for quantum plasmas over a physically significant range of coupling strength . In the following we present and discuss the second method mentioned above, in regard to the dielectric response and charge-charge correlations for electrons in $`d=3`$ and $`d=2`$. The study of spin-spin correlations requires entering the spin-polarized state, as already mentioned, and is left for future work.

In brief, following the work of Singwi et al.  we write an approximate expression for the dynamic dielectric susceptibility $`\chi _c(q,\omega )`$ from the static local-field factor $`G_+(q)`$ as

$$\chi _c(q,\omega )=\frac{\chi _0(q,\omega )}{1v_q[1G_+(q)]\chi _0(q,\omega )}$$
(19)
where $`\chi _0(q,\omega )`$ is the dynamic (Lindhard-Stern) susceptibility of the ideal Fermi gas. The electron-pair structure factor can then be calculated as

$$S(q)=\frac{1}{\pi \overline{n}}_0^{\mathrm{}}𝑑\omega \mathrm{Im}\chi _c(q,\omega ).$$
(20)
Self-consistence between pair structure and dielectric response is ensured by the fact that the local-field factor to be used in Eq. (19) depends on the pair structure according to Eqs. (10) and (12). Of course, Eqs. (19) and (20) hold for each value of $`\lambda `$ and must be solved together with Eqs. (10) and (12) up to the physical value of the coupling strength in the system.

The results of this calculation for a weakly coupled electron gas in $`d=3`$ are shown in Figures 1 and 2. It is seen from Figure 1 that the local-field factor $`G_+(q)`$ obtained from the present theoretical approach is quite close to the QMC data of Moroni et al.  over a substantial range of values for $`q/k_F`$. Important deviations from these data are found only at high momenta $`q>2k_F`$, where the details of the dielectric response have little relevance for most practical purposes: in fact, in our approach the asymptotic value of $`G(q)`$ at large momenta is a constant determined by the quantity $`1\overline{g}(r=0)`$, rather than showing a leading term of order $`q^2`$. It is also seen from Figure 1 that our self-consistent results are in good agreement with the parametrized expression of $`G_+(q)`$ given by Ichimaru and Utsumi (IU) , who combined QMC data on the compressibility with a ladder diagram calculation of $`g(r=0)`$ and a previous dielectric formulation by Utsumi and Ichimaru . The peak of $`G_+(q)`$ for momenta approaching $`2k_F`$, which in their formulation arose from a logarithmic term associated with exchange, comes in our approach from a logarithmic factor remaining inside the integral in Eq. (12) after angular integration in $`d=3`$. This peak is absent in the so-called STLS dielectric theory of Singwi et al. , as can again be seen from Figure 1.

Our results for the pair distribution function $`g(r)`$ at full self-consistence in $`d=3`$ are reported in Figure 2, in comparison with QMC data kindly provided by P. Ballone (unpublished) and with the results of the STLS theory. Evidently, the present results for the electron-pair structure are excellent in this weak-coupling regime. With increasing coupling strength the above-mentioned peak in $`G_+(q)`$, however, introduces unwanted oscillations in $`g(r)`$. It appears that as the coupling increases the frequency dependence of the local-field factors  may become important in the calculation of pair correlations via the fluctuation-dissipation theorem. Much more satisfactory results are instead obtained by calculating these correlations through the solution of an electron-electron scattering problem with effective scattering potentials embodying the many-body effects from the static local-field factors .

Finally, Figure 3 reports similar results for the local-field factor $`G_+(q)`$ in a weakly coupled electron gas in $`d=2`$. In this case satisfying the compressibility sum rule ensures that the local-field factor from QMC data  is reproduced almost up to $`q2k_F`$. Again a peak is found to be present in $`G_+(q)`$ for $`q2k_F`$, which is absent in an STLS formulation.

In summary, we have proposed a self-consistent theoretical approach to the evaluation of the local-field factors entering the dielectric and longitudinal-spin response of an interacting electron gas and given some examples of the results that it predicts for the dielectric response and the charge-charge correlations at weak coupling. In the present formulation the form of the local-field factors is very accurate in the most important range of momenta where the thermodynamic sum rules dominate the physical behavior, but may still be too sensitive to exchange effects at momenta of order $`2k_F`$. For this reason, structural self-consistence appears to be best enforced at strong coupling through the use of the local-field factors in constructing effective many-body scattering potentials.

Ackowledgements

This work was partially funded by MURST under the PRIN2001 Initiative. We wish to thank the Condensed Matter Group of the Abdus Salam International Centre for Theoretical Physics in Trieste for their hospitality during the final stages of this work. We are indebted with Professor P. Ballone for providing us with the QMC data reported in Figure 2.

References

 See, e.g. D. Ceperley, Nature 397 (1999) 386.

 R.M. Dreizler, E.K.U. Gross, Density Functional Theory, An Approach to the Quantum Many-Body Problem

(Springer, Berlin 1990).

 S. Yarlagadda, G.F. Giuliani, Phys. Rev. B 40 (1988) 5432 and B 49 (1994) 14188.

 V.M. Pudalov, M.E. Gershenson, H. Kojima, N. Butch, E.M. Dizhur, G. Brunthaler, A. Prinz, G. Bauer,

Phys. Rev. Lett. 88 (2002) 196404.

 D.M. Ceperley, B.J. Alder, Phys. Rev. Lett. 45 (1980) 566.

 B. Tanatar, D.M. Ceperley, Phys. Rev. B 39 (1989) 5005.

 S. Moroni, D.M. Ceperley, G. Senatore, Phys. Rev. Lett. 75 (1995) 689.

 G. Ortiz, M. Harris, P. Ballone, Phys. Rev. Lett. 82 (1999) 5317.

 D. Varsano, S. Moroni, G. Senatore, Europhys. Lett. 53 (2001) 348.

 P. Vashishta, K.S. Singwi, Phys. Rev. B 6 (1972) 875 and 4883.

 S. Ichimaru, Rev. Mod. Phys. 54 (1982) 1017.

 B. Davoudi, M. Polini, G.F. Giuliani, M.P. Tosi, Phys. Rev. B 64 (2001) 153101 and 233110.

 A.W. Overhauser, Can. J. Phys. 73 (1995) 683.

 P. Gori-Giorgi, J.P. Perdew, Phys. Rev. B 64 (2001)155102.

 B. Davoudi, M. Polini, R. Asgari, M.P. Tosi, Phys. Rev. B 66 (2002) 075110.

 K.S. Singwi, M.P. Tosi, R.H. Land. A. Sjölander, Phys. Rev. 176 (1968) 589.

 B. Davoudi, M. Polini, R. Asgari, M.P. Tosi, cond-mat/0206456.

 S. Ichimaru, K. Utsumi, Phys. Rev. B 24 (1981) 7385.

 R. Nifosì, S. Conti, M.P. Tosi, Phys. Rev. B 58 (1998) 12758.


format: text

text:
# The Transition State in Magnetization Reversal

## Abstract

We consider a magnet with uniaxial anisotropy in an external magnetic field along the anisotropy direction, but with a field magnitude smaller than the coercive field. There are three representative magnetization configurations corresponding to three extrema of the free energy. The equilibrium and metastable configurations, which are magnetized approximately parallel and antiparallel to the applied field, respectively, both correspond to local free-energy minima. The third extremum configuration is the saddle point separating these minima. It is also called the transition state for magnetization reversal. The free-energy difference between the metastable and transition-state configurations determines the thermal stability of the magnet. However, it is difficult to determine the location of the transition state in both experiments and numerical simulations. Here it is shown that the computational Projective Dynamics method, applied to the time dependence of the total magnetization, can be used to determine the transition state. From large-scale micromagnetic simulations of a simple model of magnetic nanowires with no crystalline anisotropy, the magnetization associated with the transition state is found to be linearly dependent on temperature, and the free-energy barrier is found to be dominated by the entropic contribution at reasonable temperatures and external fields. The effect of including crystalline anisotropy is also discussed. Finally, the influence of the spin precession on the transition state is determined by comparison of the micromagnetic simulations to kinetic Monte Carlo simulations of precession-free (overdamped) dynamics.

Since magnetic storage depends on the ability to quickly assign a magnetic orientation to a specific region of a medium, in which spontaneous reorientation is suppressed, understanding the process of magnetization reversal is technologically important. In magnetic fields smaller than the coercive value, the two states of the magnet important to information storage are free-energy minima separated by a free-energy barrier. The minimum corresponding to a magnetization parallel to the field is truly stable, while the minimum corresponding to the antiparallel magnetization is higher in energy and is therefore metastable. The free-energy maximum along the most likely path between the minima is a saddle point. To effectively engineer processes such as hybrid recording,  which use lower-than-coercive applied fields to assign magnetic orientations in high-coercivity magnetic materials, a thorough understanding of the magnetization reversal is needed. Properties of the free energy near the minima and saddle point often control the nonequilibrium dynamics of a system. For example, the free-energy difference between a minimum and the saddle point, the barrier height, is a measure of the stability of the magnetization associated with that minimum, while the curvature of the free energy near a minimum is a measure of the “attempt frequency” of escapes over the barrier. While the free-energy minima can be easily located as local maxima in histograms of the state of the system, the saddle point has proven much harder to measure. In this paper we present a method based on the Projective Dynamics method  for determining the saddle point in magnetization reversal of nanoscale magnets, and then investigate the free-energy barrier associated with the process.

The particular magnetic system considered in this paper is based on iron nanomagnets fabricated using STM-assisted chemical vapor deposition.  These magnetic pillars are modeled by a one-dimensional array of $`17`$ spins along the $`z`$ axis, each a unit vector $`\widehat{S}_i`$ representing the local orientation of the magnetization. The total energy of the pillar is given by

$$E=\frac{J}{2}\underset{i,j}{}\widehat{S}_i\widehat{S}_j\frac{D}{2}\underset{i,ji}{}\widehat{S}_i^t𝐓_{i,j}\widehat{S}_jK\underset{i}{}(S_{i,z})^2+B\underset{i}{}S_{i,z},$$
(1)
where $`J`$ is the exchange energy, $`K`$ is the uniaxial anisotropy energy, $`B`$ is the strength of the external field oriented parallel to $`\widehat{z}`$, $`D`$ is the strength of the dipole-dipole interactions in energy units, and $`𝐓_{i,j}=(3\widehat{z}\widehat{z}^t\mathrm{𝟏})/|ji|^3`$ is the dimensionless dipole-dipole interaction tensor. The sum for the exchange energies is over nearest neighbors and includes a self interaction so that the exchange energy (and the associated effective field) is zero for parallel neighbors. For the $`17`$-spin iron nanopillars, discussed previously in Ref. , the dimensionless energy corresponds to $`J`$$`=`$$`1.6\times 10^{12}`$ erg, $`D`$$`=`$$`4.1\times 10^{12}`$ erg, and $`B`$$`=`$$`1.9\times 10^{12}`$ erg for a field of $`1000`$ Oe. Dipole-dipole interactions along the pillar provide a strong uniaxial anisotropy, even for $`K`$$`=`$$`0`$.

For micromagnetic dynamics, each vector precesses around a local field $`\stackrel{}{H}_i=dE/d\widehat{S}_i`$ according to the Landau-Lifshitz-Gilbert (LLG) equation

$$\frac{d\widehat{S}_i}{dt}=\frac{\gamma _0}{1+\alpha ^2}\widehat{S}_i\times \left[\stackrel{}{H}_i\alpha \widehat{S}_i\times \stackrel{}{H}_i\right],$$
(2)
where the scaled electron gyromagnetic ratio $`\gamma _0=9.26\times 10^{21}`$ Hz/erg for this system. The phenomenological damping parameter $`\alpha =0.1`$ was chosen to give underdamped dynamics.

Previously,  we have shown that the Projective Dynamics method  can be used to locate the saddle point. The computational Projective Dynamics method involves projecting the original description of the dynamics in terms of a large number of variables onto a completely stochastic description in terms of one or two variables. In this paper, Eq (1) has $`34`$ independent variables which are projected onto a single, slowly varying variable: the $`z`$-component of the total magnetization, $`M_z.`$ Furthermore, the values of $`M_z`$ are binned, and the transition rates between bins are measured. For instance, the probability that $`M_z`$ starts a given time interval in one bin and ends the interval in the adjacent bin corresponding to smaller values of $`M_z`$ is called the “growth” probability, $`P_{\mathrm{grow}}`$, since it corresponds to an increase in the volume of stable magnetization. The probability of moving to the opposite neighboring bin is $`P_{\mathrm{shrink}}.`$

The measured $`P_{\mathrm{grow}}`$ and $`P_{\mathrm{shrink}}`$ for an applied field of $`H`$$`=`$$`1000`$ Oe, a temperature of $`T`$$`=`$$`10`$ K, and $`K`$$`=`$$`0`$ are shown in the inset of Fig. 1 as the solid and broken curves, respectively. For magnetizations with $`P_{\mathrm{grow}}`$$`>`$$`P_{\mathrm{shrink}}`$, on average the magnetization decreases with time, while it increases, on average, for magnetizations with $`P_{\mathrm{shrink}}`$$`>`$$`P_{\mathrm{grow}}`$. Where $`P_{\mathrm{grow}}`$$`=`$$`P_{\mathrm{shrink}}`$ the average rate of change is zero, and a local minimum or maximum in the free energy occurs. The right-most crossing of $`P_{\mathrm{grow}}`$ and $`P_{\mathrm{shrink}}`$ is the free-energy minimum corresponding to the metastable magnetization antiparallel to the applied field. The crossing associated with the free-energy minimum of the stable magnetization (near $`M_z`$$`=`$$`1`$) is not shown. The left-most crossing shown in the figure corresponds to the free-energy saddle point separating the metastable and stable wells.

The value of $`M_z`$ at the saddle point for $`H`$$`=`$$`1000`$ Oe and $`K`$$`=`$$`0`$ is shown in Fig. 1 vs $`T`$ as circles with error bars. These values were estimated from the intersection of lines fit to $`P_{\mathrm{grow}}`$ and $`P_{\mathrm{shrink}}`$ in the region near the crossing. The measurement errors were taken to be $`\pm 0.01,`$ based on the size of the region where $`P_{\mathrm{grow}}`$ $``$ $`P_{\mathrm{shrink}}`$. For low $`T`$, the estimated value of $`M_z`$ depends almost linearly on temperature. Good agreement exists between the estimated values and the line of best fit, which was determined from the data for $`T`$$``$$`100`$ K and is shown as the solid line in Fig. 1.

The Projective Dynamics method can also be used to estimate the free-energy barrier for the reversal process. In equilibrium, the total time spent in the $`i`$th $`M_z`$ bin, $`h(i)`$, is related to the growing and shrinking probabilities by

$$h(i)=\left[1+P_{\mathrm{shrink}}(i1)h(i1)\right]/P_{\mathrm{grow}}(i),h(1)=1/P_{\mathrm{grow}}(1).$$
(3)
The time $`h(i)`$ is also related to the free energy by the Boltzmann factor $`h(i)\mathrm{exp}(F(i)/k_BT).`$ Taking the bin containing the saddle point to be $`i_\mathrm{s}`$, and that containing the metastable minimum to be $`i_\mathrm{m},`$ the free-energy barrier is $`\mathrm{\Delta }F=k_BT\mathrm{ln}[h(i_\mathrm{m})/h(i_\mathrm{s})].`$ The measured $`\mathrm{\Delta }F`$ for $`H`$$`=`$$`1000`$ Oe and $`K`$$`=`$$`0`$ are shown vs temperature as the circles in Fig. 2. The measured $`\mathrm{\Delta }F`$ is not constant, as would be expected in the commonly assumed Arrhenius model of thermally activated processes. What is even more striking is that $`\mathrm{\Delta }E`$, the difference in average energy between the bin containing the saddle point and that containing the metastable minimum as calculated by Eq. (1), is always negative. (The absolute value of $`\mathrm{\Delta }E`$ is of the same order of magnitude as $`\mathrm{\Delta }F,`$ but generally lies within one standard deviation of zero.) This is consistent with $`E`$ vs $`M_z`$ shown in the inset of Fig. 2 (along with the contribution from the various terms) for one reversal at $`H`$$`=`$$`1000`$ Oe, $`T`$$`=`$$`10`$ K, and $`K`$$`=`$$`0`$. The total energy is seen to be nearly constant for $`M_z`$$`>`$$`0.80,`$ which is the region around the barrier. Since the free energy is the sum of $`E`$ and $`TS`$, where $`S`$ is the entropy, it is reasonable to conclude that the dominant contribution to the positive free-energy barrier is a decrease in entropy going from the metastable minimum to the saddle point.

It should be noted that $`\mathrm{\Delta }E`$ is measured from the total energy averaged in bins of $`M_z`$, and it is possible that the saddle point is associated with extreme values of $`E`$ within the bin. In that case, even though $`\mathrm{\Delta }E`$ measured from the average energy of the bin is negative, it could be possible that the $`\mathrm{\Delta }E`$ associated with the reversal is positive. However, no support for extreme values of $`E`$ is seen in $`E`$ vs $`M_z`$ or $`E`$ vs $`t`$ for individual reversals under a variety of conditions.

The effect of a weaker applied field was also investigated. For $`H`$$`=`$$`900`$ Oe and $`K`$$`=`$$`0`$ results are shown in both figures as squares. There is a small decrease in $`M_z`$ at the saddle point, and a significant increase in the free-energy barrier. These results are what one normally expects when the field is lowered, and the difference in energies between the metastable and stable magnetizations decreases. Results for $`H`$$`=`$$`1000`$ Oe and an anisotropy energy of $`K`$$`=`$$`1.9\times 10^{13}`$ erg are shown in the figures as diamonds. The broken line in Fig. 1 is a best fit, which shows that $`M_z`$ at the saddle point is much less temperature dependent, than in the $`K`$$`=`$$`0`$ case. The free-energy barrier is increased by increasing $`K`$. Although the estimates of $`\mathrm{\Delta }F`$ are more uncertain for $`K`$$`=`$$`1.9\times 10^{13}`$ erg (a consequence of decreased sampling due to the higher barrier), and data are available only for $`T`$$``$$`40`$ K, the data indicate that the temperature dependence of $`\mathrm{\Delta }F`$ may be suppressed by nonzero $`K`$. The measured $`\mathrm{\Delta }E`$ are negative, even for this value of $`K`$.

The reversal process was also simulated with a precession-free kinetic Monte Carlo (MC) method, which corresponds to the overdamped limit of the LLG equation,  to estimate the effect of the underdamped precession of the spins. In this dynamic, one spin is selected at random and is tentatively displaced by a step uniformly distributed on a sphere of radius $`R`$$`=`$$`0.005`$. Using Eq. (1) to calculate the energies, the displacement is accepted or rejected using the Metropolis method. The spins are normalized after each move to conserve their length. Monte Carlo simulations were performed only for $`H`$$`=`$$`1000`$ Oe and $`K`$$`=`$$`0.`$ The $`M_z`$ of the saddle point, the triangles in Fig. 1, are larger than those found using the LLG dynamics, but the dependence on temperature appears to be linear. The free-energy barrier is smaller than that measured for the LLG dynamics at high temperature, but the difference decreases as the temperature is decreased. Even for precession-free MC dynamics, all measured $`\mathrm{\Delta }E`$ are negative.

In summary, details of the magnetization reversal in underdamped, nanoscale magnets have been investigated with Projective Dynamics. The magnetization at the saddle point has been measured and found to decrease linearly with temperature for $`T`$$`<`$$`100`$ K. In contrast to the Arrhenius model, which assumes a temperature-independent barrier, the measured free-energy difference between the saddle point and the metastable magnetization is found to be temperature dependent. For the physically reasonable parameters considered here, the difference in the average energy between the saddle point and the metastable magnetization is negative, while the difference in the free energy is positive. From this we conclude that the free-energy barrier under these conditions is due to reduced entropy at the saddle point. Although the temperature dependence of the barrier is weaker, Monte Carlo simulations of overdamped dynamics show the same dominance of entropic contributions to the free-energy barrier

This work was supported by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory, managed by UT-Battelle, LLC for the U.S. Department of Energy under Contract No. DE-AC05-00OR22725, by the Ames Laboratory, which is operated for the U.S. Department of Energy by Iowa State University under Contract No. W-7405-82, by the National Science Foundation under Grant 0120310, and by Florida State University through CSIT and MARTECH.


text:
# On the largest eigenvalue of a random subgraph of the hypercube 11footnote 1 AMS 2000 subject classification: 05C80; keywords and phrases: random graph, hypercube, largest eigenvalue, Krivelevich-Sudakov theorem

## 1 Introduction and formulation of results

Let $`Q^n`$ be a graph whose vertices are all the vectors $`\left\{x=(x_1,\mathrm{},x_n)\right|x_i\{0,1\}\}`$ and two vectors $`x`$ and $`y`$ are adjacent if they differ in exactly one coordinate, i.e., $`_i|x_iy_i|=1`$. We call $`Q^n`$ the $`n`$-dimensional cube or simply the $`n`$-cube. Clearly $`Q^n`$ is an $`n`$-regular, bipartite graph of order $`2^n`$. In this paper we study random subgraphs of the $`n`$-cube. A random subgraph $`G(Q^n,p)`$ is a discrete probability space composed of all subgraphs of $`n`$-cube, where each edge of $`Q^n`$ appears randomly and independently with probability $`p=p(n)`$. Sometimes with some abuse of notation we will refer to a random subgraph $`G(Q^n,p)`$ as a graph on $`2^n`$ vertices generated according to the distribution described above. Usually asymptotic properties of random graphs are of interest. We say that a graph property $`𝒜`$ holds almost surely, or a.s. for brevity, in $`G(Q^n,p)`$ if the probability that $`G(Q^n,p)`$ has property $`𝒜`$ tends to one as $`n`$ tends to infinity. Necessary background information on random graphs in general and random subgraphs of $`n`$-cube can be found in .

Random subgraphs of the hypercube were studied by Burtin , Erdös and Spencer , Ajtai, Komlós and Szemerédi  and Bollobás , among others. In particular it was shown that a giant component emerges shortly after $`p=1/n`$ () and the graph becomes connected shortly after $`p=1/2`$ (, , ). Recently the model has become of interest in mathematical biology (, , ). In particular it appears ( see ,) that random graphs play an important role in a general model of a population evolving over a network of selectively neutral genotypes. It has been shown that the population’s limit distribution on the neutral network is solely determined by the network topology and given by the principal eigenvector of the network’s adjacency matrix. Moreover, the average number of neutral mutant neighbors per individual is given by the spectral radius.

The subject of this paper is the asymptotic behavior of the largest eigenvalue of the random graph $`G(Q^n,p)`$. The adjacency matrix of $`G`$ is an $`2^n\times 2^n`$ matrix $`A`$ whose entries are either one or zero depending on whether the edge $`(x,y)`$ is present in $`G`$ or not. $`A`$ is a random real symmetric matrix with the eigenvalues denoted by $`\lambda _1\lambda _2\mathrm{}\lambda _{2^n}`$. It follows from the Perron-Frobenius theorem that the largest eigenvalue is equal to the spectral norm of $`A`$, i.e. $`\lambda _{\mathrm{max}}(G)=\lambda _1(G)=A=\mathrm{max}_j|\lambda _j|`$. Note also that for a subgraph of the $`n`$-cube, or in general, for any bipartite graph, $`\lambda _k(G)=\lambda _{|V|k}(G),k=1,2,\mathrm{}`$ and in particular $`|\lambda _{\mathrm{min}}(G)|=\lambda _{\mathrm{max}}(G)`$. It is easy to observe that for every graph $`G=(V,E)`$ its largest eigenvalue $`\lambda _1(G)`$ is always squeezed between the average degree of $`G`$, $`\overline{d}=_{vV}d_G(v)/|V|`$ and its maximal degree $`\mathrm{\Delta }(G)=\mathrm{max}_{vV}d_G(v)`$. In some situtaions these two bounds have the same asymptotic value which determines the behavior of the largest eigenvalue. For example, this easily gives the asymptotics of the largest egenvalue of a random subgraph $`G(n,p)`$ of a complete graph of order $`n`$ for $`p\mathrm{log}n/n`$. On the other hand, in our case there is a gap between average and maximal degree of random graph $`G(Q^n,p)`$ for all values of $`p<1`$ and therefore it is not immediately clear how to estimate its largest eigenvalue.

Here we determine the asymptotic value of the largest eigenvalue of sparse random subgraphs of $`n`$-cube. To understand better the result, observe that if $`\mathrm{\Delta }`$ denotes a maximal degree of a graph $`G`$, then $`G`$ contains a star $`S_\mathrm{\Delta }`$ and therefore $`\lambda _1(G)\lambda _1(S_\mathrm{\Delta })=\sqrt{\mathrm{\Delta }}`$. Also, as mentioned above $`\lambda _1(G)`$ is at least as large as the average degree of $`G`$. As for all values of $`p(n)n^12^n`$, a.s. $`|E(G(Q^n,p))|=(1+o(1))pn2^n`$, we get that a.s. $`\lambda _1(G(Q^n,p))(1+o(1))np`$. Combining the above lower bounds, we get that a.s. $`\lambda _1(G(Q^n,p))(1+o(1))\mathrm{max}(\sqrt{\mathrm{\Delta }},np)`$. It turns out this lower bound can be matched by an upper bound of the same asymptotic value, as given by the following theorem:

###### Theorem 1.1

Let $`G(Q^n,p)`$ be a random subgraph of the $`n`$-cube and let $`\mathrm{\Delta }`$ be the maximum degree of $`G`$. Then almost surely the largest eigenvalue of the adjacency matrix of $`G`$ satisfies

$$\lambda _1(G)=\left(1+o(1)\right)\mathrm{max}(\sqrt{\mathrm{\Delta }},np),$$

where the $`o(1)`$ term tends to zero as $`\mathrm{max}(\mathrm{\Delta }^{1/2}(G),np)`$ tends to infinity.

As the asymptotic value of the maximal degree of $`G(Q^n,p)`$ can be easily determined for all values of $`p(n)`$ (see Lemma 2.1), the above theorem enables us to estimate the asymptotic value of $`\lambda _1(G(Q^n,p))`$ for all relevant values of $`p`$. This theorem is similar to the recent result of Krivelevich and Sudakov  on the largest eigenvalue of a random subgraph $`G(n,p)`$ of a complete graph of order $`n`$.

The rest of this paper is organized as follows. In the next section we gather some necessary technical lemmas about random subgraphs of $`n`$-cube. Section 3 is devoted to the proof of the main theorem. Section 4, the last section of the paper, contains some concluding remarks.

Throughout the paper we will systematically omit floor and ceiling signs for the sake of clarity of presentation. All logarithms are natural. We will frequently use the inequality $`\left(\begin{array}{c}a\\ b\end{array}\right)\left(ea/b\right)^b`$. Also we use the following standard notations: $`a_n=\mathrm{\Theta }(b_n),a_n=O(b_n)`$ and $`a_n=\mathrm{\Omega }(b_n)`$ for $`a_n>0,b_n>0`$ as $`n\mathrm{}`$ if there exist constants $`C_1`$ and $`C_2`$ such that $`C_1b_n<a_n<C_2b_n,a_n<C_2b_n`$ or $`a_n>C_1b_n`$ respectively. The equivalent notations $`a_n=o(b_n)`$ and $`a_nb_n`$ mean that $`a_n/b_n0`$ as $`n\mathrm{}`$. We will say that an event $`\mathrm{{\rm Y}}_n`$, depending on a parameter $`n`$, holds almost surely if $`\mathrm{Pr}(\mathrm{{\rm Y}}_n)1`$ as $`n\mathrm{}`$ (please note this phrase, very common in the literature on random structures, has a different meaning in probability theory, where it means that with probability one all but a finite number of events $`\mathrm{{\rm Y}}_n`$ take place).

## 2 Few technical lemmas

In this section we establish some properties of random subgraphs of the $`n`$-cube which we will use later in the proof of our main theorem. First we consider the asymptotic behavior of the maximal degree of $`G(Q^n,p)`$. It is not difficult to show that if $`p`$ is a constant less than $`1/2`$ then a.s. $`\mathrm{\Delta }(G)=(1+o(1))cn`$, where $`c`$ satisfies the equation $`\mathrm{log}2+c\mathrm{log}p+(1c)\mathrm{log}(1p)=c\mathrm{log}c+(1c)\mathrm{log}(1c)`$ and $`\mathrm{\Delta }(G)=(1+o(1))n`$ for $`p1/2`$. We omit the proof of this statement since for our purposes it is enough to have $`\sqrt{\mathrm{\Delta }(G)}=o(np)`$ which follows immediately from the fact that $`\mathrm{\Delta }(G)n`$. The case when $`p=o(1)`$ is studied in more details in the following lemma.

###### Lemma 2.1

Let $`G=G(Q^n,p)`$ be a random subgraph of the $`n`$-cube. Denote by

$$\kappa (n)=\mathrm{max}\left\{k:2^n\left(\begin{array}{c}n\\ k\end{array}\right)p^k(1p)^{nk}1\right\}.$$

Then the following statements hold.

$`(i)`$ If $`p=o(1)`$ and $`p`$ is not exponentially small in $`n`$ then almost surely $`\kappa (n)1\mathrm{\Delta }(G)\kappa (n)+1`$.

$`(ii)`$ If $`p=\mathrm{\Theta }(2^{n/k}n^1)`$, then $`2^n\left(\begin{array}{c}n\\ k\end{array}\right)p^k(1p)^{nk}=\mathrm{\Theta }(1)`$ and $`\kappa (n)=k1`$ or $`k`$. Also almost surely $`\mathrm{\Delta }(G)`$ is either $`k1`$ or $`k`$.

$`(iii)`$ If $`p`$ is exponentially small, but not proportional to $`2^{n/k}n^1,`$ then $`\kappa (n)=\left[\frac{n\mathrm{log}2}{\mathrm{log}(p^1)\mathrm{log}n}\right]`$ and almost surely $`\mathrm{\Delta }(G)=\kappa (n)`$.

Proof. Let $`X_k`$ be the number of vertices of $`G(Q^n,p)`$ with degree larger than $`k1`$. Then $`X_k=_{vQ^n}I_v,`$ where $`I_v`$ is the indicator random variable of the event that $`\mathrm{deg}(v)k`$. One can easily calculate the expectation $`𝐄X_k=2^n_{lk}\left(\begin{array}{c}n\\ l\end{array}\right)p^l(1p)^{nl}.`$ Also note that $`Q^n`$ is bipartite and therefore has independent set $`X`$ of size $`2^{n1}`$. By definition, the events that $`d(v)<k`$ are mutually independent for all $`vX`$. Therefore we obtain that

$$\mathrm{Pr}\left(X_k=0\right)\underset{vX}{}\mathrm{Pr}\left(d(v)<k\right)=\underset{vX}{}\left(1𝐄I_v\right)\mathrm{exp}\left(\underset{vX}{}𝐄I_v\right)=\mathrm{exp}\left(𝐄X_k/2\right).$$
(1)
Let us now consider the case (i) in more detail. We have that

$$2^{nO(np)}(n/k)^kp^k2^n\left(\begin{array}{c}n\\ k\end{array}\right)p^k(1p)^{nk}2^n(en/k)^kp^k.$$

Therefore it is easy to check that $`\kappa (n)`$ must satisfy the inequalities

$$\frac{n\mathrm{log}2\left(11/\mathrm{log}\mathrm{log}(p^1)\right)}{\mathrm{log}(p^1)}\kappa (n)\frac{n\mathrm{log}2\left(1+1/\mathrm{log}\mathrm{log}(p^1)\right)}{\mathrm{log}(p^1)}.$$

By definition, $`𝐄X_{\kappa (n)}1`$. Elementary computations show that $`𝐄X_{k+1}=(1+o(1))\frac{p\mathrm{log}(p^1)}{\mathrm{log}2}𝐄X_k`$ for $`k=(1+o(1))\kappa (n)`$ which imply $`𝐄X_{\kappa (n)1}(1+o(1))\frac{\mathrm{log}2}{p\mathrm{log}(p^1)}`$. Therefore by (1), we have that

$`\mathrm{Pr}\left(\mathrm{\Delta }(G)<\kappa (n)1\right)`$ $`=`$ $`\mathrm{Pr}\left(X_{\kappa (n)1}=0\right)\mathrm{exp}\left({\displaystyle \frac{𝐄X_{\kappa (n)1}}{2}}\right)`$
$``$ $`\mathrm{exp}\left((1+o(1)){\displaystyle \frac{\mathrm{log}2}{p\mathrm{log}(p^1)}}\right)=o(1).`$
On the other hand, since $`𝐄X_{\kappa (n)+1}1+o(1)`$ we have that $`𝐄X_{\kappa (n)+2}(1+o(1))\frac{p\mathrm{log}(p^1)}{\mathrm{log}2}=o(1)`$. Thus by Markov’s inequality we conclude that a.s. $`X_{\kappa (n)+2}=0`$ and therefore almost surely $`\kappa (n)1\mathrm{\Delta }(G)\kappa (n)+1`$.

Now consider the case (ii). Since $`p(n)=\mathrm{\Theta }(2^{n/k}n^1)`$ we have that $`2^n\left(\begin{array}{c}n\\ k\end{array}\right)p^k(1p)^{nk}=\mathrm{\Theta }(1)`$ and $`\kappa (n)=k1`$ or $`k`$. Also it is easy to check that $`𝐄X_{k+1}=\mathrm{\Theta }(2^{n/k})=o(1)`$ and $`𝐄X_{k1}=\mathrm{\Theta }(2^{n/k})`$. Therefore by (1) we have that $`\mathrm{Pr}\left(\mathrm{\Delta }(G)<k1\right)\mathrm{exp}\left(𝐄X_{k1}/2\right)=o(1)`$ and by Markov’s inequality $`\mathrm{Pr}\left(\mathrm{\Delta }(G)k+1\right)=o(1)`$.

Finally suppose that $`p(n)`$ is exponentially small but not proportional to $`2^{n/k}n^1`$ for any $`k1`$. Then it is rather straightforward to check that $`\kappa (n)=\left[\frac{n\mathrm{log}2}{\mathrm{log}(p^1)\mathrm{log}n}\right]`$ and $`𝐄X_{\kappa (n)+1}1𝐄X_{\kappa (n)}`$. Therefore, again using (1) and Markov’s inequality, we conclude that $`\mathrm{Pr}\left(\mathrm{\Delta }(G)<\kappa (n)\right)=o(1)`$ and $`\mathrm{Pr}\left(\mathrm{\Delta }(G)\kappa (n)+1\right)=o(1)`$. Thus almost surely $`\mathrm{\Delta }(G)=\kappa (n)`$. This completes the proof.

Next we need the following lemma, which shows that a.s. $`G`$ cannot have a large number of vertices of high degree too close to one another. More precisely the following is true.

###### Lemma 2.2

Let $`G(Q^n,p)`$ be a random subgraph of $`n`$-cube. Then almost surely

$`(i)`$ For every $`0<p1`$ and for any two positive constant $`a`$ and $`b`$ such that $`a+b>1`$ and $`n^b6np`$, $`G`$ contains no vertex which has within distance one or two at least $`n^a`$ vertices of $`G`$ with degree $`n^b`$.

$`(ii)`$ For $`pn^{2/3}`$ and any constant $`a>0`$, $`G`$ contains no vertex which has within distance one or two at least $`n^a/p`$ vertices of $`G`$ with degree $`np+np/\mathrm{log}n`$.

Proof. We prove lemma for the case of vertices of distance two, the case of vertices of distance one can be treated similarly. Note that since the $`n`$-cube is a bipartite graph the vertices which are within the same distance from a given vertex in $`Q^n`$ are not adjacent.

$`(𝐢)`$ Let $`X`$ be the number of vertices of $`G`$ which violate condition (i). To prove the statement we estimate the expectation of $`X`$. Clearly we can choose a vertex $`v`$ of the $`n`$-cube in $`2^n`$ ways. Since there are at most $`n^2`$ vertices in $`Q^n`$ within distance two from $`v`$ we have at most $`\left(\begin{array}{c}n^2\\ n^a\end{array}\right)`$ possibilities to chose a subset $`S`$ of size $`n^a`$ of vertices which will have degree at least $`n^b`$. The probability that the degree of some vertex in $`S`$ is at least $`n^b`$ is bounded by $`\left(\begin{array}{c}n^2\\ n^b\end{array}\right)p^{n^b}`$. Note that these events are mutually independent, since $`S`$ contains no edges of the $`n`$-cube. Therefore, using that $`a+b>1`$ and $`b>0`$, we obtain that

$$𝐄(X)2^n\left(\begin{array}{c}n^2\\ n^a\end{array}\right)\left(\left(\begin{array}{c}n^2\\ n^b\end{array}\right)p^{n^b}\right)^{n^a}2^nn^{2n^a}\left(\left(\frac{enp}{n^b}\right)^{n^b}\right)^{n^a}2^{n+2n^a\mathrm{log}_2n}\mathrm{\hspace{0.17em}2}^{n^{a+b}}=o(1).$$

Thus by Markov’s inequality we conclude that almost surely no vertex violates condition (i).

$`(\mathrm{𝐢𝐢})`$ Let again $`X`$ be the number of vertices of $`G`$ which violate condition (ii). Similarly as before we have $`2^n`$ choices for vertex $`v`$ and at most $`\left(\begin{array}{c}n^2\\ n^a/p\end{array}\right)`$ choices for set $`S`$ of vertices within distance two from $`v`$ which will have degree $`np+np/\mathrm{log}n`$. Since for all vertices $`vG`$ the degree $`d(v)`$ is binomially distributed with parameters $`n`$ and $`p`$, then by a standard large deviation inequality (cf. , e.g., , Appendix A)

$$\mathrm{𝐏𝐫}\left[d(v)t=np+np/\mathrm{log}n\right]e^{(tnp)^2/2np+(tnp)^3/2(np)^2}=e^{(1+o(1))np/(2\mathrm{log}^2n)}.$$

As we already mentioned, the events that vertices in $`S`$ have degree $`np+np/\mathrm{log}n`$ are mutually independent. Therefore, using that $`pn^{2/3}`$ and $`a>0`$, we conclude that

$`𝐄(X)`$ $``$ $`2^n\left(\begin{array}{c}n^2\\ n^a/p\end{array}\right)\left(e^{(1+o(1))np/(2\mathrm{log}^2n)}\right)^{n^a/p}2^nn^{2n^a/p}e^{(1+o(1))n^{1+a}/(2\mathrm{log}^2n)}`$
$``$ $`2^ne^{2n^{a+2/3}\mathrm{log}n}e^{(1+o(1))n^{1+a}/(2\mathrm{log}^2n)}=o(1).`$
Thus we can complete the proof of the lemma using again Markov’s inequality.

## 3 Proof of the theorem

In this section we present our main result. We start by listing some simple properties of the largest eigenvalue of a graph, that we will use later in the proof. Most of these easy statement can be found in Chapter 11 of the book of Lovász .

###### Proposition 3.1

Let $`G`$ be a graph on $`n`$ vertices and $`m`$ edges and with maximum degree $`\mathrm{\Delta }`$. Let $`\lambda _1(G)`$ be the largest eigenvalue of the adjacency matrix of $`G`$. Then is has the following properties.

$`\mathrm{max}(\sqrt{\mathrm{\Delta }},\frac{2m}{n})\lambda _1(G)\mathrm{\Delta }`$.

If $`E(G)=_iE(G_i)`$ then $`\lambda _1(G)_i\lambda _1(G_i)`$. If in addition graphs $`G_i`$ are vertex disjoint, then $`\lambda _1(G)=\mathrm{max}_i\lambda _1(G_i)`$

If $`G`$ is a bipartite graph then $`\lambda _1(G)\sqrt{m}`$. Moreover if it is a star of size $`\mathrm{\Delta }`$ then $`\lambda _1(G)=\sqrt{\mathrm{\Delta }}`$.

If the degrees on both sides of bipartition are bounded by $`\mathrm{\Delta }_1`$ and $`\mathrm{\Delta }_2`$ respectively, then $`\lambda _1(G)\sqrt{\mathrm{\Delta }_1\mathrm{\Delta }_2}`$.

For every vertex $`v`$ of $`G`$ let $`W_2(G,v)`$ denote the number of walks of length two in $`G`$ starting at $`v`$. Then $`\lambda _1(G)\sqrt{\mathrm{max}_vW_2(G,v)}`$.

Proof of Theorem 1.1. We already derived in the introduction the lower bound of this theorem so we will concentrate on proving an upper bound. We will frequently use the following simple fact that between any two distinct vertices of the $`n`$-cube there are at most two paths of lengths two. We divide the proof into few cases with respect to the value of the edge probability $`p`$. In each case we partition o $`G`$ into smaller subgraphs, whose largest eigenvalue is easier to estimate. We start with a rather easy case when the random graph is relatively sparse.

Case 1. Let $`e^{\mathrm{log}^4n}pn^{2/3}`$. For these values of $`p`$, by Lemma 2.1, we have that $`\mathrm{\Delta }(G)\mathrm{\Omega }\left(\frac{n}{\mathrm{log}^4n}\right)`$. Partition the vertex set of $`G`$ into three subsets as follows. Let $`V_1`$ be the set of vertices with degree at most $`n^{2/5}`$, let $`V_2`$ be the set of vertices with degree larger than $`n^{2/5}`$ but smaller than $`n^{4/7}`$ and let $`V_3`$ be the set of vertices with degree at least $`n^{4/7}`$. Also let $`G_1`$ be a subgraph of $`G`$ induced by $`V_1`$, let $`G_2`$ be a subgraph induced by $`V_2V_3`$, let $`G_3`$ be a bipartite graph containing edges of $`G`$ connecting $`V_1`$ and $`V_2`$ and finally let $`G_4`$ be a bipartite graph containing edges connecting $`V_1`$ and $`V_3`$. By definition $`G=_iG_i`$ and thus by claim (II) of Proposition 3.1 we obtain that $`\lambda _1(G)_{i=1}^4\lambda _1(G_i)`$.

Since the maximum degree of graph $`G_1`$ is at most $`n^{2/5}`$, then by (I) it follows that $`\lambda _1(G_1)n^{2/5}`$. The degrees of vertices of bipartite graph $`G_3`$ are bounded on one side by $`n^{2/5}`$ and on another by $`n^{4/7}`$. Hence using (IV) we conclude that $`\lambda _1(G_3)\sqrt{n^{2/5}n^{4/7}}=n^{17/35}`$. Let $`v`$ be a vertex of $`G_2`$ and let $`N_2(G_2,v)`$ be the set of vertices of $`G_2`$ which are within distance exactly two from $`v`$. Since between any two distinct vertices of $`Q^n`$ there at most two paths of length two it is easy to see that the number of walks of length two in $`G_2`$ starting at $`v`$ is bounded by $`d_{G_2}(v)+2|N_2(G_2,v)|`$. Since every vertex of $`V_2V_3`$ has degree in $`G`$ at least $`n^{2/5}`$, using Lemma 2.2 (i) with $`a=4/5`$ and $`b=2/5`$ we obtain that almost surely both $`d_{G_2}(v)`$ and $`|N_2(G_2,v)|`$ are bounded by $`n^{4/5}`$. Therefore for every vertex $`v`$ in $`G_2`$ we have $`W_2(G_2,v)d_{G_2}(v)+2|N_2(G_2,v)|3n^{4/5}`$ and hence by (V) $`\lambda _1(G_2)\sqrt{3n^{4/5}}=\sqrt{3}n^{2/5}`$.

Finally we need to estimate $`\lambda _1(G_4)`$. To do so consider partition of $`V_1`$ into two parts. Let $`V_1^{}`$ be the set of vertices in $`V_1`$ with at least two neighbors in $`V_3`$ and let $`V_1^{\prime \prime }=V_1V_1^{}`$. Let $`G_4^{}`$ and $`G_4^{\prime \prime }`$ be bipartite graphs with parts $`(V_1^{},V_3)`$ and $`(V_1^{\prime \prime },V_3)`$ respectively. By definition, $`G_4=G_4^{}G_4^{\prime \prime }`$ and hence $`\lambda _1(G_4)\lambda _1(G_4^{})+\lambda _1(G_4^{\prime \prime })`$. Since the vertices in $`V_1^{\prime \prime }`$ have at most one neighbor in $`V_3`$ and the graph $`G_4^{\prime \prime }`$ is bipartite it follows that $`G_4^{\prime \prime }`$ is the union of vertex disjoint stars of size at most $`\mathrm{\Delta }(G)`$. So by (III) we get $`\lambda _1(G_4^{\prime \prime })\sqrt{\mathrm{\Delta }(G)}`$. Now let $`u`$ be the vertex of $`V_3`$ with at least $`2n^{1/2}`$ neighbors in $`V_1^{}`$. By definition, every neighbor of $`u`$ in $`V_1^{}`$ has also an additional neighbor in $`V_3`$, which is distinct from $`u`$. Therefore we obtain that there are at least $`2n^{1/2}`$ simple paths of length two from $`u`$ to the set $`V_3`$. Since between any two distinct vertices of the $`n`$-cube there are at most two paths of length two we obtain that $`u`$ has at least $`n^{1/2}`$ other vertices of $`V_3`$ within distance two. Since the degree of all these vertices is at least $`n^{4/7}`$ it follows from Lemma 2.2 (i) with $`a=1/2`$ and $`b=4/7`$ that a.s. there is no vertex $`u`$ with this property. Therefore the degree of every vertex from $`V_3`$ in bipartite graph $`G_4^{}`$ is bounded by $`2n^{1/2}`$ and we also have that the degree of every vertex from $`V_1^{}`$ is at most $`n^{2/5}`$. So using again (IV) we obtain $`\lambda _1(G_4^{})\sqrt{2n^{1/2}n^{2/5}}=\sqrt{2}n^{9/20}`$. This implies the desired bound on $`\lambda _1(G)`$, since

$$\lambda _1(G)\underset{i}{}\lambda _1(G_i)n^{2/5}+\sqrt{3}n^{2/5}+n^{17/35}+\left(\sqrt{2}n^{9/20}+\sqrt{\mathrm{\Delta }(G)}\right)=\left(1+o(1)\right)\sqrt{\mathrm{\Delta }(G)}.$$

Case 2. Let $`pn^{4/9}`$. This case when the random graph is dense is also quite simple. Indeed, partition the vertices of $`G`$ into two parts. Let $`V_1`$ be the set of vertices with degree larger than $`np+np/\mathrm{log}n`$ and let $`V_2`$ be the rest of the vertices. Clearly $`G=_iG_i`$, where $`G_1`$ is a subgraph induced by $`V_1`$, $`G_2`$ is a subgraph induced by $`V_2`$ and $`G_3`$ is a bipartite subgraph with bipartition $`(V_1,V_2)`$. By definition, the maximum degree of $`G_2`$ is at most $`np+np/\mathrm{log}n`$, implying $`\lambda _1(G_2)np+np/\mathrm{log}n`$. Since every vertex in $`V_1`$ has degree at least $`np+np/\mathrm{log}n`$, by Lemma 2.2 (ii) with $`a=1/18`$ we obtain that almost surely no vertex in $`G`$ can have more than $`n^a/pn^{1/2}`$ vertices in $`V_1`$ within distance one or two. In particular, this implies that the maximum degree in $`G_1`$ is at most $`n^{1/2}`$ and so $`\lambda _1(G_1)n^{1/2}`$.

Partition $`V_2`$ into two parts. Let $`V_2^{}`$ be the set of vertices in $`V_2`$ with at least two neighbors in $`V_1`$ and let $`V_2^{\prime \prime }=V_2V_2^{}`$. Let $`G_3^{}`$ and $`G_3^{\prime \prime }`$ be bipartite graphs with parts $`(V_1,V_2^{})`$ and $`(V_1,V_2^{\prime \prime })`$ respectively. By definition, $`G_3=G_3^{}G_3^{\prime \prime }`$ and thus $`\lambda _1(G_3)\lambda _1(G_3^{})+\lambda _1(G_3^{\prime \prime })`$. Since the vertices in $`V_2^{\prime \prime }`$ have at most one neighbor in $`V_1`$ and the graph $`G_3^{\prime \prime }`$ is bipartite it follows that $`G_3^{\prime \prime }`$ is the union of vertex disjoint stars of size at most $`\mathrm{\Delta }(G)`$. So by (III) we get $`\lambda _1(G_3^{\prime \prime })\sqrt{\mathrm{\Delta }(G)}n^{1/2}`$. Now let $`u`$ be the vertex of $`V_1`$ with at least $`2n^{1/2}`$ neighbors in $`V_2^{}`$. By definition, every neighbor of $`u`$ in $`V_2^{}`$ has also an additional neighbor in $`V_1`$, which is distinct from $`u`$. Therefore we obtain that there are at least $`2n^{1/2}`$ simple paths of length two from $`u`$ to the set $`V_1`$. Since between any two distinct vertices there are at most two paths of length two we obtain that $`u`$ has at least $`n^{1/2}`$ other vertices of $`V_1`$ within distance two. As we already explain in the previous paragraph, this almost surely does not happen. Thus the degree of every vertex from $`V_1`$ in bipartite subgraph $`G_3^{}`$ is bounded by $`2n^{1/2}`$ and we also have that the degree of every vertex from $`V_2^{}`$ is at most $`np+np/\mathrm{log}n`$. So using (IV) we obtain $`\lambda _1(G_3^{})\sqrt{2n^{1/2}(np+np/\mathrm{log}n)}`$. Now since $`npn^{5/9}`$ it follows that all $`\lambda _1(G_1),\lambda _1(G_3^{}),\lambda _1(G_3^{\prime \prime })=o(np)`$ and therefore

$$\lambda _1(G)\underset{i}{}\lambda _1(G_i)\lambda _1(G_2)+o(np)np+np/\mathrm{log}n+o(np)=(1+o(1))np.$$

Case 3. Let $`n^{2/3}pn^{4/9}`$. This part of the proof is slightly more involved then two previous ones since in particular it needs to deal with a delicate case when $`np`$ and $`\sqrt{\mathrm{\Delta }(G)}`$ are nearly equal.

Partition the vertex set of $`G`$ into four parts. Let $`V_1`$ the set of vertices with degree at least $`n^{2/3}`$ and let $`V_2`$ be the set of vertices with degrees larger than $`np+np/\mathrm{log}n`$ but less than $`n^{2/3}`$. Let $`V_4`$ contains all vertices $`G`$ which have at least one neighbor in $`V_1`$ and degree at most $`np+np/\mathrm{log}n`$. Finally let $`V_3`$ be the set of remaining vertices of $`G`$. Note that by definition there are no edges between $`V_1`$ and $`V_3`$ and every vertex from $`V_3`$ also have degree at most $`np+np/\mathrm{log}n`$ in $`G`$.

We consider the following subgraphs of $`G`$. Let $`G_1`$ be the bipartite subgraph containing all the edges between $`V_1`$ and $`V_4`$. Partition $`V_4`$ into two parts. Let $`V_4^{}`$ be the set of vertices in $`V_4`$ with at least two neighbors in $`V_1`$ and let $`V_4^{\prime \prime }=V_4V_4^{}`$. Let $`G_1^{}`$ and $`G_1^{\prime \prime }`$ be bipartite graphs with parts $`(V_1,V_4^{})`$ and $`(V_1,V_4^{\prime \prime })`$ respectively. By definition, $`G_1=G_1^{}G_1^{\prime \prime }`$ and thus $`\lambda _1(G_1)\lambda _1(G_1^{})+\lambda _1(G_1^{\prime \prime })`$. Since the vertices in $`V_4^{\prime \prime }`$ have at most one neighbor in $`V_1`$ and the graph $`G_1^{\prime \prime }`$ is bipartite it follows that $`G_1^{\prime \prime }`$ is the union of vertex disjoint stars of size at most $`\mathrm{\Delta }(G)`$. So by (III) we get $`\lambda _1(G_1^{\prime \prime })\sqrt{\mathrm{\Delta }(G)}`$. Now let $`u`$ be the vertex of $`V_1`$ with at least $`2n^{2/5}`$ neighbors in $`V_4^{}`$. By definition, every neighbor of $`u`$ in $`V_4^{}`$ has also an additional neighbor in $`V_1`$, which is distinct from $`u`$. Therefore we obtain that there are at least $`2n^{2/5}`$ simple paths of length two from $`u`$ to the set $`V_1`$. Similar as before, this implies that $`u`$ has at least $`n^{2/5}`$ other vertices of $`V_1`$ within distance two. By Lemma 2.2 (i) with $`a=2/5`$ and $`b=2/3`$ this almost surely does not happen. Thus the degree of every vertex from $`V_1`$ in bipartite subgraph $`G_1^{}`$ is bounded by $`2n^{2/5}`$ and we also have that the degree of every vertex from $`V_4^{}`$ is at most $`np+np/\mathrm{log}nn^{5/9}`$. So using (IV) we obtain $`\lambda _1(G_1^{})\sqrt{2n^{2/5}n^{5/9}}=\sqrt{2}n^{43/90}=o(\sqrt{\mathrm{\Delta }})`$. Therefore $`\lambda _1(G_1)\lambda _1(G_1^{})+\lambda _1(G_1^{\prime \prime })(1+o(1))\sqrt{\mathrm{\Delta }}`$.

Our second subgraph $`G_2`$ is induced by the set $`V_3`$. By definition, the maximum degree in it is at most $`np+np/\mathrm{log}n`$ and therefore $`\lambda _1(G_2)(1+o(1))np`$. Crucially this graph is vertex disjoint form $`G_1`$ which implies by (II) that

$$\lambda _1\left(G_1G_2\right)=\mathrm{max}(\lambda _1(G_1),\lambda _1(G_2))\left(1+o(1)\right)\mathrm{max}(\sqrt{\mathrm{\Delta }},np).$$

Next we define the remaining graphs whose union with $`G_1`$ and $`G_2`$ equals to $`G`$ and show that their largest eigenvalues contribute only smaller order terms in the upper bound on $`\lambda _1(G)`$. Let $`G_3`$ be the subgraph of $`G`$ induced by the set $`V_1V_2`$. By definition, every vertex in $`G_3`$ have at least $`np+np/\mathrm{log}n`$ neighbors in $`G`$. Therefore by Lemma 2.2 (ii) with $`a=1/12`$ we obtain that for every $`vG_3`$ there at most $`n^a/pn^{3/4}`$ other vertices of $`G_3`$ within distance one or two. This implies that $`d_{G_3}(v)`$ and $`|N_2(G_3,v)|`$ are both bounded by $`n^{3/4}`$. Then, as we already show in Case 1, the total number of walks of length two starting at $`v`$ is bounded by $`d_{G_3}(v)+2|N_2(G_3,v)|3n^{3/4}`$. Thus by (V) we get $`\lambda _1(G_3)\sqrt{3n^{3/4}}=o(\sqrt{\mathrm{\Delta }})`$.

Let $`u`$ be a vertex of $`V_3V_4`$ which has at least $`2n^{2/5}`$ neighbors in the set $`V_4`$. Since every vertex in $`V_4`$ have at least one neighbor in $`V_1`$ we obtain that there at least $`2n^{2/5}`$ simple paths of length two from $`u`$ to $`V_1`$. On the other hand we know that there are at most two such paths between any pair of distinct vertices. This implies that $`u`$ has at least $`n^{2/5}`$ vertices within distance two whose degree is at least $`n^{2/3}`$. Using Lemma 2.2 (i) with $`a=2/5`$ and $`b=2/3`$ we conclude that almost surely there is no such vertex $`u`$. Now let $`G_4`$ be a subgraph induced by the set $`V_4`$ and let $`G_5`$ be the bipartite graph with parts $`(V_3,V_4)`$. By the above discussion, the maximum degree of $`G_4`$ is at most $`2n^{2/5}`$, implying $`\lambda _1(G_4)2n^{2/5}=o(\sqrt{\mathrm{\Delta }})`$. We also know that every vertex from $`V_3`$ has at most $`2n^{2/5}`$ neighbors in $`V_4`$ and every vertex in $`V_4`$ have at most $`np+np/\mathrm{log}nn^{5/9}`$ neighbors in $`V_3`$. Therefore by (IV) we obtain that $`\lambda _1(G_5)\sqrt{2n^{2/5}n^{5/9}}=\sqrt{2}n^{43/90}=o(\sqrt{\mathrm{\Delta }})`$.

Finally consider the bipartite subgraph $`G_6`$ whose parts are $`V_2`$ and $`V_3V_4`$. Let $`X`$ be the set of vertices from $`V_3V_4`$ with at least $`2n^{2/7}`$ neighbors in $`V_2`$ and let $`Y=V_3V_4X`$. Note that $`G_6=G_6^{}G_6^{\prime \prime }`$ where $`G_6^{}`$ is bipartite graph with parts $`(V_2,X)`$ and $`G_6^{\prime \prime }`$ is bipartite graph with parts $`(V_2,Y)`$. The upper bound on $`\lambda _1(G_6^{\prime \prime })`$ follows immediately from the facts that $`G_6^{\prime \prime }`$ is bipartite, the degree of vertices in $`V_2`$ is bounded by $`n^{2/3}`$ and, by definition, every vertex in $`Y`$ has at most $`2n^{2/7}`$ neighbors in $`V_2`$. Therefore $`\lambda _1(G_6^{\prime \prime })\sqrt{2n^{2/7}n^{2/3}}=\sqrt{2}n^{10/21}=o(\sqrt{\mathrm{\Delta }})`$. To bound $`\lambda _1(G_6^{})`$, note that almost surely every vertex in $`V_2`$ has at most $`n^{3/7}`$ neighbors in $`X`$. Indeed, let $`uV_2`$ be the vertex with more than $`n^{3/7}`$ neighbors in $`X`$. Since every neighbor of $`u`$ in $`X`$ has at least $`2n^{2/7}1`$ additional neighbors in $`V_2`$ different form $`u`$ we obtain that there at least $`(2n^{2/7}1)n^{3/7}=(2+o(1))n^{5/7}`$ simple paths of length two from $`u`$ to $`V_2`$. On the other hand we know that there are at most two such paths between any pair of distinct vertices. This implies that $`u`$ has at least $`(1+o(1))n^{5/7}`$ vertices of $`V_2`$ within distance two. By definition, every vertex of $`V_2`$ has at least $`np+np/\mathrm{log}n`$ neighbors in $`G`$. Therefore using Lemma 2.2 (ii) with $`a=1/22`$ we conclude that almost surely there is no such vertex $`u`$. Now the upper bound on $`\lambda _1(G_6^{})`$ can be obtained using that $`G_6^{}`$ is bipartite, the degree of vertices in $`X`$ is bounded by $`np+np/\mathrm{log}nn^{5/9}`$ and that every vertex in $`V_2`$ has at most $`2n^{3/7}`$ neighbors in $`X`$. Indeed, by (IV) $`\lambda _1(G_6^{})\sqrt{2n^{3/7}n^{5/9}}=\sqrt{2}n^{31/63}=o(\sqrt{\mathrm{\Delta }})`$ and hence $`\lambda _1(G_6)\lambda _1(G_6^{})+\lambda _1(G_6^{\prime \prime })=o(\sqrt{\mathrm{\Delta }})`$.

From the above definitions it is easy to check that $`G=_{i=1}^6G_i`$. Hence using our estimates on the largest eigenvalues of graphs $`G_i`$ we obtain the desired upper bound on $`\lambda _1(G)`$, as follows

$`\lambda _1(G)`$ $``$ $`\lambda _1\left(G_1G_2\right)+{\displaystyle \underset{i3}{}}\lambda _1(G_i)(1+o(1))\mathrm{max}(\sqrt{\mathrm{\Delta }(G)},np)+o\left(\sqrt{\mathrm{\Delta }(G)}\right)`$
$`=`$ $`(1+o(1))\mathrm{max}(\sqrt{\mathrm{\Delta }(G)},np).`$
This completes the proof of the third case. Now to finish the proof of the theorem it remains to deal with the last very simple case when the random graph is very sparse.

Case 4. Let $`pe^{\mathrm{log}^4n}`$. For every integer $`k1`$ denote by $`Y_k`$ the number of connected components with $`k`$ edges. It is not difficult to see that $`𝐄Y_kO(2^nk!n^kp^k)`$. Indeed, we can pick the first vertex in the connected component in $`2^n`$ ways. Suppose we already know the first $`1tk`$ vertices of the component. Then these vertices are incident to at most $`tn`$ edges of the $`n`$-cube and therefore we can pick the next edge only in at most $`tn`$ ways. This gives at most $`2^n_{t=1}^ktn=2^nk!n^k`$ ways to pick the edges of the connected component.

First consider the case when $`p`$ is not exponentially small. Then, by Lemma 2.1 we have that almost surely $`\mathrm{\Delta }(G)=(1+o(1))\kappa (n)`$, where $`\kappa (n)=\mathrm{max}\{k:2^n\left(\begin{array}{c}n\\ k\end{array}\right)p^k(1p)^{nk}1\}`$ and $`\kappa (n)`$ tends to infinity together with $`n`$. Let $`k_0=\kappa (n)+\kappa (n)/\mathrm{log}\kappa (n)`$. Then it is easy to check that $`𝐄Y_{k_0}=o(1)`$ and therefore, by Markov’s inequality, almost surely $`G(Q^n,p)`$ contains no connected component with more than $`k_0`$ edges. Since the largest eigenvalue of $`G`$ is the maximum of the eigenvalues of its connected components and the largest eigenvalue of a component with $`k_0`$ edges is not greater than $`\sqrt{k_0}`$ (see, parts (II) and (III) of Proposition 3.1), we obtain that

$$\lambda _1(G)\sqrt{k_0}\sqrt{\kappa (n)}+\sqrt{\kappa (n)/\mathrm{log}\kappa (n)}=(1+o(1))\sqrt{\mathrm{\Delta }(G)}.$$

Next, let $`p2^{\alpha n}`$ for some fixed $`\alpha >0`$. If $`p`$ is not proportional to $`2^{n/k}n^1,k=1,2,3,\mathrm{},`$ then it follows from part (iii) of Lemma 2.1 that with probability going to one the maximum degree of $`G(Q^n,p)`$ is $`\kappa (n)=\left[\frac{n\mathrm{log}2}{\mathrm{log}(p^1)\mathrm{log}n}\right]`$. Note that in this case $`\kappa (n)`$ is a constant and it is easy to check that $`𝐄Y_{\kappa (n)+1}O\left(2^nn^{\kappa (n)+1}p^{\kappa (n)+1}\right)=o(1)`$. Thus, by Markov’s inequality, there are no connected components with more than $`\kappa (n)`$ edges. Since the largest eigenvalue of $`G`$ is the maximum of the eigenvalues of its connected components and the largest eigenvalue of a component with $`k`$ edges is not greater than $`\sqrt{k}`$ ( and is equal to $`\sqrt{k}`$ only if the component is a star on $`k+1`$ vertices), we obtain that a.s. $`\lambda _1(G)=\sqrt{\kappa (n)}=\sqrt{\mathrm{\Delta }(G)}.`$

Finally if $`p(n)`$ is proportional to $`2^{n/k}n^1,k=1,2,3,\mathrm{},`$ then by part (ii) of Lemma 2.1 almost surely $`\mathrm{\Delta }(G)\{k1,k\}`$ and again one can check that $`𝐄Y_{k+1}`$ is exponentially small. Using Markov’s inequality, as before, we conclude that there are no connected components with more than $`k`$ edges. Therefore a.s. $`\lambda _1(G)`$ is either $`\sqrt{\mathrm{\Delta }(G)}`$ or $`\sqrt{\mathrm{\Delta }(G)+1}`$. This completes the proof of the theorem.

## 4 Concluding remarks

There are several other important questions that are beyond the reach of the presented technique. The most fundamental is perhaps the local statistics of the eigenvalues, in particular the local statistics near the edge of the spectrum. For results in this direction for other random matrix models we refer the reader to , , . A recent result of Alon, Krivelevich and Vu  states that the deviation of the first, second, etc. largest eigenvalues from its mean is at most of order of $`O(1)`$. Unfortunately our results give only the leading term of the mean.

A second, perhaps even more difficult question is whether the local behavior of the eigenvalues is sensitive to the details of the distribution of the matrix entries of $`A.`$ We refer the reader to , , ,  for the results of that nature for unitary invariant and Wigner random matrices.

Acknowledgements. The first author would like to thank Sergey Gavrilets and Janko Gravner for bringing this problem to his attention and for useful discussions.


text:
# Anderson-Mott Transition Driven by Spin Disorder: Spin Glass Transition and Magnetotransport in Amorphous GdSi

\[

## Abstract

A zero temperature Anderson-Mott transition driven by spin disorder can be ‘tuned’ by an applied magnetic field to achieve colossal magnetoconductance. Usually this is not possible since spin disorder by itself cannot localise a high density electron system. However, the presence of strong structural disorder can realise this situation, self consistently generating a disordered magnetic ground state. We explore such a model, constructed to understand amorphous GdSi, and highlight the emergence of a spin glass phase, Anderson-Mott signatures in transport and tunneling spectra, and unusual magneto-optical conductivity. We solve a disordered strong coupling fermion-spin-lattice problem essentially exactly on finite systems, and account for all the qualitative features observed in magnetism, transport, and the optical spectra in this system.

\]

The ‘Anderson-Mott’ insulator-metal transition (IMT) in disordered interacting systems  and the physics of ‘colossal magnetoresistance’ (CMR) in, for example, the manganese oxides  are topics of great current interest. Even though the “ultimate” example of CMR would be a magnetic field driven, zero temperature, insulator-metal transition, such a scenario had not been realised experimentally till recently. Most observations of CMR are at finite temperature, across a ferromagnet to paramagnet transition . Canonical ‘Anderson-Mott’ systems do not show large magnetoconductance (MC) and the standard CMR systems do not involve localisation physics. These two fields of research have evolved independently.

Experiments  on amorphous $`a`$-GdSi reveal that the presence of doped magnetic moments in a strongly disordered system can combine features of the standard doping driven IMT in amorphous systems  with the physics of field driven IMT and CMR. The magnetic ground state in such a system is a spin glass. There are distinct signatures of electron correlation in the conductivity and tunneling spectra, and huge transfer of optical spectral weight on application of a magnetic field. The experimental observations, discussed below, cannot be understood within the standard scenarios  developed for IMT and CMR and require an independent and comprehensive framework. Our main achievement in this paper is $`(i)`$ to provide the first understanding of the unique properties of this system, and $`(ii)`$ demonstrate a many body technique that allows controlled approximations in a strongly disordered interacting system.

The measurements have been made on $`a`$-GdSi and simultaneously on the non-magnetic analog $`a`$-YSi. $`(i)`$ Both YxSi1-x and GdxSi1-x show an IMT  as the doping, $`x`$, is increased beyond a critical value, $`x_c`$. The critical doping $`x_c14\%`$ in YSi and $`x_c15\%`$ in GdSi. $`(ii)`$ For $`xx_c`$ in GdSi, a magnetic field, $`h_c(x)`$, can actually drive an insulating sample metallic. YSi samples show weak positive magnetoresistance. $`(iii)`$ The density of states (DOS) at the Fermi level, $`N(0)`$, in GdSi, probed through tunneling conductance measurement , grows as $`(hh_c)^2`$ across the IMT, while $`\sigma _{dc}`$ increases as $`(hh_c)`$. $`(iv)`$ The optical conductivity in GdSi shows large transfer of spectral weight  to low frequency from $`\omega 0.1`$ eV on application of a field of a few Tesla. Transfer of spectral weight also occurs on raising temperature, and this is seen in both GdSi and YSi. $`(v)`$ The low field a.c susceptibility in GdSi reveals  that the magnetic degrees of freedom freeze into a spin glass state at low temperature. The freezing temperature, $`T_f`$, increases from $`1`$ K at $`x=0.04`$ to $`T_f6`$ K at $`x0.20`$. The Y doped samples are diamagnetic. $`(vi)`$ The ‘effective moment’ inferred  from $`\chi (T)`$ differs from the expected value for Gd, and the high temperature magnetic specific heat  per doped Gd is almost $`50\%`$ larger than $`log(2S+1)`$.

Observation $`(i)`$ above is standard in disordered systems, $`(ii)(iv)`$ would be expected in CMR materials, and $`(v)(vi)`$ seem to be unique to the combination.

A ‘first principles’ model for amorphous GdSi will have to consider an underlying ‘random’ structure in which a fraction $`x`$ of the sites are occupied by Gd atoms and $`(1x)`$ by Si atoms. The Gd and Si atoms have different orbital structure so a complicated set of inter-orbital, intersite hopping possibilities need to be considered. We try to retain the essential features in the following, simpler, one band model:

$`H`$ $`=t{\displaystyle \underset{ij,\sigma }{}}c_{i\sigma }^{}c_{j\sigma }+{\displaystyle \underset{i\sigma }{}}(ϵ_i\mu )n_{i\sigma }J^{}{\displaystyle \underset{\nu }{}}\sigma _\nu .𝐒_\nu `$ (2)
$`\lambda {\displaystyle \underset{\nu }{}}n_\nu x_\nu +{\displaystyle \frac{1}{2}}K{\displaystyle \underset{\nu }{}}x_\nu ^2+H_{Coul}`$
We use a tight binding model with uniform hopping $`t`$, and an on site potential $`ϵ_i`$ uniformly distributed between $`\pm \mathrm{\Delta }/2`$. The sites labelled ‘$`\nu `$’ are a fraction $`x`$ of the lattice corresponding to the dopant (Y/Gd) locations. The electron-spin coupling is $`J^{}`$, $`𝐒_i`$ are the $`S=7/2`$ Gd spins, and $`\sigma _{i\mu }=_{\alpha \beta }c_{i\alpha }^{}\tau _\mu ^{\alpha \beta }c_{i\beta }`$, where $`\tau _\mu `$ are the Pauli matrices. The $`x_i`$ are local displacement variables (bond distortions ) coupled to the electron density via $`\lambda `$, and the structural stiffness is $`K`$. $`H_{Coul}`$ would include Hubbard and long range Coulomb interactions.

The width of the impurity level distribution $`(\mathrm{\Delta })`$ in YSi/GdSi has been estimated  to be $`200`$ meV, and the ‘polaron binding energy’ $`g=\lambda ^2/K30`$ meV. The existence of lattice polaron effects in amorphous semiconductors had been argued early on by Anderson , and has been revived now  in the context of doped $`a`$-Si. We think the diamagnetism in YSi confirms bipolaronic effects, but these lattice effects are probably not very important in GdSi. There is no simple estimate of the ‘effective hopping amplitude’ to be used in a single band approximation. However, calculations on the Anderson model indicate  that we need $`\mathrm{\Delta }/t14`$ to localise $`10`$% of the electronic states in the band. This suggests a rather small effective hopping amplitude $`200`$ K, if $`\mathrm{\Delta }`$ is $`200`$ meV. The electron-spin coupling $`J^{}S`$ (called $`J^{}`$ from now on), arising out of the $`df`$ coupling in Gd, is large. It is estimated to be $`0.9`$ eV from photoemission measurements  on Gd, but would be somewhat smaller in the effective one band description that we are using. Although the parameter values have some uncertainty it is clear that $`\mathrm{\Delta },J^{}t`$. We use $`\mathrm{\Delta }/t=11`$, $`J^{}/t=4`$, $`g/t=0.5`$, roughly consistent with the experimental estimates. The electron-phonon and electron-spin coupling are operative only at the dopant sites. We distribute the ‘impurities’ (Y or Gd in the Si host) into $`Nx`$ sites with the lowest potential in any given realisation $`\{ϵ_i\}`$. This ensures that at low dopant concentration, the electrons are trapped near the dopant sites. We measure all energies in units of $`t`$, and finally assume $`t500`$ K for comparing our energy scales with the data.

Our principal results using the Hamiltonian above are the following $`(i)`$ the magnetic ground state in the low doping region is a spin glass with $`T_f`$ having overall scale $`t^2/(J^{}+\mathrm{\Delta })`$ and following the experimental doping dependence (Fig.1), $`(ii)`$ there is a metal-insulator transition for both GdSi and YSi with decreasing $`x`$, with $`x_{Gd}^cx_Y^c`$, and a field driven IMT and CMR for GdSi (Fig.2), $`(iii)`$ there is large transfer of spectral weight from high to low frequency (Fig.4) in $`\sigma (\omega )`$, driven by an applied magnetic field in GdSi. We explain our scheme of calculation next and then discuss these results in detail.

Since the Hamiltonian involves $`\mathrm{\Delta }/t,J^{}/t1`$ and $`g𝒪(t)`$ none of these couplings can be handled perturbatively. To study the properties of this model within a controlled approximation we use a finite size combination of Monte-Carlo and exact diagonalisation  (MC+ED). This approach exactly handles the strong disorder, but treats the spin and lattice variables as ‘classical’. Since we have $`2S1`$, the ‘classical’ spin limit should be a reasonable starting point. At strong disorder, the leading effect of phonons should also be accessible classically.

If we ignore $`H_{coul}`$ to start with, $`H`$ represents non-interacting fermions coupled to classical variables $`𝐒_i`$ and $`x_i`$, in addition to the random potential $`ϵ_i`$. The $`ϵ_i`$ are ‘quenched’ variables while the spin and lattice degrees of freedom are ‘annealed’, with the distribution $`P\{x,S\}=Z^1Tre^{\beta H}`$ where $`Z=𝒟S𝒟xTre^{\beta H}`$ is the full partition function for a specific realisation of $`\{ϵ_i\}`$.

The ‘exact’ MC+ED allows only small system sizes, $`𝒪(100)`$ sites, so the key step is to construct an approximate ‘effective Hamiltonian’ for the lattice and spin variables. Once the magnetic and phonon problem are self consistently solved, the $`T=0`$ electron problem can be solved in the classical ground state $`\{𝐒_i,x_i\}_0`$, which itself depends on $`\{ϵ_i\}`$, finally averaging over disorder.

Formally the magnetic effective Hamiltonian is $`H_{eff}\{S\}=\frac{1}{\beta }log𝒟xTre^{\beta H}`$. The magnetic problem involves $`J^{}/t1`$, a dilute system (the spins occupy only a fraction $`x`$ of sites), and strong disorder in the electron system. There is no perturbative expansion possible in $`J^{}`$ but the large $`J^{}`$ and $`x1`$ allows a simplification. In this limit the doped carriers are essentially localised at the magnetic sites, with the electron density falling off exponentially away from the sites. This generates a pairwise antiferromagnetic coupling, for $`R_{ij}>1`$, with $`J_{ij}(t^2/J^{})e^{R_{ij}/\lambda (J^{})}`$, with $`\lambda 1/J^{}`$. For neighbouring sites there is a ferromagnetic coupling $`𝒪(t)`$.

In the disordered system, for a given separation $`R_{ij}`$, the bonds have a distribution. We construct the distributions $`P(J,R_{ij})`$ and study the model: $`H_{eff}\{𝐒\}=_{ij}J_{ij}𝐒_i.𝐒_j.`$ For a pair of moments located at $`𝐑_i`$ and $`𝐑_j`$ the $`J_{ij}`$ is picked from $`P(J,R_{ij})`$. This ignores correlations between bonds in a specific $`\{ϵ_i\}`$ realisation. We simulate the model for different dilutions, compute the order parameter for freezing, $`q(T)=(xN)^1_i|𝐒_i_T|`$, and check that the structure factor has no peaks at any wavevector $`𝐐`$. Fig.1 shows $`q(T)`$, alongwith $`\chi (T)`$ at $`x=0.2`$, and the freezing temperature  $`T_f(x)`$. At $`x=0.2`$ our $`T_f10`$K, while experimentally $`T_f6`$K. We have done the exact MC+ED simulation for $`4^3`$ systems, with the same $`J^{},\mathrm{\Delta }`$ and $`x0.1`$ and verified  that the system freezes into a spin glass, with $`T_f`$ within $`10\%`$ of our result here.

Having established the existence of a glassy state for the $`\{𝐒_i\}`$ we will simplify the remaining electron-phonon problem by assuming the spins to be frozen in an uncorrelated random manner.

The effective Hamiltonian for phonons is $`H_{eff}\{x\}=\frac{1}{\beta }log𝒟STre^{\beta H}`$. At moderate $`g`$ and strong disorder there would be ‘frozen’ bond distortions in the ground state, and we cannot expand about the $`x_i=0`$ state. To incorporate this effect we use the lowest order self-consistent expansion, i.e, $`H_{eff}\{x\}\frac{1}{2}K_ix_i^2+_ia_ix_i`$ with $`a_i=\lambda \overline{n}_i`$, where $`\overline{n}_i=n_i`$, computed in the electronic ground state. The minimum of $`H_{eff}`$, i.e the lattice distortion in the ground state, corresponds to $`\overline{x}_i=(\lambda /K)\overline{n}_i`$. The $`T=0`$ problem now corresponds to electrons in the background of structural disorder, $`\{ϵ_i\}`$, coupled to randomly oriented spins with coupling $`J^{}`$, and density coupled to a phonon field $`x_i=(\lambda /K)\overline{n}_i`$, i.e,

$$H_{eff}^{el}=H_{kin}+\underset{i}{}ϵ_in_iJ^{}\underset{\nu }{}\sigma _\nu .𝐒_\nu g\underset{\nu }{}\overline{n}_\nu n_\nu $$
(3)
We solve this problem through iterative ED. The transport and spectral properties of YSi correspond to $`g=0.5`$ and $`J^{}=0`$, while for GdSi $`g=0.5`$ and $`J^{}=4`$. The ED is done for a sequence of sizes $`6\times 6\times L`$, with $`L=24,32,40,48`$. Due to the finite size gaps the d.c. conductivity cannot be directly computed on finite systems. We use the Kubo-Greenwood formula to compute the integrated optical spectral weight $`\sigma _{int}(\mathrm{\Delta }\omega )=_0^{\mathrm{\Delta }\omega }\sigma (\omega )𝑑\omega `$, disorder average, and invert to obtain the optical conductivity $`\sigma (\omega )`$. The extent of averaging varies from $`400100`$ realisations, decreasing with increasing $`L`$. We track $`\sigma (\omega _{ref};L)`$ with $`\omega _{ref}L^1`$, setting $`\omega _{ref}=0.08`$ at $`L=32`$, and use $`\sigma _{dc}=lim_L\mathrm{}\sigma (\omega _{ref},L)`$. Fig.2$`(a)`$ shows this ‘dc’ conductivity appropriate to YSi and GdSi. Our $`x_c`$ are smaller than the experimental values and we have not fine tuned parameters to match the data. The $`\sigma `$ are in units of $`\pi e^2/\mathrm{}a_0`$ and the typical values shown in Fig.2$`(a)`$ are $`0.01`$. For $`a_02\AA `$, $`\sigma _{dc}400`$ $`(\mathrm{\Omega }cm)^1`$, roughly as in experiments . Fig.2$`(b)`$ shows the $`L`$ dependence of $`\sigma (\omega _{ref};L)`$, while Fig.2$`(c)`$ shows the ‘magnetoconductance’. We have checked that the conductivity in a ‘spin glass’ backgound shows the same trend as for random spins and the numbers match within $`20\%`$.

To our knowledge there are no standard results on electron systems combining strong structural disorder and strong coupling to dilute magnetic moments. In the well studied opposite limit, $`\mathrm{\Delta }/t1,J^{}/t1`$, spin flip scattering actually weakens  Anderson localisation, so large $`J^{}/t`$ is crucial to enhanced localisation in GdSi. We have cross checked the trends in $`\sigma _{dc}`$ by computing the averaged Greens function $`G^{\sigma \sigma ^{}}(𝐫𝐫^{})`$ at large $`\mathrm{\Delta }`$, with increasing $`J^{}`$. Using $`TrG=_\sigma G^{\sigma \sigma }(𝐫𝐫^{})`$ as the indicator of ‘delocalisation’, we find that at $`|𝐫𝐫^{}|/a_0=6`$, $`TrG`$ grows with $`J^{}`$ upto $`J^{}0.5`$ and then falls rapidly . It recovers quickly as the spins are polarised by an applied field, tracking the change in conductivity.

The DOS in GdSi, at low $`x`$, has a broad minimum at $`ϵ_F`$, Fig.3$`(a)`$, since $`J^{}`$ pulls down states to lower energy. This minimum is not related to the Altshuler-Aronov ‘correlation gap’ which would be a sharper feature  near $`ϵ_F`$ (with effects of $`H_{coul}`$ included). In YSi, the effect of phonons on the disordered background shows up as a sharp dip  in the DOS, Fig.3$`(b)`$, since it generates a short range attractive interaction with $`U_{eff}=\lambda ^2/K`$.

We mimic the effect of finite magnetisation $`(m)`$, in GdSi, by using a spin distribution with finite $`S_z`$. Finite $`m`$ leads to significant redistribution of weight in the DOS, due to the large $`J^{}`$, which should be visible in photoemission measurements. The conjunction of increased mobility, and increased DOS near $`ϵ_F`$, Fig.3$`(c)`$, leads to the large changes observed in $`\sigma (\omega )`$, Fig.4. The ‘outer scale’ in $`\sigma (\omega )`$ is $`5t0.25`$ eV, as in the data .

There are certain experimental features for which the ‘Mott’ aspect is essential. These are principally the $`\sqrt{T}`$ dependence in $`\sigma _{dc}(T)`$, the $`\sqrt{\omega }`$ correlation gap, the $`T`$ driven spectral weight transfer in $`\sigma (\omega )`$, and the excess magnetic $`C_V`$. Most of these are generic correlation effects, well known in other amorphous systems , and unrelated to the magnetic character.

Let us re-emphasize the uniqueness of the system we study. Disorder, electron-spin coupling and electron-phonon interactions are features common, in some form, to $`a`$-GdSi, Anderson-Mott systems (NbSi, say) and the CMR manganites. The crucial differences are: $`(i)`$ GdSi is a strongly disordered ‘dilute’ magnetic system, with strong electron-spin coupling. These features are essential to the spin glass behaviour and the consequent IMT and CMR. Electron-phonon interactions, even if present, are not crucial to the physics. $`(ii)`$ Anderson-Mott systems are also strongly disordered, but nominally non magnetic. There are no remarkable magnetic field effects and the physics is controlled by disorder and electron correlations. $`(iii)`$ Most CMR manganites are reasonable metals at low temperature, indicating weak intrinsic disorder. They have strong electron-spin coupling on a periodic Mn lattice, which, in contrast to ‘dilution’, promotes double exchange ferromagnetism. Electron-phonon (Jahn-Teller) interactions are important in these systems. The finite temperature IMT and CMR are related to multi-phase coexistence  and not an Anderson transition. GdSi differs also from the diluted magnetic semiconductors in that the spin polaron concept  is not tenable in this high electron density system, due to strongly overlapping wavefunctions.

In conclusion, this is the first explanation of insulator-metal transition, CMR, spin glass freezing and optical properties of $`a`$-GdSi, bridging the gap between Anderson-Mott transition and CMR systems. Our results are based on an exact finite size calculation, handling strong disorder and interactions. The effect of Coulomb interactions is understood only qualitatively at the moment, and their inclusion would be the next step.

P.M would like to thank T. V. Ramakrishnan, Chandan Dasgupta and H. R. Krishnamurthy for discussions. We acknowledge use of the Beowulf cluster at H.R.I.


text:
# Protein induced morphological transitions in KCl crystal growth

## I Introduction

The effect of proteins, especially albumin and IgG on crystal growth has biological relevance. In crystal induced arthritis e.g., gout proteins bind the crystals a1  and have significant impact on crystal growth a2 . The immune response to the appearance of crystals is driven by the specific IgG-crystal interaction. This interaction stimulates crystal formation a3 ; a4 ; a5 . Although the rich morphology of several inorganic macroscopic crystals grown on the surface of gels (i.e., in the presence of protein) has been studied and discussed a6 ; a7  up to our knowledge this is the first study of pattern formation induced by crystal-protein interactions. Moving unstable interfaces typically lead to the formation of complex patterns. Surface tension of the boundary between the growing and surrounding phases is essential in pattern formation a8 ; a9 ; a10 ; a11 . A growth mode of crystals covered with a thin layer has been observed and explained by the surface tension between the different phases in a metal system a12 . The growth of nonequilibrium interfaces covered by a thin surfactant film was both experimentally and theoretically studied a13 . The anisotropy of the surface tension has crucial role. Viscous fingering, crystallization, electrochemical deposition, and some other phenomena can be relatively well described by Laplacian growth with appropriate boundary conditions. We argue that the growth of the numerous different microscopic patterns we observed in our KCl crystallization experiments in the presence of proteins can be explained by the change of the boundary conditions of the moving interface: the anisotropy of its surface tension is decreased by proteins.

## II Materials and methods

5 $`\mu `$l drops of 5 mg/ml KCl solution containing either tubulin (prepared from bovine brain a14 ) or FITC-BSA (bovine serum albumin conjugated with FITC, SIGMA) or human IgG-FITC (immunoglobulin G conjugated with FITC, SIGMA) or no protein were placed on clean glass cover slips. We prepared samples either by slow drying at $``$40 C in air or by fast drying in a strong airflow. Slow drying took $``$5 minutes, airflow dried the surface on the scale of seconds. Bright field, phase contrast and fluorescent images were acquired by an inverse Leica DM IRB microscope, 40x objective and a Nikon Coolprix 700 digital camera mounted on the microscope by homemade optical coupling. Atomic force microscopy (AFM) images of tubulin coated crystals were captured with a commercial AFM (TopoMetrix Explorer, Santa Clara, CA) in contact mode with a soft silicon nitride cantilever (Thermomicroscopes, coated sharp microlevers, model No. MSCT-AUHW, with typical force constant 0.03 N/m, 20 nm nominal radius of curvature) under ambient conditions.

## III Results

### III.1 Tubulin

The fast drying of 0.5 mg/ml tubulin containing drops of 5 mg/ml KCl solution on glass surface with air-flow results in a heterogeneous population of patterns that we investigated by AFM and phase contrast microscopy. The morphology of KCl crystals can be similar to diffusion-limited aggregates known to have fractal geometry. Dendritic patterns with stable and unstable tips are typical. FIG. 1 shows a pattern, which began to grow with stable tips, 4-fold symmetry. After a while tip splitting occurs at all the 4 tips. Anisotropy drops dramatically at this point. The slow drying of drops containing 0.05 mg/ml tubulin gives elongated saw-toothed crystals similar to the ones induced by IgG discussed below. In high concentration tubulin inhibits crystal growth, an apparently homogeneous stain can be observed after the drop dries up.

### III.2 FITC-BSA

We tried to shed light on the role of protein in pattern formation of salt crystals with the use of FITC labeled proteins. In case of the fast drying procedure 5 mg/ml FITC-BSA had similar effect to that of tubulin. Various branching morphologies were found. Tip splitting caused fractal growth (FIG. 2). The comparison of bright field and phase contrast images with the fluorescent ones show that crystals are covered by a layer of albumin. Protein concentration dependence of the morphology was studied with the slow drying technique. Under a critical protein concentration ($``$1$`\mu `$g/ml) only blocks of rectangular prism-shaped crystals grew corresponding to the protein free case. In the concentration range of 1-1000 $`\mu `$g/ml cubic crystal centered structures formed (FIG. 3). This observation reinforce that during a single growth process the symmetry (anisotropy) of the pattern can dramatically change due to the change of the local conditions. As the growth process elongates, the initial 4-fold symmetry with high anisotropy disappears and rather isotropic growth takes place. In the higher protein concentration range dendritic crystals grew with stable tips (FIG. 4).

### III.3 IgG-FITC

To study the protein specificity of the phenomena we examined the impact of human IgG-FITC on the KCl crystal growth. After the fast drying procedure using 2 mg/ml IgG the typical pattern we found was the elongated saw-toothed crystal (FIG. 5). Branching structures can be observed. The angle between the branches is $``$70. Concentration dependence of the morphology was investigated by the slow drying method. Under $``$20 $`\mu `$g/ml only blocks of the prism-shaped crystals grew. Above this concentration up to $``$1 mg/ml cubic and saw-toothed crystal centered structures were observed with an isotropic surrounding pattern. FIG. 6 shows the center of a typical one. In the higher concentration range dendritic patterns formed with stable tips.

### III.4 Equilibrium shape

The equilibrium shape of KCl crystals after the slow drying method using 10 $`\mu `$l 5 mg/ml KCl with 5 mg/ml FITC-BSA was observed by dropping 5 $`\mu `$l saturated KCl solution on the crystals and covering the droplet with a cover slip. We found rounded forms instead of the normal rectangular shapes of KCl. (Image not shown.)

### III.5 Gold substrate

We also studied the effect of the substrate surface, which was glass in the above experiments. However, IgG gave similar results on gold substrate to those on glass in case of the slow drying method, albumin induced the appearance of amorphous protein aggregates and blocks of prism-shaped crystals on gold instead of the patterns described above. This fact indicates the protein and substrate specificity of the phenomenon.

## IV Discussion

Proteins have significant impact on KCl crystallization. The presence of proteins in the solution from which KCl crystals grow during the drying up leads to the formation of protein specific and concentration dependent complex patterns, which we described by a morphological diagram (FIG. 7). We can give a partial explanation of the diagram. Meanwhile, the solution dries up the protein precipitates due to the increasing ionic strength. This process is known as salting out. A thick layer of protein aggregate (precipitate) covers the surface of crystals. This cover means 2 interfaces: one between the KCl crystal and the protein layer and one between the protein layer and the liquid. While the surface tension of the former one $`\gamma `$c-p is anisotropic, that of the latter one $`\gamma `$p-l is considered to be isotropic. The total surface tension $`\gamma `$t of the interface between the growing and surrounding phases is given by the sum of these two terms:

$$\gamma _t=\gamma _{cp}+\gamma _{pl}$$
(1)
The value of $`\gamma `$p-l i.e., the isotropic term is significant since precipitation means insolubility of the protein. The rounded equilibrium shape of crystals with protein cover reinforces the lower anisotropy of surface tension. In the absence of protein the extra isotropic term corresponding to the protein-liquid interface is missing. If

$$\gamma _{cp}<\gamma _{pl},$$
(2)
then an asymmetry arises between the two faces of the protein layer, which tends to bend it towards the liquid phase favoring dendritic growth. We propose that tip splitting and fractal growth instead of the formation of single crystals with 4-fold symmetry and stable tips can be attributed to the reduced anisotropy of the surface tension in case of the fast growth. Similarly, slowly grown single crystal centered structures are explained by the decrease of anisotropy of surface tension during the growth process. Our results demonstrate that the level of anisotropy can change dramatically during the growth of a single pattern. This is likely to be caused by the increase and the reaching of a critical level of protein precipitation as the drop is drying up. Various examples of pattern formation driven by moving unstable interfaces can be described by Laplacian growth. In this case the boundary condition along the $`\mathrm{\Gamma }`$ interface containing the dimensionless uΓ concentration term is a8 ; a9 ; a10 ; a11 :

$$u_\mathrm{\Gamma }=\mathrm{\Delta }d_0(\mathrm{\Theta })\kappa \beta (\mathrm{\Theta })v_n,$$
(3)
where $`\mathrm{\Delta }`$ is the undercooling, the capillary length d0 is proportional to the surface tension, $`\kappa `$ denotes the local curvature of the interface, $`\beta `$ is the kinetic coefficient, $`\mathrm{\Theta }`$ is the angle between the normal to the surface and a fixed crystallographic direction, vn is the normal velocity of the interface. To explain the stable tip-tip splitting transition, we propose that d0 is altered and its anisotropy is decreased due to the adherence of the protein layer to the KCl crystal surface. Other effects may also have an impact on the morphology of KCl patterns. The lower diffusion coefficient of K+ and Cl- ions in the liquid phase due to the high protein concentration during drying up might induce transport limited growth. Both the decreased velocity of the interface and the modification of the angular dependence of its coefficient ($`\beta `$) by a rather isotropic incorporation process of KCl into the crystal caused by the protein coating can lead to lower anisotropy of the pattern. The incorporation of proteins into calcite crystals is known to have an effect on the morphology a15 . However, fluorescent images displayed high protein concentration on the surface of crystals, we can not totally exclude incorporation. IgG typically and under some conditions tubulin and albumin also induced the growth of elongated saw-toothed crystals instead of rectangular needle-shaped ones. Branching saw-toothed structures were also found, the angle between the branches is $``$70. We argue that these are single crystals elongated in the (111) direction of the cubic crystal i.e., their axis lies in this direction. The angle between (111) and directions with the same symmetry e.g. (11-1) is 70.5. The mechanism leading to the formation of these crystals is unknown. Proteins can adhere to specific faces of the crystal with increased affinity a2 . This anisotropic interaction influences the anisotropy of the surface tension at the crystal-protein interface $`\gamma `$c-p, which may result in the change of the direction of the fast growing tip. The background of the protein specific behavior is unclear. As the experiment on the gold substrate indicates, in addition to the protein-crystal interaction protein-substrate and crystal-substrate effects also should be considered in further studies.

## V Acknowledgments

This work was supported by the Hungarian National Scientific Research Fund (OTKA, No. T-034995). We thank Noémi Rozlosnik and András Czirók for the help in establishing the instrumental background of our experiments, and Judit Ovádi and Emma Hlavanda for the tubulin samples.