Discrete Geometry: Quasirandom Graphs

Event Date: 

Wednesday, October 30, 2013 - 2:00pm to 3:00pm

Event Location: 

  • 4607B South Hall

Event Contact: 

Michael Dougherty

Email: dougherty@math.ucsb.edu

Speaker: Paddy Bartlett

Abstract: The concept of a ``random graph'' is fundamental to hundreds of questions in combinatorics and theoretical computer science. Consequently, understanding the properties that characterize random graphs is an interesting field of study: what kinds of properties are ``essential'' to random graphs? Given a sequence of graphs, is there a sensible way in which we can say that the elements of this sequence ``act like'' random graphs?

In this talk, we will motivate and introduce the idea of a *quasirandom* graph, a concept that gives us a rigorous way to deal with the questions above. Some examples of these quasirandom graphs will be presented, and a series of results ranging from 1986 to the present day will be mentioned. No prerequisites beyond a minimal knowledge of graph theory and probability should be necessary to follow this talk.