Testing permutation properties through subpermutations

DOI10.1016/J.TCS.2011.03.002MaRDI QIDQ551179zbMATH OpenOpenAlexWikidataFDO

Authors Carlos Hoppen, Yoshiharu Kohayakawa, C. Moreira, Rudini M. Sampaio

Publication date 14 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

permutationsproperty testingparameter testing

Mathematics Subject Classification ID

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

Abstract: A permutation sequence $(sigm{a}_n{)}_{ninmathbbN}$ is said to be convergent if, for every fixed permutation $au$, the density of occurrences of $au$ in the elements of the sequence converges. We prove that such a convergent sequence has a natural limit object, namely a Lebesgue measurable function $Z:[0,1{]}^{2}o[0,1]$ with the additional properties that, for every fixed $xin[0,1]$, the restriction $Z(x,cdot)$ is a cumulative distribution function and, for every $yin[0,1]$, the restriction $Z(cdot,y)$ satisfies a "mass" condition. This limit process is well-behaved: every function in the class of limit objects is a limit of some permutation sequence, and two of these functions are limits of the same sequence if and only if they are equal almost everywhere. An important ingredient in the proofs is a new model of random permutations, which generalizes previous models and is interesting for its own sake.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• A permutation regularity lemma
• A sublinear algorithm for weakly approximating edit distance
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Complex graphs and networks
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Efficient testing of large graphs
• Every Monotone Graph Property Is Testable
• Graph limits and parameter testing
• Limits of dense graph sequences
• Limits of permutation sequences
• On graphs with small subgraphs of large chromatic number
• Quantum Property Testing
• Quasi-random graphs
• Quasirandom permutations
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Spot-checkers
• Sublinear algorithms for testing monotone and unimodal distributions
• Testing graphs for colorability properties
• Testing properties of graphs and functions
• Testing satisfiability
• The complexity of the weight problem for permutation and matrix groups.
• The diameter of a scale-free random graph
• Three theorems regarding testing graph properties

Cited in

(20)

• Patterns in random permutations
• Quasi-random words and limits of word sequences
• Limits of \(k\)-dimensional poset sequences
• Fast property testing and metrics for permutations
• Poset limits can be totally ordered
• Weak regularity and finitely forcible graph limits
• Densities in large permutations and parameter testing
• Finitely forcible graphons and permutons
• Hereditary properties of permutations are strongly testable
• Tests with respect to permutations of variables in Boolean functions
• Independence of permutation limits at infinitely many scales
• A note on permutation regularity
• Testing hereditary properties of sequences
• Higher-order fluctuations in dense random graph models
• Every hereditary permutation property is testable
• Permutation Property Testing under Different Metrics with Low Query Complexity
• Limits of structures and the example of tree semi-lattices
• Density maximizers of layered permutations
• Property testing and parameter testing for permutations
• Quasirandom permutations are characterized by 4-point densities

This page was built for publication: Testing permutation properties through subpermutations

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