Density Theorems for Bipartite Graphs and Related Ramsey-Type Results

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Density Theorems for Bipartite Graphs and Related Ramsey-Type Results
Speaker:Benny Sudakov
Affiliation:University of California, Los Angeles and Member, School of Mathematics
Date:Tuesday, November 20
Time/Room:10:30am - 12:30pm/S-101

In this talk, we discuss a new technique which shows how to find a copy of a sparse bipartite graph in a graph of positive density. Our results imply several new bounds for classical problems in Ramsey theory and improve and generalize earlier results of various researchers. The proofs combine simple probabilistic arguments with some combinatorial ideas. In addition, these methods can be used to study edge intersection patterns in topological graphs, make some progress towards the Erdos-Hajnal conjecture on the largest homogeneous set in graphs with a forbidden induced subgraph, and obtain other Ramsey-type results for graphs and hypergraphs. This is joint work with Jacob Fox