A stochastic multi-cluster model of freeway traffic

A stochastic approach based on the Master equation is proposed to describe the process of formation and growth of car clusters in traffic flow in analogy to usual aggregation phenomena such as the formation of liquid droplets in supersaturated vapour. By this method a coexistence of many clusters on a one-lane circular road has been investigated. Analytical equations have been derived for calculation of the stationary cluster distribution and related physical quantities of an infinitely large system of interacting cars. If the probability per time (or p) to decelerate a car without an obvious reason tends to zero in an infinitely large system, our multi-cluster model behaves essentially in the same way as a one-cluster model studied before. In particular, there are three different regimes of traffic flow (free jet of cars, coexisting phase of jams and isolated cars, highly viscous heavy traffic) and two phase transitions between them. At finite values of p the behaviour is qualitatively different, i.e., there is no sharp phase transition between the free jet of cars and the coexisting phase. Nevertheless, a jump-like phase transition between the coexisting phase and the highly viscous heavy traffic takes place both at and at a finite p. Monte-Carlo simulations have been performed for finite roads showing a time evolution of the system into the stationary state. In distinction to the one-cluster model, a remarkable increasing of the average flux has been detected at certain densities of cars due to finite-size effects. Received 17 September 1999     

Replica Bounds for Optimization Problems and Diluted Spin Systems

In this paper we generalize to the case of diluted spin models and random combinatorial optimization problems a technique recently introduced by Guerra (cond-mat/0205123) to prove that the replica method generates variational bounds for disordered systems. We analyze a family of models that includes the Viana–Bray model, the diluted p-spin model or random XOR-SAT problem, and the random K-SAT problem, showing that the replica/cavity method, at the various levels of approximation, provides systematic schemes to obtain lower bounds of the free-energy at all temperatures and of the ground state energy. In the case of K-SAT and XOR-SAT it thus gives upper bounds of the satisfiability threshold. Our analysis underlines deep connections with the cavity method which are not evident in the long range case.     

Statistical physics analysis of the computational complexity of solving random satisfiability problems using backtrack algorithms

The computational complexity of solving random 3-Satisfiability (3-SAT) problems is investigated using statistical physics concepts and techniques related to phase transitions, growth processes and (real-space) renormalization flows. 3-SAT is a representative example of hard computational tasks; it consists in knowing whether a set of αN randomly drawn logical constraints involving N Boolean variables can be satisfied altogether or not. Widely used solving procedures, as the Davis-Putnam-Loveland-Logemann (DPLL) algorithm, perform a systematic search for a solution, through a sequence of trials and errors represented by a search tree. The size of the search tree accounts for the computational complexity, i.e. the amount of computational efforts, required to achieve resolution. In the present study, we identify, using theory and numerical experiments, easy (size of the search tree scaling polynomially with N) and hard (exponential scaling) regimes as a function of the ratio α of constraints per variable. The typical complexity is explicitly calculated in the different regimes, in very good agreement with numerical simulations. Our theoretical approach is based on the analysis of the growth of the branches in the search tree under the operation of DPLL. On each branch, the initial 3-SAT problem is dynamically turned into a more generic 2+p-SAT problem, where p and 1 - p are the fractions of constraints involving three and two variables respectively. The growth of each branch is monitored by the dynamical evolution of α and p and is represented by a trajectory in the static phase diagram of the random 2+p-SAT problem. Depending on whether or not the trajectories cross the boundary between satisfiable and unsatisfiable phases, single branches or full trees are generated by DPLL, resulting in easy or hard resolutions. Our picture for the origin of complexity can be applied to other computational problems solved by branch and bound algorithms. Received 10 March 2001     

Solution clustering in random satisfiability

For a large number of random constraint satisfaction problems, such as random k-SAT and random graph and hypergraph coloring, we have very good estimates of the largest constraint density for which solutions exist. All known polynomial-time algorithms for these problems, though, fail to find solutions at much lower densities. To understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. In particular, we show that in random k-SAT for k ≥ 8, much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. Moreover, inside each cluster most variables are frozen, i.e., take only one value.     

Frustrated Blume-Emery-Griffiths model

A generalised integer S Ising spin glass model is analysed using the replica formalism. The bilinear couplings are assumed to have a Gaussian distribution with ferromagnetic mean . Incorporation of a quadrupolar interaction term and a chemical potential leads to a richer phase diagram with transitions of first and second order. The first order transition may be interpreted as a phase separation, and contrary to what has been argued previously, it persists in the presence of disorder. Finally, the stability of the replica symmetric solution with respect to fluctuations in replica space is analysed, and the transition lines are obtained both analytically and numerically. Received 13 January 1997     

Order-parameter fluctuations (OPF) in spin glasses: Monte Carlo simulations and exact results for small sizes

The use of parameters measuring order-parameter fluctuations (OPF) has been encouraged by the recent results reported in referenece [2,3] which show that two of these parameters, G and G _c, take universal values in the . In this paper we present a detailed study of parameters measuring OPF for two mean-field models with and without time-reversal symmetry which exhibit different patterns of replica symmetry breaking below the transition: the Sherrington-Kirkpatrick model with and without a field and the Ising p-spin glass (p = 3). We give numerical results and analyze the consequences which replica equivalence imposes on these models in the infinite volume limit. We give evidence for the transition in each system and discuss the character of finite-size effects. Furthermore, a comparative study between this new family of parameters and the usual Binder cumulant analysis shows what kind of new information can be extracted from the finite T behavior of these quantities. The two main outcomes of this work are: 1) Parameters measuring OPF give better estimates than the Binder cumulant for T _c and even for very small systems they give evidence for the transition. 2) For systems with no time-reversal symmetry, parameters defined in terms of connected quantities are the proper ones to look at. Received 20 September 2000 and Received in final form 10 January 2001     

Exact solutions for diluted spin glasses and optimization problems

We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p = 3, gamma(d) = 0.818, and gamma(s) = 0.918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds ( gamma(var)(c) = 4.396 and gamma(var)(c) = 2.149).     

Disorder driven roughening transitions of elastic manifolds and periodic elastic media

The simultaneous effect of both disorder and crystal-lattice pinning on the equilibrium behavior of oriented elastic objects is studied using scaling arguments and a functional renormalization group technique. Our analysis applies to elastic manifolds, e.g., interfaces, as well as to periodic elastic media, e.g., charge-density waves or flux-line lattices. The competition between both pinning mechanisms leads to a continuous, disorder driven roughening transition between a flat state where the mean relative displacement saturates on large scales and a rough state with diverging relative displacement. The transition can be approached by changing the impurity concentration or, indirectly, by tuning the temperature since the pinning strengths of the random and crystal potential have in general a different temperature dependence. For D dimensional elastic manifolds interacting with either random-field or random-bond disorder a transition exists for 2<D<4, and the critical exponents are obtained to lowest order in . At the transition, the manifolds show a superuniversal logarithmic roughness. Dipolar interactions render lattice effects relevant also in the physical case of D=2. For periodic elastic media, a roughening transition exists only if the ratio p of the periodicities of the medium and the crystal lattice exceeds the critical value . For p<p _c the medium is always flat. Critical exponents are calculated in a double expansion in and and fulfill the scaling relations of random field models. Received 28 August 1998     

Phase diagram of randomly polymerized membrane

Using a replica formalism, a generalization of a recent mean field model corresponding to the observed wrinkling transition in randomly polymerized membranes is presented. In this model we study the effects of global fluctuations of the surface normals to the flat membrane, which can be introduced by a random local field. In absence of these global fluctuations, we show that, the model exhibits both continuous and discontinuous transitions between flat and wrinkled phases, contrary to what has been predicted by Bensimon et al. and Attal et al. Phase diagrams both in replica symmetry and in breaking of replica symmetry in sense of Almeida and Thouless are given. We have also investigated the effects of global fluctuations on the replica symmetry phase diagram. We show that, the wrinkled phase is favored and the flat phase is unstable. For large global fluctuations, the transition between wrinkled and flat phases becomes first order. Received: 3 December 1997 / Revised: 31 March 1998 / Accepted: 3 August 1998     

What makes a phase transition? Analysis of the random satisfiability problem

In the last 30 years it was found that many combinatorial systems undergo phase transitions. One of the most important examples of these can be found among the random k-satisfiability problems (often referred to as k-SAT), asking whether there exists an assignment of Boolean values satisfying a Boolean formula composed of clauses with k random variables each. The random 3-SAT problem is reported to show various phase transitions at different critical values of the ratio of the number of clauses to the number of variables. The most famous of these occurs when the probability of finding a satisfiable instance suddenly drops from 1 to 0. This transition is associated with a rise in the hardness of the problem, but until now the correlation between any of the proposed phase transitions and the hardness is not totally clear. In this paper we will first show numerically that the number of solutions universally follows a lognormal distribution, thereby explaining the puzzling question of why the number of solutions is still exponential at the critical point. Moreover we provide evidence that the hardness of the closely related problem of counting the total number of solutions does not show any phase transition-like behavior. This raises the question of whether the probability of finding a satisfiable instance is really an order parameter of a phase transition or whether it is more likely to just show a simple sharp threshold phenomenon. More generally, this paper aims at starting a discussion where a simple sharp threshold phenomenon turns into a genuine phase transition.     

Model glasses coupled to two different heat baths

In a p-spin interaction spherical spin-glass model both the spins and the couplings are allowed to change with time. The spins are coupled to a heat bath with temperature T, while the coupling constants are coupled to a bath having temperature T_J. In an adiabatic limit (where relaxation time of the couplings is much larger that of the spins) we construct a generalized two-temperature thermodynamics. It involves entropies of the spins and the coupling constants. The application for spin-glass systems leads to a standard replica theory with a non-vanishing number of replicas, n=T/T _J . For p>2 there occur at low temperatures two different glassy phases, depending on the value of n. The obtained first-order transitions have positive latent heat, and positive discontinuity of the total entropy. This is an essentially non-equilibrium effect. The dynamical phase transition exists only for n<1. For p=2 correlation of the disorder (leading to a non-zero n) removes the known marginal stability of the spin glass phase. If the observation time is very large there occurs no finite-temperature spin glass phase. In this case there are analogies with the non-equilibrium (aging) dynamics. A generalized fluctuation-dissipation relation is derived. Received 12 July 1999 and Received in final form 8 December 1999     

Dielectric resonances in three-dimensional binary disordered media

Powdered solids often present very specific properties due to their granular nature. Such powders are often obtained by mixing two ingredients in variable proportions: conductor and insulator, or conductor and super-conductor. In a very natural way, these systems are modeled by regular lattices, whose sites or bonds are randomly chosen with given probabilities. It is known that the electrical and optical properties of random bi-dimensional (2D) networks are well described by their conductance's poles (resonances) and residues (amplitudes). The numerical implementation of a spectral method gave the spectral density, the AC conductivity, the multi-fractal properties of the moments for the local electric field (or currents), and spectrum of resonances characteristic of some small clusters (animals). This work extends the spectral method to the three-dimensional (3D) case where the problem is more complicated because the duality property and the corresponding symmetries are broken. As in the 2D-case, the two significant parameters are the ratio of the complex conductances and of both phases, and the probability p (resp. 1-p) of (resp. ). All the resonances lie on the negative real h-axis, i.e. for pure non resistive networks in the AC case. For a static (DC) system, only the value h=0 (corresponding to a binary system with finite and , or and finite) can give a resonance. Some applications are proposed, in particular the ability for small clusters (animals with one, two or three bonds) to present a singular response for well identified frequencies of the incident electromagnetic field. Received 24 March 1999     

Effect of relevant umklapp process on the two-leg Hubbard ladder with a half-filled band under pressure

By means of perturbative renormalization approach we study the effect of relevant umklapp process on dimensional crossover caused by interladder one particle hopping in weakly coupled two-leg Hubbard ladders with a half filled-band. We found that a crossover takes place at a finite value which increases as the amplitude of umklapp process increases. For the system undergoes a phase transition to the spin density wave phase (SDW) via the two particle hopping process, while for the system undergoes a crossover to the two dimensional Fermi liquid phase via one particle hopping process. Received 25 December 1998     

The Stochastic Traveling Salesman Problem: Finite Size Scaling and the Cavity Prediction

We study the random link traveling salesman problem, where lengths l _ij between city i and city j are taken to be independent, identically distributed random variables. We discuss a theoretical approach, the cavity method, that has been proposed for finding the optimum tour length over this random ensemble, given the assumption of replica symmetry. Using finite size scaling and a renormalized model, we test the cavity predictions against the results of simulations, and find excellent agreement over a range of distributions. We thus provide numerical evidence that the replica symmetric solution to this problem is the correct one. Finally, we note a surprising result concerning the distribution of k th-nearest neighbor links in optimal tours, and invite a theoretical understanding of this phenomenon.     

Time distribution and loss of scaling in granular flow

Two cellular automata models with directed mass flow and internal time scales are studied by numerical simulations. Relaxation rules are a combination of probabilistic critical height (probability of toppling p) and deterministic critical slope processes with internal correlation time t_c equal to the avalanche lifetime, in model A, and ,in model B. In both cases nonuniversal scaling properties of avalanche distributions are found for , where is related to directed percolation threshold in d=3. Distributions of avalanche durations for are studied in detail, exhibiting multifractal scaling behavior in model A, and finite size scaling behavior in model B, and scaling exponents are determined as a function of p. At a phase transition to noncritical steady state occurs. Due to difference in the relaxation mechanisms, avalanche statistics at approaches the parity conserving universality class in model A, and the mean-field universality class in model B. We also estimate roughness exponent at the transition. Received: 29 May 1998 / Revised: 8 September 1998 / Accepted: 10 September 1998     

Dynamics of learning for the binary perceptron problem

A polynomial learning algorithm for a perceptron with binary bonds and random patterns is investigated within dynamic mean field theory. A discontinuous freezing transition is found at a temperature where the entropy is still positive. Critical slowing down is observed approaching this temperature from above. The fraction of errors resulting from this learning procedure is finite in the thermodynamic limit for all temperatures and all finite values of the number of patterns per bond. Monte-Carlo simulations on larger samples (N127) are in quantitative agreement. Simulations on smaller samples indicate a finite bound for the existence of perfect solutions in agreement with the replica theory and the zero entropy criterion. This suggests that perfect solutions exist also in larger samples but cannot be found with a polynomial procedure as expected for a combinatorial hard problem.     

A Self-Consistent Ornstein–Zernike Approximation for the Random Field Ising Model

We extend the self-consistent Ornstein–Zernike approximation (SCOZA), first formulated in the context of liquid-state theory, to the study of the random field Ising model. Within the replica formalism, we treat the quenched random field just as another spin variable, thereby avoiding the usual average over the random field distribution. This allows us to study the influence of the distribution on the phase diagram in finite dimensions. The thermodynamics and the correlation functions are obtained as solutions of a set a coupled partial differential equations with magnetization, temperature, and disorder strength as independent variables. A preliminary analysis based on high-temperature and 1/d series expansions shows that the theory can predict accurately the dependence of the critical temperature on disorder strength (no sharp transition, however, occurs for d4). For the bimodal distribution, we find a tricritical point which moves to weaker fields as the dimension is reduced. For the Gaussian distribution, a tricritical point may appear for d around 4.     

Structure and rheology of concentrated wormlike micelles [4]at the shear-induced isotropic-to-nematic transition

We have investigated the simple shear flow behavior of wormlike micelles using small-angle neutron scattering and mechanical measurements. Ternary surfactant solutions made of cetylpyridinium chloride, hexanol and brine (0.2 M NaCl) and hereafter abbreviated as CPCl-Hex were studied in the concentrated regime, . In a preliminary report (Berret et al. [#!ref16!#]), the discontinuity of slope observed in the shear stress versus shear rate curve was interpreted in terms of first-order phase transition between an isotropic state and a shear-induced nematic state ( transition). At the transition rate, , the solution exhibits a macroscopic phase separation into viscous and fluid layers (inhomogeneous shear flow). Above a second characteristic shear rate, the flow becomes homogeneous again, the sheared solution being nematic only. The neutron patterns obtained in the two-state inhomogeneous region have been re-examined. Based on a consistent analysis of both orientational and translational degrees of freedom related to the wormlike micelles, we emphasize new features for the transition. In the present paper, the shear rate variations of the relative proportions of each phase in the two-state region, as well as the viscosity ratio between isotropic and nematic phases are derived. We demonstrate in addition that slightly above the transition rate, the shear induced nematic phase is already strongly oriented, with an order parameter P ₂ = 0.65. The orientational state is that of a nematic flow-oriented monodomain. Finally, from the locations of the neutron scattering maxima for each isotropic and nematic contributions, we evaluate the concentrations for each phase and and derived a dynamical phase diagram of CPCl-Hex, in terms of the stress versus and . According to the classification by Schmitt et al. [#!ref22!#], the transition observed in CPCl-Hex micellar solutions could result from a positive flow-concentration coupling, in agreement with the observed monotonically increasing shear stress in the two-phase region. Received: 16 February 1998 / Revised: 18 February 1998 / Accepted: 24 May 1998     

Collapse transitions of a periodic hydrophilic hydrophobic chain

We study a single self avoiding hydrophilic hydrophobic polymer chain, through Monte-Carlo lattice simulations. The affinity of monomer i for water is characterized by a (scalar) charge , and the monomer-water interaction is short-ranged. Assuming incompressibility yields an effective short ranged interaction between monomer pairs (i,j), proportional to . In this article, we take (resp. ()) for hydrophilic (resp. hydrophobic) monomers and consider a chain with (i) an equal number of hydro-philic and -phobic monomers (ii) a periodic distribution of the along the chain, with periodicity 2p. The simulations are done for various chain lengths N, in d=2 (square lattice) and d=3 (cubic lattice). There is a critical value p _c (d,N) of the periodicity, which distinguishes between different low temperature structures. For p >p _c , the ground state corresponds to a macroscopic phase separation between a dense hydrophobic core and hydrophilic loops. For p <p _c (but not too small), one gets a microscopic (finite scale) phase separation, and the ground state corresponds to a chain or network of hydrophobic droplets, coated by hydrophilic monomers. We restrict our study to two extreme cases, and to illustrate the physics of the various phase transitions. A tentative variational approach is also presented. Received: 10 March 1998 / Received in final form: 25 June 1998 / Accepted: 1st July 1998     

Adsorption of a Gaussian random copolymer chain at an interface

We consider the adsorption of an isolated, Gaussian, random, and quenched copolymer chain at an interface. We first propose a simple analytical method to obtain the adsorption/depletion transition, by averaging over the disorder the partition function instead of the free energy. The adsorption thresholds obtained by previous authors at a solid/liquid and at a liquid/liquid interface for multicopolymer chains can be rederived using this method. We also compare the adsorption thresholds obtained for bimodal and for Gaussian disorder; they only agree for small disorder. We focus on the specific case of an ideally flat asymmetric liquid/liquid interface, and consider the situation where the chain is composed of monomers of two different chemical species A and B. The replica method is developed for this case. We show that the Hartree approximation, coupled to a replica symmetry assumption, leads to the same adsorption thresholds as obtained from our general method. In order to describe the properties of the adsorbed (or depleted) chain, we develop a new approximation for long chains, within the framework of the replica theory. In most cases, the behavior of a random copolymer chain can be mapped onto that of a homopolymer chain at an asymmetric attractive interface. The values of the effective adsorption energy are different for a random and a periodic copolymer chain. Finally, we consider the case of uncorrelated annealed disorder. The behavior of an annealed chain can be mapped onto that of a homopolymer chain at an asymmetric non attractive interface; hence, an annealed chain cannot adsorb at an asymmetric interface. Received 21 January 1999