Computability and Enumeration

od · 23. červenec 2016 · 606 zhlédnutí ·

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.

© SlidesLive s.r.o.