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     

四元数矩阵理论中的几个概念间的关系

本文指出并改正文［１］中的错误，给出弱特征多项式［２］与重特征多项式［３］间的显式关系，同时也给出行列式［２］与重行列式［４］间的显式关系，最后讨论了左特征值、右特征值、特征值和特征根之间的关系及最小多项式与弱特征多项式根之间的关系．     

一种可压缩流动的高阶加权紧致非线性格式(WCNS)的加速收敛方法

以高超声速粘性绕流的数值模拟为例,研究LU-SGS、高斯-赛德尔点松弛、线松弛以及GMRES等隐式求解方法在空间项采用高阶精度格式WCNS离散时的收敛性,并对GMRES(generalized minimal residual)方法中的子迭代影响作了对比计算.结果表明,采用准确的解析雅克比矩阵的点、线松弛的收敛速度优于LU-SGS,以线松弛为预处理的GMRES算法具有良好的收敛特性.     

Addendum to: “Hamilton-laceable bi-powers of locally finite bipartite graphs” [Discrete Math. 345 (2022) 112777]

In this addendum we give a short and easy negative answer to the two questions raised in the original article.     

The effect of a market factor on information flow between stocks using the minimal spanning tree

We empirically investigated the effects of market factors on the information flow created from N(N−1)/2 linkage relationships among stocks. We also examined the possibility of employing the minimal spanning tree (MST) method, which is capable of reducing the number of links to N−1. We determined that market factors carry important information value regarding information flow among stocks. Moreover, the information flow among stocks showed time-varying properties according to the changes in market status. In particular, we noted that the information flow increased dramatically during periods of market crises. Finally, we confirmed, via the MST method, that the information flow among stocks could be assessed effectively with the reduced linkage relationships among all links among stocks from the perspective of the overall market.     

On Clique-Transversals and Clique-Independent Sets

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. A clique-independent set is a subset of pairwise disjoint cliques of G. Denote by _C (G) and _C (G) the cardinalities of the minimum clique-transversal and maximum clique-independent set of G, respectively. Say that G is clique-perfect when _C (H)= _C (H), for every induced subgraph H of G. In this paper, we prove that every graph not containing a 4-wheel nor a 3-fan as induced subgraphs and such that every odd cycle of length greater than 3 has a short chord is clique-perfect. The proof leads to polynomial time algorithms for finding the parameters _C (G) and _C (G), for graphs belonging to this class. In addition, we prove that to decide whether or not a given subset of vertices of a graph is a clique-transversal is Co-NP-Complete. The complexity of this problem has been mentioned as unknown in the literature. Finally, we describe a family of highly clique-imperfect graphs, that is, a family of graphs G whose difference _C (G)– _C (G) is arbitrarily large.     

The Flooding Time in Random Graphs

Based on our analysis of the hopcount of the shortest path between two arbitrary nodes in the class G _p (N) of random graphs, the corresponding flooding time is investigated. The flooding time T _N (p) is the minimum time needed to reach all other nodes from one node. We show that, after scaling, the flooding time T _N (p) converges in distribution to the two-fold convolution ^(2*) of the Gumbel distribution function (z)=exp (–e ^–z ), when the link density p _N satisfies Np _N /(log N)³ if N .     

Quantum Mayer Graphs for Coulomb Systems and the Analog of the Debye Potential

Within the Feynman–Kac path integral representation, the equilibrium quantities of a quantum plasma can be represented by Mayer graphs. The well known Coulomb divergencies that appear in these series are eliminated by partial resummations. In this paper, we propose a resummation scheme based on the introduction of a single effective potential that is the quantum analog of the Debye potential. A low density analysis of shows that it reduces, at short distances, to the bare Coulomb interaction between the charges (which is able to lead to bound states). At scale of the order of the Debye screening length ^–1 _D, approaches the classical Debye potential and, at large distances, it decays as a dipolar potential (this large distance behaviour is due to the quantum nature of the particles). The prototype graphs that result from the resummation obey the same diagrammatical rules as the classical graphs of the Abe–Meeron series. We give several applications that show the usefulness of to account for Coulombic effects at all distances in a coherent way.