Algebraic Combinatorics

ID : 
ΕΛ
Semester : 
6
Track: 
Free Electives

Department of Mathematics

15101038 Algebraic Combinatorics (6th semester) 5  ECTS

Instructor: Athanasiadis

Review of fundamental principles and techniques of enumeration, with an emphasis on bijective proofs and the method of generating functions. Examples (sets, permutations, integer partitions etc) (2 weeks).

Permutations as words, elements of the symmetric group, disjoint union of cycles (cycle structure), 0-1 matrices, increasing trees etc. Permutation enumeration (inversions, cycles, descents, excedences, fixed points, alternating permutations, major index and MacMahon's Theorem). Permutations of multisets, inversions and q-binomial coefficients. Young tableaux and the hook-length formula, the Robinson-Schensted correspondence, Knuth equivalence, Schutzenberger's teasing game, applications to monotone subsequences, the evacuation tableau and Schutzenberger's theorem on the inverse and reverse permutation. The weak Bruhat order and applications on the enumeration of reduced decompositions of permutations (7 weeks).

Elements of algebraic graph theory, the adjacency matrix of a graph (directed or not), eigenvalues and enumeration of walks. The Laplacian matrix, spanning trees and the Matrix-Tree Theorem, applications to complete (Cayley's formula) and bipartite graphs. Walks in the Young lattice and differential partially ordered sets. Applications of linear algebra on topics such as: the unimodality of q-binomial coefficients, existence of matchings in graphs and Sperner's Theorem and its generalizations (4 weeks).

 

There is no registered book for this course