Arithmetic Combinatorics
On the Property Testing of Hereditary Graph and Hypergraph Properties
Recent work of Alon-Shapira and Rodl-Schacht has demonstrated that every hereditary graph and hypergraph property is testable with one-sided error. This result appears definitive, but there are some subtleties to it that I will present here. For instance, if one seeks to take a graph or hypergraph which tests positive for such a property, and construct a nearby graph or hypergraph which actually does satisfy that property, one can do so in a "local" manner for undirected graphs, but not for directed graphs or undirected hypergraphs. There are similar issues when trying to extend the results to continuous graphs and hypergraphs (where the vertex set is replaced with a probability space). The reason for these distinctions arises from Ramsey theory (and the limitations thereof). This is joint work with Tim Austin.