Contact | Description | Topics | Texts | Notes | Lectures | Assessment and Assignments |

mulogo

MAST90030
Advanced Discrete Math

Semester II 2025

Lecturer: Arun Ram, 174 Peter Hall Building, email: aram@unimelb.edu.au

Time and Location:

  • Lecture:
    • Wednesday 10:00-11:00 Evan Williams Theatre, Peter Hall Building
    • Thursday 10:00-11:00 Evan Williams Theatre, Peter Hall Building
    • Friday 9:00-10:00 Evan Williams Theatre, Peter Hall Building
  • Consultation/Problem/ProofandWriting/ResearchExploration/Tutorial sessions:
    • Wednesday 11:00-12:00 in Russell Love
    • Thursday 9:00-10:00 in Evan Williams
    • Friday 11:00-12:00 in Russell Love

I am often available for additional questions/discussions after class on Friday.

I am available by appointment. I rarely come in to the University before 12 as I have other responsibilities in the morning until 12. If you email me suggesting some weekday afternoon times for an appointment that work for you then I can choose one of them that also works for me. If you email me and don't suggest some times that work for you, then I will respond by asking you to suggest some weekday afternoon times that work for you.

Some of my thoughts about teaching have been written down in the Lecture script: Teaching Math in the Next Life
I am very interested in listening to and discussing any thoughts/reaction/improvements that you have in relation to this content.

The student representatives are
??? ???   email: ???@student.unimelb.edu.au
??? ???   email: ???@student.unimelb.edu.au

The handbook entry for this course is at https://handbook.unimelb.edu.au/2025/subjects/mast90030/print

Main Topics

  • (1) Partitions and symmetric functions
  • (2) Posets, lattices and generating functions
  • (3) The symmetric group and GLn(𝔽q)
  • (4) Catalan, Modified Hall-Littlewood and Modified Macdonald polynomials
  • (5) Moment graphs and Kazdhan-Lusztig polynomials
  • (6) Flag varietes, Schubert varieties and Springer fibers

Announcements

  • No books, notes, calculators, tablets, ipads, phones, etc at the exam.
  • Prof. Ram reads email but generally does not respond by email. Usually these are collated and reponses to email queries are provided in the first few minutes of lectures. That way all students can benefit from the answer to the query.
  • Compared to the other resources on this page Lecture Capture is not an efficient way to absorb material for this course. If you want to get a hang on the naterial covered in a particular lecture, you should make a handwritten copy of the Handwritten Lecture Notes for that lecture which are posted below, and ask any questions that come up as you make your handwritten copy in the Proof and Solution writing sessions.

Assessment

The basic assessment structure for the course will be as follows:

  • Assignment 1: write an 18 page exposition of a topic (Some suggestions are below. Hopefully these will be things the markers will actually enjoy reading about).
  • Assignment 2: Write a report and produce and improvement of another student’s assignment 1. This should also total 18 pages (the handbook says 36 pages for assignments).
  • 3 hour Final exam: Write lecture notes for a 1 hour lecture on a topic (chosen from a list that I’ll advertise in advance, drafted below, for the most part these will be the topics covered in class)
More details about the Final exam and the Asignments is given below. I reserve the right to make changes to this plan if it becomes necessary for some reason (though I expect this to be extremely unlikely).

Resources

Recommended are:

  • The notes on this page

Another favourite resource for some of the the material we will cover is

Richard Stanley, Enumberative combinatorics, Volumes I and II, ????, 20??.

Another favourite resource for some of the material we will cover is

I.G. Macdonald, Symmetric functions and Hall polynomials, Second edition, Oxford University Press, 1995.

Notes written by Arun Ram

Resources in preparation

In class lectures

Week 1: Partitions, the exponential, and the symmetric group

  • 28 July 2025 Lecture 1: Partitions and Bratelli diagrams Draft Hand written Lecture Notes
  • 30 July 2025 Lecture 2: The binomial theorem and the exponential Draft Hand written Lecture Notes
  • 1 August 2025 Lecture 3: The symmetric group Draft Hand written Lecture Notes

Week 2: Posets, lattices and rank generating functions

  • 4 August 2025 Lecture 4: Posets and lattices Draft Hand written Lecture Notes
  • 6 August 2025 Lecture 5: The subspace lattice 𝔾(𝔽n) Draft Hand written Lecture Notes
  • 8 August 2025 Lecture 6: The subset lattice 𝕊(n), and simple refelctions in Sn Draft Hand written Lecture Notes

Week 3: Fundamental symmetric functions

  • 11 August 2025 Lecture 7: Generating functions and monomial formulas Draft Hand written Lecture Notes
  • 13 August 2025 Lecture 8: Power sums and the Cauchy-Macdonald kernel Draft Hand written Lecture Notes
  • 15 August 2025 Lecture 9: Binomial theorems Draft Hand written Lecture Notes

Week 4: Crystals

  • 18 August 2025 Lecture 10: The tensor category of crystals Draft Hand written Lecture Notes
  • 20 August 2025 Lecture 11: The irreducible crystals B(λ) Draft Hand written Lecture Notes
  • 22 August 2025 Lecture 12: Schur functions and the Weyl character formulas

Week 5: Littlewood-Richardson rule, combinatorial R-matrix, RSK, Cauchy identities, Pieri rules, and characters

  • 25 August 2025 Lecture 13: Products and restrictions and the Littlwood-Richardson rule
  • 27 August 2025 Lecture 14: The comibnatorial R-matrix, RSK and Cauchy identities
  • 29 August 2025 Lecture 15: Pieri tules and characters of the symmetric group and the Hecke algebra

Week 6: q-t-Catalan

  • 1 September 2025 Lecture 16: q-t-Catalan by Dyck paths
  • 3 September 2025 Lecture 17: ∇en and diagonal coinvariants
  • 5 September 2025 Lecture 18: Modified Macdonald polynomials and Garsia-Haiman modules

Week 7: G/B

  • 8 September 2025 Lecture 19: Generator and relations for GLn(𝔽)
  • 10 September 2025 Lecture 20: The Bruhat decomposition and the Poincare polynomial
  • 12 September 2025 Lecture 21: Schubert varieties, and Grassmannians

Week 8: Moment graphs and Kazhdan-Lusztig polynomials

  • 15 September 2025 Lecture 22: HT(G/B)
  • 17 September 2025 Lecture 23: Sheaves on moment graphs
  • 19 September 2025 Lecture 24: Kazhdan-Lusztig polynomials

Week 9: Springer fibers

  • 22 September 2025 Lecture 25: Cells in Springer fibers
  • 24 September 2025 Lecture 26: Modified Hall-Littlewood polynomials
  • 26 September 2025 Lecture 27: AFL Grand Final Eve holiday

Non-teaching week 29 September - 3 October

Week 10: Review and Student talks

  • 6 October 2025 Lecture 28: Review and Student Talks
  • 8 October 2025 Lecture 29: Review and Student Talks
  • 10 October 2025 Lecture 30: Review and Student Talks

Week 11: Review and Student Talks

  • 13 October 2025 Lecture 31: Review and Student Talks
  • 15 October 2025 Lecture 32: Review and Student Talks
  • 17 October 2025 Lecture 33: Review and Student Talks

Week 12: Reivew and Student Talks

  • 20 October 2025 Lecture 34: Review and Student Talks
  • 22 October 2025 Lecture 35: Review and Student Talks
  • 24 October 2025 Lecture 36: Review and Student Talks

Final exam

The final exam is 64% of the total mark for the course: The final exam will be to write detailed, careful, thorough notes for a 50 minute lecture on one of the topics which appears on the following list. Which topic it will be will not be disclosed until the exam begins. Possible topics for final exam

  1. Symmetric functions
  2. Tableaux and representations
  3. Presentations of the symmetric group
  4. Crystals
  5. Binomial and q-binomial theorems
  6. Schur functions and the Weyl character formula
  7. Row reduction, permutations and the Bruhat order
  8. Kazhdan-Lusztig polynomials and Hecke algebras
  9. Moment graphs
  10. Flag varieties, Grassmannians and projective space
You are encouraged to give practice talks and get feedback, in the problem session slots, in the ART seminar, personally with me by appointment, as many times and topics as you like. If you actively take advantage of these resources during the semester it should not be a problem to reconstruct the talk notes in a 3 hour exam setting. For a couple hundred examples of notes for a 50 minute lecture see my Presentations web page.

Assignments

Assignment 1: Small paper on a topic of your choice from the topic list: Length — exactly 18 pages.
A significant portion of this exercise to help teach time management. This assignment will be turned in incrementally, each submission being a revision of the previous pages and an additional page or two. All submissions should be in a pdf file, typeset using LaTeX, emailed to Arun Ram at aram@unimelb.edu.au before the appropriate deadline. No late submissions will be accepted (this is a strict time management training exercise).

  • 1 page to be turned in before noon on Friday 1 August.
  • 3 pages to be turned in before noon on Monday 4 August.
  • 4 pages to be turned in before noon on Wednesday 6 August.
  • 5 pages to be turned in before noon on Friday 8 August.
  • 6 pages to be turned in before noon on Monday 11 August.
  • 7 pages to be turned in before noon on Wednesday 13 August.
  • 8 pages to be turned in before noon on Friday 15 August.
  • 9 pages to be turned in before noon on Monday 18 August.
  • 10 pages to be turned in before noon on Wednesday 20 August.
  • 11 pages to be turned in before noon on Friday 22 August.
  • 12 pages to be turned in before noon on Monday 25 August.
  • 13 pages to be turned in before noon on Wednesday 27 August.
  • 14 pages to be turned in before noon on Friday 29 August.
  • 15 pages to be turned in before noon on Monday 1 September.
  • 16 pages to be turned in before noon on Wednesday 3 September.
  • 17 pages to be turned in before noon on Friday 5 September.
  • 18 pages to be turned in before noon on Monday 8 September.

Marking for assignment 1: You will receive 0 or 1 mark for each submission, for a total of 17 marks. I will try to provide feedback throughout, daily on each submission. The goal will be to create a manuscript that will receive high marks on the final submission, from a marker other than me. Then the final submission will be marked for quality of

  1. Delivery, presentation, format, pictures and diagrams
  2. Choice of content and explanation of context
  3. Accuracy of definitions and statements
  4. Exposition of proofs
  5. Exposition of examples
  6. Referencing and quality of mathematical writing (grammar, punctuation etc)
The marking for each of these 6 criteria will be
  • 0 not attended to
  • 1 insufficient or lacking
  • 2 OK
  • 3 well done
This will be a total of 18 marks on the final work, for a total of 17+18 = 35 total marks for Assignment 1.

Assignment 2: An improvement of someone else's submission for Assignment 1: Length exactly 15 pages + 3 page report The 3 page report should contain a detailed account of the improvement that you made to the exposition and content. You must not steal/obtain the LateX from the other student. Your paper for Assignment 2 should be typed completely and totally yourself. You may use only printed (not electronic) copies of resources from the student that wrote Assignment 1.

Once again, this assignment will be turned in incrementally. Each submission being a revision of the previous pages and an additional page. All submissions should be in a pdf file, typeset using LaTeX, emailed to Arun Ram at aram@unimelb.edu.au before the appropriate deadline. No late submissions will be accepted (this is a strict time management training exercise).

  • 1 page to be turned in before noon on Wednesday 10 September
  • 2 pages to be turned in before noon on Friday 12 September
  • 3 pages to be turned in before noon on Monday 15 September
  • 4 pages to be turned in before noon on Wednesday 17 September
  • 5 pages to be turned in before noon on Friday 19 September
  • 6 pages to be turned in before noon on Monday 22 September
  • 7 pages to be turned in before noon on Wednesday 24 September
  • 8 pages to be turned in before noon on Wednesday 1 October
  • 9 pages to be turned in before noon on Friday 3 October
  • 10 pages to be turned in before noon on Monday 6 October
  • 11 pages to be turned in before noon on Wednesday 8 October
  • 12 pages to be turned in before noon on Friday 10 October
  • 13 pages to be turned in before noon on Monday 13 October
  • 14 pages to be turned in before noon on Wednesday 15 October
  • 15 pages to be turned in before noon on Friday 17 October
  • 16 pages to be turned in before noon on Monday 20 October
  • 17 pages to be turned in before noon on Wednesday 22 October
  • 18 pages to be turned in before noon on Friday 24 October

Marking for assignment 2: You will receive 0 or 1 mark for each submission, for a total of 18 marks. Then the final submission will be marked for quality of

  1. The report explaining the improvements made
  2. improvements to delivery, presentation, format, pictures and diagrams
  3. improvements to content and explanation of context
  4. improvements to accuracy and exposition of definitions and statements and proofs
  5. improvements to examples and pictures
  6. Referencing and quality of mathematical writing (grammar, punctuation etc)
The marking for critrerion 1 will be 0-3 for thoroughness, sensitivity, professionalism, accuracy, and each of the other criteria will be marked 0-2 according to the heuristic
  • 0 not attended to
  • 1 minimally improved or not improved
  • 2 attentive improvement
This will be a total of 3+5x2 = 13 marks on the final work, for a total of 18+13 = 21 total marks for Assignment 2.

The weighted assignment mark will be (36/70)x((ass1mark)+(ass2mark)x35/21) which will account for 36% of the final mark. The other 64% of the final mark comes from the 3 hour final examination.

FAQ

Answers to some questions from feedback that has already been collected:

  1. Overall, the content of week 1 seems a bit all over the place, but maybe that's intentional?
    Yes, in my head the 3 main tenets of Discrete math are combinatorial sequences, generating functions and symmetries, and these three lectures allow me to give an honest flavour of these (Young lattice and relatives, exponential function and symmetric group). If they only get a feel the first week and then drop off, then at lest they will have gotten the real feel of our subject, and I will be grateful to have had the opportunity to show them that glimpse of its beauty. If I start with a bunch of axioms ...
  2. I'm a little worried about assignment 2 as what the student must do depends very much on what the other student has done before. Say the first student has done an excellent job on assignment 1, and there's little/no room for improvement. What is the student supposed to do for assignment 2? Or maybe I misunderstood the principle?
    I guess my music training made me believe that there is always infinite room for improvement. Otherwise there would be no more math to do or learn and no new points of view to consider, and no-one would ever write an exposition of anything that had already had an exposition written about it. In my mind, this exercise is about learning that important part of the "research" process (and writing process).

Topic suggestions for Assignment 1

  • Difference equations and q-integrals (q-analogues of exponentials, gamma functions, beta functions, hypergeometric functions)
  • Schubert polynomials
  • Characters of symmetric groups and Hecke algebras
  • Farahat-Higman
  • Springer fibers

  • Schubert calculus
  • Cauchy identities
  • Pieri rules and Littlewood-Richardson rules
  • Plane partitions
  • Latin squares

  • Representations of symmetric groups
  • Representations of GL_n(C)
  • Representations of GL_n(F_q)
  • Clifford theory and examples in from combinatorial representation theory
  • Representations of complex semisimple Lie algebras

  • Descent algebras
  • Free Lie algebras
  • Lyndon words and Hall bases
  • Grobner bases
  • Stanley-Reisner rings

  • Hecke algebras
  • Brauer algebras and BMW algebras
  • Partition algebras
  • Temperley-Lieb algebras
  • Khovanov homology

  • Reflection groups
  • Noncrossing and non nesting partitions
  • Cyclic sieving
  • Poincare-Birkhoff-Witt theorems and examples
  • Link invariants

  • Poset homology
  • Chip firing
  • Combinatorial Hodge theory
  • Kostka polynomials and Hall-Littlewood polynomials
  • Kostka-Foulkes polynomials

  • n-periodic matrices, loop Grassmanians and affine flag varieties
  • Macdonald polynomials
  • Chromatic symmetric functions
  • Spherical functions and Zonal polynomials
  • Affine Weyl groups

  • Combinatorics of Weyl groups and complex semsimple Lie algebras
  • Polya theory
  • Designs
  • Classical Hecke operators and double cosets
  • Root systems and weight lattices

  • Card shuffling
  • Combinatorial Markov chains
  • Matroids
  • Conjugacy classes via examples (symmetric groups, alternating groups, etc)
  • Alternating sign matrices

  • Mapping class groups
  • Fundamental regions for SL_2(Z) and other groups
  • Quivers, finite dimensional algebras and quiver varieties
  • Cluster algebras
  • Quiver Hecke algebras (i.e. KLR algebras)

  • Crystals for affine Lie algebras
  • Vertex models
  • Poincare polynomials for reflection groups
  • R-matrices
  • Quantum groups

  • Hall algebras
  • Plethysm coefficients
  • Kronecker coefficients
  • Aztec diamonds and other growth models
  • Littelmann paths