Algebraic Combinatorics

Instructor: Narayanan N

Lecture Schedule: 4:00pm to 5:30pm Mon
4:00pm - 5:30pm Friday
Venue: HSB 266

Prerequisites: A good understanding of Linear algebra and basic group theory.
Course Info:

Objectives:

The course aims to reveal the fascinating interplay between Algebra, Combinatorics, and Graphs. It not only builds the fundamentals for students who plan to do PhD in Algebra/ Combinatorics / Graph theory and related topics, but also useful to students and researchers in other areas of science and engineering to which the methods of Algebra, Combinatorics, Graph theory may be applied.

Course Contents:

Eigenvalues and Walks on graphs. Radon transform and hypercubes. Sperner property, lattices and boolean algebra. Enumeration under group actions. Ferrer's diagram, Young tableaux and Matrix Tree theorem. Applications to Electrical networks, planar graphs. Introduction to combinatorial commutative algebra.

Text Books:

Richard P Stanley, Algebraic Combinatorics : Walks - Trees - Tableaux and More, Springer, 2013.
A preliminary copy of the book is available from Stanley's webpage.

Reference Books:

  1. Richard P Stanley, Enumerative Combinatorics - Volume 1, Springer. 2001
  2. Richard P Stanley, Enumerative Combinatorics - Volume 2, Springer, 2001.
  3. Combinatorial Commutative Algebra. Erza Miller and Bernd Sturmfels. Springer, 2005.
  4. Rafael H Villarreal, Monomial Algebras, CRC Press, 2015.
  5. R B Bapat, Graphs and Matrices, Springer, 2014.

Lecture 1 (First class)

Introduction to the course.
Graphs, Simple graphs, walks. Adjacency matrix. Walks and eigenvalues. Examples and Exercises.

Lecture 2 (20/Jan/17)

Open walks in $K_n$. A quick visit to ordinary and exponential generation functions. A powerful identity regarding sums of complex powers. Eigenvalues from walks.

Assignment: Here is the first assignment with a minor correction.

Lecture 3 (23/Jan/17)

Walking on the Hypercube: The Finite Radon Transform.

Lecture 4 (28/Jan/17)

More on the Finite Radon Transform. The eigenvectors of an arbitrary graph and its meaning. Examples using SAGE.

Lecture 5 (31/Jan/17)

Species of combinatorial structures.

Lecture 6 (3/Feb/17)

Cannonical sum representation of a species. Products of species and examples. Composition of Species. Examples.

Lecture 7 (6/Feb/17)

Derivative of a species. Pointing operation.

Assignment: Here is the second assignment.

Lecture 8 (10/Feb/17)

Vertebrates and Cayley's formula. More on generating functions.

Lecture 9 (24/Feb/17)

Markov Chains and Random Walks. Perron's theorem for positive matrices.

Lecture 10 (27/Feb/17)

Frobenius extension of Perron's theorem for irreducible non-negative matrices. Hitting time using Linear Algebra.

Lecture 11 (3/Mar/17)

Partial Orders and graded Posets. Sperner property of set systems. Some results on ordermatchings.

Lecture 12

The boolean algebra $B_n$ has sperner property. Another proof (combinatorial) given by Lubell.

Lecture 13

Group action. The quotient poset $B_n/G$ is rank-symmetric and rank unimodal.

Lecture 14

The quotient poset $B_n/G$ has Sperner property. Reading asmt: Applications to edge reconstruction conjecture.

Lecture 15

Integer partitions, Young's lattice and Young Diagrams. Examples. Properties of poset $L(m,n)$.

Lecture 16

The $q$-analogue of binomial coefficient. Poset $L(m,n)$ is rank-unimodal and Sperner.

Lecture 17

LGV Lemma and applications.

Lecture 18

Lecturer: Suresh Dara. Applications of sperner property of $L(m,n)$.

Lecture 19

TBA
Thanks must go to my friend Amri from whose page I stole the template.