Computer Science/Discrete Mathematics Seminar II

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