Finding order in chaos; the Regularity Method Associate Professor Gabor Sarkozy Computer Science Department, WPI Friday, February 6, 2009 11:00 a.m. - 12:00 p.m. Hagglund Room, Campus Center ABSTRACT: In many practical applications of graph theory we are faced with a huge graph on billions of nodes, and we have to find a special subgraph of this big graph. For example one such a graph is the Internet graph where the nodes are the websites and we connect two nodes if there is a link between them. Where do we start in a problem like this? First we have to find some "order in chaos"; we have to find some structure in our gigantic graph. This is provided by the Regularity Lemma of Szemeredi which claims the shocking statement that every large graph can be partitioned into random-looking (regular) subgraphs. Then our Blow-up Lemma tells us how to exploit this information; namely it claims that under some natural restrictions ANY subgraph can be found in these regular subgraphs. The two lemmas together with some technical tools form the Regularity Method, one of the most successful methods in the modern theory of large and dense discrete structures. In this talk we overview the history and the basics of the method and we present some results that we were able to obtain with this method. ______ Gabor Sarkozy is currently an affiliated associate professor at the Computer Science Department of WPI. He is also a senior researcher at the Computer and Automation Research Institute (SZTAKI) of the Hungarian Academy of Sciences. He is the founder and director of the Budapest WPI Project Center at SZTAKI. He received his B.S. in mathematics from the Budapest Eotvos Lorand University, Hungary in 1990. He received his M.S. and Ph.D. in computer science from Rutgers University in 1994 under the supervision of Steele Prize winner Endre Szemeredi. His area of specialization is Discrete Mathematics and Theoretical Computer Science. He has published close to 50 refereed international journal papers. His research was supported by the NSA, NSF, OTKA (Hungarian NSF) and by a Janos Bolyai Research Grant. His main hobby is tennis, he was the over-35 tennis champion of Hungary. Host: Professor Micha Hofri Refreshments will be served. Maintained by webmaster@cs.wpi.edu Last modified: January 27,2009

Department of Computer Science - Worcester Polytechnic Institute
100 Institute Road, Worcester, MA 01609-2280
Phone: +1-508-831-5357 - Fax: +1-508-831-5776 - cs@wpi.edu