#
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.