Monday, April 8th, 2013 | 4pm-5pm | Burnside 1205 |

Mathematics Institute, University of Warwick

Hereditary properties of permutations are strongly testable

Property testing is a topic with growing importance with many connections to various areas of mathematics and computer science. A property tester is an algorithm that decides whether a large input object has the considered property by querying only a small sample of it. Since the tester is presented with a part of the input structure, it is necessary to allow an error based on the robustness of the tested property of the input. The most investigated area of property testing is testing graph properties. One of the most significant results in this area is that of Alon and Shapira asserting that every hereditary graph property, i.e., a property preserved by taking induced subgraphs, is testable. Hoppen, Kohayakawa, Moreira, Sampaio obtained the similar result for permutations, showing, that every hereditary property of permutations is weakly testable, i.e., testable with respect to the rectangular distance, and they conjectured the same to be true with respect to a finer measure called the Kendall's tau distance. We have resolved this problem in affirmative by showing that for every such property P and every epsilon>0, there exists an integer M such that if a permutation is epsilon-far from P in the Kendall's tau distance, then its random subpermutation of order M has the property P with probability at most epsilon. Joint work with Dan Kral.