Computability and Enumeration
Jul 23, 2016
About
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.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.…
Organizer
The Mathematics of Jiří Matoušek
Account · 15 followers
Categories
Mathematics
Category · 2.4k presentations
About The Mathematics of Jiří Matoušek
International Conference on The Mathematics of Jiří Matoušek, Charles University, Prague 2016
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Charles IV and Charles University
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
On the complexity of Ryser's Conjecture
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
High-dimensional permutations and discrepancy
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
On Codimension one Embedding of Simplicial Complexes
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Geometry and the semi-random method
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Ranks of matrices with few distinct entries
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%