##### Department of Mathematics,

University of California San Diego

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

### Food for Thought

## Ross Richardson

#### UCSD, Graduate Student

## Graphs & probability a perfect matching

##### Abstract:

Erd\H{o}s in 1947 provided a bound on the so-called diagonal Ramsey numbers with a startling and elegant proof drawn from probability. In 1960 Erd\H{o}s and Renyi published a landmark paper introducing the notion of a random graph and exploring the rather quirky nature of these objects. Slowly at first, and now with increasing speed, the probabilistic method in combinatorics has grown from these beginnings into a large and vibrant field with deep connections to many fundamental questions in mathematics and computer science. In this talk, we will give a taste of probabilistic methods, using the subject of random graphs as a foil. We'll give a whirlwind tour of the properties of random graphs, their applications, and a look at some very large graphs. This talk should be accessible to anyone with a basic understanding of undergraduate probability, and of interest to all.

Host:

### April 13, 2006

### 11:00 AM

### AP&M 5829

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