Tutte seminar - Chris Godsil

Friday, July 24, 2009 3:30 pm - 4:30 pm EDT (GMT -04:00)

Awful Graphs

Speaker: Dan McQuillan
Affiliation: Norwich University
Room:

Mathematics & Computer Building (MC) 5158

Abstract:

Apparently despite the computational evidence, at the recent BCC Willem Haemers conjectured that almost all graphs are determined by their characteristic polynomial of their adjacency matrix. I will describe recent work that offers strong support for this conjecture, based on the concept of "awful" graphs. An n-vertex graph is awful if its adjacency matrix A and the all-ones matrix J together generate the algebra of all n×n. I will describe some of the theory of this class of graphs, and show how it supports Haemers' conjecture.