Printable PDF
Department of Mathematics,
University of California San Diego

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

Food For Thought Seminar

Franklin Kenter

UCSD

A Spectrum of Colorful Diameters

Abstract:

For any finite simple graph $G$, we can form its adjacency matrix $A$ to be defined as $A_{ij} = 1$ if $i$ is adjacent to $j$ and $=0$ otherwise. This matrix has several interpretations, and because of these interpretations, the eigenvalues (i.e., the spectrum) determine a lot of information about the graph. Let $\lambda_{min}$ and $\lambda_{max}$ denote the minimal and maximal eigenvalues of $A$ respectively, and let $\chi(G)$ denote the chromatic number of $G$. Hoffman proved (1969) $\chi(G) \ge 1- \frac{\lambda_{max}}{\lambda{min}}$. In this talk, we present a new simple probabilistic proof of Hoffman's Theorem. We will then follow up on how to apply Hoffman's theorem, and it's connection to the Lovasz Theta function, to yield a spectral bound on the diameter of the graph. The intention of the talk (and its seemingly ridiculous title) is to showcase how several different basic mathematical tools- including those from probability, linear algebra, and combinatorics- can be used to in concert to yield beautiful results.

September 30, 2010

11:00 AM

AP&M 7321

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