First order limits of sparse graphs: Plane trees and path‐width

Ne?et?il and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree‐depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path‐width has a limit modeling. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 612–635, 2017     

Convergent sequences of sparse graphs: A large deviations approach

Models based on sparse graphs are of interest to many communities: they appear as basic models in combinatorics, probability theory, optimization, statistical physics, information theory, and more applied fields of social sciences and economics. Different notions of similarity (and hence convergence) of sparse graphs are of interest in different communities. In probability theory and combinatorics, the notion of Benjamini‐Schramm convergence, also known as left‐convergence, is used quite frequently. Statistical physicists are interested in the the existence of the thermodynamic limit of free energies, which leads naturally to the notion of right‐convergence. Combinatorial optimization problems naturally lead to so‐called partition convergence, which relates to the convergence of optimal values of a variety of constraint satisfaction problems. The relationship between these different notions of similarity and convergence is, however, poorly understood. In this paper we introduce a new notion of convergence of sparse graphs, which we call Large Deviations or LD‐convergence, and which is based on the theory of large deviations. The notion is introduced by “decorating” the nodes of the graph with random uniform i.i.d. weights and constructing corresponding random measures on and . A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on . The corresponding large deviations rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object. We then establish that LD‐convergence implies the other three notions of convergence discussed above, and at the same time establish several previously unknown relationships between the other notions of convergence. In particular, we show that partition‐convergence does not imply left‐ or right‐convergence, and that right‐convergence does not imply partition‐convergence. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 52–89, 2017     

Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing

We consider sequences of graphs (Gn) and define various notions of convergence related to these sequences: “left convergence” defined in terms of the densities of homomorphisms from small graphs into Gn; “right convergence” defined in terms of the densities of homomorphisms from Gn into small graphs; and convergence in a suitably defined metric.In Part I of this series, we show that left convergence is equivalent to convergence in metric, both for simple graphs Gn, and for graphs Gn with nodeweights and edgeweights. One of the main steps here is the introduction of a cut-distance comparing graphs, not necessarily of the same size. We also show how these notions of convergence provide natural formulations of Szemerédi partitions, sampling and testing of large graphs.     

First order convergence of matroids

The model theory based notion of the first order convergence unifies the notions of the left-convergence for dense structures and the Benjamini–Schramm convergence for sparse structures. It is known that every first order convergent sequence of graphs with bounded tree-depth can be represented by an analytic limit object called a limit modeling. We establish the matroid counterpart of this result: every first order convergent sequence of matroids with bounded branch-depth representable over a fixed finite field has a limit modeling, i.e., there exists an infinite matroid with the elements forming a probability space that has asymptotically the same first order properties. We show that neither of the bounded branch-depth assumption nor the representability assumption can be removed.     

Intersections of graphs

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H. We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K₂ with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P, the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011     

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     

Homomorphisms and polynomial invariants of graphs

This paper initiates a general study of the connection between graph homomorphisms and the Tutte polynomial. This connection can be extended to other polynomial invariants of graphs related to the Tutte polynomial such as the transition, the circuit partition, the boundary, and the coboundary polynomials. As an application, we describe in terms of homomorphism counting some fundamental evaluations of the Tutte polynomial in abelian groups and statistical physics. We conclude the paper by providing a homomorphism view of the uniqueness conjectures formulated by Bollobás, Pebody and Riordan.     

Some results related with statistical convergence and Berezin symbols

The concept of discrete statistical Abel convergence is introduced. In terms of Berezin symbols we present necessary and sufficient condition under which a series with bounded sequence {an}_n?0 of complex numbers is discrete statistically Abel convergent. By using concept of statistical convergence we also give slight strengthening of a result of Gokhberg and Krein on compact operators.     

Limits of random trees

Local convergence of bounded degree graphs was introduced by Benjamini and Schramm [2]. This result was extended further by Lyons [4] to bounded average degree graphs. In this paper, we study the convergence of a random tree sequence (T _n ), where the probability of a given tree T is proportional to $\prod_{v_{i}\in V(T)}d(v_{i})!$ . We show that this sequence is convergent and describe the limit object, which is a random infinite rooted tree.     

Reflection positivity, rank connectivity, and homomorphism of graphs

It is shown that a graph parameter can be realized as the number of homomorphisms into a fixed (weighted) graph if and only if it satisfies two linear algebraic conditions: reflection positivity and exponential rank connectivity. In terms of statistical physics, this can be viewed as a characterization of partition functions of vertex coloring models.

     

Limits of locally–globally convergent graph sequences

The colored neighborhood metric for sparse graphs was introduced by Bollobás and Riordan [BR11]. The corresponding convergence notion refines a convergence notion introduced by Benjamini and Schramm [BS01]. We prove that even in this refined sense, the limit of a convergent graph sequence (with uniformly bounded degree) can be represented by a graphing. We study various topics related to this convergence notion such as: Bernoulli graphings, factor of i.i.d. processes and hyperfiniteness.     

Periodic groups of operators in Banach spaces

Spectral operators of scalar type in the sense of Dunford often occur in connection with unconditionally convergent series expansions, whereas conditionally convergent expansions under similar conditions may be described with the help of operators having a more general type of spectral decomposition. We show that under certain conditions even in the latter case we can restrict our considerations to a dense linear submanifold of the original Banach space with a stronger topology, where the convergence of the expansion under study will be unconditional. Though our conditions could be formulated in terms of a single operator, it seems to be more natural to state them in terms of (the generator of) a periodic group of operators.

     

TVS-锥度量空间中的统计收敛

本文研究TVS-锥度量空间中的统计收敛以及TVS-锥度量空间的统计完备性.令（X，E，P，d）表示一个TVS-锥度量空间.利用定义在有序Hausdorff拓扑向量空间E上的Minkowski函数ρ，证明了在X上存在一个通常意义下的度量d_ρ，使得X中的序列（x_n）在锥度量d意义下统计收敛到x ∈ X，当且仅当（x_n）在度量d_ρ意义下统计收敛到x.基于此，我们证明了任意一个TVS-锥统计Cauchy序列是几乎处处TVS-锥Cauchy序列，还证明了任意一个TVS-锥统计收敛的序列是几乎处处TVS-锥收敛的.从而，TVS-锥度量空间（X，d）是d-完备的，当且仅当它是d-统计完备的.基于以上结论，通常度量空间中统计收敛的许多性质都可以平行地推广到锥度量空间中统计收敛的情形.     

Asynchronous cellular automata and pattern classification

This article designs an efficient two‐class pattern classifier utilizing asynchronous cellular automata (ACAs). The two‐state three‐neighborhood one‐dimensional ACAs that converge to fixed points from arbitrary seeds are used here for pattern classification. To design the classifier, (1) we first identify a set of ACAs that always converge to fixed points from any seeds, (2) each ACA should have at least two but not huge number of fixed point attractors, and (3) the convergence time of these ACAs are not to be exponential. To address the second issue, we propose a graph, coined as fixed point graph of an ACA that facilitates in counting the fixed points. We further perform an experimental study to estimate the convergence time of ACAs, and find there are some convergent ACAs which demand exponential convergence time. Finally, we identify there are 73 (out of 256) ACAs which can be effective candidates as pattern classifier. We use each of the candidate ACAs on some standard datasets, and observe the effectiveness of each ACAs as pattern classifier. It is observed that the proposed classifier is very competitive and performs reliably better than many standard existing classifier algorithms. © 2016 Wiley Periodicals, Inc. Complexity 21: 370–386, 2016     

Normalized convergence in stochastic optimization

A new concept of (normalized) convergence of random variables is introduced. This convergence is preserved under Lipschitz transformations, follows from convergence in mean and itself implies convergence in probability. If a sequence of random variables satisfies a limit theorem then it is a normalized convergent sequence. The introduced concept is applied to the convergence rate study of a statistical approach in stochastic optimization.     

Construction of a new family of Bernstein‐Kantorovich operators

In the present paper, we construct a new sequence of Bernstein‐Kantorovich operators depending on a parameter α. The uniform convergence of the operators and rate of convergence in local and global sense in terms of first‐ and second‐order modulus of continuity are studied. Some graphs and numerical results presenting the advantages of our construction are obtained. The last section is devoted to bivariate generalization of Bernstein‐Kantorovich operators and their approximation behaviors.     

Multicolor containers,extremal entropy,and counting

In breakthrough results, Saxton‐Thomason and Balogh‐Morris‐Samotij developed powerful theories of hypergraph containers. In this paper, we explore some consequences of these theories. We use a simple container theorem of Saxton‐Thomason and an entropy‐based framework to deduce container and counting theorems for hereditary properties of k‐colorings of very general objects, which include both vertex‐ and edge‐colorings of general hypergraph sequences as special cases. In the case of sequences of complete graphs, we further derive characterization and transference results for hereditary properties in terms of their stability families and extremal entropy. This covers within a unified framework a great variety of combinatorial structures, some of which had not previously been studied via containers: directed graphs, oriented graphs, tournaments, multigraphs with bounded multiplicity, and multicolored graphs among others. Similar results were recently and independently obtained by Terry.     

Banach空间中渐近非扩张映射逼近序列的强收敛性

该文研究了序列{x_n}的收敛性。其中x_0∈C, x_{n+1}=α_n T^n x_n+(1-α_n)x, n=0,1,2,…,这里0≤α_n≤1，T是Banach空间中非空闭凸子集C到自身的渐近非扩张映射。同时证明了：当z_n=(1-t_n/k_n)u+t_n/k_n T^n z_n且lim_{n→∞}{(k_n-1)/(1-t_n)}=0,lim‖z_n-Tz_n‖=0时，T有不动点当且仅当{z_n}有界。这时{z_n}强收敛于T的不动点。     

Stability of the geometric Ekeland variational principle: Convex case

In geometric terms, the Ekeland variational principle says that a lower-bounded proper lower-semicontinuous functionf defined on a Banach spaceX has a point (x ₀,f(x ₀)) in its graph that is maximal in the epigraph off with respect to the cone order determined by the convex coneK _λ = {(x, α) ∈X × ?:λ ∥x∥ ≤ ? α}, where λ is a fixed positive scalar. In this case, we write (x ₀,f(x ₀))∈λ-extf. Here, we investigate the following question: if (x ₀,f(x ₀))∈λ-extf, wheref is a convex function, and if 〈f _n 〉 is a sequence of convex functions convergent tof in some sense, can (x ₀,f(x ₀)) be recovered as a limit of a sequence of points taken from λ-extf _n ? The convergence notions that we consider are the bounded Hausdorff convergence, Mosco convergence, and slice convergence, a new convergence notion that agrees with the Mosco convergence in the reflexive setting, but which, unlike the Mosco convergence, behaves well without reflexivity.     

Some Convergence Properties of Descent Methods

In this paper, we discuss the convergence properties of a class of descent algorithms for minimizing a continuously differentiable function f on R ⁿ without assuming that the sequence { x _k } of iterates is bounded. Under mild conditions, we prove that the limit infimum of is zero and that false convergence does not occur when f is convex. Furthermore, we discuss the convergence rate of { } and { f(x _k )} when { x _k } is unbounded and { f(x _k )} is bounded.