Christian Bean, Keele University

Abstract

Permutations, words, set partitions, and other such families of objects often play a role in diverse subfields of mathematics, physics and computer science. When the structure of the object under investigation is known there are well-established tools, such as symbolic and analytic combinatorics, that derive an enumeration, asymptotics, and the ability to randomly generate instances of the objects. However, the initial step from a definition of the object to a structural description is often ad-hoc, human-staring-at-a-blackboard type of work. This is the gap combinatorial exploration attempts to fill.

Combinatorial exploration is a domain-agnostic algorithmic framework to automatically and rigorously study the structure of combinatorial objects and derive their counting sequences and generating functions. We describe how it works and provide an open-source Python implementation. As a prerequisite, we build up a new theoretical foundation for combinatorial decomposition strategies and combinatorial specifications.

Combinatorial exploration has been most extensively applied to permutation classes, rederiving hundreds of results in the literature as well as discovering many novel results (which can be found on permpal.com). As well as unifying earlier methods, one key advantage of our approach is its ability to utilise a growing library of strategies in a simultaneous manner to build a greater understanding of the structure of the permutation classes.

Link to video: https://vimeo.com/1070154147?share=copy

Presented Via Zoom: https://rutgers.zoom.us/j/91865817691

Password: 6564120420

For further information see: https://sites.math.rutgers.edu/~zeilberg/expmath/