The Laplacian spectra of graphs with a tree structure

Trees are very common in the theory and applications of combinatorics. In this article, we consider graphs whose underlying structure is a tree, except that its vertices are graphs in their own right and where adjacent graphs (vertices) are linked by taking their join. We study the spectral properties of the Laplacian matrices of such graphs. It turns out that in order to capture known spectral properties of the Laplacian matrices of trees, it is necessary to consider the Laplacians of vertex-weighted graphs. We focus on the second smallest eigenvalue of such Laplacians and on the properties of their corresponding eigenvector. We characterize the second smallest eigenvalue in terms of the Perron branches of a tree. Finally, we show that our results are applicable to advancing the solution to the problem of whether there exists a graph on n vertices whose Laplacian has the integer eigenvalues 0, 1, …, n ? 1.     

A new dissimilarity measure for comparing labeled graphs

We use spectral graph theory to compare graphs that share the same node set, taking into account global graph structures. We propose a general framework using eigendecomposition of graph Laplacians. We show its special cases and propose a new dissimilarity measure that avoid problems of spectral analysis. The new dissimilarity emphasizes the importance of small eigenvalues which are known to carry the main information on graphs. General properties of the dissimilarity are discussed. The dissimilarity provides an efficient and intuitive tool for graph analysis.     

Towards a spectral theory of graphs based on the signless Laplacian, II

A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular to those based on the adjacency matrix A and the Laplacian L. As demonstrated in the first part, the Q-theory can be constructed in part using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, common features with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles.     

On the Co-PI and Laplacian Co-PI eigenvalues of a graph

In this paper we present an equivalent definition of Co-PI index and then determine the eigenvalues of Co-PI matrices and their Laplacians of Cartesian product graphs, including bounds on the second and third Co-PI spectral moment of a graph. The explicit formulae for the Co-PI index of Cartesian product graphs are also presented.     

Laplacians and the Cheeger Inequality for Directed Graphs

We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.Received September 8, 2004     

CONVERGENCE OF LAPLACIAN SPECTRA FROM RANDOM SAMPLES

Eigenvectors and eigenvalues of discrete Laplacians are often used for manifold learning and nonlinear dimensionality reduction. Graph Laplacian is one widely used discrete laplacian on point cloud. It was previously proved by Belkin and Niyogithat the eigenvectors and eigenvalues of the graph Laplacian converge to the eigenfunctions and eigenvalues of the Laplace-Beltrami operator of the manifold in the limit of infinitely many data points sampled independently from the uniform distribution over the manifold. Recently, we introduced Point Integral method (PIM) to solve elliptic equations and corresponding eigenvalue problem on point clouds. In this paper, we prove that the eigenvectors and eigenvalues obtained by PIM converge in the limit of infinitely many random samples. Moreover, estimation of the convergence rate is also given.     

Approximating Spectral Invariants of Harper Operators on Graphs

We study Harper operators and the closely related discrete magnetic Laplacians (DML) on a graph with a free action of a discrete group, as defined by Sunada (Sun). A main result in this paper is that the spectral density function of DMLs associated to rational weight functions on graphs with a free action of an amenable discrete group can be approximated by the average spectral density function of the DMLs on a regular exhaustion, with either Dirichlet or Neumann boundary conditions. This then gives a criterion for the existence of gaps in the spectrum of the DML, as well as other interesting spectral properties of such DMLs. The technique used incorporates some results of algebraic number theory.     

Compact Heisenberg manifolds as CR manifolds

Let M be the quotient of the Heisenberg group by a discrete co-compact subgroup, with the natural strongly pseudoconvex CR structure. We identify the eigenvalues and eigenforms of the Kohn Laplacians on M and show how to realize M as the boundary of a bounded domain in a line bundle over an Abelian variety.     

Critical Groups of Simplicial Complexes

We generalize the theory of critical groups from graphs to simplicial complexes. Specifically, given a simplicial complex, we define a family of abelian groups in terms of combinatorial Laplacian operators, generalizing the construction of the critical group of a graph. We show how to realize these critical groups explicitly as cokernels of reduced Laplacians, and prove that they are finite, with orders given by weighted enumerators of simplicial spanning trees. We describe how the critical groups of a complex represent flow along its faces, and sketch another potential interpretation as analogues of Chow groups.     

On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions

Given a finite simple graph G with n vertices, we can construct the Cayley graph on the symmetric group S _n generated by the edges of G, interpreted as transpositions. We show that, if G is complete multipartite, the eigenvalues of the Laplacian of Cay (G) have a simple expression in terms of the irreducible characters of transpositions and of the Littlewood–Richardson coefficients. As a consequence, we can prove that the Laplacians of G and of Cay (G) have the same first nontrivial eigenvalue. This is equivalent to saying that Aldous’s conjecture, asserting that the random walk and the interchange process have the same spectral gap, holds for complete multipartite graphs.     

A survey of automated conjectures in spectral graph theory

During the last three decades, the computer has been widely used in spectral graph theory. Many results about graph eigenvalues were first conjectured, and in some cases proved, using computer programs, such as GRAPH, Graffiti, Ingrid, newGRAPH and AutoGraphiX. This paper presents a survey and a discussion of such results.     

Algebraic multigrid methods for Laplacians of graphs

Classical algebraic multigrid theory relies on the fact that the system matrix is positive definite. We extend this theory to cover the positive semidefinite case as well, by formulating semiconvergence results for these singular systems. For the class of irreducible diagonal dominant singular M-matrices we show that the requirements of the developed theory hold and that the coarse level systems are still of the same class, if the C/F-splitting is good enough. An important example for matrices that are irreducible diagonal dominant M-matrices are Laplacians of graphs. Recent shape optimizing methods for graph partitioning require to solve singular linear systems involving these Laplacians. We present convergence results as well as experimental results for numerous graphs arising from finite element discretizations with up to 10⁶ vertices.     

Eigenvalue bracketing for discrete and metric graphs

We develop eigenvalue estimates for the Laplacians on discrete and metric graphs using various types of boundary conditions at the vertices of the metric graph. Via an explicit correspondence of the equilateral metric and discrete graph spectrum (also in the “exceptional” values of the metric graph corresponding to the Dirichlet spectrum) we carry over these estimates from the metric graph Laplacian to the discrete case. We apply the results to covering graphs and present examples where the covering graph Laplacians have spectral gaps.     

On the eigenvalues and eigenvectors of certain finite,vertex-weighted,bipartite graphs

The established, spectral characterisation of bipartite graphs with unweighted vertices (which are here termed homogeneous graphs) is extended to those bipartite graphs (called heterogeneous) in which all of the vertices in one set are weighted h₁ , and each of those in the other set of the bigraph is weighted h₂. All the eigenvalues of a homogeneous bipartite graph occur in pairs, around zero, while some of the eigenvalues of an arbitrary, heterogeneous graph are paired around $\text{1}\text{2}$(h₁ + h₂), the remainder having the value h₂ (or h_l). The well-documented, explicit relations between the eigenvectors belonging to “paired” eigenvalues of homogeneous graphs are extended to relate the components of the eigenvectors associated with each couple of “paired” eigenvalues of the corresponding heterogeneous graph. Details are also given of the relationships between the eigenvectors of an arbitrary, homogeneous, bipartite graph and those of its heterogeneous analogue.     

Eigenvectors of random graphs: Nodal Domains

We initiate a systematic study of eigenvectors of random graphs. Whereas much is known about eigenvalues of graphs and how they reflect properties of the underlying graph, relatively little is known about the corresponding eigenvectors. Our main focus in this article is on the nodal domains associated with the different eigenfunctions. In the analogous realm of Laplacians of Riemannian manifolds, nodal domains have been the subject of intensive research for well over a hundred years. Graphical nodal domains turn out to have interesting and unexpected properties. Our main theorem asserts that there is a constant c such that for almost every graph G, each eigenfunction of G has at most two large nodal domains, and in addition at most c exceptional vertices outside these primary domains. We also discuss variations of these questions and briefly report on some numerical experiments which, in particular, suggest that almost surely there are just two nodal domains and no exceptional vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 39–58, 2011     

Approximating spectral invariants of Harper operators on graphs II

We study Harper operators and the closely related discrete magnetic Laplacians (DML) on a graph with a free action of a discrete group, as defined by Sunada. The spectral density function of the DML is defined using the von Neumann trace associated with the free action of a discrete group on a graph. The main result in this paper states that when the group is amenable, the spectral density function is equal to the integrated density of states of the DML that is defined using either Dirichlet or Neumann boundary conditions. This establishes the main conjecture in a paper by Mathai and Yates. The result is generalized to other self adjoint operators with finite propagation speed.

     

Law of large numbers for Betti numbers of homogeneous and spatially independent random simplicial complexes

The Linial–Meshulam complex model is a natural higher dimensional analog of the Erd?s–Rényi graph model. In recent years, Linial and Peled established a limit theorem for Betti numbers of Linial–Meshulam complexes with an appropriate scaling of the underlying parameter. The present article aims to extend that result to more general random simplicial complex models. We introduce a class of homogeneous and spatially independent random simplicial complexes, including the Linial–Meshulam complex model and the random clique complex model as special cases, and we study the asymptotic behavior of their Betti numbers. Moreover, we obtain the convergence of the empirical spectral distributions of their Laplacians. A key element in the argument is the local weak convergence of simplicial complexes. Inspired by the work of Linial and Peled, we establish the local weak limit theorem for homogeneous and spatially independent random simplicial complexes.     

Generalized tight p-frames and spectral bounds for Laplace-like operators

We prove sharp upper bounds for sums of eigenvalues (and other spectral functionals) of Laplace-like operators, including bi-Laplacians and fractional Laplacians. We show that among linear images of a highly symmetric domain, our spectral functionals are maximal on the original domain. We exploit the symmetries of the domain, and the operator, avoiding the necessity of finding good test functions for variational problems. This is especially important for fractional Laplacians, since exact solutions are not even known on intervals, making it hard to find good test functions.To achieve our goals we generalize tight p-fusion frames, to extract the best possible geometric results for domains with isometry groups admitting tight p-frames. Any such group generates a tight p-fusion frame via conjugations of a fixed projection matrix. We show that generalized tight p-frames can also be obtained by conjugations of an arbitrary rectangular matrix, with the frame constant depending on the singular values of the matrix.