MATH 581 (Spring 2019)

Combinatorics and Symbolic Computation 

This course provides an introduction to computational and symbolic combinatorics, focused on effective computation and connections to various areas of mathematics. Topics will be tailored to student interests and include:  basics of enumerative combinatorics and computer algebra; computer algebra tools for generating functions; effective analytic methods for asymptotics (residue computations, saddle point integrals, etc.); algorithmic transcendence proofs and transcendence of constants vs functions;  rational, algebraic, D-finite, differential-algebraic and hypertranscendental functions, and their algebraic/analytic/arithmetic properties; computability and complexity questions in enumeration and connections to formal languages; Morse-theoretic methods for asymptotics; rigorous numerical analytic continuation of functions.

Familiarity with advanced methods in symbolic computation / computer algebra will not be assumed, however students taking this course for credit will be expected to perform basic coding in a computer algebra system (Maple, Sage, Mathematica, etc.). Evaluation will consist of 2 homework assignments during the semester, together with a final presentation on a research paper.

Date and Time: 12:00-1:30pm on Tuesdays and Thursdays in DRL 4C4

Expected Background: Students should be comfortable with the basics of real analysis (especially sequences and series), complex analysis (analytic functions, Cauchy residue theorem), and algebra (linear algebra, rings and fields). Exposure to courses in computer science, combinatorics,  probability theory, or computer algebra would be beneficial. Interested students unsure of their background should email the instructor for more information.

A good idea of the selection of topics can be found in notes from a recent two week summer school, available here.

Assignments

Will be posted later.

References

The main reference for this class is a manuscript draft which will be distributed, based on the PhD thesis:

Analytic Combinatorics in Several Variables: Effective Asymptotics and Lattice Path Enumeration
S. Melczer. PhD Thesis, University of Waterloo and ENS Lyon, 2017.
https://arxiv.org/abs/1709.05051

Additional details on certain topics can be found in the following sources, all of which are freely available.

Analytic Combinatorics
P. Flajolet and B. Sedgewick. Cambridge University Press, 2009.
http://ac.cs.princeton.edu/home/

Generatingfunctionology
H. Wilf. Academic Press, 1990.
https://www.math.upenn.edu/~wilf/DownldGF.html

Analytic Combinatorics in Several Variables
R. Pemantle and M. Wilson. Cambridge University Press, 2013.
https://www.math.upenn.edu/~pemantle/papers/ACSV.pdf

Algorithmes Efficaces en Calcul Formel [Efficient Algorithms in Computer Algebra]
A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy and E. Schost, 2017.
https://hal.archives-ouvertes.fr/AECF/
(In French)