Expansion in matrix-weighted graphs

DOI10.1016/J.LAA.2021.08.009MaRDI QIDQ821011zbMATH OpenOpenAlexFDO

Authors Jakob K. Hansen

Publication date 29 September 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.12008

zbMATH Keywords

expander graphcellular sheafmatrix-weighted graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Signed and weighted graphs (05C22) Expander graphs (05C48)

Abstract: A matrix-weighted graph is an undirected graph with a $kimesk$ positive semidefinite matrix assigned to each edge. There are natural generalizations of the Laplacian and adjacency matrices for such graphs. These matrices can be used to define and control expansion for matrix-weighted graphs. In particular, an analogue of the expander mixing lemma and one half of a Cheeger-type inequality hold for matrix-weighted graphs. A new definition of a matrix-weighted expander graph suggests the tantalizing possibility of families of matrix-weighted graphs with better-than-Ramanujan expansion.

Recommendations

• scientific article; zbMATH DE number 15874
• On the Edge-Expansion of Graphs
• On expansive graphs
• Character expansion methods for matrix models of dually weighted graphs
• The direct expansion of graphs
• Expander graphs and their applications
• Expander graphs in pure and applied mathematics
• Eigenvalues and expansion of regular graphs
• Eigenvalues and expansion of bipartite graphs
• Expanding factors of graphs

Cites work

• scientific article; zbMATH DE number 47944 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• A Cheeger Inequality for the Graph Connection Laplacian
• Constructing tight fusion frames
• Embedding Riemannian manifolds by the heat kernel of the connection Laplacian
• Explicit construction of linear sized tolerant networks
• Graph connection Laplacian and random matrices with random blocks
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Introduction to finite frame theory
• Laplacian and vibrational spectra for homogeneous graphs
• Lifts, discrepancy and nearly optimal spectral gap
• Matrix-weighted consensus and its applications
• Observability Through a Matrix-Weighted Graph
• On the second eigenvalue of a graph
• Ranking and sparsifying a connection graph
• Resistance matrices of graphs with matrix weights
• Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Spectra of combinatorial Laplace operators on simplicial complexes
• Spectra of uniform hypergraphs
• Synchronization under matrix-weighted Laplacian
• Toward a spectral theory of cellular sheaves
• Vector diffusion maps and the connection Laplacian

Cited in

(5)

• On the inverse and Moore-Penrose inverse of resistance matrix of graphs with more general matrix weights
• Bounds for graph expansions via elasticity
• Squared distance matrices of trees with matrix weights
• A unified framework for the expander mixing lemma for irregular graphs and its applications
• On the Edge-Expansion of Graphs

This page was built for publication: Expansion in matrix-weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q821011)