MATH 581 (Spring 2019)
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.
Combinatorics and Symbolic Computation
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.
Will be posted later.
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.
Additional details on certain topics can be found in the following sources, all of which are freely available.
P. Flajolet and B. Sedgewick. Cambridge University Press, 2009.
H. Wilf. Academic Press, 1990.
Analytic Combinatorics in Several Variables
R. Pemantle and M. Wilson. Cambridge University Press, 2013.
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.