96730 - Algebraic Combinatorics

Learning outcomes

By the end of the course, students understand the representations of finite groups with characteristic zero; in particular, they understand the representations of the symmetric group and the associated symmetric functions. They are able to decompose a representation into irreducible groups and solve various combinatorial and algebraic problems.

Course contents

Module 1 - Prof. Moci

Introduction, examples of representations. Regular representation, group algebra. Subrepresentations, morphisms of representations. Simple and irreducible representations. The complement theorem and its consequences. Recall of linear algebra. Direct sum and tensor product of representations. Dual, symmetric power, and exterior power of a representation. Representation on the space of homomorphisms between two representations.

Character of a representation, invariance over conjugacy classes. Schur's lemma. Dot product between central functions. Theorem: The characters of irreducible representations are an orthonormal system. Consequences: Multiplicity of an irreducible in a given representation, irreducibility criterion, two representations with the same character are isomorphic. Theorem: Every irreducible appears in the regular representation with multiplicity equal to its dimension. Theorem: The irreducible characters form a basis for the space of central functions. Consequences on the number and dimension of irreducibles: examples.

Representations of cyclic groups. Representations associated with the quotient for normal subgroups; example: the sign representation of symmetric groups. Representations of the symmetric group on 3 and 4 letters. Theorem: a group is abelian if and only if all its irreducible representations have dimension 1. Irreducible representations of the direct product of two groups. Theorem: the irreducible representations of a group have dimension less than or equal to the index of each abelian subgroup. Representations of dihedral groups.

Induced representation (two definitions); its character. Examples. Restriction, Frobenius reciprocity theorem. Integral elements on the integers and their properties. Center of group algebra and properties of its elements. Theorem: the dimension of each irreducible representation divides the order of the group.

Set of partitions of a given integer, its cardinality and orderings. Young diagrams and their numbering; tabloids. Tabloid module and Specht module associated with a partition. Example: the symmetric group on 3 letters. Theorem: Specht modules are irreducible and pairwise non-ismomorphic. The characters of the representations of the symmetric group have integer values. Morphisms and decompositions of tabloid modules. Example: the symmetric groups on 4 and 5 letters.

Standard and semistandard tableaux, skew tableaux. Three products: row insertion, sliding, and word concatenation modulo Knuth equivalence. Theorem: the three above products coincide (without proof). Robinson–Schensted–Knuth bijection. Theorem: the dimension of the Specht module is equal to the number of standard tableaux on that partition. Hook formula (without proof). Examples.

Module 2 - Professor Morigi

Algebra of symmetric functions. Five bases and their orthogonality relations (without proof). Transposition of a partition and its induced involution. Characteristics of tabloid moduli (without proof). Algebra of representations of symmetric groups. Theorem: There is an isomorphism and isometry between this algebra and the algebra of symmetric functions (with proof, modulo the previous calculations). Corollaries: combinatorial formula for the decomposition of tabloid moduli, characteristics of Specht moduli.

Graphs. Vertices and edges; degree of a vertex. Simple graphs. In any graph, the number of vertices with odd degree is even. Paths in a graph. Connected graphs. Eulerian paths. Euler's criteria: a connected graph has a closed Eulerian path if and only if every vertex has even degree.
Adjacency matrix A(G) of a graph G. For any positive integer n, the (i,j)-th entry of the matrix A(G)ⁿ equals the number of paths of length n from vertex vᵢ to vertex vⱼ. Computation of aᵢⱼ using the eigenvectors of the matrix A(G). Counting closed paths of length n in a graph.
The complete graph Kₚ with p vertices. Explicit computation of the eigenvalues of M(Kₚ), and consequently, of the number of closed paths of length n from a given vertex. Conversely, the number of closed paths of length n from a given vertex, as n varies, determines the eigenvalues of M(Kₚ).
The n-dimensional cube Cₙ and the finite Radon transform on it. Computation of M(Cₙ) and its eigenvectors. Number of paths of length s between two vertices of Cₙ that differ in k coordinates.
The determinant of a finite group and its factorization into irreducibles (Frobenius Theorem).
Trees and their characterization. Every tree with at least two vertices has at least two vertices of degree 1. Tree-growing procedure: every graph obtained through the tree-growing procedure is a tree, and every tree can be obtained this way. Every tree with n vertices has n−1 edges. Cayley’s Theorem: the number of labeled trees with n vertices is nⁿ⁻².

Readings/Bibliography

we will read some pages of the following books:

Serre, Linear representations of finite groups

Fulton, Young Tableaux


E. P. Stanley. Algebraic combinatorics. Walks, trees, tableaux, and more. Second edition. Undergraduate Texts in Mathematics. Springer, Cham, 2018.

L. Lovász, J. Pelikán, K. Vesztergombi,
Discrete mathematics.
Elementary and beyond. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 2003.

Teaching methods

lectures, exercises

Assessment methods

written and oral exam

Teaching tools

virtuale webpage

Office hours

See the website of Luca Moci

See the website of Marta Morigi