SPEAKER:  Asaf Shapira  (Tel Aviv University)

TITLE:    The removal lemma against an unknown distribution

ABSTRACT: 

The removal lemma, in its most general form, states that if a graph is far from satisfying a hereditary property P, then with high probability, a random sample of vertices of constant size induces a graph not satisfying P.

This result implicitly assumes that one measures a graph’s distance to satisfying a property with respect to a uniform distribution on its vertex set. Goldreich asked if the removal lemma continues to hold for all hereditary properties even if the graph’s vertices are endowed with an *arbitrary* distribution. This distribution then determines the way by which one samples vertices from the graph, and the way by which one measures the graph’s distance from satisfying the property.

In this talk I will describe a complete solution to Goldreich’s problem. Joint work with L. Gishboliner