Densities in large permutations and parameter testing
From MaRDI portal
Publication:338581
DOI10.1016/J.EJC.2016.09.006zbMATH Open1348.05010arXiv1412.5622OpenAlexW2522262817WikidataQ101496298 ScholiaQ101496298MaRDI QIDQ338581FDOQ338581
Hong Liu, Yoshiharu Kohayakawa, Tereza Klimošová, Roman Glebov, Carlos Hoppen, Daniel Král'
Publication date: 7 November 2016
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1412.5622
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
- Limits of dense graph sequences
- Limits of permutation sequences
- Property testing and its connection to learning and approximation
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
- Szemerédi's lemma for the analyst
- Quasirandom permutations are characterized by 4-point densities
- Testing properties of graphs and functions
- On graphs with small subgraphs of large chromatic number
- Graph limits and parameter testing
- Title not available (Why is that?)
- Title not available (Why is that?)
- Every Monotone Graph Property Is Testable
- Title not available (Why is that?)
- Three theorems regarding testing graph properties
- Finitely forcible graphons and permutons
- Hereditary properties of permutations are strongly testable
- Title not available (Why is that?)
- Testing permutation properties through subpermutations
Cited In (6)
- Limits of \(k\)-dimensional poset sequences
- The feasible region for consecutive patterns of permutations is a cycle polytope
- Universal limits of substitution-closed permutation classes
- 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)
