Combinatorics Seminar
When: Sunday, January 15, 10am
Where: Schreiber 309
Speaker: Benny Sudakov, ETH
Title: Quantitative quasirandomness
Abstract:
A graph is quasirandom if its edge distribution is similar (in a well
defined quantitative way) to that of a random graph with the same edge
density. Classical results of Thomason and Chung-Graham-Wilson show
that a variety of graph properties are equivalent to quasirandomness.
On the other hand, in some known proofs the error terms which measure
quasirandomness can change quite dramatically when going from one
property to another which might be problematic in some applications.
Simonovits and Sós proved that the property that all induced
subgraphs have about the expected number of copies of a fixed graph H
is quasirandom. However, their proof relies on the regularity lemma
and gives a very weak estimate. They asked to find a new proof for
this result with a better estimate. The purpose of this talk is to
accomplish this. Moreover when H is a clique our estimate is optimal
up to a constant factor.
Joint work with D. Conlon and J. Fox.