Jay Pantone

John Wesley Young Research Instructor
Dartmouth College

jaypantone@dartmouth.edu


Experimental Analysis of Combinatorial Sequences

Georgia Tech Combinatorics Seminar - Atlanta, GA (February 24, 2017)

In enumerative combinatorics, it is quite common to have in hand a number of known initial terms of a combinatorial sequence whose behavior you'd like to study. In this talk we'll describe two techniques that can be used to shed some light on the nature of a sequence using only some known initial terms. While these methods are, on the face of it, experimental, they often lead to rigorous proofs. As we talk about these two techniques -- automated conjecturing of generating functions, and the method of differential approximation -- we'll exhibit their usefulness through a variety of combinatorial topics, including matchings, permutation classes, and inversion sequences.

On the Growth of Merges and Staircases of Permutation Classes

AMS Section Meeting - Minneapolis, MN (October 29, 2015)

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.

Sorting with C-machines: Enumerative and Analytic Aspects (Video Recording)

Slides

BIRS Workshop in Analytic and Probabilistic Combinatorics - Banff, Canada (October 24, 2016)

\(\mathcal{C}\)-machines are a class of sorting machines that naturally generalize stacks and queues. A \(\mathcal{C}\)-machine is a container that is allowed to hold permutations from the class \(\mathcal{C}\) into which entries can be pushed and out of which entries may be popped. With this notation, a stack is the \(\operatorname{Av}(12)\)-machine. This structural description allows us to find many terms in the counting sequences of three permutation classes of interest, but despite these numerous initial terms we are unable to find the exact or asymptotic behavior of their generating functions. In this talk I'll describe what we do know, what we don't know, and what experimental methods tell us we might one day know.

Approximate Asymptotic Analysis of Combinatorial Sequences (Video Recording)

Rutgers Experimental Mathematics Seminar - Piscataway, NJ (June 28, 2016)

In enumerative combinatorics, it is quite common to have in hand a number of known initial terms of a combinatorial sequence whose behavior you'd like to study. In this talk we'll describe the Method of Differential Approximants, a technique that can be used to shed some light on the nature of a sequence using only some known initial terms. While this method is, on the face of it, experimental, it often leads the way to rigorous proofs. We'll exhibit the usefulness of this method through a variety of combinatorial topics, including chord diagrams, permutation classes, and inversion sequences.

Growth Rates of Permutation Classes

Permutation Patterns 2016 - Washington, D.C. (June 28, 2016)

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.

Exact and Asymptotic Analysis of Combinatorial Sequences

[requires Acrobat Reader for video]
Dartmouth Mathematics Colloquium - Hanover, NH (May 12, 2016)

In enumerative combinatorics, it is quite common to have in hand a number of known initial terms of a combinatorial sequence whose behavior you'd like to study. In this talk we'll describe two techniques that can be used to shed some light on the nature of a sequence using only some known initial terms. While these methods are, on the face of it, experimental, they often lead to rigorous proofs. As we talk about these two techniques – automated conjecturing of generating functions, and the method of differential approximants – we'll exhibit their usefulness through a variety of combinatorial topics, including chord diagrams, permutation classes, and inversion sequences.

The Method of Differential Approximants (extended version)

Schloss Dagstuhl - Warden, Germany (February 18, 2016)

For decades, the method of differential approximants has been applied to the study of statistical mechanics to estimate the singularity structure of the generating function of a sequence of positive integers, using only a finite number of initial terms of the generating function. While all such approximations are of course only non-rigorous estimates, experience shows these estimates to be remarkably accurate.

Differential approximants can be extremely useful to combinatorialists. We provide several examples of combinatorial sequences for which no generating function is known or conjectured yet the method of differential approximants provides a very accurate approximation of the asymptotic behavior of the sequence. We then describe several extensions to the method that are in progress.

The Method of Differential Approximants

AMS Section Meeting - Chicago, IL (October 3, 2015)

When you’re unable to find the generating function for a combinatorial sequence, the next best thing is to compute many initial terms. Recently, we’ve found thousands of initial terms of four permutation classes for which we cannot derive (or even guess) the generating functions.

The Method of Differential Approximants allows one to predict the asymptotic behavior of a combinatorial sequence using only known initial terms. While this technique is well-known in the field of statistical mechanics, we have not seen it used very often in combinatorics. After explaining how the method works, we’ll use it to estimate the asymptotic behavior of our four mysterious permutation classes.

Sorting with \(\mathcal{C}\)-Machines

University of Melbourne Statistical Mechanics Seminar - Melbourne, Australia (July 27, 2015)

In The Art of Computer Science, Knuth asks the reader to prove that the permutations that can be sorted by a stack are those that avoid the pattern 231. Sorting machines such as stacks, queues, and deques have all been studied in the context of permutation patterns, yielding many exciting results.

In this talk, we construct a generalized sorting machine called a "C-machine" that we then use to study many interesting classes of pattern-avoiding permutations. In the process, we use both classic combinatorial techniques as well as tools from statistical mechanics in an effort to understand the enumeration of these permutation classes.

Equivalence of Words in the Generalized Factor Order

AMS Section Meeting - Washington, D.C. (March 7, 2015)

The generalized factor order has been studied frequently in recent years. In this talk, we survey results on enumerative equivalence among words in the generalized factor order over the positive integers, including progress toward proving the Rearrangement Conjecture of Kitaev, Liese, Remmel, and Sagan. We further provide new conditions guaranteeing equivalence of certain rearrangements.

Equipopularity in the Separable Permutations

AMS Section Meeting - Eau Claire, WI (September 20, 2014)

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 equipopularity classes in the set of separable permutations. In particular, we show that the equipopularity classes of length \(n\) patterns are in bijection with the partitions of the integer \(n\).

Pattern-Avoiding Involutions

Permutation Patterns 2014 - Johnson City, TN (July 7, 2014)

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.

The Rearrangement Conjecture (poster)

FPSAC 2014 - Chicago, IL (June 29, 2014)

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.

Checker Jumping, Coin Counting, and Cap Throwing: Why Generating Functions are Magic!

UF Graduate Student Colloquium - Gainesville, FL (August 28, 2013)

Generating functions can be extremely useful in combinatorics, number theory, probability, algebra, and many other fields. In this talk, we'll start with the definition of a generating function and move on to the techniques which make them so powerful. Then, we'll finish with a look at three quick applications of generating functions to common combinatorial problems. The material will be accessible to anyone who has taken Calc 2.

Enumeration of Av(3124,4312)

Permutation Patterns 2013 - Paris, France (July 2, 2013)

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.

The History of π (in expository form)

UF Pi Mu Epsilon Seminar - Gainesville, FL (March 14, 2012)

In this talk, we'll give a chronological history of the development of our modern notion of the mathematical constant Pi. We'll start with the ancient peoples (Egyptians, Babylonians) and our best guesses at how they found their results. We'll progress though Medieval to Modern Europe with the contributions of Viete, Newton, Euler, Gauss, Lambert, and more. Lastly, we'll talk about efforts to find digits of Pi computationally, including some modern algorithms and the records set using them.