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

parameter testingpermutationsproperty 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

• 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
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• 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

(25)

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

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)