Core percolation in random graphs: a critical phenomena analysis

We study both numerically and analytically what happens to a random graph of average connectivity α when its leaves and their neighbors are removed iteratively up to the point when no leaf remains. The remnant is made of isolated vertices plus an induced subgraph we call the core. In the thermodynamic limit of an infinite random graph, we compute analytically the dynamics of leaf removal, the number of isolated vertices and the number of vertices and edges in the core. We show that a second order phase transition occurs at α = e = 2.718 ... : below the transition, the core is small but above the transition, it occupies a finite fraction of the initial graph. The finite size scaling properties are then studied numerically in detail in the critical region, and we propose a consistent set of critical exponents, which does not coincide with the set of standard percolation exponents for this model. We clarify several aspects in combinatorial optimization and spectral properties of the adjacency matrix of random graphs. Received 31 January 2001 and Received in final form 26 June 2001     

Dynamics of heuristic optimization algorithms on random graphs

In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity random graphs is analysed. In every algorithmic step, a vertex is chosen with respect to its vertex degree. This vertex, and some environment of it, is covered and removed from the graph. This graph reduction process can be described as a Markovian dynamics in the space of random graphs of arbitrary degree distribution. We discuss some solvable cases, including algorithms already analysed using different techniques, and develop approximation schemes for more complicated cases. The approximations are corroborated by numerical simulations. Received 14 March 2002 Published online 31 July 2002     

Phase transitions in a cluster molecular field approximation

Cluster molecular field approximations represent a substantial progress over the simple Weiss theory where only one spin is considered in the molecular field resulting from all the other spins. In this work we discuss a systematic way of improving the molecular field approximation by inserting spin clusters of variable sizes into a homogeneously magnetised background. The density of states of these spin clusters is then computed exactly. We show that the true non-classical critical exponents can be extracted from spin clusters treated in such a manner. For this purpose a molecular field finite size scaling theory is discussed and effective critical exponents are analysed. Reliable values of critical quantities of various Ising and Potts models are extracted from very small system sizes. Received 30 September 2002 / Received in final form 25 November 2002 Published online 27 January 2003 RID="a" ID="a"e-mail: pleim@theorie1.physik.uni-erlangen.de     

Self-affine random surfaces

We consider general d-dimensional random surfaces that are characterized by power-law power spectra defined in both infinite and finite spectral regions. The first type of surfaces belongs to the class of ideal fractals, whereas the second possess both the smallest and the largest scales and physically is more realistic. For both types we calculate the structure functions (SF) exactly; in addition for the second type we obtain the SF's asymptotic expansions. On this basis we show that the surfaces are (in statistical sense) self-affine and approximately self-affine, respectively. Depending on the value of the spectral exponent, we find imbalance between the finite size effects which results in systematic discrepancy in the scaling properties between the two types of surfaces. Explicit expressions for the topothesy, and in the case of second type of surfaces for the large correlation length and cross-over distances are also derived. Received 3 October 2001 / Received in final form 5 March 2002 Published online 2 October 2002 RID="a" ID="a"e-mail: oyordanov@aubg.bg     

The secondary structure of RNA under tension

We study the force-induced unfolding of random disordered RNA or single-stranded DNA polymers. The system undergoes a second-order phase transition from a collapsed globular phase at low forces to an extensive necklace phase with a macroscopic end-to-end distance at high forces. At low temperatures, the sequence inhomogeneities modify the critical behaviour. We provide numerical evidence for the universality of the critical exponents which, by extrapolation of the scaling laws to zero force, contain useful information on the ground-state (f = 0) properties. This provides a good method for quantitative studies of scaling exponents characterizing the collapsed globule. In order to get rid of the blurring effect of thermal fluctuations, we restrict ourselves to the ground state at fixed external force. We analyze the statistics of rearrangements, in particular below the critical force, and point out its implications for force-extension experiments on single molecules. Received 18 June 2002 and Received in final form 23 September 2002 RID="a" ID="a"e-mail: muller@ipno.in2p3.fr     

Switching current noise and relaxation of ferroelectric domains

We simulate field-induced nucleation and switching of domains in a three-dimensional model of ferroelectrics with quenched disorder and varying domain sizes. We study (1) bursts of the switching current at slow driving along the hysteresis loop (electrical Barkhausen noise) and (2) the polarization reversal when a strong electric field was applied and back-switching after the field was removed. We show how these processes are related to the underlying structure of domain walls, which in turn is controlled by the pinning at quenched local electric fields. When the depolarization fields of bound charges are properly screened we find that the fractal switching current noise may appear with two distinct universal behaviors. The critical depinning of plane domain walls determines the universality class in the case of weak random fields, whereas for large randomness the massive nucleation of domains in the bulk leads to different scaling properties. In both cases the scaling exponents decay logarithmically when the driving frequency is increased. The polarization reverses in the applied field as a power-law, while its relaxation in zero field is a stretch exponential function of time. The stretching exponent depends on the strength of pinning. The results may be applicable for uniaxial relaxor ferroelectrics, such as doped SBN:Ce. Received 7 February 2002 / Received in final form 10 April 2002 Published online 9 July 2002     

Localization of polymers in a finite medium with fixed random obstacles

In this paper we investigate the conformation statistics of a Gaussian chain embedded in a medium of finite size, in the presence of quenched random obstacles. The similarities and differences between the case of random obstacles and the case of a Gaussian random potential are elucidated. The connection with the density of states of electrons in a metal with random repulsive impurities of finite range is discussed. We also interpret the results obtained in some previous numerical simulations. Received 14 August 2001     

Spin glasses on Bethe lattices for large coordination number

We study spin glasses on random lattices with finite connectivity. In the infinite connectivity limit they reduce to the Sherrington Kirkpatrick model. In this paper we investigate the expansion around the high connectivity limit. Within the replica symmetry breaking scheme at two steps, we compute the free energy at the first order in the expansion in inverse powers of the average connectivity (z), both for the fixed connectivity and for the fluctuating connectivity random lattices. It is well known that the coefficient of the 1/z correction for the free energy is divergent at low temperatures if computed in the one step approximation. We find that this annoying divergence becomes much smaller if computed in the framework of the more accurate two steps breaking. Comparing the temperature dependance of the coefficients of this divergence in the replica symmetric, one step and two steps replica symmetry breaking, we conclude that this divergence is an artefact due to the use of a finite number of steps of replica symmetry breaking. The 1/z expansion is well defined also in the zero temperature limit. Received 15 July 2002 Published online 31 December 2002     

Random quantum magnets with broad disorder distribution

We study the critical behavior of Ising quantum magnets with broadly distributed random couplings (J), such that P(ln J) ∼ | ln J|^{-1 - α}, α > 1, for large | ln J| (Lévy flight statistics). For sufficiently broad distributions, α < , the critical behavior is controlled by a line of fixed points, where the critical exponents vary with the Lévy index, α. In one dimension, with = 2, we obtained several exact results through a mapping to surviving Riemann walks. In two dimensions the varying critical exponents have been calculated by a numerical implementation of the Ma-Dasgupta-Hu renormalization group method leading to ≈ 4.5. Thus in the region 2 < α < , where the central limit theorem holds for | ln J| the broadness of the distribution is relevant for the 2d quantum Ising model. Received 6 December 2000 and Received in final form 22 January 2001     

Towards finite-dimensional gelation

We consider the gelation of particles which are permanently connected by random crosslinks, drawn from an ensemble of finite-dimensional continuum percolation. To average over the randomness, we apply the replica trick, and interpret the replicated and crosslink-averaged model as an effective molecular fluid. A Mayer-cluster expansion for moments of the local static density fluctuations is set up. The simplest non-trivial contribution to this series leads back to mean-field theory. The central quantity of mean-field theory is the distribution of localization lengths, which we compute for all connectivities. The highly crosslinked gel is characterized by a one-to-one correspondence of connectivity and localization length. Taking into account higher contributions in the Mayer-cluster expansion, systematic corrections to mean-field can be included. The sol-gel transition shifts to a higher number of crosslinks per particle, as more compact structures are favored. The critical behavior of the model remains unchanged as long as finite truncations of the cluster expansion are considered. To complete the picture, we also discuss various geometrical properties of the crosslink network, e.g. connectivity correlations, and relate the studied crosslink ensemble to a wider class of ensembles, including the Deam-Edwards distribution. Received on 24 April 2002 Published online 14 October 2002 RID="a" ID="a"deceased RID="b" ID="b"e-mail: weigt@theorie.physik.uni-goettingen.de     

Properties of a growing random directed network

We study a number of properties of a simple random growing directed network which can be used to model real directed networks such as the world-wide web and call graphs. We confirm numerically that the distributions of in- and out-degree are consistent with a power law, in agreement with previous analytical results and with empirical measurements from real graphs. We study the distribution and mean of the minimum path length, the high degree nodes, the appearance and size of the giant component and the topology of the nodes outside the giant component. These properties are compared with empirical studies of the world-wide web. Received 15 June 2001 and Received in final form 12 July 2001     

Non-equilibrium behavior at a liquid-gas critical point

Second-order phase transitions in a non-equilibrium liquid-gas model with reversible mode couplings, i.e., model H for binary-fluid critical dynamics, are studied using dynamic field theory and the renormalization group. The system is driven out of equilibrium either by considering different values for the noise strengths in the Langevin equations describing the evolution of the dynamic variables (effectively placing these at different temperatures), or more generally by allowing for anisotropic noise strengths, i.e., by constraining the dynamics to be at different temperatures in d _|| - and d _⊥-dimensional subspaces, respectively. In the first, isotropic case, we find one infrared-stable and one unstable renormalization group fixed point. At the stable fixed point, detailed balance is dynamically restored, with the two noise strengths becoming asymptotically equal. The ensuing critical behavior is that of the standard equilibrium model H. At the novel unstable fixed point, the temperature ratio for the dynamic variables is renormalized to infinity, resulting in an effective decoupling between the two modes. We compute the critical exponents at this new fixed point to one-loop order. For model H with spatially anisotropic noise, we observe a critical softening only in the d _⊥-dimensional sector in wave vector space with lower noise temperature. The ensuing effective two-temperature model H does not have any stable fixed point in any physical dimension, at least to one-loop order. We obtain formal expressions for the novel critical exponents in a double expansion about the upper critical dimension d _c = 4 - d _|| and with respect to d _|| , i.e., about the equilibrium theory. Received 4 April 2002 Published online 13 August 2002     

Infinite chain of different deltas: A simple model for a quantum wire

We present the exact diagonalization of the Schr?dinger operator corresponding to a periodic potential with N deltas of different couplings, for arbitrary N. This basic structure can repeat itself an infinite number of times. Calculations of band structure can be performed with a high degree of accuracy for an infinite chain and of the correspondent eigenlevels in the case of a random chain. The main physical motivation is to modelate quantum wire band structure and the calculation of the associated density of states. These quantities show the fundamental properties we expect for periodic structures although for low energy the band gaps follow unpredictable patterns. In the case of random chains we find Anderson localization; we analize also the role of the eigenstates in the localization patterns and find clear signals of fractality in the conductance. In spite of the simplicity of the model many of the salient features expected in a quantum wire are well reproduced. Received 24 June 2002 Published online 29 November 2002     

Symmetry-breaking in local Lyapunov exponents

Integrable dynamical systems, namely those having as many independent conserved quantities as freedoms, have all Lyapunov exponents equal to zero. Locally, the instantaneous or finite time Lyapunov exponents are nonzero, but owing to a symmetry, their global averages vanish. When the system becomes nonintegrable, this symmetry is broken. A parallel to this phenomenon occurs in mappings which derive from quasiperiodic Schr?dinger problems in 1-dimension. For values of the energy such that the eigenstate is extended, the Lyapunov exponent is zero, while if the eigenstate is localized, the Lyapunov exponent becomes negative. This occurs by a breaking of the quasiperiodic symmetry of local Lyapunov exponents, and corresponds to a breaking of a symmetry of the wavefunction in extended and critical states. Received 25 October 2001 / Received in final form 8 December 2001 Published online 2 October 2002 RID="a" ID="a"e-mail: r.ramaswamy@mail.jnu.ac.in     

Renormalized tricritical behaviour for wetting transitions

In this paper we study tricritical wetting behaviour in three dimensions. In particular we concentrate on systems with short-ranged forces and apply linear functional renormalization group techniques to elucidate the effect of fluctuations upon tricriticality. In comparison with studies of critical wetting we identify an additional fluctuation regime which is relevant for values of the capillary parameter between 2/9 and 1/2. We demonstrate that this regime essentially provides a crossover from mean-field like behaviour, in which tricritical exponents are always distinct from their critical counterparts, from intermediate- and strong-fluctuation behaviour where the critical exponents for tricritical and critical wetting are found to always coincide. We conclude by discussing briefly the possible relevance of these results for experimental studies of wetting. Received 4 January 2001 and Received in final form 11 May 2001     

Low temperature properties of the random field Potts chain

The random field q-states Potts model is investigated using exact groundstates and finite-temperature transfer matrix calculations. It is found that the domain structure and the Zeeman energy of the domains resembles for general q the random field Ising case (q = 2). This is also the expected outcome based on a random-walk picture of the groundstate. The domain size distribution is exponential, and the scaling of the average domain size with the disorder strength is similar for q arbitrary. The zero-temperature properties are compared to the equilibrium spin states at small temperatures, to investigate the effect of local random field fluctuations that imply locally degenerate regions. The response to field perturbations (`chaos') and the susceptibility are investigated. In particular for the chaos exponent it is found to be 1 for q = 2,..., 5. Finally for q = 2 (Ising case) the domain length distribution is studied for correlated random fields. Received 27 August 2002 Published online 19 December 2002 RID="a" ID="a"e-mail: rieger@lusi-sb.de     

Magnetism and phase separation in the ground state of the Hubbard model

We discuss the ground state magnetic phase diagram of the Hubbard model off half filling within the dynamical mean-field theory. The effective single-impurity Anderson model is solved by Wilson's numerical renormalization group calculations, adapted to symmetry broken phases. We find a phase separated, antiferromagnetic state up to a critical doping for small and intermediate values of U, but could not stabilize a Néel state for large U and finite doping. At very large U, the phase diagram exhibits an island with a ferromagnetic ground state. Spectral properties in the ordered phases are discussed. Received 9 January 2002 Published online 25 June 2002     

Growth and addition in a herding model

A model of herding is introduced which is exceptionally simple, incorporating only two phenomena, growth and addition. At each time step either (i) with probability p the system grows through the introduction of a new agent or (ii) with probability q = 1 - p a free agent already in the system is added at random to a group of size k with rate A_k. Two versions of the model, A _k = k and A _k = 1, are solved and in both versions we find two different types of behaviour. When p > 1/2 all the moments of the distribution of group sizes are linear in time for large time and the group distribution is power-law. When p < 1/2 the system runs out of free agents in a finite time. Received 12 February 2002 Published online 9 July 2002     

On the finite size corrections to some random matching problems

We get back to the computation of the leading finite size corrections to some random link matching problems, first adressed by Mézard and Parisi [J. Phys. France 48, 1451 (1987)]. In the so-called bipartite case, their result is in contradiction with subsequent works. We show that they made some mistakes, and correcting them, we get the expected result. In the non bipartite case, we agree with their result but push the analytical treatment further. Received 28 April 2002 Published online 14 October 2002 RID="a" ID="a"e-mail: giorgio.parisi@roma1.infn.it RID="b" ID="b"e-mail: matthieu.ratieville@roma1.infn.it     

Directed spiral site percolation on the square lattice

A new site percolation model, directed spiral percolation (DSP), under both directional and rotational (spiral) constraints is studied numerically on the square lattice. The critical percolation threshold p _c ≈ 0.655 is found between the directed and spiral percolation thresholds. Infinite percolation clusters are fractals of dimension d _f ≈ 1.733. The clusters generated are anisotropic. Due to the rotational constraint, the cluster growth is deviated from that expected due to the directional constraint. Connectivity lengths, one along the elongation of the cluster and the other perpendicular to it, diverge as p → p _c with different critical exponents. The clusters are less anisotropic than the directed percolation clusters. Different moments of the cluster size distribution P _s(p) show power law behaviour with | p - p _c| in the critical regime with appropriate critical exponents. The values of the critical exponents are estimated and found to be very different from those obtained in other percolation models. The proposed DSP model thus belongs to a new universality class. A scaling theory has been developed for the cluster related quantities. The critical exponents satisfy the scaling relations including the hyperscaling which is violated in directed percolation. A reasonable data collapse is observed in favour of the assumed scaling function form of P _s(p). The results obtained are in good agreement with other model calculations. Received 10 November 2002 / Received in final form 20 February 2003 Published online 23 May 2003 RID="a" ID="a"e-mail: santra@iitg.ernet.in