***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Rajko Nenadov, Google Zurich

Thursday 7th October, 3:00 via Zoom.

Title: A new proof of the KLR conjecture.

Abstract: 
We give a new, short and intuitive proof of the celebrated KŁR conjecture.  Slightly rephrased, 
the conjecture states that if we condition on uniform edge distribution, the archetypal property
of random graphs, the probability that the Erdős–Rényi random graph G(n,m) does not contain a 
copy of a fixed graph H becomes superexponentially small in m, for sufficiently large m > m(n, H).
As its most prominent application, this conjecture implies that with high
probability all subgraphs of the Binomial random graph with appropriate parameters satisfy an 
embedding lemma which complements the sparse regularity lemma. The proof proceeds by induction 
and, in some way, can be considered a `deterministic' analogue of the multiple-exposure
technique from random graph theory.


		----------------------------------

Next week: Shira Zerbib

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)