Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, April 17, 2018 - 3:00pm

Jay Pantone



University of Pennsylvania


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 examine enumerative properties of families of chord diagrams that avoid local patterns. In particular, we prove that for all k, the generating function for chord diagrams in which every chord has length at least k is D-finite (and therefore the counting sequence satisfies a linear recurrence with polynomial coefficients). We conjecture that a similar but much more general statement is also true. The proof uses several interesting tools: finite state machines, the sieve method, creative telescoping, and D-finite closure properties. We also give examples of local patterns for which experimental evidence suggests that the generating function is non-D-finite, or worse.
This is joint work with Peter Doyle and Everett Sullivan.