Computability and Enumeration

Jul 23, 2016



I will describe new approach to combinatorial objects which are provably “hard to enumerate”. In particular this shows how to construct objects whose generating function is not D-finite and even ADE. We illustrate our approach in two key examples: words over a linear group (we resolve negatively Kontsevich’s problem) pattern avoiding permutations (we resolve negatively Noonan-Zeilberger’s Conjecture) Joint work with Scott Garrabrant.


About The Mathematics of Jiří Matoušek

International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016

Store presentation

Should this presentation be stored for 1000 years?

How do we store presentations

Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%


Recommended Videos

Presentations on similar topic, category or speaker