Rutgers Discrete Mathematics Seminar

This seminar runs every Monday during the semester at 2PM in Hill 705. The current organizers are Jeff Kahn, Bhargav Narayanan and Corrine Yap.

If you wish to join our listserv, please email Corrine Yap at corrine.yap@rutgers.edu.

Click here for the abstract archive for this semester, and here for older abstracts.

We have resumed in-person meetings for the Fall 2021 semester.

Next Talk:

Date: January 5, 2021 at 11:30AM via Zoom

Speaker: Fan Wei (Princeton)

Title: Regularity lemma: Discrete and Continuous Perspectives


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.


Upcoming Speakers: