Lower bounds for superpatterns and universal sequences

Zachary Chroman, Matthew Kwan, Mihir SinghalJ. Comb. Theory a 2021 · DOI

TL;DR

This paper disproves a long-standing conjecture about the minimum length of a "superpattern" (a permutation containing all smaller permutations as subsequences). The authors introduce a novel encoding scheme that improves the trivial lower bound by a constant factor, showing that superpatterns must be longer than previously thought. This work has implications for understanding the structure of permutations and related combinatorial objects.

What Problem Does This Paper Address?

The paper tackles the problem of finding the shortest possible permutation that contains every permutation of a given length $k$ as a subsequence. Such a permutation is called a $k$-superpattern. A simple counting argument shows that a permutation of length $n$ can have at most $\binom{n}{k}$ distinct subsequences of length $k$. Since there are $k!$ possible permutations of length $k$, a $k$-superpattern must satisfy $\binom{n}{k} \ge k!$. This leads to a trivial lower bound of $n \ge (1/e^2 + o(1))k^2$. Arratia conjectured that this bound is essentially tight, meaning $k$-superpatterns of length close to $(1/e^2 + o(1))k^2$ exist. However, this paper shows that this conjecture is false, and the trivial bound can be improved by a constant factor.

Methods

The core of the paper's contribution lies in developing a new, more efficient encoding scheme for the patterns present in a permutation $\sigma$. Instead of simply encoding the positions of the elements of a pattern, the authors devise a method that selectively encodes either the position or the relative value of an element based on the "width" (the difference between adjacent indices) around it. If the width is large, specifying the relative value is cheaper than specifying the exact position. This "information-theoretic" approach allows them to bound the number of distinct patterns more effectively than the naive counting argument. The proof relies on a probabilistic lemma about "large gaps" in random sets, which is then used to show that the new encoding scheme outputs significantly fewer distinct values than the trivial bound suggests.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Disproving Arratia's Conjecture: The paper demonstrates that the trivial lower bound for $k$-superpatterns is not asymptotically tight, meaning superpatterns must be longer than previously believed.
  • Efficient Encoding as a Tool: The authors introduce a novel encoding scheme that leverages the structure of permutation patterns (specifically, the "widths" between indices) to reduce the number of possible patterns that can be encoded. This is a significant methodological advance.
  • "Information Cost" of Encoding: The core idea is that specifying an element's position can be "expensive" if it falls within a large gap. The new encoding intelligently chooses to encode relative values when this cost is high, leading to a tighter bound.
  • Probabilistic Lemma for Gaps: A key technical component is a lemma showing that in random sets, large gaps are not excessively rare, which is crucial for the encoding scheme to be effective.

Key Results

The paper proves Theorem 1.1, which states that any permutation $\sigma \in S_n$ with $n < (1.000076/e^2)k^2$ contains only $o(k!)$ distinct patterns of length $k$. This directly implies that there is no $k$-superpattern of length less than $(1.000076/e^2)k^2$. This improves the trivial lower bound by a constant factor. The paper also extends this result to $r$-ary sequences, improving bounds on $k$-universal sequences.

Limitations and Future Work

The authors acknowledge that their constant factor improvement is modest and that fully optimizing the constant would be very complicated. They suggest that their method might not be directly applicable to graph universality problems due to fundamental differences in information content. Future work could involve exploring more sophisticated encoding schemes, investigating exact large deviation bounds for widths, and applying these ideas to other universality-type problems in combinatorics. The paper also raises questions about the exact minimal length of a $k$-superpattern and the behavior of random permutations in containing almost all $k$-patterns.

Summary updated

BibTeX
@article{chroman2021lower,
  author = {Zachary Chroman and Matthew Kwan and Mihir Singhal},
  title = {{Lower bounds for superpatterns and universal sequences}},
  journal = {J. Comb. Theory a},
  year = {2021},
  doi = {10.1016/j.jcta.2021.105467},
}

Loading related content...

Figure