Superpattern

In the mathematical study of permutations and permutation patterns, a superpattern 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]

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 ith element of the pattern for s should be less than the jthe element if and only if the ith element of s is less than the jth 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:

Subsequence Pattern
253 132
251 231
254 132
231 231
234 123
214 213
531 321
534 312
514 312
314 213

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

Richard 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 remains the strongest known lower bound on the length of superpatterns.

However, the upper bound of k2 on superpattern length proven by Arratia is not tight. After intermediate improvements,[3] the best current upper bound on the size of a superpattern is by Alison Miller (2009), who proved that, for every k, there exists a k-superpattern of length at most k(k + 1)/2.[4]

Eriksson et al. conjectured that the true length of the shortest k-superpattern is within lower-order terms of k2/2, matched on one side by Miller's upper bound.[3][4] However, this is in contradiction with a conjecture of Richard Arratia that the k2/e2 lower bound is tight,[2] and also contradicts a conjecture of Noga 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.[5] 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 Noga Alon the conjecture that, for any ε > 0, with high probability, random permutations of length k2/(4 −ε) will be k-superpatterns.

See also

References

  1. ↑ Bóna, Miklós (2012), Combinatorics of Permutations, Discrete Mathematics and Its Applications, 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, MR 1710623.
  3. 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.
  4. 1 2 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.
  5. ↑ Godbole, Anant; Liendo, Martha (2013), Waiting time distribution for the emergence of superpatterns, arXiv:1302.4668Freely accessible.
This article is issued from Wikipedia - version of the 10/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.