[Theory] [Theory Lunch] Olga Medrano

[Alec Sun via Theory]

Please join us for the first theory lunch of the quarter tomorrow!

*Time: *Wednesday, March 26, 2025, 12pm-1pm in JCL 390

*Speaker: *Olga Medrano

*Title: *Short Visit to Regularity Lemmas

*Abstract: *In this expository talk, we will overview Szémerédi’s
regularity lemma, a result from extremal graph theory with different
applications. We will then mention some considerations about this result,
including the existence of irregular pairs in the partitions obtained, as
well as the large size of those partitions. Time permitting, we very
briefly reflect on how the proof of Szémerédi's regularity lemma is not
algorithmic and mention a few lines of work that were focused on finding
algorithms to output regular partitions. In the second half of this talk,
we will describe versions of this lemma over certain classes of graphs. In
particular, we state both the Ultra-strong regularity lemma, which works
for the class of graphs of bounded VC dimension, and the Stable regularity
lemma, which works for the class of k-edge stable graphs (namely, those not
containing a bi-induced bipartite graph). We conclude by acknowledging that
algorithmic questions for both results remain open.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250325/c6b15a18/attachment.html>