Geometry, Structure and Randomness in Combinatorics
timetable:
Wed 5 Sep, 9:00 - 10:00, Aula Dini
<< Go back
Discrepancy in graphs, hypergraphs and tournaments
speaker: Alex Scott (Oxford University )abstract: How uniformly can the edges of a graph be distributed? Erdős and Spencer showed in 1971 that every graph on n vertices has an induced subgraph on which the number of edges and nonedges differ by at least \(cn^{3/2}\), and gave a similar result for hypergraphs. Erdős, Goldberg, Pach and Spencer subsequently generalised this to graphs with different densities. We discuss recent generalizations and related questions for graphs, hypergraphs and tournaments. Joint work with Béla Bollobás.
timetable:
Wed 5 Sep, 9:00 - 10:00, Aula Dini
<< Go back