***********************************
* 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)