Seminar: April 23

Gabor Lippner, Harvard University

Bounded degree parameter testing via measurable graphs

Parameter testing studies which quantities can be approximated using randomized constant query complexity algorithms. In the case of bounded degree graphs, this is intimately connected with the notion of Benjamini-Schramm convergence.

Gabor Elek observed that measurable graphs arise naturally as limit objects for Benjamini-Schramm convergent graphs sequences. I will describe a general pull-back method that uses this connection to translate results in measure theory to a combinatorial setting. It can be applied to give simple proofs of testability for various graph parameters, as well as to prove a regularity-lemma like decomposition theorem for bounded degree graphs.