ICE-TCS seminar: Christian Bean

“It goes as follow. Have a (as of now, human) mathematician get a brilliant idea. Teach that idea to a computer, and let the computer do research using that idea.” - Doron Zeilberger.

  • 21.4.2017, 12:15 - 13:00

ICE-TCS-logo-200px

Date/Time: Friday, 21 April 2017, from 12:15 till about 13:00
Location: M113 - Reykjavík University
Speaker: Christian Bean (Reykjavik University)

Creating a Virtual Combinatorist

Abstract: “It goes as follow. Have a (as of now, human) mathematician get a brilliant idea. Teach that idea to a computer, and let the computer do research using that idea.” - Doron Zeilberger.

Our goal is to create a virtual combinatorist that can enumerate permutation classes, which are sets of permutations closed downwards by containment. We follow the mentality set out by Zeilberger. The first step, therefore, is to have “a brilliant idea”. We call these proof strategies. In our case, we are always working with a permutation class C, which is a subset of all permutations. For some subset S of all permutations, a proof strategy is a disjoint set of subsets of S, such that when each subset is intersected with C their disjoint union is equal to the intersection of S and C.

Consider the tree where the root node is some permutation class. The children of a node are subsets obtained by some proof strategy, thus form a disjoint union for their parent while working inside the permutation class. If all the leaves of the tree are subsets of the class then their disjoint union define a description for it, while the tree itself is a proof certificate of this description. We call such trees proof trees.