论文标题
签名图拉普拉斯人的时刻不平等和积极性
A moment inequality and positivity for signed graph Laplacians
论文作者
论文摘要
许多最近的论文考虑了签名的图形laplacians，这是对经典图形laplacian的概括，其中允许边缘权重采用任何一个符号。在经典的情况下，边缘权重全部为正，laplacian为正半准，其内核的尺寸代表图形的连接组件的数量。在许多应用中，人们对建立条件感兴趣，以保证矩阵的正半定义。在本文中，我们在边缘权重的前两个矩方面呈现了加权图拉普拉斯（重量不需要特定符号）的特征值的不等式。该结合涉及图表上同等加权拉普拉斯的特征值以及线图的邻接矩阵的特征值（Edge-to-vertex dual Graph）。对于常规图，可以完全按照同等加权的拉普拉斯式的第二个特征值表示，该对象已被广泛研究，该对象与扩展器图和图形连接的光谱测量值有关。我们提供了几个示例，包括关键和亚临界方案中的Erdős-rényi随机图，随机大$ d $ regarbular图以及完整的图表，此处的不平等是紧密的。
A number of recent papers have considered signed graph Laplacians, a generalization of the classical graph Laplacian, where the edge weights are allowed to take either sign. In the classical case, where the edge weights are all positive, the Laplacian is positive semi-definite with the dimension of the kernel representing the number of connected components of the graph. In many applications one is interested in establishing conditions which guarantee the positive semi-definiteness of the matrix. In this paper we present an inequality on the eigenvalues of a weighted graph Laplacian (where the weights need not have any particular sign) in terms of the first two moments of the edge weights. This bound involves the eigenvalues of the equally weighted Laplacian on the graph as well as the eigenvalues of the adjacency matrix of the line graph (the edge-to-vertex dual graph). For a regular graph the bound can be expressed entirely in terms of the second eigenvalue of the equally weighted Laplacian, an object that has been extensively studied in connection with expander graphs and spectral measures of graph connectivity. We present several examples including Erdős-Rényi random graphs in the critical and subcritical regimes, random large $d$-regular graphs, and the complete graph, for which the inequalities here are tight.
