Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423818 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
In 2010 Moreira and three of the current authors introduced a notion of property testing for permutations based on a distance that measures the randomness of a permutation. They proved that every hereditary permutation property is testable in this sense, or weakly testable in their terminology. In this paper, we show that hereditary permutation properties are testable in a stronger sense, namely when testability is defined by means of the usual â1-distance for permutations. This is the permutation analogue of the well-known Alon-Shapira result on the testability of hereditary graph properties.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Antônio J.O. Bastos, Carlos Hoppen, Yoshiharu Kohayakawa, Rudini M. Sampaio,