CRM: Centro De Giorgi
logo sns
Geometry, Structure and Randomness in Combinatorics

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.

Wed 5 Sep, 9:00 - 10:00, Aula Dini
<< Go back