Jay Pantone

Assistant ProfessorMarquette University jay.pantone@marquette.edu

How Many Chord Diagrams Have No Short Chords?

Special Session on Enumerative Combinatorics, JMM 2019 - Baltimore, MD (January 19, 2019)

A chord diagram with $$n$$ chords is a set of $$2n$$ points in a line connected in $$n$$ pairs. Chord diagrams, sometimes called matchings, play an important role in mathematical biology, knot theory, and combinatorics, and as a result they have been intensely studied by mathematicians, computer scientists, and biologists alike. We use a combination of symbolic, analytic, and experimental methods to examine the enumeration of chord diagrams without short chords.

Sorting Permutations with C-Machines

Dagstuhl Seminar on Genomics, Pattern Avoidance, and Statistical Mechanics - Wadern, Germany (November 7, 2018)

In his seminal work, The Art of Computer Programming, Donald Knuth asks the reader to prove that the permutations that can be sorted by a stack are exactly those that avoid the pattern 231. This is one of the earliest questions from a field now known as Permutation Patterns that has been steadily growing and developing in the decades since.

In this talk, we'll return to and generalize this genesis question by introducing a sorting device called a C-machine that generalizes stacks and queues from computer science. After introducing the field of Permutation Patterns, I'll show how the framework of C-machines unlocks a structural description that helps us answer many intriguing questions.

For several cases where we can't find exact answers, I'll describe two computational and experimental methods that are guiding the way toward solutions: automated conjecturing of generating functions, and differential approximation of asymptotic behavior.

Circuit Scramble: Using algebra for fun and profit (chalk talk)

Marquette University Pure Math Seminar - Milwaukee, WI (October 15, 2018)

We show how to use a computational tool from abstract algebra, Gröbner bases, to solve a puzzle game called Circuit Scramble. In Circuit Scramble, the player has to figure out how to set the inputs to a logic circuit as True or False in order to make the final output True. (See here for a small example.) More generally (and, to be honest, more usefully) we'll see how Gröbner bases can also be used to formally verify the correctness of large circuits.

On the Growth of Merges and Staircases of Permutation Classes

Permutation Patterns 2018 - Hanover, NH (July 10, 2018)

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.

Patterns and Colorability in Chord Diagrams

JMM 2018, Special Session on Applied and Computational Combinatorics - San Diego, CA (January 10, 2018)

A chord diagram with $$n$$ chords is a set of $$2n$$ points in a line connected in $$n$$ pairs. Chord diagrams, sometimes called matchings, play an important role in mathematical biology, knot theory, and combinatorics, and as a result they have been intensely studied by mathematicians, computer scientists, and biologists alike. In this talk we'll examine two interesting families: 2-colorable chord diagrams, and chord diagrams without short chords. Using a combination of symbolic, analytic, and experimental methods we find counting sequences, generating functions, and asymptotics for each family.

Sorting with C-Machines

Brandeis University Combinatorics Seminar - Waltham, MA (November 7, 2017)

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

Combinatorial Exploration: A New Approach to Enumeration (keynote file)

University of Florida Mathematics Colloquium - Gainesville, FL (October 2, 2017)

Combinatorial structures are ubiquitous throughout mathematics. Graphs, permutations, words, and other such families of combinatorial objects often play a central role in work from many different fields. The study of enumerative combinatorics is concerned with the elucidation of structural properties of these families, including counting, classification, and limiting behavior.

Combinatorial Exploration is a framework that unifies the often ad-hoc methods used in enumerative combinatorics. In this talk we’ll explain how Combinatorial Exploration works, how it can be automated, and how it’s being applied to the study of pattern-avoiding permutations to prove new results and reprove dozens of old ones.

The Method of Differential Approximation in Enumerative Combinatorics

SIAM Applied Algebraic Geometry, Symbolic Combinatorics Session - Atlanta, GA (August 1, 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 the Method of Differential Approximation, a technique 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 guide the way toward rigorous proofs. We'll exhibit the usefulness of this method through a variety of combinatorial topics, including chord diagrams, permutation classes, and inversion sequences.

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.

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

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.