MATH 172 Combinatorics (Fall 2004):

Instructor: Alexander Yong, 1035 Evans Hall, ayong@math.berkeley.edu

Lectures: Tuesdays and Thursdays 12:30-2:00PM, 103 Moffitt

Office hours: Mondays 1-2PM, Wednesdays 3-4PM (in 1035 Evans)

Required Text: Combinatorics: Topics, Techniques, Algorithms by Peter J. Cameron, Cambridge University Press, 1994 (reprinted 1996).

Other recommended texts:

1. R.P. Stanley "Enumerative Combinatorics I"

2. R.P. Stanley "Enumerative Combinatorics II"

3. D. Stanton and D. White "Constructive combinatorics"

4. R. Brualdi, "Introductory Combinatorics"

Grading: Regular Assignments (40%), five "your choice" problems (20%), project (20%), take home final (20%)

Homework: Occasional assignments, final.

Homework 0: Send me an email about you and your (mathematical) background so I can get to better know you.

Exams: TBA

Prerequisites: No specific prerequisites, however exposure to courses such as abstract algebra (Math 113) will be helpful. This will be an advanced undergraduate course on combinatorics.

Syllabus: This is the ultimate fun course on combinatorics. Combinatorial methods are applied widely throughout mathematics; this class will be an introduction to various aspects of combinatorial theory. Some sample topics include: generating series, graph theory, poset theory, combinatorics of trees (parking functions, Catalan numbers, matrix-tree theorem), tableaux and the symmetric group (permutation statistics, the Schensted correspondence, hook-length formula), partitions, symmetric functions.

A different with the same course number was taught in Spring 2004. This course will not depend on the material covered in that course. Although there will be some material overlap, I plan to cover a wider range of topics this term.

This course should be of interest to anyone who like algorithms, computation, and problem solving.


Part I: Introduction/Preliminaries:

Lecture 1: We will discuss a little about the course, what we will cover. Some philosophy on what is and isn't combinatorics (meant to be provocative). Here are some papers that I'd like you to look over (browse the introduction for example and try to come away with the "point" of why the paper was written and what the combinatorics is) and eventually choose one for deeper study (in no particular order); but please come and talk to me about them:

Determinants, paths and plane partitions (Gessel and Viennot) .

Coverings, heat kernels and spanning trees (Chung-Graham and Yau)

Total positivity: tests and parametrizations (Fomin and Zelevinsky) .

The Laurent phenomenon (Fomin and Zelevinsky) .

Cluster algebras I: Foundations (Fomin and Zelevinsky) .

The honeycomb model of GL(n) tensor products I: proof of the saturation conjecture (Knutson and Tao) .

Puzzles and (equivariant) cohomology of Grassmannians (Knutson and Tao) .

Grobner Geometry of Schubert polynomials (Knutson and Miller) .

Algebraic methods in integer programming (Thomas) .

A direct bijective proof of the hook-length formula (Novelli, Pak, Stoyanovsky) .

A Combinatorial Formula for the Character of the Diagonal Coinvariants (Haiman, Haglund, Loehr, Remmel, Ulyanov).

Longest increasing subsequences of random colored permutations (Borodin).

First steps in tropical geometry (Jurgen, Sturmfels, Theobald)

Short rational generating functions for lattice point problems (Barvinok, Woods)

The Strong Perfect Graph Theorem (this is a webpage, see the paper by Chudnovsky and Seymour)

The distributions of the entries of Young tableaux (McKay, Morse, Wilf)

Differential posets (Stanley) [WARNING: you may need to be on the UC Berkeley network to access this file]

Of course, this is just a personal selection. I think that most of these papers represent a major recent story in combinatorics and/or really nice combinatorics. I've tried to have papers in a variety of areas on combinatorics: optimization, algebraic, enumerative, bijective, probabalistic, graph theory, posets, geometric, representation theoretic.. but have (necessarily?) failed to hit every stream of research in the subject. Please consider the following links, e.g., starting from my "people" page , to get more ideas about what people do in the subject. Here is the first day survey (PDF file) . We started talking about (ordinary, single variable) generating series. The philosophy is this. You have some set of combinatorial objects S that you want to count with respect to some weight w. The principle is often it is easier to compute the generating series \sum_{i=0}^{\infty} c(n)x^n where c(n)=# of elts of S with weight w than to compute each c(n) independently. We gave some examples of combinatorial sets (bills in my pocket, partitions, plane planted trees) and weights (face value of a bill, sum of the parts, number of nodes). Here are some problems
Problem 1: Show that Q[[x]] is a ring.
Problem 2: When does a generating series have an inverse?

Lecture 2: We begain with a very rich example of a combinatorial set: the set of permutations on {1,2,3,...,n}. How rich is it? Well, we developed the language of diagrams and explained the connection to certain varieties (read: zero set of a system of polynomial equations) defined by a bunch of minors.

Problem 3: What is the minimal subset of the diagram that defines the same variety as the entire diagram itself?

We also talked about the following open question that I'm interested it: can you give a "closed form" answer to what subset of nxn is the diagram of some permutation?

We then talked about some basic lemmas about generating series: the sum lemma and product lemma. We applied them to count plane planted trees with respect to the number of nodes.

Lecture 3: We started talking about using ordinary generating series to compute formulas about partitions. We showed how to apply _algebraic_ techniques to derive combinatorial facts:

Problem 4: Give an explicit bijection between R_{2,3,5} and R_{2,3,6,9,10 mod 12}.

We have a new grading method. I'll hand out some assignments (about once per month or so) that will be graded (40%). Then I'll ask you to turn in five of the listed problems at the end of the term (20%). The project will cover 20% and a take home final will be the last 20%. Lecture 4: We gave a proof of a classical identity of Euler and Gauss and worked towards another one. Did you figure out the trick of what to do with Ferrers' shapes for paritions with odd, distinct parts? They are in bijection with paritions that are self-conjugate (they stey the same under conjugation). This is done by folding each part of the odd, distinct parts into an upside down "L" and putting the corner on the main diagonal. For example, (7,5,3) goes to (4,4,3).

Lecture 5: We finished the proof of the second Euler-Gauss identity. Then we did some simple binomial identities (interesting ones to follow). Assignment 1 due on October 5, 2004. Lecture 6: We finished our discussion of ordinary generating series by discussing the refinement principle (a way to track extra information about the combinatorial set). We talked about how to use combiantorial objects to model things in the world. We defined as simplicial complex and started talking about the stable marriage problem which we will start to work towards.

Lecture 7: We started talking about bipartite graph matchings. Did you pick a paper to study yet? The Pak paper is taken.
Problem 5: Prove that any two domino tilings of a mxn rectangle (assuming m and n are chosen that a complete tiling exists) can be obtained from one another via a sequence of "flips" insider 2x2 squares.

Lecture 8: We proved that a matching M in a bipartite graph G=(X,\Delta,Y) is maximal if and only if there does not exist an M-alternating path. We discussed how the minimal covering problem is "dual" to the maximal matching problem.

Lecture 9: We'll state and prove the matching algorithm, and deduce Konig's theorem: that for any bipartite graph the maximal size of a matching equals the minimal size of a cover.

Lecture 10: We stated and proved the marriage algorithm.
Problem 6 (easy): Extend the marriage algorithm to the case that each female can have multiple spouses, but that the number of "spots" open equals the number of men.

Lecture 11: We'll start talking about Groebner bases and the related combinatorics. Here is Assignment 2 , due Tuesday November 9, 2004.

Lecture 12: No class today. I'll be here .

Lecture 13: We gave the division algorithm for k[x_1,...,x_n]. We explained some more about the connection between the original ideal I and the (monomial) initial ideal init(I), with respect to a given term order. We began to discuss monomial ideals and their properties.

Lecture 14: We started with a

Special Problem: Use a computer to conjecture a Grobner basis for the ideal cutting out matrices satisfying rank conditions prescribed by a given permutation.

After that, we proved that any monomial ideal is finitely generated (this is Dickson's Lemma). In the typical philosophy of this game, we showed that the general case (Hilbert's basis theorem): that any ideal is finitely generated can actually be derived from the monomial ideal case. Moreover, our proof (based on the division algorithm) gives as a porism the existence of Grobner bases with respect to any monomial order.

Lecture 15: More on properties of Grobner bases: once we have an algorithm that constructs a Grobner basis, we will have solved the ideal membership problem. Similarity to the combinatorial group theory word problem.

Lecture 16: Grobner enough basis open problem. We used MAPLE to explore an ideal generated by elementary symmetric polynomials and its Grobner basis with respect to tdeg(x_n,x_{n-1},...,x_1).

Lecture 17: We proved the Buchberger S-polynomial criterion.

Lecture 18: We stated and proved the Buchberger algorithm to find a Grobner basis with respect to a given term order. This ends our discussion of Grobner bases. We will now move to talking about relating symmetric group combinatorics, simplicial complexes, symmetric polynomials and trees.

Lecture 19: We started by defining the weak Bruhat order on the symmetric group which has covering relations given by u>v if v=us_i for some simple reflection s_i=(i<->i+1). Here are some basic questions: is this poset ranked (yes, by length of its reduced word). What is a direct way to compute the length (and: inversions). How does one present the symmetric group as generated by the s_i 's modulo some commutation relations? Are any two reduced words equivalent via these commutation relations? We stated the an open problem asking to extend some of these ideas to tree generators of S_n.

Lecture 20: We answered the questions from the previous lecture (except the open problem) from last time.

Lecture 21: Assignment 3 due the last day of class. We'll study the Schensted correspondence. The "trace" of this bijection says that n!=\sum (f^{\lambda})^2 where the sum is over all partitions of size n. P. Diaconis' has asked the following open question, which I pass along to you: find a "nice" formula for \sum (f^{\lambda})^3. As part of our analysis we will show that \sum f^{\lambda is equal to the number of self inverse permutations in S_n.

Lecture 22: We proved the symmetry of the Schensted algorithm under inverses of permutations. In fact, we did this by describing an alternative "growth diagram" formulation of Schensted (due to Fomin).

Lecture 23: Today was n^{n-2} day, we explained why the number of labelled trees on n vertices is counted by this number. We gave a special problem to establish that the number of parking functions on $n$ cars is equal to (n+1)^{n-1}, and that all parking functions are easily characterized after rearrangement. Finally we explained that the number of factorizations of the cycle (12...n) into n-1 transpositions also equals n^{n-2} and gave "half" a bijection. The observation is that the mapping we exhibited corresponds leaves to the number of transpositions of the form (i i+1). The special problem is to prove this fact, along with finishing the bijection. I also asked as a special problem to find a Prufer code for factorizations.

We also decided on the schedule for the talks. Plan for a 25 minute presentation with 5 minutes for questions. December 7: Arne, Justin, Linda (in class); Pat and Visnu (5:10-6PM in a room TBA), December 9: Will, James, Carol (in class); Bart and Shyam (5:10 - 6PM in a room TBA).

Lecture 24: I will explain simplicial complexes in a specific example: how to make a simplicial complex out of a tableaux. The next two classes after Thankgiving are being guest lectured by Dr. Esther Lamken, who will cover the combinatorics of Design Theory (she's an expert!), and in relation to things such as coding theory. Please read/look over Chapters 6, 8 and 16 in preparation for her classes.

Assignment 3 hints, notes: Q4 should read "n -1's" not "(n-1)'s". Observe that choose(n,k-1)*choose(n-1,k-1) is the number of pairs of compositions A:a_1+...+a_k=n+1 and B:b_1+..+b_k=n. From these compositions construct a sequence w=w(A,B) consisting of a_1 1's, b_1 -1's, a_2 1's, b_s -1's etc.; further hint: use the following theorem: let R=(r_0,r_1,...,r_m)\in Naturals^{m+1} with \sum r_i = n and \sum (1-i)*r_i = k>0. Then the number of plane forests with n vertices and k components having r_i vertcies with i successors is equal to (k/n)*(n choose r_0,r_1,...,r_m); a multinomial coefficient. [Prove this if you use it]. Q5. Try to compute what the polynomial is for n=1,2,3,4. If it's too nasty by hand, find a friend with MAPLE and download John Stembridge's "symmetric functions" package found here. (Use the function "top"--meaning "to power sum basis"). You will probably have to look at the introduction. Q6. There is a bijection between dissections D of an (n+2)-gon with d diagonals and integer sequences A=(a_1,a_2,...,a_{n+d+1}) such that (a) either a_i=1 or a_i>=1; (b) exactly n terms are equal to -1; (c) a_1+a_2+...+a_i>=0 for all i; (d) a_1+a_2+...+a_{n+d+1}=0. Prove this first.

Talks: the evening session will be from 5-6PM in 959 Evans Hall. All participants are asked to attend. There will be a projector (ordinary and laptop). The during class talks will begin at 12:40 sharp. Each talk will run for 28 minutes. Please arrive early if possible.

Lecture 25: (Guest Lecturer Esther Lamken, here's her summary:) we went over the mathematics related to Euler's 36 Officer problem. I described some constructions for sets of mutually orthogonal Latin squares (MOLS) and indicated a proof of Euler's conjecture. We ended with an application in authentication.

Lecture 26: (Guest Lecturer Esther Lamken, here's her summary:) we discussed necessary conditions for the existence of balanced incomplete block designs (BIBDs) including a proof of Fisher's inequality. I described a solution to Kirkman's 15 Schoolgirl problem and discussed constructions for Steiner triple systems. We ended with an example of a t-design from graph theory.
Some good references to the material I discussed are the following.
1. A Course in Combinatorics, Jack van Lint and Rick Wilson. A good general textbook on combinatorics which includes material on designs, codes, and graphs and connections between the areas.
2. The Handbook of Combinatorial Designs, editors C.J. Colbourn and J.H. Dinitz. It is a good reference with lots of tables and sections on applications.
3. Combinatorial Designs: Construction Methods, Ian Anderson. A good undergraduate textbook on design theory.
4. Combinatorial Designs: Constructions and Analysis. D.R. Stinson. A good new textbook on Design theory with chapters on applications.
5. Cryptography: Theory and Practice, D.R. Stinson. A good textbook on cryptography. The third edition is coming out soon.

Lecture 27: We had outstanding lectures by Linda Hung on Total positivity, Arne Baste on Bijective proofs of the hook length formula (here's his Java code that runs through the bijection of Pak, Novelli and Stoyanovsky ), and Justin Ghan on what the probability is that a large Young tableaux contains a given one. In the evening, we heard from Pat Chau on Equivariant grassmannian Schubert calculus (i.e., how puzzles compute them) and Vishnu Narayanan on how Grobner bases give test sets for integer programming problems. Excellent job.