Algebraic Combinatorics Seminar - Lukas Nabergall

Title: Enumerating hereditary classes of chord diagrams

Abstract:

A class of combinatorial structures is hereditary if membership in the class is closed under taking substructures. Hereditary classes have been extensively studied for a variety of objects, notably graphs and permutations. A central problem is to determine the number of objects of size n in a given hereditary class. We discuss this problem for chord diagrams, perfect matchings of [2n]. After discussing past work enumerating hereditary classes defined by forbidding subdiagrams of size 2 and 3, we consider forbidding certain graphically-inspired infinite sets of subdiagrams. Rich enumerative relationships seem to emerge from these classes after imposing one of several connectedness notions. In particular, these classes connect to combinatorial maps, Catalan lattices, and uniquely-sorted permutations, conjecturally allowing for their enumeration.