This book describes the spectral theory of finite graphs.
A modern, comprehensive 2010 overview providing an easy introduction for applied scientists who are not versed in mathematics.
This volume, the third in a sequence that began with The Theory of Matroids and Combinatorial Geometries, concentrates on the applications of matroid theory to a variety of topics from engineering (rigidity and scene analysis), combinatorics (graphs, lattices, codes and designs), topology and operations research (the greedy algorithm).
The purpose of this book, which was first published in 1978, is to give a complete account of the theory of permanents, their history and applications. This volume was the first complete account of the theory of permanents, covering virtually the whole of the subject, a feature that no simple survey of the theory of matrices can even attempt. The work also contains many results stated without formal proofs. This book can be used as a textbook at the advanced undergraduate or graduate level. The only prerequisites are a standard undergraduate course in the theory of matrices and a measure of mathematical maturity.
Graphs and matrices enjoy a fascinating and mutually beneficial relationship. This interplay has benefited both graph theory and linear algebra. In one direction, knowledge about one of the graphs that can be associated with a matrix can be used to illuminate matrix properties and to get better information about the matrix. Examples include the use of digraphs to obtain strong results on diagonal dominance and eigenvalue inclusion regions and the use of the Rado-Hall theorem to deduce properties of special classes of matrices. Going the other way, linear algebraic properties of one of the matrices associated with a graph can be used to obtain useful combinatorial information about the graph. The adjacency matrix and the Laplacian matrix are two well-known matrices associated to a graph, and their eigenvalues encode important information about the graph. Another important linear algebraic invariant associated with a graph is the Colin de Verdiere number, which, for instance, characterizes certain topological properties of the graph. This book is not a comprehensive study of graphs and matrices. The particular content of the lectures was chosen for its accessibility, beauty, and current relevance, and for the possibility of enticing the audience to want to learn more.
The arrangement of nonzero entries of a matrix, described by the graph of the matrix, limits the possible geometric multiplicities of the eigenvalues, which are far more limited by this information than algebraic multiplicities or the numerical values of the eigenvalues. This book gives a unified development of how the graph of a symmetric matrix influences the possible multiplicities of its eigenvalues. While the theory is richest in cases where the graph is a tree, work on eigenvalues, multiplicities and graphs has provided the opportunity to identify which ideas have analogs for non-trees, and those for which trees are essential. It gathers and organizes the fundamental ideas to allow students and researchers to easily access and investigate the many interesting questions in the subject.
There is no other book with such a wide scope of both areas of algebraic graph theory.
Model theory is concerned with the notions of definition, interpretation and structure in a very general setting, and is applied to a wide range of other areas such as set theory, geometry, algebra and computer science. This book provides an integrated introduction to model theory for graduate students.
This book contains the notes of the lectures delivered at an Advanced Course on Combinatorial Matrix Theory held at Centre de Recerca Matemàtica (CRM) in Barcelona. These notes correspond to five series of lectures. The first series is dedicated to the study of several matrix classes defined combinatorially, and was delivered by Richard A. Brualdi. The second one, given by Pauline van den Driessche, is concerned with the study of spectral properties of matrices with a given sign pattern. Dragan Stevanović delivered the third one, devoted to describing the spectral radius of a graph as a tool to provide bounds of parameters related with properties of a graph. The fourth lecture was delivered by Stephen Kirkland and is dedicated to the applications of the Group Inverse of the Laplacian matrix. The last one, given by Ángeles Carmona, focuses on boundary value problems on finite networks with special in-depth on the M-matrix inverse problem.