CS 269S, Fall 2013: Theory Seminar
Bren Hall, Room 1422, 1pm
October 25, 2013:

Hereditary properties of permutations are strongly testable

By Tereza Klimosova and Daniel Kral

Presented by Michael Bannister

We show that for every hereditary permutation property P and every e0 > 0, there exists an integer M such that if a permutation pi is e0-far from P in the Kendall's tau distance, then a random sub-permutation of pi of order M has the property P with probability at most e0. This settles an open problem whether hereditary permutation properties are strongly testable, i.e., testable with respect to the Kendall's tau distance. In addition, our method also yields a proof of a conjecture of Hoppen, Kohayakawa, Moreira and Sampaio on the relation of the rectangular distance and the Kendall's tau distance of a permutation from a hereditary property.