MATH 146 (Algebraic Combinatorics) - Spring 2014, UC Davis

Lectures: MWF 4:10-5:00pm, 1060 Bainer (Anne Schilling)
Discussion Sessions: MAT 146-001, CRN 29228, R 5:10-6:00 PM in Giedt 1006
Instructor: Anne Schilling, MSB 3222, phone: 554-2326,
Office hours: Wednesdays 1pm-3pm
T.A.: Federico Castillo, MSB 3217
Office hours: Tuesday 1-3pm
Text: I will mostly follow Richard Stanley's new book on "Algebraic Combinatorics: walks, trees, tableaux and more", published by Springer, first edition, 2013. A free pdf version of the book without exercises can be found on Stanley's homepage.
Pre-requisite: MAT 25; 22A or 67; 145
Problem Sets: There will be weekly homework assignments due on Fridays at the beginning of class.
You are encouraged to discuss the homework problems with other students. However, the homeworks that you hand in should reflect your own understanding of the material. You are NOT allowed to copy solutions from other students or other sources. If you need help with the problems, come to the discussion session and office hours! The best way to learn mathematics is by working with it yourself. No late homeworks will be accepted. A random selection of homework problems will be graded.
During the weekly disucssion sessions more problems are discussed, some of which might appear on the midterm and/or final! Make sure to attend!
Computing: During class, I might illustrate some results using the open source computer algebra system Sage. When you follow the link, you can try it out yourself using Sage Online Notebook. Or you can sign up for a Class Account with the math department. Log into and type the command `sage` to launch a Sage session in the terminal.
Exams: There will be one Midterm on Friday May 9 in class. The Final exam will be Monday, June 9, 1-3pm.
There will not be any make-up exams!
Grading: The final grade will be based on: Problem sets 30%, Midterm 30%, Final 40%.
Grades will be recorded on SmartSite.
Bed Time Reading: If you would like some bedtime reading related to math, I can recommend two really good books by Simon Singh: "Fermat's Last Theorem" and "The Code Book".

Course description

This course is an introduction to algebraic combinatorics. We will cover topics with relations to algebra (linear algebra and some group theory), probability theory (random walks and Tsetlin libraries), and representation theory (partitions and Young tableaux).

1. Random Walks
Walks on graphs, cubes and the Radon transform, random walks, Tsetlin library

2. Posets
Sperner property

3. Young diagrams
q-binomial coefficients, Rogers-Ramanujan identities, generating functions for partitions, Young tableaux, RSK algorithm

Sage examples

Walks on graphs: pdf or sage worksheet
The n-cube: pdf or sage worksheet
The Tsetlin library
Young's lattice and RSK


Rogers-Ramanujan identities pdf
Symmetric chain decomposition of cyclic quotients of Boolean algebras pdf

Problem sets

Homework 1: due April 11 in class: pdf

Homework 2: due April 18 in class: pdf

Homework 3: due April 25 in class: pdf

Homework 4: due May 2 in class: pdf

Midterm: in class on May 9.
The midterm will cover Chapters 1-4 and Chapter 6 from the beginning up to and including Theorem 6.6 (pg 57-63 in the print version of the book). It will have 3 problems, one asking for definitions and statements of the main theorems we covered in class, one problem with True/False question that you need to justify, and one problem on walks on graphs. Make sure you know how to compute the determinant of a 2x2 matrix and how to solve quadratic equations!

No homework due on May 9 due to midterm on May 9!!

Homework 5: due May 16 in class: pdf

Homework 6: due May 23 in class: pdf

Homework 7: due May 30 in class: pdf

Homework 8: due June 6 in class: pdf

Final Exam: Monday, June 9, 1-3pm in the usual classroom
The final exam is comprehensive and will cover all topics we discussed in class and on the homework assignments. This includes Stanley Chapters 1-6 and 8 as well as the notes on Rogers-Ramanujan identities. There will be again one question asking for definitions and statements of the main theorems as well as one True/False question that you need to justify.