Seminars & Colloquia Calendar

Download as iCal file

Special Colloquium

Regularity lemma: discrete and continuous perspectives

Fan Wei - Princeton University

Location:  Zoom
Date & time: Wednesday, 05 January 2022 at 11:30AM - 12:30PM

Abstract: SzemerĂ©di's regularity lemma is a game-changer in extremal combinatorics and provides a global perspective to study large combinatorial objects. It has connections to number theory, discrete geometry, and theoretical computer science. One of its classical applications, the removal lemma, is the essence for many property testing problems, an active field in theoretical computer science. Unfortunately, the bound on the sample size from the regularity method typically is either not explicit or is enormous. For testing natural permutation properties, we show one can avoid the regularity proof and yield a tester with polynomial sample size. For graphs, we prove a stronger, "L_infty'' version of the graph removal lemma, where we conjecture that the essence of this new removal lemma for cliques is indeed the regularity-type proof. The analytic interpretation of the regularity lemma also plays an important role in graph limits, a recently developed powerful theory in studying graphs from a continuous perspective. Based on graph limits, we developed a method combining with both analytic and spectral methods, to answer and make advances towards some famous conjectures on a common theme in extremal combinatorics: when does randomness give nearly optimal bounds? These works are based on joint works with Jacob Fox, Dan Kral',  Jonathan Noel, Sergey Norin, and Jan Volec.

This talk is for the local Rutgers Math Community only, Zoom links will be sent by the Department Chair via email

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.