Speaker: Noga Alon, Tel Aviv University and IAS, Princeton

Title: The structure of large graphs

Abstract: A property of graphs is hereditary if it is closed under deleting vertices. Most interesting properties of graphs are hereditary, and their study reveals some unexpected phenomena. This study combines combinatorial, probabilistic, geometric and analytic tools, including Szemeredi's Regularity Lemma and Grothendieck's Inequality, and leads to interesting extremal and algorithmic applications. I will survey the topic, mentioning the main questions, describing several recent results and giving a brief description of the relevant proof techniques.

Place: Science and Technology Building I, Room 242

Refreshments will be served before the talk at 3:00 p.m. in Room 222.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491