University of Connecticut College of Liberal Arts and Sciences
Department of Mathematics
Tom Roby's Math 3094 Home Page (Fall 2013)
Algebraic Combinatorics (Math Scholars)

Questions or Comments?

Class Information

COORDINATES: Classes meet Tuesdays and Thursdays 12:30–1:45 in MSB 215. The registrar calls this Section 001, #8222.

PREREQUISITES: MATH 2710 or MATH 2142 and consent of instructor.

TEXT: Richard P. Stanley: Algebraic Combinatorics: Walks, Trees, Tableaux, and More. A list of errata for this edition is available here. You may find the exposition to be terse in places, but it's an essential skill to learn how fill in details you don't immediately understand. Feel free also to ask your classmates or me about any places you get stuck. In particular, be sure you can answer all the various "[Why?]"s that show up in the text.

WEB RESOURCES: The homepage for this course is I may list some others resources below.

SOFTWARE: In most areas of mathematics it is frequently helpful to use computer software to explore examples, search for patterns, or test conjectures. For combinatorics in particular, one of the best software packages is the free open-source computer algebra system called Sage. There are many built-in commands and examples one can use to quickly play around with combinatorial objects without having to build them from scratch, and the large community of users and developers is continually documenting, improving, and helping others get up to speed on the software. Sage also provides a full-fledge programming environment via the Python programming language.

Our sysadmin has provided a local copy of the downloads for Sage.

GRADING: Your grade will be based on homework assignments, a midterm exam, and a final project or exam (TBD).

The breakdown of points is:

HW Midterm Final
35% 30% 35%

EXAMS: Will cover all the material up to that point in the term. It is currently scheduled for 5 November 2013 during our usual class meeting. Please let me know immediately if you have a conflict with this date. There are no makeup exams. If we have a in-class final exam (TBD), it will be scheduled for 10:30-12:30 on FRIDAY 13 December. In lieu of a final exam, students will be doing projects instead.

HOMEWORK: Homework will be assigned most weeks, and should be attempted by the following TUESDAY, when I will be happy to answer questions or provide hints. It will generally be due Thursdays at the start of class. Since I may discuss the homework problems in class the day they are due, late assignments will be accepted only under the most extreme circumstances. (Please let me know as soon as possible if you find yourself with a situation that might qualify.) The lowest written homework score will be dropped in any event.

PROJECTS: are described in the link. Please select your research topics by 10 October. First drafts of papers are due 12 14 November. Presentations will start shortly thereafter after Thanksgiving break.

You may find some homework problems to be challenging, even frustrating, leading you to spend lots of time and effort working on them. This is a natural part of doing mathematics, faced by everyone from school children to top researchers. I encourage you to work with other people in person or electronically. It's OK to get significant help from any resource, but in the end, please write your own solution in your own words. Copying someone else's work without credit is plagiarism and will be dealt with according to university policy. It also is a poor learning strategy.

ACADEMIC INTEGRITY: Please make sure you are familiar with and abide by The Student Code governing Academic Integrity in Undergraduate Education and Research. For quizzes and exams you may not discuss the material with anyone other than the instructor or offical proctor, and no calculators, phones, slide rules or other devices designed to aid communication or computation may be used unless otherwise specifically indicated on the exam.

ACKNOWLEDGEMENTS: Many people have influenced my approach to this material, particularly Richard Stanley, Gian-Carlo Rota, and many of my research collaborators.

CONTENT: Combinatorics is related to the word "combinations", and much of the field deals with counting problems ("enumeration"). More broadly combinatorics considers discrete structures such as graphs (as opposed to the continuous structures considers in calculus and analysis), and questions that go beyond simply counting the number of possibilities. With the advent of computers in the second half of the last century, such questions have become increasingly important in applications as well as more managable to solve.

This particular class will focus on algebraic combinatorics, where one uses techniques from linear or abstract algebra to study combinatorial objects (and sometimes vice-versa). In particular, I hope to cover the following topics from the text:

  • Walks in Graphs, including complete graphs and cubes;
  • Random Walks;
  • The Sperner property in Posets;
  • Group Actions on Boolean Algebras;
  • Young Diagrams and q-binomial coefficients;
  • Enumeration Under Group Actions;
  • Young Tableaux;
  • The Matrix-Tree Theorem;
  • Eulerian Digraphs;
  • Miscellaneous Gems of Algebraic Combinatorics; and
  • Other topics according to student interest, as time permits.

ACCESSIBILITY & DISABILITY ISSUES: Please contact me and UConn's Center for Students with Disabilities as soon as possible if you have any accessibility issues, have a (documented) disability and wish to discuss academic accommodations, or if you would need assistance in the event of an emergency.

LEARNING: The only way to learn mathematics is by doing it! Complete each assignment to the best of your ability, and get help when you are confused. Come to class prepared with questions. Don't hesitate to seek help from other students. Sometimes the point of view of someone who has just figured something out can be the most helpful.

Especially for learning this subject, it is important to do lots of problems—many more than I could reasonably assign you to hand in. The text's exposition is condensed in places, and you will probably need to stop and think about why a certain statement is true. The author sometimes flags such intentional gaps with "[Why?]", and you should make a serious attempt to answer this before moving on.

CLASSTIME: We will sometimes spend classtime doing things in groups, presenting mathematics to one another, or having interactive discussions. There will not be time to "cover" all material in a lecture format so you will need to read and learn some topics on your own from handouts, web sources, or otherwise.

SCHEDULE: The following is a the start of a tentative schedule that I will update throughout the semester. If you have a religious observance that conflicts with your participation in the course, please meet with me within the first two weeks of the term to discuss any appropriate accommodations.

Date Section Topics HW, etc.
8/27 T Ch. 1 Intro to Alg. Combinatorics & Sage HW #1 assigned (see below)
8/29 R Ch. 1 Walks on Graphs & Eigenvalues Bring laptops for Sage install
9/3 T Ch. 1 Closed Walks & Complete Graphs Questions on HW #1
9/5 R Ch.1 Problems \& Block matrices HW #1 due
9/10 T Ch. 2 Walks in the cube graph
9/12 R Ch. 2 Discrete Radon Transform
9/17 T Ch. 2 Discrete Radon Transform HW #2 due
9/19 R Ch. 3 Random Walks on Graphs
9/24 T Ch. 3 Random Walks on Graphs
9/26 R Ch. 12, 4 Oddtown & Posets Basics HW #3 due
10/1 T Ch. 4 Sperner Property in Posets HW #3 due
10/3 R Ch. 4 Spernerity of Boolean Algebras
10/8 T Ch. 4 Spernerity of Boolean Algebras
10/10 R Ch. 5 Group Actions on Posets
10/15 T Ch. 5 Group Actions on Boolean Algebras HW#4 due
10/17 R Ch. 5 Group Actions on Boolean Algebras
10/22 T Ch. 6 Partitions and Young Diagrams
10/24 R Ch. 6 Spernerity of L(m,n)
10/29 T Ch. 8 Young Tableaux
10/31 R Ch. 8 Down & Up operators
11/7 R Work on Class Projects
11/12 T Ch. 8 Oscillating Walks in Young's Lattice
11/19 T Ch. 8 Robinson-Schensted-Knuth correspondence First drafts of papers due
11/21 R Ch. 8 Enumeration of Plane Partitions
12/3 T John P. & Brian M.
12/5 R Tim C., Nicole B., Junyu C. Written papers (for projects) due
FRIDAY 13 DECEMBER 10:30-12:30: Tim S., Nikhil S., Eric R., Jessica H.

Web Resources

Anonymous Feedback (Currently disabled)

Use this form to send me anonymous feedback or to answer the question: How can I improve your learning in this class?  I will respond to any constructive suggestions or comments in the space below the form. 

Feedback & Responses

  1. This is a test.

    This is only a test.



Here are the homework assignments:

UConn The Web People