Emergence of regularity in large graphs

Add to your list(s) Download to your calendar using vCal

• Benny Sudakov (ETH Zürich)
• Wednesday 10 April 2024, 09:00-10:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact nobody.

OOEW04 - Structure and Randomness - a celebration of the mathematics of Timothy Gowers

“Every large system, chaotic as it may be, contains a well-organized subsystem”.This phenomenon is truly ubiquitous and manifests itself in different mathematicalareas. One of the central problems in extremal combinatorics, which was extensively studied in thelast hundred years, is to estimate how large a graph/hypergraph needs to be to guarantee theemergence of such well-organized substructures. In the first part of this talk we will give an introduction to this topic, mentioning some classical resultsas well as a few applications to other areas of mathematics. Then we discuss the recent solution(with Oliver Janzer) of the following fundamental problem, posed by Erdos and Sauer about 50 years ago:”How many edges on n vertices force the existence of an r-regular subgraph (r>2)?”Our proof uses algebraic and probabilistic tools, building on earlier works byAlon, Friedland, Kalai, Pyber, Rödl and Szemerédi.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.