Complexity problems in enumerative combinatorics

Abstract

We give a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.

31 pages; an expanded version of the ICM 2018 paper (Section 4 added, refs expanded)

References in corpus (10)

• Graph Isomorphism in Quasipolynomial Time
• An introduction to the dimer model
• Arctic curves of the six-vertex model on generic domains: the Tangent Method
• Intervals in the greedy Tamari posets
• Counting quadrant walks via Tutte's invariant method
• A q-rious positivity
• A Combinatorial Interpretation of The Numbers $6(2n)!/n!(n+2)!$
• Pattern avoidance is not P-recursive
• On the connectivity of spaces of three-dimensional tilings
• Division by three

Cited by in corpus (3)

• Sorting probability of Catalan posets
• What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I
• Effective formulas for linear recurrence sequences of integers