Hereditary properties of permutations are strongly testable

DOI10.1137/1.9781611973402.86MaRDI QIDQ5384048zbMATH OpenOpenAlexWikidataFDO

Authors Tereza Klimošová, Daniel Král'

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.2624

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05)

Abstract: We show that for every hereditary permutation property P and every eps>0, there exists an integer M such that if a permutation p is eps-far from P in the Kendall's tau distance, then a random subpermutation of p of order M has the property P with probability at most eps. 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.

Recommendations

• Every hereditary permutation property is testable
• Permutation Property Testing under Different Metrics with Low Query Complexity
• Fast property testing and metrics for permutations
• Property testing and parameter testing for permutations
• Testing permutation properties through subpermutations

Cited in

(12)

• Limits of \(k\)-dimensional poset sequences
• Patterns in random permutations
• Every hereditary permutation property is testable
• Fast property testing and metrics for permutations
• Densities in large permutations and parameter testing
• Testing hereditary properties of sequences
• Property testing and parameter testing for permutations
• Testing permutation properties through subpermutations
• Quasi-random words and limits of word sequences
• On pattern-avoiding permutons
• Posets are easily testable
• A polynomial removal lemma for posets (extended abstract)

This page was built for publication: Hereditary properties of permutations are strongly testable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384048)