Algebraic Combinatorics

About the Course:The objective of this course is to introduce the student to some powerful paradigms in modern combinatorics, namely Möbius inversion on partially ordered sets, combinatorial classes and combinatorial species, and the Lindström-Gessel-Viennot lemma. It will also include an introduction to the theory of symmetric functions.INTENDED AUDIENCE: M.Sc./M.Tech. (Mathematics, Computer Science), PhD coursework (Mathematics, Computer Science), advanced undergraduates, B.Sc., B.E., B.Tech. (Mathematics, Computer Science).PREREQUISITES: Knowledge of set theory, linear algebra, and algebra at the undergraduate level, basic undergraduate discrete mathematics (induction, graphs, trees, basic counting techniques, recurrence relations, etc.).INDUSTRY SUPPORT: Nil

Syllabus

Week 1: Partially ordered sets and Möbius inversionWeek 2: Finite distributive latticesWeek 3: Combinatorial classes and their ordinary generating functionsWeek 4: Operations on combinatorial classesWeek 5: Combinatorial specificationsWeek 6: Groups of permutations, cycle structure, orbit counting methodWeek 7: Polya’s enumeration theorem, the cycle index generating functionWeek 8: Combinatorial species and associated generating functionsWeek 9: Operations on speciesWeek 10: The LGV lemmaWeek 11: Symmetric functions – elementery, complete, power sumWeek 12: Symmetric functions – Schur functions