Jay Pantone

Assistant Professor
Marquette University


Universal Layered Permutations

with Michael Albert, Michael Engen, and Vince Vatter

We establish an exact formula for the length of the shortest permutation containing all layered permutations of length n, proving a conjecture of Gray.

Staircases, dominoes, and the growth rate of 1324-avoiders (conference paper)

with David Bevan, Robert Brignall, and Andrew Elvey Price
Published in Electronic Notes in Discrete Mathematics.

We establish a lower bound of 10.271 for the growth rate of the permutations avoiding 1324, and an upper bound of 13.5. This is done by first finding the precise growth rate of a subclass whose enumeration is related to West-2-stack-sortable permutations, and then combining copies of this subclass in particular ways.

Shift Equivalence in the Generalized Factor Order

with Jennifer Fidler, Daniel Glasscock, Brian Miceli, and Min Xu

We provide a geometric condition that guarantees strong Wilf equivalence in the generalized factor order. This provides a powerful tool for proving specific and general Wilf equivalence results, and several such examples are given.

On the Growth of Merges and Staircases of Permutation Classes

with Michael Albert and Vincent Vatter

There is a well-known upper bound on the growth rate of the merge of two permutation classes. Curiously, there is no known merge for which this bound is not achieved. Using staircases of permutation classes, we provide sufficient conditions for this upper bound to be achieved. In particular, our results apply to all merges of principal permutation classes. We end by demonstrating how our techniques can be used to reprove a result of Bóna.

Is the Full Susceptibility of the Square-Lattice Ising Model a Differentially Algebraic Function?

with Tony Guttmann, Iwan Jensen, and Jean-Marie Maillard.
Published in the Journal of Physics, A.

We study the class of non-holonomic power series with integer coefficients that reduce, modulo primes, or powers of primes, to algebraic functions. In particular we try to determine whether the susceptibility of the square-lattice Ising model belongs to this class, and more broadly whether the susceptibility is a solution of a differentially algebraic equation.

The Asymptotic Number of Simple Singular Vector Tuples of a Cubical Tensor

To appear in the Online Journal of Analytic Combinatorics.

S. Ekhad and D. Zeilberger recently proved that the multivariate generating function for the number of simple singular vector tuples of a generic \(m_1 \times \cdots \times m_d\) tensor has an elegant rational form involving elementary symmetric functions, and provided a partial conjecture for the asymptotic behavior of the cubical case \(m_1 = \cdots = m_d\). We prove this conjecture and further identify completely the dominant asymptotic term, including the multiplicative constant. Finally, we use the method of differential approximants to conjecture that the subdominant connective constant effect observed by Ekhad and Zeilberger for a particular case in fact occurs more generally.

Growth Rates of Permutation Classes: Categorization up to the Uncountability Threshold

with Vincent Vatter

In the antecedent paper to this it was established that there is an algebraic number \(\xi\approx 2.30522\) such that while there are uncountably many growth rates of permutation classes arbitrarily close to \(\xi\), there are only countably many less than \(\xi\). Here we provide a complete characterization of the growth rates less than \(\xi\). In particular, this classification establishes that \(\xi\) is the least accumulation point from above of growth rates and that all growth rates less than or equal to \(\xi\) are achieved by finitely based classes. A significant part of this classification is achieved via a reconstruction result for sum indecomposable permutations. We conclude by refuting a suggestion of Klazar, showing that \(\xi\) is an accumulation point from above of growth rates of finitely based permutation classes.

Pattern Avoidance in Forests of Binary Shrubs

with David Bevan, Derek Levin, Peter Nugent, Lara Pudwell, Manda Riehl and ML Tlachac
Published in Discrete Mathematics and Theoretical Computer Science.

We investigate pattern avoidance in permutations satisfying some additional restrictions. These are naturally considered in terms of avoiding patterns in linear extensions of certain forest-like partially ordered sets, which we call binary shrub forests. In this context, we enumerate forests avoiding patterns of length three. In four of the five non-equivalent cases, we present explicit enumerations by exhibiting bijections with certain lattice paths bounded above by the line \(y=\ell x\), for some \(\ell\in\mathbb{Q}^+\), one of these being the celebrated Duchon's club paths with \(\ell=2/3\). In the remaining case, we use the machinery of analytic combinatorics to determine the minimal polynomial of its generating function, and deduce its growth rate.

Generating Permutations with Restricted Containers

with Michael Albert, Cheyne Homberger, Nathaniel Shar, and Vincent Vatter
To appear in the Journal of Combinatorial Theory, Series A.

We investigate a generalization of stacks that we call \(\mathcal{C}\)-machines. We show how this viewpoint rapidly leads to functional equations for the classes of permutations that \(\mathcal{C}\)-machines generate, and how these systems of functional equations can frequently be solved by either the kernel method or, much more easily, by guessing and checking. General results about the rationality, algebraicity, and the existence of Wilfian formulas for some classes generated by \(\mathcal{C}\)-machines are given. We also draw attention to some relatively small permutation classes which, although we can generate thousands of terms of their enumerations, seem to not have D-finite generating functions.

Pattern-Avoiding Involutions: Exact and Asymptotic Enumeration

with Miklós Bóna, Cheyne Homberger, and Vincent Vatter
Published in the Australasian Journal of Combinatorics.

We consider the enumeration of pattern-avoiding involutions, focusing in particular on sets defined by avoiding a single pattern of length 4. We directly enumerate the involutions avoiding \(1342\) and the involutions avoiding \(2341\). As we demonstrate, the numerical data for these problems exhibits some surprising behavior. This strange behavior even provides some very unexpected data related to the number of \(1324\)-avoiding permutations.

Deflatability of Permutation Classes

with Michael Albert, Mike Atkinson, and Cheyne Homberger
Published in the Australasian Journal Combinatorics.

A permutation class is said to be deflatable if its simple permutations are contained within a proper subclass. Deflatable classes are often easier to describe, analyze, and enumerate than their non-deflatable counterparts. This paper presents theorems guaranteeing the non-deflatability of principal classes, constructs an infinite family of deflatable principal classes, and provides examples of each.

On Isomorphism Classes of Generalized Fibonacci Cubes

with Jernej Azarija, Sandi Klavžar, Jaehun Lee, and Yoomi Rho
Published in the European Journal of Combinatorics.

The generalized Fibonacci cube \(Q_d(f)\) is the subgraph of the \(d\)-cube \(Q_d\) induced on the set of all strings of length \(d\) that do not contain \(f\) as a substring. It is proved that if \(Q_d(f) \cong Q_d(f')\) then \(|f|=|f'|\). The key tool to prove this result is a result of Guibas and Odlyzko about the autocorrelation polynomial associated to a binary string. It is also proved that there exist pairs of strings \(f, f'\) such that \(Q_d(f) \cong Q_d(f')\), where \(|f| \ge \frac{2}{3}(d+1)\) and \(f'\) cannot be obtained from \(f\) by its reversal or binary complementation. Strings \(f\) and \(f'\) with \(|f|=|f'|=d-1\) for which \(Q_d(f) \cong Q_d(f')\) are characterized.

Two Examples of Unbalanced Wilf-Equivalence

with Alex Burstein
Published in the Journal of Combinatorics.

We prove that the set of patterns \(\{1324,3416725\}\) is Wilf-equivalent to the pattern \(1234\) and that the set of patterns \(\{2143,3142,246135\}\) is Wilf-equivalent to the set of patterns \(\{2413,3142\}\). These are the first known unbalanced Wilf-equivalences for classical patterns between finite sets of patterns.

Equipopularity Classes in the Separable Permutations

with Michael Albert and Cheyne Homberger
Published in the Electronic Journal of Combinatorics.

When two patterns occur equally often in a set of permutations, we say that these patterns are equipopular. Using both structural and analytic tools, we classify the equipopular patterns in the set of separable permutations. In particular, we show that the number of equipopularity classes for length \(n\) patterns in the separable permutations is equal to the number of partitions of the integer \(n-1\).

The Enumeration of Permutations Avoiding 3124 and 4312

Published in the Annals of Combinatorics.

We find the generating function for the class of all permutations that avoid the patterns \(3124\) and \(4312\) by showing that it is an inflation of the union of two geometric grid classes.

On the Rearrangement Conjecture for Generalized Factor Order over \(\mathbb{P}\).

with Vincent Vatter
Published in Discrete Mathematics and Theoretical Computer Science, FPSAC 2014 Proceedings.

The Rearrangement Conjecture states that if two words over \(\mathbb{P}\) are Wilf-equivalent in the factor order on \(\mathbb{P}^\ast\) then they are rearrangements of each other. We introduce the notion of strong Wilf-equivalence and prove that if two words over \(\mathbb{P}\) are strongly Wilf-equivalent then they are rearrangements of each other. We further conjecture that Wilf-equivalence implies strong Wilf-equivalence.