printable pdf
比利时vs摩洛哥足彩 ,
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

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