Variations on twins in permutations

DOI10.37236/9734MaRDI QIDQ2048547zbMATH OpenOpenAlexFDO

Authors Andrzej Dudek, Jarosław Grytczuk, Andrzej Ruciński

Publication date 6 August 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/2001.05589

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

permutation patternsubpermutationtwins

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Asymptotic enumeration (05A16) Combinatorial probability (60C05)

Abstract: Let $pi$ be a permutation of the set $[n]=1,2,dots,n$. Two disjoint order-isomorphic subsequences of $pi$ are called twins. How long twins are contained in every permutation? The well known ErdH{o}s-Szekeres theorem implies that there is always a pair of twins of length $Omega(sqrtn)$. On the other hand, by a simple probabilistic argument Gawron proved that for every $ngeqslant1$ there exist permutations with all twins having length $O(n^{2/3})$. He conjectured that the latter bound is the correct size of the longest twins guaranteed in every permutation. We support this conjecture by showing that almost all permutations contain twins of length $Omega(n^{2/3}/log{n}^{1/3})$. Recently, Bukh and Rudenko have tweaked our proof and removed the log-factor. For completeness, we also present our version of their proof (see Remark 1.2 below on the interrelation between the two proofs). In addition, we study several variants of the problem with diverse restrictions imposed on the twins. For instance, if we restrict attention to twins avoiding a fixed permutation $au$, then the corresponding extremal function equals $Theta(sqrtn)$, provided that $au$ is not monotone. In case of block twins (each twin occupies a segment) we prove that it is $(1+o(1))fraclognloglogn$, while for random permutations it is twice as large. For twins that jointly occupy a segment (tight twins), we prove that for every $n$ there are permutations avoiding them on all segments of length greater than $24$.

Review text

Summary: Let \(\pi\) be a permutation of the set \([n]=\{1,2,\dots, n\}\). Two disjoint order-isomorphic subsequences of \(\pi\) are called twins. How long twins are contained in every permutation? The well known Erdős-Szekeres theorem implies that there is always a pair of twins of length \(\Omega(\sqrt{n})\). On the other hand, by a simple probabilistic argument \textit{M. Gawron} [Izomorficzne podstruktury w s lowach i permutacjach. Kraków: Uniwersytet Jagielloński (Master Thesis) (2014)] proved that for every \(n\geqslant 1\) there exist permutations with all twins having length \(O(n^{2/3})\). He conjectured that the latter bound is the correct size of the longest twins guaranteed in every permutation. We support this conjecture by showing that almost all permutations contain twins of length \(\Omega(n^{2/3}/\log n^{1/3})\). Recently, \textit{B. Bukh} and \textit{O. Rudenko} [SIAM J. Discrete Math. 34, No. 3, 1620--1622 (2020; Zbl 1450.05001)] have tweaked our proof and removed the log-factor. For completeness, we also present our version of their proof (see Remark 2 below on the interrelation between the two proofs). In addition, we study several variants of the problem with diverse restrictions imposed on the twins. For instance, if we restrict attention to twins avoiding a fixed permutation \(\tau \), then the corresponding extremal function equals \(\Theta(\sqrt{n})\), provided that \(\tau\) is not monotone. In case of block twins (each twin occupies a segment) we prove that it is \((1+o(1))\frac{\log n}{\log\log n} \), while for random permutations it is twice as large. For twins that jointly occupy a segment (tight twins), we prove that for every \(n\) there are permutations avoiding them on all segments of length greater than 24.

Recommendations

• Order-isomorphic twins in permutations
• Tight multiple twins in permutations
• Twins in words and long common subsequences in permutations
• On weak twins and up-and-down subpermutations
• On weak twins and up-and-down sub-permutations

Cites work

• A regularity lemma and twins in words
• Bisection of trees and sequences
• Concentration for Independent Permutations
• Concentration for locally acting permutations
• Concentration of measure and isoperimetric inequalities in product spaces
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Herbert S. Wilf (1931--2012)
• scientific article; zbMATH DE number 2127722 (Why is no real title available?)
• scientific article; zbMATH DE number 4152423 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3675942 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• Minimal decompositions of graphs into mutually isomorphic subgraphs
• On square-free permutations
• Order-isomorphic twins in permutations
• Reflections on a Theme of Ulam
• Repetitions in graphs and sequences
• Self-similarity of graphs
• The Banach-Tarski paradox
• The probabilistic method
• Twins in words and long common subsequences in permutations

Cited in

(14)

• On permutations involving pairs of twins
• Twins in words and long common subsequences in permutations
• On weak twins and up-and-down sub-permutations
• On weak twins and up-and-down subpermutations
• Order-isomorphic twins in permutations
• Long twins in random words
• scientific article; zbMATH DE number 7771747 (Why is no real title available?)
• Patterns in ordered (random) matchings
• Decomposing Random Permutations into Order-Isomorphic Subpermutations
• Ordered unavoidable sub-structures in matchings and random matchings
• Bicrucial k-power-free permutations
• Twins in ordered hyper-matchings
• On P-crucial and S-crucial square-free permutations
• Tight multiple twins in permutations

This page was built for publication: Variations on twins in permutations

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