اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدCombinatorial approach to the interpolation method and scaling limits in sparse random graphs
216
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We establish the existence of free energy limits for several combinatorial models on Erd{o}s-R{e}nyi graph $mathbb {G}(N,lfloor cNrfloor)$ and random $r$-regular graph $mathbb {G}(N,r)$. For a variety of models, including independent sets, MAX-CUT, coloring and K-SAT, we prove that the free energy both at a positive and zero temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. In the zero temperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. This resolves an open problem which was proposed by Aldous (Some open problems) as one of his six favorite open problems. It was also mentioned as an open problem in several other places: Conjecture 2.20 in Wormald [In Surveys in Combinatorics, 1999 (Canterbury) (1999) 239-298 Cambridge Univ. Press]; Bollob{a}s and Riordan [Random Structures Algorithms 39 (2011) 1-38]; Janson and Thomason [Combin. Probab. Comput. 17 (2008) 259-264] and Aldous and Steele [In Probability on Discrete Structures (2004) 1-72 Springer].
قيم البحث
اقرأ أيضاً
In this paper we complete the investigation of scaling limits of the odometer in divisible sandpiles on $d$-dimensional tori generalising the works Chiarini et al. (2018), Cipriani et al. (2017, 2018). Relaxing the assumption of independence of the w
eights of the divisible sandpile, we generate generalised Gaussian fields in the limit by specifying the Fourier multiplier of their covariance kernel. In particular, using a Fourier multiplier approach, we can recover fractional Gaussian fields of the form $(-Delta)^{-(1+s)} W$ for $s>0$ and $W$ a spatial white noise on the $d$-dimensional unit torus.
We show that at any location away from the spectral edge, the eigenvalues of the Gaussian unitary ensemble and its general beta siblings converge to Sine_beta, a translation invariant point process. This process has a geometric description in term of
the Brownian carousel, a deterministic function of Brownian motion in the hyperbolic plane. The Brownian carousel, a description of the a continuum limit of random matrices, provides a convenient way to analyze the limiting point processes. We show that the gap probability of Sine_beta is continuous in the gap size and $beta$, and compute its asymptotics for large gaps. Moreover, the stochastic differential equation version of the Brownian carousel exhibits a phase transition at beta=2.
We consider various asymptotic scaling limits $Ntoinfty$ for the $2N$ complex eigenvalues of non-Hermitian random matrices in the symmetry class of the symplectic Ginibre ensemble. These are known to be integrable, forming Pfaffian point processes, a
nd we obtain limiting expressions for the corresponding kernel for different potentials. The first part is devoted to the symplectic Ginibre ensemble with a Gaussian potential. We obtain the asymptotic at the edge of the spectrum in the vicinity of the real line. The unifying form of the kernel allows us to make contact with the bulk scaling along the real line and with the edge scaling away from the real line, where we recover the known determinantal process of the complex Ginibre ensemble. Part two covers ensembles of Mittag-Leffler type with a singularity at the origin. For potentials $Q(zeta)=|zeta|^{2lambda}-(2c/N)log|zeta|$, with $lambda>0$ and $c>-1$, the limiting kernel obeys a linear differential equation of fractional order $1/lambda$ at the origin. For integer $m=1/lambda$ it can be solved in terms of Mittag-Leffler functions. In the last part, we derive the Wards equation for a general class of potentials as a tool to investigate universality. This allows us to determine the functional form of kernels that are translation invariant up to its integration domain.
We study a particular class of complex-valued random variables and their associated random walks: the complex obtuse random variables. They are the generalization to the complex case of the real-valued obtuse random variables which were introduced in
cite{A-E} in order to understand the structure of normal martingales in $RR^n$.The extension to the complex case is mainly motivated by considerations from Quantum Statistical Mechanics, in particular for the seek of a characterization of those quantum baths acting as classical noises. The extension of obtuse random variables to the complex case is far from obvious and hides very interesting algebraical structures. We show that complex obtuse random variables are characterized by a 3-tensor which admits certain symmetries which we show to be the exact 3-tensor analogue of the normal character for 2-tensors (i.e. matrices), that is, a necessary and sufficient condition for being diagonalizable in some orthonormal basis. We discuss the passage to the continuous-time limit for these random walks and show that they converge in distribution to normal martingales in $CC^N$. We show that the 3-tensor associated to these normal martingales encodes their behavior, in particular the diagonalization directions of the 3-tensor indicate the directions of the space where the martingale behaves like a diffusion and those where it behaves like a Poisson process. We finally prove the convergence, in the continuous-time limit, of the corresponding multiplication operators on the canonical Fock space, with an explicit expression in terms of the associated 3-tensor again.
We give a method for taking microscopic limits of normal matrix ensembles. We apply this method to study the behaviour near certain types of singular points on the boundary of the droplet. Our investigation includes ensembles without restrictions nea
r the boundary, as well as hard edge ensembles, where the eigenvalues are confined to the droplet. We establish in both cases existence of new types of determinantal point fields, which differ from those which can appear at a regular boundary point, or in the bulk.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
