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.

Winter 2013 Schedule