ACA'2020 Session: Algorithmic CombinatoricsACA'2020: Home, Sessions
- Hao Du (RICAM, Austrian Academy of Sciences)
- Christoph Koutschan (RICAM, Austrian Academy of Sciences)
- Ali Uncu (RICAM, Austrian Academy of Sciences)
Aims and ScopeThe interplay between computer algebra and combinatorics has been very fruitful for many years and can be subsumed under the name "algorithmic combinatorics", which nowadays is a well-established research area. It is one of the many success stories concerning the applications of computer algebra, and it perfectly demonstrates how two scientific disciplines can interact and inspire each other: on the one hand, combinatorialists appreciate the power of computer algebra systems, and on the other hand, problems from combinatorics are one of the driving forces for the development of new computer algebra algorithms and packages.
Examples include the enumeration of different types of lattice walks, the study of symmetry classes of plane partitions and alternating sign matrices, various types of tiling problems in the plane, the counting of lattice points in polytopes and the computation of Ehrhart polynomials, partition analysis and q-identities, graph theory, and pattern avoidance questions. There are numerous ways in which experimental mathematics, and specifically computer algebra, can contribute to these problem areas:
- generation of experimental data in order to formulate or support conjectures
- manipulation of generating functions, such as executing D-finite closure properties, extracting coefficients, or determining the asymptotic behaviour
- (q-) difference and differential equations: construction of explicit solutions and investigation of structural properties
- evaluation of binomial sums, as well as more general sums and integrals, by means of the Wilf-Zeilberger algorithmic proof theory
- fast and/or high-precision numerical evaluation of combinatorial sequences and special functions
- hypergeometric series: identities, evaluation, asymptotics
- symbolic evaluation of determinants and Pfaffians related to counting problems
- etc. etc.