Math 155r - Combinatorics (formerly Math 192)

Math 155 - (Algebraic) Combinatorics - Fall 2007

Lectures: Tuesday and Thursday 11:30am - 1pm, in Science Center 101B

Lecturer: Lauren Williams (office Science Center 432, e-mail lauren@math.harvard.edu)

Office Hours: TUESDAYS 3:30-4:30pm at Science Center 432

Section: MONDAYS 3-4pm at Science Center 232

Course Assistant: Vinh Le (vinh@math.harvard.edu)

Handouts

Syllabus

Some ideas for your final project

Course description

This course is an introductory course in algebraic combinatorics. The course is meant to be challenging but also a lot of fun. Rigorous mathematical proofs are expected. No prior knowledge of combinatorics is expected, but I will assume that you have taken Math 122 or the equivalent. Some knowledge of the representation theory of finite groups would be helpful but is not required.

There will be problem sets every week or so (worth 55%), an in-class exam (15%), and a final project (5% oral plus 25% written) in lieu of a final exam.

Some recommended books include:

William Fulton, Joe Harris: Representation Theory, a first course.
Bruce Sagan: The Symmetric group
William Fulton: Young Tableaux
Richard Stanley: Enumerative Combinatorics 2

The topics of this course include enumerative and algebraic combinatorics related to the symmetric group, symmetric functions, and Young tableaux. In particular, I am likely to discuss:

An overview of representations and characters of finite groups.
A more detailed study of the representation theory of the symmetric group, including Young symmetrizers, Specht modules, the branching rule, Gelfand-Tzetlin bases.
Some representation theory of the general linear group.
Symmetric functions, including Schur functions.
Schur-Weyl duality.
The Bruhat order and (a little bit about) flag varieties.
Young tableaux, the hook-length formula, and the RSK algorithm.
If time permits I will talk about Dodgson's condensation, alternating sign matrices, plane partitions, and related topics ...

Lectures

Lecture 1 (Sept. 18): Introduction, motivation, and review of representation theory of finite groups

Lecture 2 (Sept. 20): Analysis of representations of S₃ using an abelian subgroup; definitions and results about characters

Lecture 3 (Sept. 25): Construction of the irreducible representations of S_n using Young symmetrizers, Specht modules, etc.

Lecture 4 (Sept. 27): Proof that the Specht modules are distinct and irreducible; RSK correspondence.

Lecture 5 (Oct. 2): Increasing and decreasing subsequences of permutations, and Viennot's shadow diagrams.

Lecture 6 (Oct. 4): Knuth equivalence and Green's Theorem; hook-length formula also?

Lecture 7 (Oct. 9): Vershik-Okounkov approach to the representation theory of S_n; how to discover Young tableaux. Paper of Vershik-Okounkov

Lecture 8 (Oct. 11): Vershik-Okounkov approach to the representation theory of S_n (cont.)

Lecture 9 (Oct. 16): Vershik-Okounkov approach to the representation theory of S_n (almost finish)

Lecture 10 (Oct. 18): Finish Vershik-Okounkov stuff and start symmetric functions.

Lecture 11 (Oct. 23): Fundamental theorem of symmetric functions, and definitions of monomial, elementary, homogeneous, and Schur functions.

Lecture 12 (Oct. 25): Symmetry of Schur functions, Cauchy identity, inner product on symmetric functions.

Lecture 13 (Oct. 30): Pieri's rule and a first connection between characters of S_n and symmetric functions.

Lecture 14 (Nov. 1): Young's Rule and the characteristic map between characters of S_n and symmetric functions.

Lecture 15 (Nov. 6): The Murnaghan-Nakayama Rule for characters of the symmetric group

Lecture 16 (Nov. 8): An overview of what we've done so far: what is the big picture?!

Lecture 17 (Nov. 13): Construction of some representations of the general linear group (Schur modules)

Lecture 18 (Nov. 15): More about the representation theory of the general linear group including the connection to Schur polynomials

Lecture 19 (Nov. 20): A quick introduction to the Grassmannian and the flag variety; Bruhat order.

No Lecture (Nov. 22): Happy Thanksgiving!

Lecture 20 (Nov. 27): Alternating sign matrices: how they were discovered, and the main conjectures/theorems

Lecture 21 (Nov. 29): MacMahon's results on plane partitions, and a brief overview of the ASM Conjecture (Theorem)

Section! (Dec 3): In-class presentations (Note: meet in the usual room for section)

Lecture 22 (Dec. 4): In-class presentations

Lecture 23 (Dec. 6): In-class presentations

Lecture 24 (Monday Dec. 10): Review session in section

No lecture (Dec. 11): Study for exam

Lecture 25 (Dec. 13): In-class exam

Lecture 26 (Dec. 18): Guest lecture by David Speyer on jeu de taquin (game of teasing) and related topics.

Lecture notes brought to you by Xournal

Problem Sets

Problem Set 1: due Sept. 27

Problem Set 2: due Oct. 11

Problem Set 3: due Oct. 25

Problem Set 4: due Nov. 8

Problem Set 5: due Nov. 20

Final Project

I will provide a list of suggestions for your final project. You need to give an in-class presentation (of approximately 30 minutes) and write a paper in Latex (of approximately 5 pages) which is due at the end of reading period in January.