Segui questo link per vedere altri tipi di pubblicazioni sul tema: Permutations. Mathematics.
Articoli di riviste sul tema "Permutations. Mathematics"
Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili
Vedi i top-50 articoli di riviste per l'attività di ricerca sul tema "Permutations. Mathematics".
Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.
Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.
Vedi gli articoli di riviste di molte aree scientifiche e compila una bibliografia corretta.
1
Brualdi, Richard A., e Geir Dahl. "Permutation Matrices, Their Discrete Derivatives and Extremal Properties". Vietnam Journal of Mathematics 48, n. 4 (24 marzo 2020): 719–40. http://dx.doi.org/10.1007/s10013-020-00392-5.
Testo completoAbstract (sommario):
AbstractFor a permutation π, and the corresponding permutation matrix, we introduce the notion of discrete derivative, obtained by taking differences of successive entries in π. We characterize the possible derivatives of permutations, and consider questions for permutations with certain properties satisfied by the derivative. For instance, we consider permutations with distinct derivatives, and the relationship to so-called Costas arrays.
2
Drakakis, Konstantinos. "On the Measurement of the (Non)linearity of Costas Permutations". Journal of Applied Mathematics 2010 (2010): 1–14. http://dx.doi.org/10.1155/2010/149658.
Testo completoAbstract (sommario):
We study several criteria for the (non)linearity of Costas permutations, with or without the imposition of additional algebraic structure in the domain and the range of the permutation, aiming to find one that successfully identifies Costas permutations as more nonlinear than randomly chosen permutations of the same order.
3
Steingrı́msson, Einar. "Permutation Statistics of Indexed Permutations". European Journal of Combinatorics 15, n. 2 (marzo 1994): 187–205. http://dx.doi.org/10.1006/eujc.1994.1021.
Testo completo
4
Hajnal, Péter. "A short note on Layman permutations". Acta Universitatis Sapientiae, Mathematica 14, n. 2 (1 dicembre 2022): 231–38. http://dx.doi.org/10.2478/ausm-2022-0015.
Testo completoAbstract (sommario):
Abstract A permutation p of [k] = {1, 2, 3, …, k} is called Layman permutation iff i + p(i) is a Fibonacci number for 1 ≤ i ≤ k. This concept is introduced by Layman in the A097082 entry of the Encyclopedia of Integers Sequences, that is the number of Layman permutations of [n]. In this paper, we will study Layman permutations. We introduce the notion of the Fibonacci complement of a natural number, that plays a crucial role in our investigation. Using this notion we prove some results on the number of Layman permutations, related to a conjecture of Layman that is implicit in the A097083 entry of OEIS.
5
Choi, Wonseok, Jooyoung Lee e Yeongmin Lee. "Building PRFs from TPRPs: Beyond the Block and the Tweak Length Bounds". IACR Transactions on Symmetric Cryptology 2024, n. 1 (1 marzo 2024): 35–70. http://dx.doi.org/10.46586/tosc.v2024.i1.35-70.
Testo completoAbstract (sommario):
A secure n-bit tweakable block cipher (TBC) using t-bit tweaks can be modeled as a tweakable uniform random permutation, where each tweak defines an independent random n-bit permutation. When an input to this tweakable permutation is fixed, it can be viewed as a perfectly secure t-bit random function. On the other hand, when a tweak is fixed, it can be viewed as a perfectly secure n-bit random permutation, and it is well known that the sum of two random permutations is pseudorandom up to 2n queries.A natural question is whether one can construct a pseudorandom function (PRF) beyond the block and the tweak length bounds using a small number of calls to the underlying tweakable permutations. A straightforward way of constructing a PRF from tweakable permutations is to xor the outputs from two tweakable permutations with c bits of the input to each permutation fixed. Using the multi-user security of the sum of two permutations, one can prove that the (t + n − c)-to-n bit PRF is secure up to 2n+c queries.In this paper, we propose a family of PRF constructions based on tweakable permutations, dubbed XoTPc, achieving stronger security than the straightforward construction. XoTPc is parameterized by c, giving a (t + n − c)-to-n bit PRF. When t < 3n and c = t/3 , XoTPt/3 becomes an (n + 2t/3 )-to-n bit pseudorandom function, which is secure up to 2n+2t/3 queries. It provides security beyond the block and the tweak length bounds, making two calls to the underlying tweakable permutations. In order to prove the security of XoTPc, we extend Mirror theory to q ≫ 2n, where q is the number of equations. From a practical point of view, our construction can be used to construct TBC-based MAC finalization functions and CTR-type encryption modes with stronger provable security compared to existing schemes.
6
Burov, Dmitry A. "Subgroups of direct products of groups invariant under the action of permutations on factors". Discrete Mathematics and Applications 30, n. 4 (26 agosto 2020): 243–55. http://dx.doi.org/10.1515/dma-2020-0021.
Testo completoAbstract (sommario):
AbstractWe study subgroups of the direct product of two groups invariant under the action of permutations on factors. An invariance criterion for the subdirect product of two groups under the action of permutations on factors is put forward. Under certain additional constraints on permutations, we describe the subgroups of the direct product of a finite number of groups that are invariant under the action of permutations on factors. We describe the subgroups of the additive group of vector space over a finite field of characteristic 2 which are invariant under the coordinatewise action of inversion permutation of nonzero elements of the field.
7
WANG, LI-YUAN, e HAI-LIANG WU. "APPLICATIONS OF LERCH’S THEOREM TO PERMUTATIONS OF QUADRATIC RESIDUES". Bulletin of the Australian Mathematical Society 100, n. 3 (10 luglio 2019): 362–71. http://dx.doi.org/10.1017/s000497271900073x.
Testo completoAbstract (sommario):
Let $n$ be a positive integer and $a$ an integer prime to $n$. Multiplication by $a$ induces a permutation over $\mathbb{Z}/n\mathbb{Z}=\{\overline{0},\overline{1},\ldots ,\overline{n-1}\}$. Lerch’s theorem gives the sign of this permutation. We explore some applications of Lerch’s result to permutation problems involving quadratic residues modulo $p$ and confirm some conjectures posed by Sun [‘Quadratic residues and related permutations and identities’, Preprint, 2018, arXiv:1809.07766]. We also study permutations involving arbitrary $k$th power residues modulo $p$ and primitive roots modulo a power of $p$.
8
BLOCK, LOUIS, ALEXANDER M. BLOKH e ETHAN M. COVEN. "ZERO ENTROPY PERMUTATIONS". International Journal of Bifurcation and Chaos 05, n. 05 (ottobre 1995): 1331–37. http://dx.doi.org/10.1142/s0218127495001009.
Testo completoAbstract (sommario):
The entropy of a permutation is the (topological) entropy of the "connect-the-dots" map determined by it. We give matrix- and graph-theoretic, geometric, and dynamical characterizations of zero entropy permutations, as well as a procedure for constructing all of them. We also include some information about the number of zero entropy permutations.
9
ZHOU, YINGCHUN, e MURAD S. TAQQU. "APPLYING BUCKET RANDOM PERMUTATIONS TO STATIONARY SEQUENCES WITH LONG-RANGE DEPENDENCE". Fractals 15, n. 02 (giugno 2007): 105–26. http://dx.doi.org/10.1142/s0218348x07003526.
Testo completoAbstract (sommario):
Bucket random permutations (shuffling) are used to modify the dependence structure of a time series, and this may destroy long-range dependence, when it is present. Three types of bucket permutations are considered here: external, internal and two-level permutations. It is commonly believed that (1) an external random permutation destroys the long-range dependence and keeps the short-range dependence, (2) an internal permutation destroys the short-range dependence and keeps the long-range dependence, and (3) a two-level permutation distorts the medium-range dependence while keeping both the long-range and short-range dependence. This paper provides a theoretical basis for investigating these claims. It extends the study started in Ref. 1 and analyze the effects that these random permutations have on a long-range dependent finite variance stationary sequence both in the time domain and in the frequency domain.
10
Cioni, Lapo, e Luca Ferrari. "Sorting with a popqueue". RAIRO - Theoretical Informatics and Applications 58 (2024): 13. http://dx.doi.org/10.1051/ita/2024010.
Testo completoAbstract (sommario):
We introduce a new sorting device for permutations, which we call popqueue. It consists of a special queue, having the property that any time one wants to extract elements from the queue, actually all the elements currently in the queue are poured into the output. We illustrate two distinct optimal algorithms, called Min and Cons, to sort a permutation using such a device, which allow us also to characterize sortable permutations in terms of pattern avoidance. We next investigate what happens by making two passes through a popqueue, showing that the set of sortable permutations is not a class for Min, whereas it is for Cons. In the latter case we also explicitly find the basis of the class of sortable permutations. Finally, we study preimages under Cons (by means of an equivalent version of the algorithm), and find a characterization of the set of preimages of a given permutation. We also give some enumerative results concerning the number of permutations having k preimages, for k = 1, 2, 3, and we conclude by observing that there exist permutations having k preimages for any value of k ≥ 0.
11
Yakymiv, Arsen L. "Asymptotics with remainder term for moments of the total cycle number of random A-permutation". Discrete Mathematics and Applications 31, n. 1 (1 febbraio 2021): 51–60. http://dx.doi.org/10.1515/dma-2021-0005.
Testo completoAbstract (sommario):
Abstract Dedicated to the memory of Alexander Ivanovich Pavlov. We consider the set of n-permutations with cycle lengths belonging to some fixed set A of natural numbers (so-called A-permutations). Let random permutation τ n be uniformly distributed on this set. For some class of sets A we find the asymptotics with remainder term for moments of total cycle number of τ n .
12
Gu, Yutong. "Introduction of Several Special Groups and Their Applications to Rubik’s Cube". Highlights in Science, Engineering and Technology 47 (11 maggio 2023): 172–75. http://dx.doi.org/10.54097/hset.v47i.8186.
Testo completoAbstract (sommario):
Group theory is the subject that aims to study the symmetries and structures of groups in mathematics. This work provides an introduction to group theory and explores some potential applications of group theory on complex geometric objects like the Rubik's cube. To this end, the concepts of symmetric group, permutation group, and cyclic group are introduced, and the famous Lagrange’s theorem and Cayley’s theorem are mentioned briefly. The former theorem establishes that a subgroup’s order must be a divisor of the parent group’s order. Concerning the permutation group, it is a set of permutations that form a group under composition. Hence, the various groups that can be formed by the Rubik's cube are discussed, including the group of all possible permutations of the cube's stickers, and the subgroups that are generated through permutations of the six basic movements embedded in Rubik’s cube. Overall, this essay provides an accessible introduction to group theory and its applications to the popular Rubik's cube.
13
Matitaputty, Christi, Wilmintjie Mataheru e Taufan Talib. "ANALISIS KESALAHAN MAHASISWA DALAM MENYELESAIKAN MASALAH PERMUTASI DAN KOMBINASI". Jurnal Magister Pendidikan Matematika (JUMADIKA) 4, n. 2 (27 ottobre 2022): 43–49. http://dx.doi.org/10.30598/jumadikavol4iss2year2022page43-49.
Testo completoAbstract (sommario):
Permutations and combinations are one of the materials in discrete mathematics courses that have many benefits in everyday life and are closely related to the context of real life. However, students need to improve in solving permutation and combination problems. This study aims to describe the errors made by students in solving permutation and combination problems. The research subjects comprised 25 first-semester students of the 2021/2022 academic year of the Mathematics Education Study Program, FKIP Unpatti. The research method used is descriptive qualitative. The research instrument consisted of 6 test questions related to permutations and combinations. The results showed that most students made mistakes because they needed help understanding the statement (58%). In addition, students also made mistakes in remembering value parameters (13%), paying attention to order (10%), recognizing objects (8%), using formulas (7%), and errors in performing arithmetic operations (4%). The implications of this research are expected to be able to contribute to lecture activities in the first year
14
Miranda, Guilherme Henrique Santos, Alexsandro Oliveira Alexandrino, Carla Negri Lintzmayer e Zanoni Dias. "Approximation Algorithms for Sorting λ-Permutations by λ-Operations". Algorithms 14, n. 6 (1 giugno 2021): 175. http://dx.doi.org/10.3390/a14060175.
Testo completoAbstract (sommario):
Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented as the identity permutation, and, so, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of rearrangements. This work investigates the problems of sorting permutations using reversals and/or transpositions, with some additional restrictions of biological relevance. Given a value λ, the problem now is how to sort a λ-permutation, which is a permutation whose elements are less than λ positions away from their correct places (regarding the identity), by applying the minimum number of rearrangements. Each λ-rearrangement must have size, at most, λ, and, when applied to a λ-permutation, the result should also be a λ-permutation. We present algorithms with approximation factors of O(λ2), O(λ), and O(1) for the problems of Sorting λ-Permutations by λ-Reversals, by λ-Transpositions, and by both operations.
15
Olshevska, V. A. "Permutation codes over Sylow 2-subgroups $Syl_2(S_{2^n})$ of symmetric groups $S_{2^n}$". Researches in Mathematics 29, n. 2 (30 dicembre 2021): 28. http://dx.doi.org/10.15421/242107.
Testo completoAbstract (sommario):
The permutation code (or the code) is well known object of research starting from 1970s. The code and its properties is used in different algorithmic domains such as error-correction, computer search, etc. It can be defined as follows: the set of permutations with the minimum distance between every pair of them. The considered distance can be different. In general, there are studied codes with Hamming, Ulam, Levensteins, etc. distances.In the paper we considered permutations codes over 2-Sylow subgroups of symmetric groups with Hamming distance over them. For this approach representation of permutations by rooted labeled binary trees is used. This representation was introduced in the previous author's paper. We also study the property of the Hamming distance defined on permutations from Sylow 2-subgroup $Syl_2(S_{2^n})$ of symmetric group $S_{2^n}$ and describe an algorithm for finding the Hamming distance over elements from Sylow 2-subgroup of the symmetric group with complexity $O(2^n)$. The metric properties of the codes that are defined on permutations from Sylow 2-subgroup $Syl_2(S_{2^n})$ of symmetric group $S_{2^n}$ are studied. The capacity and number of codes for the maximum and the minimum non-trivial distance over codes are characterized.
16
Khashaev, Arthur A. "On the membership problem for finite automata over symmetric groups". Discrete Mathematics and Applications 32, n. 6 (1 dicembre 2022): 383–89. http://dx.doi.org/10.1515/dma-2022-0033.
Testo completoAbstract (sommario):
Abstract We consider automata in which transitions are labelled with arbitrary permutations. The language of such an automaton consists of compositions of permutations for all possible admissible computation paths. The membership problem for finite automata over symmetric groups is the following decision problem: does a given permutation belong to the language of a given automaton? We show that this problem is NP-complete. We also propose an efficient algorithm for the case of strongly connected automata.
17
BERNARDI, OLIVIER, ROSENA R. X. DU, ALEJANDRO H. MORALES e RICHARD P. STANLEY. "Separation Probabilities for Products of Permutations". Combinatorics, Probability and Computing 23, n. 2 (13 dicembre 2013): 201–22. http://dx.doi.org/10.1017/s0963548313000588.
Testo completoAbstract (sommario):
We study the mixing properties of permutations obtained as a product of two uniformly random permutations of fixed cycle types. For instance, we give an exact formula for the probability that elements 1,2,. . .,k are in distinct cycles of the random permutation of {1,2,. . .,n} obtained as a product of two uniformly random n-cycles.
18
Liu, Mengyu, e Huilan Li. "A Hopf Algebra on Permutations Arising from Super-Shuffle Product". Symmetry 13, n. 6 (4 giugno 2021): 1010. http://dx.doi.org/10.3390/sym13061010.
Testo completoAbstract (sommario):
In this paper, we first prove that any atom of a permutation obtained by the super-shuffle product of two permutations can only consist of some complete atoms of the original two permutations. Then, we prove that the super-shuffle product and the cut-box coproduct on permutations are compatible, which makes it a bialgebra. As this algebra is graded and connected, it is a Hopf algebra.
19
Brignall, Robert, Vít Jelínek, Jan Kynčl e David Marchant. "ZEROS OF THE MÖBIUS FUNCTION OF PERMUTATIONS". Mathematika 65, n. 4 (2019): 1074–92. http://dx.doi.org/10.1112/s0025579319000251.
Testo completoAbstract (sommario):
We show that if a permutation $\unicode[STIX]{x1D70B}$ contains two intervals of length 2, where one interval is an ascent and the other a descent, then the Möbius function $\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]$ of the interval $[1,\unicode[STIX]{x1D70B}]$ is zero. As a consequence, we prove that the proportion of permutations of length $n$ with principal Möbius function equal to zero is asymptotically bounded below by $(1-1/e)^{2}\geqslant 0.3995$. This is the first result determining the value of $\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]$ for an asymptotically positive proportion of permutations $\unicode[STIX]{x1D70B}$. We further establish other general conditions on a permutation $\unicode[STIX]{x1D70B}$ that ensure $\unicode[STIX]{x1D707}[1,\unicode[STIX]{x1D70B}]=0$, including the occurrence in $\unicode[STIX]{x1D70B}$ of any interval of the form $\unicode[STIX]{x1D6FC}\oplus 1\oplus \unicode[STIX]{x1D6FD}$.
20
Malyshev, Fedor M. "On affine classification of permutations on the space GF(2)3". Discrete Mathematics and Applications 29, n. 6 (18 dicembre 2019): 363–71. http://dx.doi.org/10.1515/dma-2019-0035.
Testo completoAbstract (sommario):
Abstract We give an elementary proof that by multiplication on left and right by affine permutations A, B ∈ AGL(3, 2) each permutation π : GF(2)3 → GF(2)3 may be reduced to one of the 4 permutations for which the 3 × 3-matrices consisting of the coefficients of quadratic terms of coordinate functions have as an invariant the rank, which is either 3, or 2, or 1, or 0, respectively. For comparison, we evaluate the number of classes of affine equivalence by the Pólya enumerative theory.
21
Cao, Xiwang, Lei Hu e Zhengbang Zha. "Constructing permutation polynomials from piecewise permutations". Finite Fields and Their Applications 26 (marzo 2014): 162–74. http://dx.doi.org/10.1016/j.ffa.2013.12.001.
Testo completo
22
ATAPOUR, MAHSHID, e NEAL MADRAS. "Large Deviations and Ratio Limit Theorems for Pattern-Avoiding Permutations". Combinatorics, Probability and Computing 23, n. 2 (13 dicembre 2013): 161–200. http://dx.doi.org/10.1017/s0963548313000576.
Testo completoAbstract (sommario):
For a fixed permutation τ, let$\mathcal{S}_N(\tau)$be the set of permutations onNelements that avoid the pattern τ. Madras and Liu (2010) conjectured that$\lim_{N\rightarrow\infty}\frac{|\mathcal{S}_{N+1}(\tau)|}{ |\mathcal{S}_N(\tau)|}$exists; if it does, it must equal the Stanley–Wilf limit. We prove the conjecture for every permutation τ of length 5 or less, as well as for some longer cases (including 704 of the 720 permutations of length 6). We also consider permutations drawn at random from$\mathcal{S}_N(\tau)$, and we investigate properties of their graphs (viewing permutations as functions on {1,. . .,N}) scaled down to the unit square [0,1]2. We prove exact large deviation results for these graphs when τ has length 3; it follows, for example, that it is exponentially unlikely for a random 312-avoiding permutation to have points above the diagonal strip |y−x| < ε, but not unlikely to have points below the strip. For general τ, we show that some neighbourhood of the upper left corner of [0,1]2is exponentially unlikely to contain a point of the graph if and only if τ starts with its largest element. For patterns such as τ=4231 we establish that this neighbourhood can be extended along the sides of [0,1]2to come arbitrarily close to the corner points (0,0) and (1,1), as simulations had suggested.
23
KUBA, MARKUS, e ALOIS PANHOLZER. "Analysis of Statistics for Generalized Stirling Permutations". Combinatorics, Probability and Computing 20, n. 6 (11 ottobre 2011): 875–910. http://dx.doi.org/10.1017/s0963548311000381.
Testo completoAbstract (sommario):
In this work we give a study of generalizations of Stirling permutations, a restricted class of permutations of multisets introduced by Gessel and Stanley [15]. First we give several bijections between such generalized Stirling permutations and various families of increasing trees extending the known correspondences of [20, 21]. Then we consider several permutation statistics of interest for generalized Stirling permutations as the number of left-to-right minima, the number of left-to-right maxima, the number of blocks of specified sizes, the distance between occurrences of elements, and the number of inversions. For all these quantities we give a distributional study, where the established connections to increasing trees turn out to be very useful. To obtain the exact and limiting distribution results we use several techniques ranging from generating functions, connections to urn models, martingales and Stein's method.
24
Arnold, Vladimir I. "Permutations". Russian Mathematical Surveys 64, n. 4 (31 agosto 2009): 583–624. http://dx.doi.org/10.1070/rm2009v064n04abeh004628.
Testo completo
25
Maehara, Takanori, e Yuma Inoue. "Group Decision Diagram (GDD): A Compact Representation for Permutations". Proceedings of the AAAI Conference on Artificial Intelligence 33 (17 luglio 2019): 2986–94. http://dx.doi.org/10.1609/aaai.v33i01.33012986.
Testo completoAbstract (sommario):
Permutation is a fundamental combinatorial object appeared in various areas in mathematics, computer science, and artificial intelligence. In some applications, a subset of a permutation group must be maintained efficiently. In this study, we develop a new data structure, called group decision diagram (GDD), to maintain a set of permutations. This data structure combines the zero-suppressed binary decision diagram with the computable subgroup chain of the permutation group. The data structure enables efficient operations, such as membership testing, set operations (e.g., union, intersection, and difference), and Cartesian product. Our experiments demonstrate that the data structure is efficient (i.e., 20–300 times faster) than the existing methods when the permutation group is considerably smaller than the symmetric group, or only subsets constructed by a few operations over generators are maintained.
26
Sheet, Lugen M. Zake. ""Efficiency Comparison of Algorithms for Finding Determinants Via Permutations "". Muthanna Journal of Pure Science 8, n. 1 (13 gennaio 2021): 56–65. http://dx.doi.org/10.52113/2/08.01.2021/56-65.
Testo completoAbstract (sommario):
"Determiners have been used extensively in a selection of applications throughout history. It also biased many areas of mathematics such as linear algebra. There are algorithms commonly used for computing a matrix determinant such as: Laplace expansion, LDU decomposition, Cofactor algorithm, and permutation algorithms. The determinants of a quadratic matrix can be found using a diversity of these methods, including the well-known methods of the Leibniz formula and the Laplace expansion and permutation algorithms that computes the determinant of any n×n matrix in O(n!). In this paper, we first discuss three algorithms for finding determinants using permutations. Then we make out the algorithms in pseudo code and finally, we analyze the complexity and nature of the algorithms and compare them with each other. We present permutations algorithms and then analyze and compare them in terms of runtime, acceleration and competence, as the presented algorithms presented different results.
27
Tymofijeva, N. K. "Objective Function in Combinatorial Optimization and Its Properties". Control Systems and Computers, n. 4 (304) (2023): 3–11. http://dx.doi.org/10.15407/csc.2023.04.003.
Testo completoAbstract (sommario):
Introduction. Some properties of combinatorial optimization problems are described, which affect the regularity of changes in the values of the objective function regardless of the input data. It is shown that this regularity depends on the arrangement of combinatorial configurations, a certain structure of input information, the transposition of permutation elements and the symmetry of combinatorial sets (argument). In problems that are solved on permutations, and a subset of isomorphic combinatorial configurations, the class of the objective function is determined depending on their ordering and the structure of the input data. Formulation of the problem. There are works where, in combinatorial optimization, the change in the values of the objective function is investigated depending on the special structure of the input information. These studies are related to the selection of subclasses of solvable problems, and various structures are generalized for which the objective function changes in the same way. The task is to identify the parameters of problems of this class, in which the input data do not affect the pattern of changes in the values of the objective function. The proposed approach. To identify the parameters under which the input data do not affect the pattern of changes in the objective function values in combinatorial optimization, this pattern is analyzed from the arrangement of permutations, the transposition of its elements, and the structure of the input information. The change of the values of the objective function from the structure of its argument (the structure of combinatorial sets) is also investigated. Conclusion. Knowing the properties of combinatorial functions allows you to establish a change in the values of the target function depending on the transposition of the elements in the permutation, on the arrangement of combinatorial configurations. If the combinatorial set consists of one subset of isomorphic combinatorial configurations (permutations), then the set of values of the objective function follows the rules characteristic of permutations. If the set consists of subsets of isomorphic combinatorial configurations, then they can be ordered in such a way that the objective function for this ordering varies as piecewise monotonic functions regardless of the input data, and for the isomorphic subset it varies as in problems whose objective function argument is the permutation.
28
Ayyer, Arvind, e Beáta Bényi. "Toppling on Permutations with an Extra Chip". Electronic Journal of Combinatorics 28, n. 4 (5 novembre 2021). http://dx.doi.org/10.37236/10420.
Testo completoAbstract (sommario):
The study of toppling on permutations with an extra labeled chip was initiated by the first author with D. Hathcock and P. Tetali (arXiv:2010.11236), where the extra chip was added in the middle. We extend this to all possible locations $p$ as well as values $r$ of the extra chip and give a complete characterization of permutations which topple to the identity. Further, we classify all permutations which are outcomes of the toppling process in this generality, which we call resultant permutations. Resultant permutations turn out to be certain decomposable permutations. The number of configurations toppling to a given resultant permutation is shown to depend purely on the number of left-to-right maxima (or records) of the permutation to the left of $p$ and the number of right-to-left minima to the right of $p$. The number of permutations toppling to a given resultant permutation (identity or otherwise) is shown to be the binomial transform of a poly-Bernoulli number of type B.
29
Khovanova, Tanya, e Eric Zhang. "Limit Densities of Patterns in Permutation Inflations". Electronic Journal of Combinatorics 28, n. 1 (29 gennaio 2021). http://dx.doi.org/10.37236/8234.
Testo completoAbstract (sommario):
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 \geq 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$.
30
Avgustinovich, Sergey, Sergey Kitaev e Anna Taranenko. "On Five Types of Crucial Permutations with Respect to Monotone Patterns". Electronic Journal of Combinatorics 30, n. 1 (24 febbraio 2023). http://dx.doi.org/10.37236/11500.
Testo completoAbstract (sommario):
A crucial permutation is a permutation that avoids a given set of prohibitions, but any of its extensions, in an allowable way, results in a prohibition being introduced.
In this paper, we introduce five natural types of crucial permutations with respect to monotone patterns, notably quadracrucial permutations that are linked most closely to Erdős-Szekeres extremal permutations. The way we define right-crucial and bicrucial permutations is consistent with the definition of respective permutations studied in the literature in the contexts of other prohibitions. For each of the five types, we provide its characterization in terms of Young tableaux via the Robinson-Schensted correspondence. Moreover, we use the characterizations to prove that the number of such permutations of length $n$ is growing when $n\to\infty$, and to enumerate minimal crucial permutations in all but one case. We also provide other enumerative results.
31
Borga, Jacopo, Sayan Das, Sumit Mukherjee e Peter Winkler. "Large Deviation Principle for Random Permutations". International Mathematics Research Notices, 16 maggio 2023. http://dx.doi.org/10.1093/imrn/rnad096.
Testo completoAbstract (sommario):
Abstract We derive a large deviation principle for random permutations induced by probability measures of the unit square, called permutons. These permutations are called $\mu $-random permutations. We also introduce and study a new general class of models of random permutations, called Gibbs permutation models, which combines and generalizes $\mu $-random permutations and the celebrated Mallows model for permutations. Most of our results hold in the general setting of Gibbs permutation models. We apply the tools that we develop to the case of $\mu $-random permutations conditioned to have an atypical proportion of patterns. Several results are made more concrete in the specific case of inversions. For instance, we prove the existence of at least one phase transition for a generalized version of the Mallows model where the base measure is non-uniform. This is in contrast with the results of Starr (2009, 2018) on the (standard) Mallows model, where the absence of phase transition, that is, phase uniqueness, was proven. Our results naturally lead us to investigate a new notion of permutons, called conditionally constant permutons, which generalizes both pattern-avoiding and pattern-packing permutons. We describe some properties of conditionally constant permutons with respect to inversions. The study of conditionally constant permutons for general patterns seems to be a new challenging problem.
32
Albert, Michael, e Murray Tannock. "Prolific Permutations". Electronic Journal of Combinatorics 28, n. 2 (9 aprile 2021). http://dx.doi.org/10.37236/9966.
Testo completoAbstract (sommario):
The concept of prolificity was previously introduced by the authors in the context of compositions of integers. We give a general interpretation of prolificity that applies across a range of relational structures defined in terms of counting embeddings. We then proceed to classify prolificity in permutation classes with bases consisting of permutations of length 2, or 3; completely classifying all such classes except ${\rm Av}(321)$. We then show a number of interesting properties that arise when studying prolificity in ${\rm Av}(321)$, concluding by showing that the class of permutations that are not prolific for any increasing permutation in ${\rm Av}(321)$ form a polynomial subclass.
33
Dutta, Avijit, Mridul Nandi e Suprita Talnikar. "Permutation Based EDM: An Inverse Free BBB Secure PRF". IACR Transactions on Symmetric Cryptology, 11 giugno 2021, 31–70. http://dx.doi.org/10.46586/tosc.v2021.i2.31-70.
Testo completoAbstract (sommario):
In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure n-bit to n-bit PRF constructions, i.e., SoEM22 and SoKAC21, which are built on public permutations, where n is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based n-bit to n-bit beyond the birthday bound secure PRF, which they refer to as PDMMAC. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based n-bit to n-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose pEDM, a single permutation based n-bit to n-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to 22n/3 construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.
34
Egge, Eric S., e Kailee Rubin. "Snow Leopard Permutations and Their Even and Odd Threads". Discrete Mathematics & Theoretical Computer Science Vol. 18 no. 2, Permutation..., Permutation Patterns (1 giugno 2016). http://dx.doi.org/10.46298/dmtcs.1279.
Testo completoAbstract (sommario):
Caffrey, Egge, Michel, Rubin and Ver Steegh recently introduced snow leopard permutations, which are the anti-Baxter permutations that are compatible with the doubly alternating Baxter permutations. Among other things, they showed that these permutations preserve parity, and that the number of snow leopard permutations of length $2n-1$ is the Catalan number $C_n$. In this paper we investigate the permutations that the snow leopard permutations induce on their even and odd entries; we call these the even threads and the odd threads, respectively. We give recursive bijections between these permutations and certain families of Catalan paths. We characterize the odd (resp. even) threads which form the other half of a snow leopard permutation whose even (resp. odd) thread is layered in terms of pattern avoidance, and we give a constructive bijection between the set of permutations of length $n$ which are both even threads and odd threads and the set of peakless Motzkin paths of length $n+1$. Comment: 25 pages, 6 figures. Version 3 is modified to use standard Discrete Mathematics and Theoretical Computer Science but is otherwise unchanged
35
Kobayashi, Masato. "Bijection Between Bigrassmannian Permutations Maximal below a Permutation and its Essential Set". Electronic Journal of Combinatorics 17, n. 1 (20 maggio 2010). http://dx.doi.org/10.37236/476.
Testo completoAbstract (sommario):
Bigrassmannian permutations are known as permutations which have precisely one left descent and one right descent. They play an important role in the study of Bruhat order. Fulton introduced the essential set of a permutation and studied its combinatorics. As a consequence of his work, it turns out that the essential set of bigrassmannian permutations consists of precisely one element. In this article, we generalize this observation for essential sets of arbitrary permutations. Our main theorem says that there exists a bijection between bigrassmanian permutations maximal below a permutation and its essential set. For the proof, we make use of two equivalent characterizations of bigrassmannian permutations by Lascoux-Schützenberger and Reading.
36
Burstein, Alexander, e Niklas Eriksen. "Combinatorial properties of permutation tableaux". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AJ,..., Proceedings (1 gennaio 2008). http://dx.doi.org/10.46298/dmtcs.3615.
Testo completoAbstract (sommario):
International audience We give another construction of a permutation tableau from its corresponding permutation and construct a permutation-preserving bijection between $1$-hinge and $0$-hinge tableaux. We also consider certain alignment and crossing statistics on permutation tableaux that have previously been shown to be equidistributed by mapping them to patterns in related permutations. We give two direct maps on tableaux that prove the equidistribution of those statistics by exchanging some statistics and preserving the rest. Finally, we enumerate some sets of permutations that are restricted both by pattern avoidance and by certain parameters of their associated permutation tableaux. Nous donnons une nouvelle construction d'un tableau de permutation à partir de la permutation correspondante. Nous construisons ensuite une permutation qui préserve la bijection entre un tableau charnière $1$ et tableau charnière $0$. Nous considérons également certaines statistiques sur les alignements et croisements dans les tableaux de permutations. L'équidistribution de ces données statistiques est connue, et donnée par le biais d'une application très compliquée associant les alignements et croisements des tableaux a des motifs des permutations correspondantes. Nous construisons deux involutions définies sur les tableaux qui démontrent l'équidistribution des statistiques en échangeant certaines données tout en préservant d'autres. Enfin, nous dénombrons quelques ensembles de permutations définis non seulement par l'absence de certains motifs mais aussi par certains paramètres issus des tableaux de permutations.
37
Brignall, Robert. "Labelled Well-Quasi-Order in Juxtapositions of Permutation Classes". Electronic Journal of Combinatorics 31, n. 2 (19 aprile 2024). http://dx.doi.org/10.37236/12655.
Testo completoAbstract (sommario):
The juxtaposition of permutation classes $\mathcal{C}$ and $\mathcal{D}$ is the class of all permutations formed by concatenations $\sigma\tau$, such that $\sigma$ is order isomorphic to a permutation in $\mathcal{C}$, and $\tau$ to a permutation in $\mathcal{D}$.
We give simple necessary and sufficient conditions on the classes $\mathcal{C}$ and $\mathcal{D}$ for their juxtaposition to be labelled well-quasi-ordered (lwqo): namely that both $\mathcal{C}$ and $\mathcal{D}$ must themselves be lwqo, and at most one of $\mathcal{C}$ or $\mathcal{D}$ can contain arbitrarily long zigzag permutations. We also show that every class without long zigzag permutations has a growth rate which must be integral.
38
Cho, Soojin, e Kyoungsuk Park. "Alignments, crossings, cycles, inversions, and weak Bruhat order in permutation tableaux of type $B$". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (1 gennaio 2015). http://dx.doi.org/10.46298/dmtcs.2484.
Testo completoAbstract (sommario):
International audience Alignments, crossings and inversions of signed permutations are realized in the corresponding permutation tableaux of type $B$, and the cycles of signed permutations are understood in the corresponding bare tableaux of type $B$. We find the relation between the number of alignments, crossings and other statistics of signed permutations, and also characterize the covering relation in weak Bruhat order on Coxeter system of type $B$ in terms of permutation tableaux of type $B$. De nombreuses statistiques importantes des permutations signées sont réalisées dans les tableaux de permutations ou ”bare” tableaux de type $B$ correspondants : les alignements, croisements et inversions des permutations signées sont réalisés dans les tableaux de permutations de type $B$ correspondants, et les cycles des permutations signées sont comprises dans les ”bare” tableaux de type $B$ correspondants. Cela nous mène à relier le nombre d’alignements et de croisements avec d’autres statistiques des permutations signées, et aussi de caractériser la relation de couverture dans l’ordre de Bruhat faible sur des systèmes de Coxeter de type $B$ en termes de tableaux de permutations de type $B$.
39
Kurečka, Martin. "Lower bound on the size of a quasirandom forcing set of permutations". Combinatorics, Probability and Computing, 27 luglio 2021, 1–16. http://dx.doi.org/10.1017/s0963548321000298.
Testo completoAbstract (sommario):
Abstract A set S of permutations is forcing if for any sequence $\{\Pi_i\}_{i \in \mathbb{N}}$ of permutations where the density $d(\pi,\Pi_i)$ converges to $\frac{1}{|\pi|!}$ for every permutation $\pi \in S$ , it holds that $\{\Pi_i\}_{i \in \mathbb{N}}$ is quasirandom. Graham asked whether there exists an integer k such that the set of all permutations of order k is forcing; this has been shown to be true for any $k\ge 4$ . In particular, the set of all 24 permutations of order 4 is forcing. We provide the first non-trivial lower bound on the size of a forcing set of permutations: every forcing set of permutations (with arbitrary orders) contains at least four permutations.
40
Blitvić, Natasha. "SIF Permutations and Chord-Connected Permutations". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AT,..., Proceedings (1 gennaio 2014). http://dx.doi.org/10.46298/dmtcs.2443.
Testo completoAbstract (sommario):
International audience A <i>stabilized-interval-free </i> (SIF) permutation on [n], introduced by Callan, is a permutation that does not stabilize any proper interval of [n]. Such permutations are known to be the irreducibles in the decomposition of permutations along non-crossing partitions. That is, if $s_n$ denotes the number of SIF permutations on [n], $S(z)=1+\sum_{n\geq1} s_n z^n$, and $F(z)=1+\sum_{n\geq1} n! z^n$, then $F(z)= S(zF(z))$. This article presents, in turn, a decomposition of SIF permutations along non-crossing partitions. Specifically, by working with a convenient diagrammatic representation, given in terms of perfect matchings on alternating binary strings, we arrive at the \emphchord-connected permutations on [n], counted by $\{c_n\}_{n\geq1}$, whose generating function satisfies $S(z)= C(zS(z))$. The expressions at hand have immediate probabilistic interpretations, via the celebrated <i>moment-cumulant formula </i>of Speicher, in the context of the <i>free probability theory </i>of Voiculescu. The probability distributions that appear are the exponential and the complex Gaussian.
41
Cornwell, Christopher, e Nathan McNew. "Unknotted Cycles". Electronic Journal of Combinatorics 29, n. 3 (9 settembre 2022). http://dx.doi.org/10.37236/11016.
Testo completoAbstract (sommario):
Noting that cycle diagrams of permutations visually resemble grid diagrams used to depict knots and links in topology, we consider the knot (or link) obtained from the cycle diagram of a permutation. We show that the permutations which correspond in this way to an unknot are enumerated by the Schröder numbers, and also enumerate the permutations corresponding to an unlink. The proof uses Bennequin's inequality.
42
Claesson, Anders, Vít Jelínek, Eva Jelínková e Sergey Kitaev. "Pattern avoidance in partial permutations (extended abstract)". Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AN,..., Proceedings (1 gennaio 2010). http://dx.doi.org/10.46298/dmtcs.2818.
Testo completoAbstract (sommario):
International audience Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A $\textit{partial permutation of length n with k holes}$ is a sequence of symbols $\pi = \pi_1 \pi_2 \cdots \pi_n$ in which each of the symbols from the set $\{1,2,\ldots,n-k\}$ appears exactly once, while the remaining $k$ symbols of $\pi$ are "holes''. We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length $k$ correspond to a Wilf-type equivalence class with respect to partial permutations with $(k-2)$ holes. Lastly, we enumerate the partial permutations of length $n$ with $k$ holes avoiding a given pattern of length at most four, for each $n \geq k \geq 1$. Nous introduisons un concept de permutations partielles. $\textit{Une permutation partielle de longueur n avec k trous}$ est une suite finie de symboles $\pi = \pi_1 \pi_2 \cdots \pi_n$ dans laquelle chaque nombre de l'ensemble $\{1,2,\ldots,n-k\}$ apparaît précisément une fois, tandis que les $k$ autres symboles de $\pi$ sont des "trous''. Nous introduisons l'étude des permutations partielles à motifs exclus et nous montrons que la plupart des résultats sur l'équivalence de Wilf peuvent être généralisés aux permutations partielles avec un nombre arbitraire de trous. De plus, nous montrons que les permutations de Baxter d'une longueur donnée $k$ forment une classe d'équivalence du type Wilf par rapport aux permutations partielles avec $(k-2)$ trous. Enfin, nous présentons l'énumération des permutations partielles de longueur $n$ avec $k$ trous qui évitent un motif de longueur $\ell \leq 4$, pour chaque $n \geq k \geq 1$.
43
Adam Kabela, Daniel Král', Jonathan A. Noel e Théo Pierron. "Density Maximizers of Layered Permutations". Electronic Journal of Combinatorics 29, n. 3 (9 settembre 2022). http://dx.doi.org/10.37236/10781.
Testo completoAbstract (sommario):
A permutation is layered if it contains neither $231$ nor $312$ as a pattern.It is known that, if $\sigma$ is a layered permutation, then the density of $\sigma$ in a permutation of order $n$ is maximized by a layered permutation. Albert, Atkinson, Handley, Holton and Stromquist [Electron. J. Combin. 9 (2002), #R5] claimed that the density of a layered permutation with layers of sizes $(a,1,b)$ where $a,b\geq2$ is asymptotically maximized by layered permutations with a bounded number of layers, and conjectured that the same holds if a layered permutation has no consecutive layers of size one and its first and last layers are of size at least two.
We show that, if $\sigma$ is a layered permutation whose first layer is sufficiently large and second layer is of size one, then the number of layers tends to infinity in every sequence of layered permutations asymptotically maximizing the density of $\sigma$. This disproves the conjecture and the claim of Albert et al. We complement this result by giving sufficient conditions on a layered permutation to have asymptotic or exact maximizers with a bounded number of layers.
44
Lipson, Mark. "Completion of the Wilf-Classification of 3-5 Pairs Using Generating Trees". Electronic Journal of Combinatorics 13, n. 1 (4 aprile 2006). http://dx.doi.org/10.37236/1057.
Testo completoAbstract (sommario):
A permutation $\pi$ is said to avoid the permutation $\tau$ if no subsequence in $\pi$ has the same order relations as $\tau$. Two sets of permutations $\Pi_1$ and $\Pi_2$ are Wilf-equivalent if, for all $n$, the number of permutations of length $n$ avoiding all of the permutations in $\Pi_1$ equals the number of permutations of length $n$ avoiding all of the permutations in $\Pi_2$. Using generating trees, we complete the problem of finding all Wilf-equivalences among pairs of permutations of which one has length 3 and the other has length 5 by proving that $\{123,32541\}$ is Wilf-equivalent to $\{123,43251\}$ and that $\{123,42513\}$ is Wilf-equivalent to $\{132, 34215\}$. In addition, we provide generating trees for fourteen other pairs, among which there are two examples of pairs that give rise to isomorphic generating trees.
45
Eriksson, Kimmo, e Svante Linusson. "The size of Fulton's essential set". Electronic Journal of Combinatorics 2, n. 1 (3 aprile 1995). http://dx.doi.org/10.37236/1200.
Testo completoAbstract (sommario):
The essential set of a permutation was defined by Fulton as the set of southeast corners of the diagram of the permutation. In this paper we determine explicit formulas for the average size of the essential set in the two cases of arbitrary permutations in $S_n$ and $321$-avoiding permutations in $S_n$. Vexillary permutations are discussed too. We also prove that the generalized Catalan numbers ${r+k-1\choose n}-{r+k-1\choose n-2}$ count $r\times k$-matrices dotted with $n$ dots that are extendable to $321$-avoiding permutation matrices.
46
Claesson, Anders, Vít Jelínek, Eva Jelínková e Sergey Kitaev. "Pattern Avoidance in Partial Permutations". Electronic Journal of Combinatorics 18, n. 1 (26 gennaio 2011). http://dx.doi.org/10.37236/512.
Testo completoAbstract (sommario):
Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A partial permutation of length $n$ with $k$ holes is a sequence of symbols $\pi=\pi_1\pi_2\dotsb\pi_n$ in which each of the symbols from the set $\{1,2,\dotsc,n-k\}$ appears exactly once, while the remaining $k$ symbols of $\pi$ are "holes". We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length $k$ correspond to a Wilf-type equivalence class with respect to partial permutations with $(k-2)$ holes. Lastly, we enumerate the partial permutations of length $n$ with $k$ holes avoiding a given pattern of length at most four, for each $n\ge k\ge 1$.
47
Pan, Ran, e Jeffrey B. Remmel. "Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays". Discrete Mathematics & Theoretical Computer Science Vol. 18 no. 2, Permutation..., Permutation Patterns (20 maggio 2016). http://dx.doi.org/10.46298/dmtcs.1315.
Testo completoAbstract (sommario):
A permutation $\tau$ in the symmetric group $S_j$ is minimally overlapping if any two consecutive occurrences of $\tau$ in a permutation $\sigma$ can share at most one element. B\'ona \cite{B} showed that the proportion of minimal overlapping patterns in $S_j$ is at least $3 -e$. Given a permutation $\sigma$, we let $\text{Des}(\sigma)$ denote the set of descents of $\sigma$. We study the class of permutations $\sigma \in S_{kn}$ whose descent set is contained in the set $\{k,2k, \ldots (n-1)k\}$. For example, up-down permutations in $S_{2n}$ are the set of permutations whose descent equal $\sigma$ such that $\text{Des}(\sigma) = \{2,4, \ldots, 2n-2\}$. There are natural analogues of the minimal overlapping permutations for such classes of permutations and we study the proportion of minimal overlapping patterns for each such class. We show that the proportion of minimal overlapping permutations in such classes approaches $1$ as $k$ goes to infinity. We also study the proportion of minimal overlapping patterns in standard Young tableaux of shape $(n^k)$. Comment: Accepted by Discrete Math and Theoretical Computer Science. Thank referees' for their suggestions
48
Vatter, Vincent. "An Erd\H{o}s--Hajnal analogue for permutation classes". Discrete Mathematics & Theoretical Computer Science Vol. 18 no. 2, Permutation..., Permutation Patterns (24 marzo 2016). http://dx.doi.org/10.46298/dmtcs.1328.
Testo completoAbstract (sommario):
Let $\mathcal{C}$ be a permutation class that does not contain all layered permutations or all colayered permutations. We prove that there is a constant $c$ such that every permutation in $\mathcal{C}$ of length $n$ contains a monotone subsequence of length $cn$.
49
Dudek, Andrzej, Jarosław Grytczuk e Andrzej Ruciński. "Variations on Twins in Permutations". Electronic Journal of Combinatorics 28, n. 3 (16 luglio 2021). http://dx.doi.org/10.37236/9734.
Testo completoAbstract (sommario):
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 Gawron 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, Bukh and Rudenko 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$.
50
Linman, Julie, e Michael Pinsker. "Permutations on the Random Permutation". Electronic Journal of Combinatorics 22, n. 2 (22 giugno 2015). http://dx.doi.org/10.37236/4910.
Testo completoAbstract (sommario):
The random permutation is the Fraïssé limit of the class of finite structures with two linear orders. Answering a problem stated by Peter Cameron in 2002, we use a recent Ramsey-theoretic technique to show that there exist precisely 39 closed supergroups of the automorphism group of the random permutation, and thereby expose all symmetries of this structure. Equivalently, we classify all structures which have a first-order definition in the random permutation.