Superpattern

Last updated

In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a k-superpattern contains all possible patterns of length k. [1]

Contents

Definitions and example

If π is a permutation of length n, represented as a sequence of the numbers from 1 to n in some order, and s = s1, s2, ..., sk is a subsequence of π of length k, then s corresponds to a unique pattern, a permutation of length k whose elements are in the same order as s. That is, for each pair i and j of indexes, the i-th element of the pattern for s should be less than the j-th element if and only if the i-th element of s is less than the j-th element. Equivalently, the pattern is order-isomorphic to the subsequence. For instance, if π is the permutation 25314, then it has ten subsequences of length three, forming the following patterns:

SubsequencePattern
253132
251231
254132
231231
234123
214213
531321
534312
514312
314213

A permutation π is called a k-superpattern if its patterns of length k include all of the length-k permutations. For instance, the length-3 patterns of 25314 include all six of the length-3 permutations, so 25314 is a 3-superpattern. No 3-superpattern can be shorter, because any two subsequences that form the two patterns 123 and 321 can only intersect in a single position, so five symbols are required just to cover these two patterns.

Length bounds

Arratia  ( 1999 ) introduced the problem of determining the length of the shortest possible k-superpattern. [2] He observed that there exists a superpattern of length k2 (given by the lexicographic ordering on the coordinate vectors of points in a square grid) and also observed that, for a superpattern of length n, it must be the case that it has at least as many subsequences as there are patterns. That is, it must be true that , from which it follows by Stirling's approximation that n ≥ k2/e2, where e ≈ 2.71828 is Euler's number. This lower bound was later improved very slightly by Chroman,Kwan,andSinghal ( 2021 ), who increased it to 1.000076k2/e2, [3] disproving Arratia's conjecture that the k2/e2 lower bound was tight. [2]

The upper bound of k2 on superpattern length proven by Arratia is not tight. After intermediate improvements, [4] Miller  ( 2009 ) proved that there is a k-superpattern of length at most k(k + 1)/2 for every k. [5] This bound was later improved by EngenandVatter ( 2021 ), who lowered it to ⌈(k2 + 1)/2⌉. [6]

Eriksson et al. conjectured that the true length of the shortest k-superpattern is asymptotic to k2/2. [4] However, this is in contradiction with a conjecture of Alon on random superpatterns described below.

Random superpatterns

Researchers have also studied the length needed for a sequence generated by a random process to become a superpattern. [7] Arratia (1999) observes that, because the longest increasing subsequence of a random permutation has length (with high probability) approximately 2√n, it follows that a random permutation must have length at least k2/4 to have high probability of being a k-superpattern: permutations shorter than this will likely not contain the identity pattern. [2] He attributes to Alon the conjecture that, for any ε > 0, with high probability, random permutations of length k2/(4 − ε) will be k-superpatterns.

See also

Related Research Articles

<span class="mw-page-title-main">Permutation</span> Mathematical version of an order change

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.

<span class="mw-page-title-main">Erdős–Ko–Rado theorem</span> Upper bound on intersecting set families

In mathematics, the Erdős–Ko–Rado theorem limits the number of sets in a family of sets for which every two sets have at least one element in common. Paul Erdős, Chao Ko, and Richard Rado proved the theorem in 1938, but did not publish it until 1961. It is part of the field of combinatorics, and one of the central results of extremal set theory.

In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky.

In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique. The longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time where denotes the length of the input sequence.

The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is singly exponential. It was proved by Adam Marcus and Gábor Tardos (2004) and is no longer a conjecture. Marcus and Tardos actually proved a different conjecture, due to Zoltán Füredi and Péter Hajnal (1992), which had been shown to imply the Stanley–Wilf conjecture by Klazar (2000).

<span class="mw-page-title-main">Cartesian tree</span> Binary tree derived from a sequence of numbers

In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ.

In the study of permutation patterns, there has been considerable interest in enumerating specific permutation classes, especially those with relatively few basis elements. This area of study has turned up unexpected instances of Wilf equivalence, where two seemingly-unrelated permutation classes have the same numbers of permutations of each length.

A Gilbreath shuffle is a way to shuffle a deck of cards, named after mathematician Norman Gilbreath. Gilbreath's principle describes the properties of a deck that are preserved by this type of shuffle, and a Gilbreath permutation is a permutation that can be formed by a Gilbreath shuffle.

In mathematics and computer science, a stack-sortable permutation is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees.

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible.

Richard Alejandro Arratia is a mathematician noted for his work in combinatorics and probability theory.

In the study of permutations and permutation patterns, a permutation class is a set of permutations for which every pattern within a permutation in is also in . In other words, a permutation class is a hereditary property of permutations, or a downset in the permutation pattern order. A permutation class may also be known as a pattern class, closed class, or simply class of permutations.

In mathematics, the Chvátal–Sankoff constants are mathematical constants that describe the lengths of longest common subsequences of random strings. Although the existence of these constants has been proven, their exact values are unknown. They are named after Václav Chvátal and David Sankoff, who began investigating them in the mid-1970s.

<span class="mw-page-title-main">Planted clique</span> Complete subgraph added to a random graph

In computational complexity theory, a planted clique or hidden clique in an undirected graph is a clique formed from another graph by selecting a subset of vertices and adding edges between each pair of vertices in the subset. The planted clique problem is the algorithmic problem of distinguishing random graphs from graphs that have a planted clique. This is a variation of the clique problem; it may be solved in quasi-polynomial time but is conjectured not to be solvable in polynomial time for intermediate values of the clique size. The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption.

In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations.

In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However, there are other algorithms that use fewer comparisons.

<span class="mw-page-title-main">Affine symmetric group</span> Mathematical structure

The affine symmetric groups are a family of mathematical structures that describe the symmetries of the number line and the regular triangular tiling of the plane, as well as related higher-dimensional objects. In addition to this geometric description, the affine symmetric groups may be defined in other ways: as collections of permutations (rearrangements) of the integers that are periodic in a certain sense, or in purely algebraic terms as a group with certain generators and relations. They are studied in combinatorics and representation theory.

Hunter Snevily (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.

The Baik–Deift–Johansson theorem is a result from probabilistic combinatorics. It deals with the subsequences of a randomly uniformly drawn permutation from the set . The theorem makes a statement about the distribution of the length of the longest increasing subsequence in the limit. The theorem was influential in probability theory since it connected the KPZ-universality with the theory of random matrices.

References

  1. ↑ Bóna, Miklós (2012), Combinatorics of Permutations, Discrete Mathematics and Its Applications, vol. 72 (2nd ed.), CRC Press, p. 227, ISBN   9781439850510 .
  2. 1 2 3 Arratia, Richard (1999), "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics , 6: N1, doi: 10.37236/1477 , MR   1710623
  3. ↑ Chroman, Zachary; Kwan, Matthew; Singhal, Mihir (2021), "Lower bounds for superpatterns and universal sequences", Journal of Combinatorial Theory , Series A, 182, Paper No. 105467 (15 pp), arXiv: 2004.02375 , doi:10.1016/j.jcta.2021.105467, MR   4253319
  4. 1 2 Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (2007), "Dense packing of patterns in a permutation", Annals of Combinatorics , 11 (3–4): 459–470, doi:10.1007/s00026-007-0329-7, MR   2376116, S2CID   2021533
  5. ↑ Miller, Alison (2009), "Asymptotic bounds for permutations containing many different patterns", Journal of Combinatorial Theory , Series A, 116 (1): 92–108, doi:10.1016/j.jcta.2008.04.007
  6. ↑ Engen, Michael; Vatter, Vincent (2021), "Containing all permutations", American Mathematical Monthly , 128 (1): 4–24, arXiv: 1810.08252 , doi: 10.1080/00029890.2021.1835384
  7. ↑ Godbole, Anant P.; Liendo, Martha (2016), "Waiting time distribution for the emergence of superpatterns", Methodology and Computing in Applied Probability, 18 (2): 517–528, arXiv: 1302.4668 , doi:10.1007/s11009-015-9439-6, MR   3488590
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.