Regularity Lemmas as Structured Decompositions

Abstract: One way of viewing Szemerédi's regularity lemma is that it gives a way of decomposing a graph (approximately) into a structured part (the "unary" data) and a random part. Then hypergraph regularity, the generalization to k-uniform hypergraphs, can be viewed as a decomposition into multiple "tiers" of structure - a unary part as well as a binary part and so on, and then finally a random part.

We'll discuss how an analytic approach can make these decompositions exact instances of the conditional expectation in probability, and how these analytic proofs relate to combinatorial proofs with explicit bounds. Finally, we'll discuss regularity lemmas for other mathematical objects, focusing on the example of ordered graphs and hypergraphs, and show how the "tiers of structures" perspective makes it possible to see regularity lemmas for other mathematical objects as examples of the regularity lemma for hypergraphs.

(No prior knowledge of the regularity lemma and its variants is assumed.)

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.