Supertrees (Q2181994)

Summary: A \(k\)-universal permutation, or \(k\)-superpermutation, is a permutation that contains all permutations of length \(k\) as patterns. The problem of finding the minimum length of a \(k\)-superpermutation has recently received significant attention in the field of permutation patterns. One can ask analogous questions for other classes of objects. In this paper, we study \(k\)-supertrees. For each \(d\geq 2\), we focus on two types of rooted plane trees called \(d\)-ary plane trees and \([d]\)-trees. Motivated by recent developments in the literature, we consider ``contiguous'' and ``noncontiguous'' notions of pattern containment for each type of tree. We obtain both upper and lower bounds on the minimum possible size of a \(k\)-supertree in three cases; in the fourth, we determine the minimum size exactly. One of our lower bounds makes use of a recent result of \textit{M. Albert} et al. [Electron. J. Comb. 25, No. 3, Research Paper P3.23, 5 p. (2018; Zbl 1393.05003)] on \(k\)-universal layered permutations.