Nagy Zoltán Lóránt: Outerplanar Turán numbers and number of k-vertex subtrees in binary trees
Nagy Zoltán LórántKombinatorika szeminárium
on 3/18/21
I will describe an elementary proof of the constructive Lovász Local Lemma
that could be understood at the level of an undergraduate course on discrete mathematics.
The proof boils down to a plain counting argument and an inductive upper bound on
the probabilities of certain events. The argument that I present is inspired by the
"forward-looking" analysis of Harvey and Vondrák FOCS'15 (https://doi.org/10.1109/FOCS.2015.85)
and is described in more details in a paper I wrote with Or Sattath FOCS'17 (https://doi.org/10.1109/FOCS.2017.47)
If time permits I will mention some extensions related to "resampling oracles" and
discuss the relevance to the constructive quantum Lovász Local Lemma.