Weighted enumeration of spanning subgraphs in locally tree‐like graphs

Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree‐like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a b‐matching in the Erd?s–Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb{N}Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree‐like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a b‐matching in the Erd?s–Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb{N}$. To the best of our knowledge, this is the first time that correlation inequalities and unimodularity are combined together to yield a general proof of uniqueness of Gibbs measures on infinite trees. We believe that a similar argument is applicable to other Gibbs measures than those over spanning subgraphs considered here. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Gibbs measures on Brownian currents

Motivated by applications to quantum field theory, we consider Gibbs measures for which the reference measure is Wiener measure and the interaction is given by a double stochastic integral and a pinning external potential. In order to properly characterize these measures through Dobrushin‐Lanford‐Ruelle (DLR) equations, we are led to lifting Wiener measure and other objects to a space of configurations where the basic observables are not only the position of the particle at all times but also the work done by test vector fields. We prove existence and basic properties of such Gibbs measures in the weak coupling regime by means of cluster expansion. © 2008 Wiley Periodicals, Inc.     

Poset limits and exchangeable random posets

We develop a theory of limits of finite posets in close analogy to the recent theory of graph limits. In particular, we study representations of the limits by functions of two variables on a probability space, and connections to exchangeable random infinite posets.     

Gibbs state on a distance-regular graph and its application to a scaling limit of the spectral distributions of discrete Laplacians

On the adjacency algebra of a distance-regular graph we introduce an analogue of the Gibbs state depending on a parameter related to temperature of the graph. We discuss a scaling limit of the spectral distribution of the Laplacian on the graph with respect to the Gibbs state in the manner of central limit theorem in algebraic probability, where the volume of the graph goes to ∞ while the temperature tends to 0. In the model we discuss here (the Laplacian on the Johnson graph), the resulting limit distributions form a one parameter family beginning with an exponential distribution (which corresponds to the case of the vacuum state) and consisting of its deformations by a Bessel function. Received: 7 July 1999 / Revised version: 23 February 2000 / Published online: 5 September 2000     

Geometric Gibbs theory

We extend the classical Gibbs theory for smooth potentials to the geometric Gibbs theory for certain continuous potentials. We study the existence and uniqueness and the compatibility of geometric Gibbs measures associated with these continuous potentials. We introduce a complex Banach manifold structure on the space of these continuous potentials as well as on the space of all geometric Gibbs measures. We prove that with this complex Banach manifold structure, the space is complete and, moreover, is the completion of the space of all smooth potentials as well as the space of all classical Gibbs measures. There is a maximum metric on the space, which is incomplete. We prove that the topology induced by the newly introduced complex Banach manifold structure and the topology induced by the maximal metric are the same. We prove that a geometric Gibbs measure is an equilibrium state, and the infimum of the metric entropy function on the space is zero.

     

A sharp first order analysis of Feynman–Kac particle models,Part II: Particle Gibbs samplers

This article provides a new theory for the analysis of the particle Gibbs (PG) sampler (Andrieu et al., 2010). Following the work of Del Moral and Jasra (2017) we provide some analysis of the particle Gibbs sampler, giving first order expansions of the kernel and minorization estimates. In addition, first order propagation of chaos estimates are derived for empirical measures of the dual particle model with a frozen path, also known as the conditional sequential Monte Carlo (SMC) update of the PG sampler. Backward and forward PG samplers are discussed, including a first comparison of the contraction estimates obtained by first order estimates. We illustrate our results with an example of fixed parameter estimation arising in hidden Markov models.     

Random graphons and a weak Positivstellensatz for graphs

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2‐variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory     

A note on random k-dimensional posets

In 2009, Janson [Poset limits and exchangeable random posets, Institut Mittag-Leffler preprint, 36pp, arXiv:0902.0306] extended the recent theory of graph limits to posets, defining convergence for poset sequences and proving that every such sequence has a limit object. In this paper, we focus on k-dimensional poset sequences. This restriction leads to shorter proofs and to a more intuitive limit object. As before, the limit object can be used as a model for random posets, which generalizes the well known random k-dimensional poset model. This investigation also leads to a definition of quasirandomness for k-dimensional posets, which can be captured by a natural distance that measures the discrepancy of a k-dimensional poset.     

Multigraph limits and exchangeability

The theory of limits of dense graph sequences was initiated by Lovász and Szegedy in [8]. We give a possible generalization of this theory to multigraphs. Our proofs are based on the correspondence between dense graph limits and countable, exchangeable arrays of random variables observed by Diaconis and Janson in [5]. The main ingredient in the construction of the limit object is Aldous?? representation theorem for exchangeable arrays, see [1].     

Thermodynamic Limit for Directed Polymers and Stationary Solutions of the Burgers Equation

The first goal of this paper is to prove multiple asymptotic results for a time-discrete and space-continuous polymer model of a random walk in a random potential. These results include: existence of deterministic free energy density in the infinite-volume limit for every fixed asymptotic slope, concentration inequalities for free energy implying a bound on its fluctuation exponent, and straightness estimates implying a bound on the transversal fluctuation exponent. The culmination of this program is almost sure existence and uniqueness of polymer measures on one-sided infinite paths with given endpoint and slope, and interpretation of these infinite-volume Gibbs measures as thermodynamic limits. Moreover, we prove that marginals of polymer measures with the same slope and different endpoints are asymptotic to each other. The second goal of the paper is to develop ergodic theory of the Burgers equation with positive viscosity and random kick forcing on the real line without any compactness assumptions. Namely, we prove a one force–one solution principle, using the infinite-volume polymer measures to construct a family of stationary global solutions for this system, and proving that each of those solutions is a one-point pullback attractor on the initial conditions with the same spatial average. This provides a natural extension of the same program realized for the inviscid Burgers equation with the help of action minimizers that can be viewed as zero temperature limits of polymer measures. © 2018 Wiley Periodicals, Inc.     

Regularity lemmas in a Banach space setting

Szemerédi’s regularity lemma is a fundamental tool in extremal graph theory, theoretical computer science and combinatorial number theory. Lovász and Szegedy (2007) gave a Hilbert space interpretation of the lemma and an interpretation in terms of compactness of the space of graph limits. In this paper we prove several compactness results in a Banach space setting, generalising results of Lovász and Szegedy (2007) as well as a result of Borgs et al. (2014).     

Geometric Gibbs theory In Memory of Professor Shantao Liao

We extend the classical Gibbs theory for smooth potentials to the geometric Gibbs theory for certain continuous potentials. We study the existence and uniqueness and the compatibility of geometric Gibbs measures associated with these continuous potentials. We introduce a complex Banach manifold structure on the space of these continuous potentials as well as on the space of all geometric Gibbs measures. We prove that with this complex Banach manifold structure, the space is complete and, moreover, is the completion of the space of all smooth potentials as well as the space of all classical Gibbs measures. There is a maximum metric on the space,which is incomplete. We prove that the topology induced by the newly introduced complex Banach manifold structure and the topology induced by the maximal metric are the same. We prove that a geometric Gibbs measure is an equilibrium state, and the infimum of the metric entropy function on the space is zero.     

Large deviations for Gibbs random fields

A large deviation principle for Gibbs random fields on Z^d is proven and a corresponding large deviations proof of the Gibbs variational formula is given. A generalization of the Lanford theory of large deviations is also obtained.This work was partially supported by NSF-DMR81-14726     

More on quasi-random graphs,subgraph counts and graph limits

We study some properties of graphs (or, rather, graph sequences) defined by demanding that the number of subgraphs of a given type, with vertices in subsets of given sizes, approximatively equals the number expected in a random graph. It has been shown by several authors that several such conditions are quasi-random, but that there are exceptions. In order to understand this better, we investigate some new properties of this type. We show that these properties too are quasi-random, at least in some cases; however, there are also cases that are left as open problems, and we discuss why the proofs fail in these cases.The proofs are based on the theory of graph limits; and on the method and results developed by Janson (2011), this translates the combinatorial problem to an analytic problem, which then is translated to an algebraic problem.     

Quadri-tilings of the Plane

We introduce quadri-tilings and show that they are in bijection with dimer models on a family of graphs R ^* arising from rhombus tilings. Using two height functions, we interpret a sub-family of all quadri-tilings, called triangular quadri-tilings, as an interface model in dimension 2+2. Assigning “critical" weights to edges of R ^*, we prove an explicit expression, only depending on the local geometry of the graph R ^*, for the minimal free energy per fundamental domain Gibbs measure; this solves a conjecture of Kenyon (Invent Math 150:409–439, 2002). We also show that when edges of R ^* are asymptotically far apart, the probability of their occurrence only depends on this set of edges. Finally, we give an expression for a Gibbs measure on the set of all triangular quadri-tilings whose marginals are the above Gibbs measures, and conjecture it to be that of minimal free energy per fundamental domain.     

Multifractal analysis and the variance of Gibbs measures

The multifractal decomposition of Gibbs measures for a conformaliterated function system is well known. We look at a finer decompositionwhich also takes into account the rate of convergence. Thisis motivated by the work of Olsen in the self-similar case.Our study of this finer decomposition involves investigationof the variance of Gibbs measures. This is a problem of independentinterest.     

Construction of Gibbs measures for 1-dimensional continuum fields

We study 1-dimensional continuum fields of Ginzburg-Landau type under the presence of an external and a long-range pair interaction potentials. The corresponding Gibbs states are formulated as Gibbs measures relative to Brownian motion [17]. In this context we prove the existence of Gibbs measures for a wide class of potentials including a singular external potential as hard-wall ones, as well as a non-convex interaction. Our basic methods are: (i) to derive moment estimates via integration by parts; and (ii) in its finite-volume construction, to represent the hard-wall Gibbs measure on C(ℝ;ℝ⁺) in terms of a certain rotationally invariant Gibbs measure on C(ℝ;ℝ³).     

Translation-invariant and periodic Gibbs measures for the Potts model on a Cayley tree

We study translation-invariant Gibbs measures on a Cayley tree of order k = 3 for the ferromagnetic three-state Potts model. We obtain explicit formulas for translation-invariant Gibbs measures. We also consider periodic Gibbs measures on a Cayley tree of order k for the antiferromagnetic q-state Potts model. Moreover, we improve previously obtained results: we find the exact number of periodic Gibbs measures with the period two on a Cayley tree of order k ≥ 3 that are defined on some invariant sets.