##### 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

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