ترغب بنشر مسار تعليمي؟ اضغط هنا

Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model

116   0   0.0 ( 0 )
 نشر من قبل Thomas Jackson
 تاريخ النشر 2009
  مجال البحث فيزياء
والبحث باللغة English




اسأل ChatGPT حول البحث

The minimum spanning tree (MST) is a combinatorial optimization problem: given a connected graph with a real weight (cost) on each edge, find the spanning tree that minimizes the sum of the total cost of the occupied edges. We consider the random MST, in which the edge costs are (quenched) independent random variables. There is a strongly-disordered spin-glass model due to Newman and Stein [Phys. Rev. Lett. 72, 2286 (1994)], which maps precisely onto the random MST. We study scaling properties of random MSTs using a relation between Kruskals greedy algorithm for finding the MST, and bond percolation. We solve the random MST problem on the Bethe lattice (BL) with appropriate wired boundary conditions and calculate the fractal dimension D=6 of the connected components. Viewed as a mean-field theory, the result implies that on a lattice in Euclidean space of dimension d, there are of order W^{d-D} large connected components of the random MST inside a window of size W, and that d = d_c = D = 6 is a critical dimension. This differs from the value 8 suggested by Newman and Stein. We also critique the original argument for 8, and provide an improved scaling argument that again yields d_c=6. The result implies that the strongly-disordered spin-glass model has many ground states for d>6, and only of order one below six. The results for MSTs also apply on the Poisson-weighted infinite tree, which is a mean-field approach to the continuum model of MSTs in Euclidean space, and is a limit of the BL. In a companion paper we develop an epsilon=6-d expansion for the random MST on critical percolation clusters.



قيم البحث

اقرأ أيضاً

We propose a mean field theory for the localization of damage in a quasistatic fuse model on a cylinder. Depending on the quenched disorder distribution of the fuse thresholds, we show analytically that the system can either stay in a percolation reg ime up to breakdown, or start at some current level to localize starting from the smallest scale (lattice spacing), or instead go to a diffuse localization regime where damage starts to concentrate in bands of width scaling as the width of the system, but remains diffuse at smaller scales. Depending on the nature of the quenched disorder on the fuse thresholds, we derive analytically the phase diagram of the system separating these regimes and the current levels for the onset of these possible localizations. We compare these predictions to numerical results.
We develop a simple method to study the high temperature, or high external field, behavior of the Sherrington-Kirkpatrick mean field spin glass model. The basic idea is to couple two different replicas with a quadratic term, trying to push out the tw o replica overlap from its replica symmetric value. In the case of zero external field, our results reproduce the well known validity of the annealed approximation, up to the known critical value for the temperature. In the case of nontrivial external field, we prove the validity of the Sherrington-Kirkpatrick replica symmetric solution up to a line, which falls short of the Almeida-Thouless line, associated to the onset of the spontaneous replica symmetry breaking, in the Parisi Ansatz. The main difference with the method, recently developed by Michel Talagrand, is that we employ a quadratic coupling, and not a linear one. The resulting flow equations, with respect to the parameters of the model, turn out to be much simpler, and more tractable. By applying the cavity method, we show also how to determine free energy and overlap fluctuations, in the region where replica symmetry has been shown to hold.
We develop a mean-field theory of the growth, exchange and distribution (GED) model introduced by Kang et al. (preceding paper) that accurately describes the phase transition in the limit that the number of agents $N$ approaches infinity. The GED mod el is a generalization of the Yard-Sale model in which the additional wealth added by economic growth is nonuniformly distributed to the agents according to their wealth in a way determined by the parameter $lambda$. The model was shown numerically to have a phase transition at $lambda=1$ and be characterized by critical exponents and critical slowing down. Our mean-field treatment of the GED model correctly predicts the existence of the phase transition, critical slowing down, the values of the critical exponents, and introduces an energy whose probability satisfies the Boltzmann distribution for $lambda < 1$, implying that the system is in thermodynamic equilibrium in the limit that $N to infty$. We show that the values of the critical exponents obtained by varying $lambda$ for a fixed value of $N$ do not satisfy the usual scaling laws, but do satisfy scaling if a combination of parameters, which we refer to as the Ginzburg parameter, is much greater than one and is held constant. We discuss possible implications of our results for understanding economic systems and the subtle nature of the mean-field limit in systems with both additive and multiplicative noise.
In this paper we present a new mathematical rigorous technique for computing the average free energy of a disordered system with quenched randomness, using the replicas. The basic tool of this technique is a distributional zeta-function, a complex fu nction whose derivative at the origin yields the average free energy of the system as the sum of two contributions: the first one is a series in which all the integer moments of the partition function of the model contribute; the second one, which can not be written as a series of the integer moments, can be made as small as desired. This result supports the use of integer moments of the partition function, computed via replicas, for expressing the average free energy of the system. One advantage of the proposed formalism is that it does not require the understanding of the properties of the permutation group when the number of replicas goes to zero. Moreover, the symmetry is broken using the saddle-point equations of the model. As an application for the distributional zeta-function technique, we obtain the average free energy of the disordered $lambdavarphi^{4}$ model defined in a $d$-dimensional Euclidean space.
Mean-field theory (MFT) is one of the main available tools for analytical calculations entailed in investigations regarding many-body systems. Recently, there have been an urge of interest in ameliorating this kind of method, mainly with the aim of i ncorporating geometric and correlation properties of these systems. The correlated cluster MFT (CCMFT) is an improvement that succeeded quite well in doing that for classical spin systems. Nevertheless, even the CCMFT presents some deficiencies when applied to quantum systems. In this article, we address this issue by proposing the quantum CCMFT (QCCMFT), which, in contrast to its former approach, uses general quantum states in its self-consistent mean-field equations. We apply the introduced QCCMFT to the transverse Ising model in honeycomb, square, and simple cubic lattices and obtain fairly good results both for the Curie temperature of thermal phase transition and for the critical field of quantum phase transition. Actually, our results match those obtained via exact solutions, series expansions or Monte Carlo simulations.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا