Some results on superpatterns for preferential arrangements

DOI10.1016/J.AAM.2016.08.004zbMATH Open1352.05184arXiv1603.01736OpenAlexW2963867491MaRDI QIDQ730640FDOQ730640

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)

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.

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

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

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)

Cites Work

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

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)