Limit densities of patterns in permutation inflations

DOI10.37236/8234MaRDI QIDQ2223480zbMATH OpenOpenAlexFDO

Authors Tanya Khovanova, Eric Zhang

Publication date 29 January 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(k\)-inflatable permutationslimit densities of patterns

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: Call a permutation $k$-inflatable if the sequence of its tensor products with uniform random permutations of increasing lengths has uniform $k$-point pattern densities. Previous work has shown that nontrivial $k$-inflatable permutations do not exist for $kgeq4$. In this paper, we derive a general formula for the limit densities of patterns in the sequence of tensor products of a fixed permutation with each permutation from a convergent sequence. By applying this result, we completely characterize $3$-inflatable permutations and find explicit examples of $3$-inflatable permutations with various lengths, including the shortest examples with length $17$.

Review text

Summary: Call a permutation \(k\)-inflatable if the sequence of its tensor products with uniform random permutations of increasing lengths has uniform \(k\)-point pattern densities. Previous work has shown that nontrivial \(k\)-inflatable permutations do not exist for \(k \geqslant 4\). In this paper, we derive a general formula for the limit densities of patterns in the sequence of tensor products of a fixed permutation with each permutation from a convergent sequence. By applying this result, we completely characterize 3-inflatable permutations and find explicit examples of 3-inflatable permutations with various lengths, including the shortest examples with length 17.

Recommendations

• Large deviations and ratio limit theorems for pattern-avoiding permutations
• On some densities in the set of permutations
• Permutations with fixed pattern densities
• Scaling limits of permutation classes with a finite specification: a dichotomy
• On permutation-invariance of limit theorems
• scientific article; zbMATH DE number 4013620
• Asymptotics of permutations with nearly periodic patterns of rises and falls
• scientific article; zbMATH DE number 714511
• The limit shape of random permutations with polynomially growing cycle weights
• scientific article; zbMATH DE number 4022354

Cites work

• Generalized quasirandom graphs
• Quasi-random graphs
• Quasirandom permutations
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Simple permutations and pattern restricted permutations

Cited in

(1)

• Chip firing on directed k-ary trees

This page was built for publication: Limit densities of patterns in permutation inflations

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