Volume 49, Issue 12, December 2008

We analyze a new general representation for the minimum weight Steiner tree problem that translates the topological connectivity constraint into a set of local conditions, which can be analyzed by the socalled cavity equation techniques. For the limit case of the spanning tree, we prove that the fixed point of the algorithm arising from the cavity equations leads to the global optimum.
 SPECIAL ISSUE: STATISTICAL MECHANICS ON RANDOM STRUCTURES


Introduction to Special Issue: Statistical Mechanics on Random Structures
View Description Hide Description 
The interaction between multioverlaps in the high temperature phase of the Sherrington–Kirkpatrick spin glass
View Description Hide DescriptionIn this paper we explore the joint behavior of a finite number of multioverlaps in the high temperature phase of the Sherrington–Kirkpatrick model. Extending the work by Talagrand [Spin Glasses: A Challenge for Mathematicians. Cavity and Mean FieldModels, A series of Modern Surveys in Mathematics Vol. 46 (SpringerVerlag, Berlin, 2003)], we show that, when these objects are scaled to have nontrivial limiting distributions, the joint behavior is described by a Gaussian process with an explicit covariance structure.

Fluctuations of the partition function in the generalized random energy model with external field
View Description Hide DescriptionWe study Derrida’s generalized random energy model (GREM) in the presence of uniform external field. We compute the fluctuations of the ground state and of the partition function in the thermodynamic limit for all admissible values of parameters. We find that the fluctuations are described by a hierarchical structure which is obtained by a certain coarse graining of the initial hierarchical structure of the GREM with external field. We provide an explicit formula for the free energy of the model. We also derive some large deviation results providing an expression for the free energy in a class of models with Gaussian Hamiltonians and external field. Finally, we prove that the coarsegrained parts of the system emerging in the thermodynamic limit tend to have a certain optimal magnetization, as prescribed by the strength of the external field and by parameters of the GREM.

Minimal supporting subtrees for the free energy of polymers on disordered trees
View Description Hide DescriptionWe consider a model of directed polymers on a regular tree with a disorder given by independent, identically distributed weights attached to the vertices. For suitable weight distributions this model undergoes a phase transition with respect to its localization behavior. We show that, for high temperatures, the free energy is supported by a random tree of positive exponential growth rate, which is strictly smaller than that of the full tree. The growth rate of the minimal supporting subtree decreases to zero as the temperature decreases to the critical value. At the critical value and all lower temperatures, a single polymer suffices to support the free energy. Our proofs rely on elegant martingale methods adapted from the theory of branching random walks.

A remark on the infinitevolume Gibbs measures of spin glasses
View Description Hide DescriptionIn this note, we point out that infinitevolume Gibbs measures of spin glass models on the hypercube can be identified as random probability measures on the unit ball of a Hilbert space. This simple observation follows from a result of Dovbysh and Sudakov on weakly exchangeable random matrices. Limiting Gibbs measures can then be studied as single welldefined objects. This approach naturally extends the space of random overlap structures as defined by Aizenman et al. We discuss the Ruelle probability cascades and the stochastic stability within this framework. As an application, we use an idea of Parisi and Talagrand to prove that if a sequence of finitevolume Gibbs measures satisfies the Ghirlanda–Guerra identities, then the infinitevolume measure must be singular as a measure on a Hilbert space.

Universal structures in some mean field spin glasses and an application
View Description Hide DescriptionWe discuss a spin glass reminiscent of the random energymodel (REM), which allows, in particular, to recast the Parisi minimization into a more classical Gibbs variational principle, thereby shedding some light into the physical meaning of the order parameter of the Parisi theory. As an application, we study the impact of an extensive cavity field on Derrida’s REM: Despite its simplicity, this model displays some interesting features such as ultrametricity and chaos in temperature.

A rigorous analysis of the cavity equations for the minimum spanning tree
View Description Hide DescriptionWe analyze a new general representation for the minimum weight Steiner tree problem that translates the topological connectivity constraint into a set of local conditions, which can be analyzed by the socalled cavity equation techniques. For the limit case of the spanning tree, we prove that the fixed point of the algorithm arising from the cavity equations leads to the global optimum.

Susceptibility in subcritical random graphs
View Description Hide DescriptionWe study the evolution of the susceptibility in the subcritical random graph as tends to infinity. We obtain precise asymptotics of its expectation and variance and show that it obeys a law of large numbers. We also prove that the scaled fluctuations of the susceptibility around its deterministic limit converge to a Gaussian law. We further extend our results to higher moments of the component size of a random vertex and prove that they are jointly asymptotically normal.

Loss and recovery of Gibbsianness for models in external fields
View Description Hide DescriptionWe consider planar rotors ( spins) in , starting from an initial Gibbs measure and evolving with infinitetemperature stochastic (diffusive) dynamics. At intermediate times, if the system starts at low temperature, Gibbsianness can be lost. Due to the influence of the external initial field, Gibbsianness can be recovered after large finite times. We prove some results supporting this picture.

Universality for distances in powerlaw random graphs
View Description Hide DescriptionWe survey the recent work on phase transition and distances in various random graph models with general degree sequences. We focus on inhomogeneous random graphs, the configuration model, and affine preferential attachment models, and pay special attention to the setting where these random graphs have a powerlaw degree sequence. This means that the proportion of vertices with degree in large graphs is approximately proportional to for some . Since many real networks have been empirically shown to have powerlaw degree sequences, these random graphs can be seen as more realistic models for real complex networks than classical random graphs such as the Erdős–Rényi random graph. It is often suggested that the behavior of random graphs should have a large amount of universality, meaning, in this case, that random graphs with similar degree sequences share similar behavior. We survey the available results on graph distances in powerlaw random graphs that are consistent with this prediction.

Mathematical foundation of quantum annealing
View Description Hide DescriptionQuantum annealing is a generic name of quantum algorithms that use quantummechanical fluctuations to search for the solution of an optimization problem. It shares the basic idea with quantum adiabatic evolution studied actively in quantum computation. The present paper reviews the mathematical and theoretical foundations of quantum annealing. In particular, theorems are presented for convergence conditions of quantum annealing to the target optimal state after an infinitetime evolution following the Schrödinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence for both the Schrödinger dynamics and the stochastic dynamics in spite of the essential difference of these two types of dynamics. Also described are the prescriptions to reduce errors in the final approximate solution obtained after a long but finite dynamical evolution of quantum annealing. It is shown there that we can reduce errors significantly by an ingenious choice of annealing schedule (time dependence of the control parameter) without compromising computational complexity qualitatively. A review is given on the derivation of the convergence condition for classical simulated annealing from the view point of quantum adiabaticity using a classicalquantum mapping.

An example of mathematical authorship attribution
View Description Hide DescriptionIn this paper we discuss a novel mathematical approach to authorship attribution which we implemented recently to face a concrete problem of author recognition. The fundamental ideas for our methods came from statistical mechanics and information theory. We combine two approaches. Both of them use similarity measures between couples of texts as indicators of stylistic closeness: the first one is based on the comparison of frequencies of fixed length substrings ( grams) throughout the texts; the second one relies on a suitable use of compression algorithms as relative entropy approximators, in the spirit of the socalled Ziv–Merhav theorem. The two methods were separately developed and then combined, together with a suitable and theoretically founded ranking analysis, to produce an original authorship attribution procedure that yielded very successful results on the specific problem to which it was applied. This ranking analysis could be of interest also in other application fields.

A mean field model for spin glasses based on a 2level perceptron
View Description Hide DescriptionWe introduce a mean fieldmodel for spin glasses that is obtained by “iterating” the definition of the perceptron model of [SG] and we prove the validity of the replicasymmetric solution under a condition of the type “high temperature.” The replicasymmetric equations involve six different parameters. This model illustrates, on one hand, that we now have efficient tools to deal with such systems, and on the other hand, that it is probably unreasonable to hope for abstract theorems independent of the specific type of the system.

Central limit theorem and recurrence for random walks in bistochastic random environments
View Description Hide DescriptionWe prove the annealed central limit theorem for random walks in bistochastic random environments on with zerolocal drift. The proof is based on a “dynamicist’s interpretation” of the system and requires a much weaker condition than the customary uniform ellipticity. Moreover, recurrence is derived for .

Coupling, concentration inequalities, and stochastic dynamics
View Description Hide DescriptionIn the context of interacting particle systems, we study the influence of the action of the semigroup on the concentration property of Lipschitz functions. As an application, this gives a new approach to estimate the relaxation speed to equilibrium of interacting particle systems. We illustrate our approach in a variety of examples for which we obtain several new results with short and nontechnical proofs. These examples include the symmetric and asymmetric exclusion processes and hightemperature spinflip dynamics (“Glauber dynamics”). We also give a new proof of the Poincaré inequality, based on coupling, in the context of onedimensional Gibbs measures. In particular, we cover the case of polynomially decaying potentials, where the logSobolev inequality does not hold.

Continuous spin meanfield models: Limiting kernels and Gibbs properties of local transforms
View Description Hide DescriptionWe extend the notion of Gibbsianness for meanfield systems to the setup of general (possibly continuous) local state spaces. We investigate the Gibbs properties of systems arising from an initial meanfield Gibbs measure by application of given local transition kernels. This generalizes previous case studies made for spins taking finitely many values to the first step in the direction to a general theory containing the following parts: (1) A formula for the limiting conditional probability distributions of the transformed system (it holds both in the Gibbs and in the nonGibbs regime and invokes a minimization problem for a “constrained rate function”), (2) a criterion for Gibbsianness of the transformed system for initial Lipschitz–Hamiltonians involving concentration properties of the transition kernels, and (3) a continuity estimate for the singlesite conditional distributions of the transformed system. While (2) and (3) have provable lattice counterparts, the characterization of (1) is stronger in mean field. As applications we show shorttime Gibbsianness of rotator meanfieldmodels on the dimensional sphere under diffusive time evolution and the preservation of Gibbsianness under local coarse graining of the initial local spin space.

On the surveypropagation equations in random constraint satisfiability problems
View Description Hide DescriptionIn this paper we study the existence of a solution of the surveypropagation equations for a given instance of a random problem in the framework of constraint satisfiability. We consider the concrete examples of satisfiability and coloring. We conjecture that when the number of variables goes to infinity, the solution of the surveypropagation equations for a given instance can be obtained by finding the (supposed unique) solution of the corresponding equations on an infinite tree. We conjecture that the surveypropagation equations on a random infinite tree have a unique solution in the suitable range of parameters. We also present analytic arguments that indicate that the surveypropagation equations do have solutions in the satisfiable phase. For simplicity of notation the argument is presented in the case of the coloring problem. The same results extend to other optimization problems where exist configurations that have cost zero, i.e., in the satisfiable phase. On a random graph the solutions of the beliefpropagation equations are associated with the existence of many well separated clusters of configurations (clustering states). We argue that on a random graph the beliefpropagation equations have solutions almost everywhere: the statement may be sharpened by introducing the concept of quasisolution of the beliefpropagation equations.

About the ergodic regime in the analogical Hopfield neural networks: Moments of the partition function
View Description Hide DescriptionIn this paper we introduce and exploit the real replica approach for a minimal generalization of the Hopfield model by assuming the learned patterns to be distributed according to a standard unit Gaussian. We consider the high storage case, when the number of patterns linearly diverges with the number of neurons. We study the infinite volume behavior of the normalized momenta of the partition function. We find a region in the parameter space where the free energy density in the infinite volume limit selfaverages around its annealed approximation, as well as the entropy and the internal energy density. Moreover, we evaluate the corrections to their extensive counterparts with respect to their annealed expressions. The fluctuations of properly introduced overlaps, which act as order parameters, are also discussed.

First passage percolation on locally treelike networks. I. Dense random graphs
View Description Hide DescriptionWe study various properties of least cost paths under independent and identically distributed (iid) disorder for the complete graph and dense Erdős–Rényi random graphs in the connected phase, with iid exponential and uniform weights on edges. Using a simple heuristic, we compute explicitly limiting distributions for (properly recentered) lengths of shortest paths between typical nodes as well as multiple source destination pairs; we also derive asymptotics for the number of edges on the shortest path, namely, the hopcount, and find that the addition of edge weights converts these graphs from ultrasmall world networks to small world networks. Finally we study the Vickrey–Clarke–Groves measure of overpayment for the complete graph with exponential edge weights and show that the complete graph is far from monopolistic for large .

The peculiar phase structure of random graph bisection
View Description Hide DescriptionThe mincut graph bisection problem involves partitioning the vertices of a graph into disjoint subsets, each containing exactly vertices, while minimizing the number of “cut” edges with an endpoint in each subset. When considered over sparse random graphs, the phase structure of the graph bisection problem displays not only certain familiar properties but also some surprises. It is known that when the mean degree is below the critical value of , the cutsize is zero with high probability. We study how the minimum cutsize increases with mean degree above this critical threshold, finding a new analytical upper bound that improves considerably upon previous bounds. Combined with recent results on expander graphs, our bound suggests the unusual scenario that random graph bisection is replica symmetric up to and beyond the critical threshold, with a replica symmetry breaking transition possibly taking place above the threshold. An intriguing algorithmic consequence is that although the problem is NPhard, we can conceivably find nearoptimal cutsizes (whose ratio to the optimal value approaches 1 asymptotically) in polynomial time for typical instances near the phase transition.
