Meistaravörn í tölvunarfræði: Unnar Freyr Erlendsson

Effective enumeration of permutation classes and their juxtapositions

  • 24.5.2019, 14:00 - 15:00

Student: Unnar Freyr Erlendsson
Title: Effective enumeration of permutation classes and their juxtapositions
Date and Location: Friday, May 24th, 2019 at 14:00 in M208
Supervisors: Henning Arnór Úlfarsson, Assistant Professor, Reykjavík University, Iceland and Christian Bean, Post doc, Reykjavík University, Iceland

Title: Effective enumeration of permutation classes and their juxtapositions

Abstract: We generalise the idea of greedily gridding permutations to help enumerate 1xN grid classes introduced by Brignall and Sliačan by translating it to the language of tilings developed by Bean. We then use automatic methods to get proofs of the enumeration for several known 1x2 grid classes and some previously unknown ones. We develop an automatic method to obtain recurrence relations from proof trees obtained by CombSpecSearcher (Bean). This gives a polynomial time enumeration for every proof tree, including those where an explicit generating function has proven hard to find.



Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á ru.is eða með því að senda tölvupóst á netfangið: personuvernd@ru.is
//
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our ru.is or send an e-mail: personuvernd@ru.is