Densities in large permutations and parameter testing

DOI10.1016/J.EJC.2016.09.006MaRDI QIDQ338581zbMATH OpenOpenAlexWikidataFDO

Authors Roman Glebov, Carlos Hoppen, Tereza Klimošová, Daniel Král', Yoshiharu Kohayakawa, Hong Liu

Publication date 7 November 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

graphcopy functions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Connectivity (05C40) Density (toughness, etc.) (05C42)

Abstract: A classical theorem of Erdos, Lovasz and Spencer asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and we then apply the methods used in the proof to give an example of a finitely approximable permutation parameter that is not finitely forcible. The latter answers a question posed by two of the authors and Moreira and Sampaio.

Recommendations

• Testing equality of a large number of densities under mixing conditions
• Permutation Tests Using Estimated Distribution Functions
• scientific article; zbMATH DE number 714487
• Testing equality of a large number of densities
• Permutation tests using arbitrary permutation distributions
• A Note on Density Model Size Testing
• On some densities in the set of permutations
• Permutation tests for equality of distributions in high-dimensional settings

Cites work

• scientific article; zbMATH DE number 2186865 (Why is no real title available?)
• scientific article; zbMATH DE number 3722700 (Why is no real title available?)
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Every Monotone Graph Property Is Testable
• Finitely forcible graphons and permutons
• Graph limits and parameter testing
• Hereditary properties of permutations are strongly testable
• Limits of dense graph sequences
• Limits of permutation sequences
• On graphs with small subgraphs of large chromatic number
• Packing rates of measures and a conjecture for the packing density of 2413
• Property testing and its connection to learning and approximation
• Property testing and parameter testing for permutations
• Quasirandom permutations are characterized by 4-point densities
• Szemerédi's lemma for the analyst
• Testing permutation properties through subpermutations
• Testing properties of graphs and functions
• Three theorems regarding testing graph properties

Cited in

(6)

• Limits of \(k\)-dimensional poset sequences
• Universal limits of substitution-closed permutation classes
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Weak regularity and finitely forcible graph limits
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Independence of permutation limits at infinitely many scales

This page was built for publication: Densities in large permutations and parameter testing

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