Some results on superpatterns for preferential arrangements

DOI10.1016/J.AAM.2016.08.004MaRDI QIDQ730640zbMATH OpenOpenAlexFDO

Authors Yonah Biers-Ariel, Yiguang Zhang, Anant P. Godbole

Publication date 28 December 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationsuperpatterncomplete wordspreferential arrangement

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Extremal combinatorics (05D99)

Abstract: A {it superpattern} is a string of characters of length $n$ that contains as a subsequence, and in a sense that depends on the context, all the smaller strings of length $k$ in a certain class. We prove structural and probabilistic results on superpatterns for {em preferential arrangements}, including (i) a theorem that demonstrates that a string is a superpattern for all preferential arrangements if and only if it is a superpattern for all permutations; and (ii) a result that is reminiscent of a still unresolved conjecture of Alon on the smallest permutation on $[n]$ that contains all $k$-permutations with high probability.

Recommendations

• Preferential arrangement superpatterns
• Simple permutations, alternating permutations, and the superpatterns that contain them.
• Note on superpatterns
• Asymptotic bounds for permutations containing many different patterns
• Lower bounds for superpatterns and universal sequences

Cites work

• scientific article; zbMATH DE number 4217776 (Why is no real title available?)
• A construction of short sequences containing all permutations of a set as subsequences
• A lower bound on the length of a sequence containing all permutations as subsequences
• Analytic combinatorics
• Dense packing of patterns in a permutation
• Omnibus sequences, coupon collection, and missing word counts
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Packing patterns into words
• Some New Aspects of the Coupon Collector's Problem
• Waiting time distribution for the emergence of superpatterns

Cited in

(4)

• Simple permutations, alternating permutations, and the superpatterns that contain them.
• Note on superpatterns
• An asymptotically tight lower bound for superpatterns with small alphabets
• Preferential arrangement superpatterns

This page was built for publication: Some results on superpatterns for preferential arrangements

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