Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Steve Butler

UCSD

Anti-coverings of graphs

Abstract:

Spectral graph theory has enjoyed much success in using eigenvalues of matrices associated with a graph to understand some structural property or bound various kinds of behavior of the graph. When two graphs share many eigenvalues in common it can often be traced to some sort of common structure that they share. Well known examples of this are common coverings or equitable partitions. We will consider another variation of this where (for the normalized Laplacian) two graphs do not project to a common graph but share a common ``anti-covering'' (which we will define). We will also consider anti-covers for the adjacency matrix and use it to establish the following linear algebra result (among others): {\it Let $M$ be an $n{\times}n$ real symmetric matrix and $|M|$ be the $n{\times}n$ matrix found by taking (entrywise) the absolute values of $M$; then there exists a nonnegative symmetric $2n{\times}2n$ matrix ${\cal N}$ such that the spectrum of ${\cal N}$ is the union of the spectrums of $M$ and $|M|$.}

May 22, 2007

4:00 PM

AP&M 7321

****************************