Publications

Containing All Permutations

Michael Engen and Vincent Vatter
A mathematical figure depicting the plot of a universal permutation of size 13 on the Cartesian plane.
Abstract: Numerous versions of the question “what is the shortest object containing all permutations of a given length?” have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in 1993; and by Arratia in 1999. The large variety of questions of this form, which have previously been considered in isolation, stands in stark contrast to the dearth of answers. We survey and synthesize these questions and their partial answers, introduce infinitely more related questions, and then establish an improved upper bound for one of these questions.

Stack-sorting, set partitions, and Lasalle's sequence

Colin Defant, Michael Engen, and Jordan A. Miller
A mathematical figure depicting the plot of a permutation together with its valid hook configuration.
Abstract: We exhibit a bijection between recently-introduced combinatorial objects known as valid hook configurations and certain weighted set partitions. When restricting our attention to set partitions that are matchings, we obtain three new combinatorial interpretations of Lassalle's sequence. One of these interpretations involves permutations that have exactly one preimage under the (West) stack-sorting map. We prove that the sequences obtained by counting these permutations according to their first entries are symmetric, and we conjecture that they are log-concave. We also obtain new recurrence relations involving Lassalle's sequence and the sequence that enumerates valid hook configurations. We end with several suggestions for future work.

On the dimension of downsets of integer partitions and compositions

Michael Engen and Vincent Vatter
A mathematical figure depicting the Hasse diagram of a crown of order-dimension 3. The elements of the partial order are skyline diagrams.
Abstract: We characterize the downsets of integer partitions (ordered by containment of Ferrers diagrams) and compositions (ordered by the generalized subword order) which have finite dimension in the sense of Dushnik and Miller. In the case of partitions, while the set of all partitions has infinite dimension, we show that every proper downset of partitions has finite dimension. For compositions we identify four minimal downsets of infinite dimension and establish that every downset which does not contain one of these four has finite dimension.

A Counterexample Regarding Labelled Well-Quasi-Ordering

Robert Brignall, Michael Engen, and Vincent Vatter
A mathematical figure depicting the plot of a Widdershins permutation. The points of the plot form a counterclockwise outward spiral, which is drawn.
Abstract: Korpelainen, Lozin, and Razgon conjectured that a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by only finitely many minimal forbidden induced subgraphs is labelled well-quasi-ordered, a notion stronger than that of n-well-quasi-order introduced by Pouzet in the 1970s. We present a counterexample to this conjecture. In fact, we exhibit a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by finitely many minimal forbidden induced subgraphs yet is not 2-well-quasi-ordered. This counterexample is based on the widdershins spiral, which has received some study in the area of permutation patterns.

Universal Layered Permutations

Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter
A mathematical figure depicting the plot of a permutation with a number of labeled regions.
Abstract: We establish an exact formula for the length of the shortest permutation containing all layered permutations of length n, proving a conjecture of Gray.