We consider the discrete Gaussian Free Field in a square box in ( Z ^2 ) of side length N with zero boundary conditions and study the joint law of its properly-centered extreme values (h) and their scaled spatial positions (x) in the limit as ( N ). Restricting attention to extreme local maxima, i.e., the extreme points that are maximal in an r N -neighborhood thereof, we prove that the associated process tends, whenever ( r_N ) and ( r_N N 0 ), to a Poisson point process with intensity measure ( Z ( dx) e ^ - h d h ), where ( := 2 g ) with g: = 2 π and where Z(dx) is a random Borel measure on [0, 1]2. In particular, this yields an integral representation of the law of the absolute maximum, similar to that found in the context of Branching Brownian Motion. We give evidence that the random measure Z is a version of the derivative martingale associated with the continuum Gaussian Free Field.
Building further upon this beautiful structure, Arguin, Bovier and Kistler @cite_41 @cite_35 @cite_3 and independently A "id 'ekon, Berestycki, Brunet and Shi @cite_32 have recently managed to control the full distribution of the extreme points of the set @math as @math . The limit point process is a cluster process associated with Gumbel law of intensity @math , again quite analogously to what we show (modulo the clusters) for the DGFF in Theorem . A key fact (proved in @cite_41 ) is the separation of time scales: If @math and @math are close to @math , then the corresponding Brownian paths split either right at the beginning (i.e., at a time @math ) or or right at the very end (i.e., at a time @math ). The splittings in time @math give rise to a residual'' randomness in the problem; this is the origin of the random variable @math .
@cite_41 @cite_35 @cite_32 @cite_3
2000931246 1971902881 2056809837 2102318662
Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 As a first step toward a characterization of the limiting extremal process of branching Brownian motion, we proved in a recent work [Comm. Pure Appl. Math. 64 (2011) 1647-1676] that, in the limit of large time @math , extremal particles descend with overwhelming probability from ancestors having split either within a distance of order 1 from time 0, or within a distance of order 1 from time @math . The result suggests that the extremal process of branching Brownian motion is a randomly shifted cluster point process. Here we put part of this picture on rigorous ground: we prove that the point process obtained by retaining only those extremal particles which are also maximal inside the clusters converges in the limit of large @math to a random shift of a Poisson point process with exponential density. The last section discusses the Tidal Wave Conjecture by Lalley and Sellke [Ann. Probab. 15 (1987) 1052-1061] on the full limiting extremal process and its relation to the work of Chauvin and Rouault [Math. Nachr. 149 (1990) 41-59] on branching Brownian motion with atypical displacement. We prove that the extremal process of branching Brownian motion, in the limit of large times, converges weakly to a cluster point process. The limiting process is a (randomly shifted) Poisson cluster process, where the positions of the clusters is a Poisson process with intensity measure with exponential density. The law of the individual clusters is characterized as branching Brownian motions conditioned to perform “unusually large displacements”, and its existence is proved. The proof combines three main ingredients. First, the results of Bramson on the convergence of solutions of the Kolmogorov–Petrovsky–Piscounov equation with general initial conditions to standing waves. Second, the integral representations of such waves as first obtained by Lalley and Sellke in the case of Heaviside initial conditions. Third, a proper identification of the tail of the extremal process with an auxiliary process (based on the work of Chauvin and Rouault), which fully captures the large time asymptotics of the extremal process. The analysis through the auxiliary process is a rigorous formulation of the cavity method developed in the study of mean field spin glasses. We study the maximum of a Gaussian field on @math ( @math ) whose correlations decay logarithmically with the distance. Kahane Kah85 introduced this model to construct mathematically the Gaussian multiplicative chaos in the subcritical case. Duplantier, Rhodes, Sheffield and Vargas DRSV12a DRSV12b extended Kahane's construction to the critical case and established the KPZ formula at criticality. Moreover, they made in DRSV12a several conjectures on the supercritical case and on the maximum of this Gaussian field. In this paper we resolve Conjecture 12 in DRSV12a : we establish the convergence in law of the maximum and show that the limit law is the Gumbel distribution convoluted by the limit of the derivative martingale.