Course Info

Title: MAT 526: Topics in Combinatorics
Semester: Spring 2021
Credits: 3
Section: 1
Time: 9:10-10:00AM MWF
Location: AMB 207

Instructor Info

  Dana C. Ernst, PhD
  AMB 176
  MWF 1:30-2:30PM, T 1:00-2:00PM via Zoom
  dana.ernst@nau.edu
  928.523.6852
  danaernst.com

Prerequisites

MAT 226, MAT 316, and MAT 411 with grades of C or better.

Catalog Description

Topics in enumerative, algebraic, and geometric combinatorics, chosen at instructor’s discretion; may include advanced counting techniques, graph theory, combinatorial designs, matroids, and error-correcting codes.

Textbook and Course Materials

We will be using the recently published textbook Eulerian Numbers by T. Petersen (DePaul University). All other necessary material (including homework) will be made available via handouts and postings on the course webpage. You should be seeking clarification about the material whenever necessary by asking questions in class, working with our students, stopping by office hours, or emailing me. Here’s one of my favorite quotes about reading mathematics. You can find the current errata for the book here.

Don’t just read it; fight it! Ask your own questions, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? What happens in the classical special case? What about the degenerate cases? Where does the proof use the hypothesis?

Outline of Course

The tentative plan is to cover Chapters 1-6 and 11 of Eulerian Numbers, but we may cover more or less depending on time and interests. Here are the proposed topics:

  • Eulerian numbers
    • Binomial coefficients
    • Generating functions
    • Classical Eulerian numbers
    • Eulerian polynomials
    • Two important identities
    • Exponential generating function
  • Narayana numbers
    • Catalan numbers
    • Pattern-avoiding permutations
    • Narayana numbers
    • Dyck paths
    • Planar binary trees
    • Noncrossing partitions
  • Partially ordered sets
    • Basic definitions and terminology
    • Labeled posets and P-partitions
    • The shard intersection order
    • The lattice of noncrossing partitions
    • Absolute order and Noncrossing partitions
  • Gamma-nonnegativity
    • The idea of gamma-nonnegativity
    • Gamma-nonnegativity for Eulerian numbers
    • Gamma-nonnegativity for Narayana numbers
    • Palindromicity, unimodality, and the gamma basis
    • Computing the gamma vector
    • Real roots and log-concavity
    • Symmetric boolean decomposition
  • Weak order, hyperplane arrangements, and the Tamari lattice
    • Inversions
    • The weak order
    • The braid arrangement
    • Euclidean hyperplane arrangements
    • Products of faces and the weak order on chambers
    • Set compositions
    • The Tamari lattice
    • Rooted planar trees and faces of the associahedron
  • Refined enumeration
    • The idea of a $q$-analogue
    • Lattice paths by area
    • Lattice paths by major index
    • Euler-Mahonian distributions
    • Descents and major index
    • $q$-Catalan numbers
    • $q$-Narayana numbers
    • Dyck paths by area
  • Coxeter groups
    • The symmetric group
    • Finite Coxeter groups: generators and relations
    • $W$-Mahonian distribution
    • $W$-Euleria numbers
    • Finite reflection groups and root systems
    • The Coxeter arrangement and the Coxeter complex
    • Action of $W$ and cosets of parabolic subgroups
    • Counting faces in the Coxeter complex
    • The $W$-Euler-Mahonian distribution
    • The weak order
    • The shard intersection order

An ounce of practice is worth more than tons of preaching.

Rights of the Learner

As a student in this class, you have the right:

  1. to be confused,
  2. to make a mistake and to revise your thinking,
  3. to speak, listen, and be heard, and
  4. to enjoy doing mathematics.

You may encounter many defeats, but you must not be defeated.

Commitment to the Learning Community

In our classroom, diversity and individual differences are respected, appreciated, and recognized as a source of strength. Students in this class are encouraged and expected to speak up and participate during class and to carefully and respectfully listen to each other. Every member of this class must show respect for every other member of this class. Any attitudes or actions that are destructive to the sense of community that we strive to create are not welcome and will not be tolerated. In summary: Be good to each other. I would appreciate private responses to the following question: Are there aspects of your identity that you would like me to attend to when forming groups, and if so, how?

Students are also expected to minimize distracting behaviors. In particular, every attempt should be made to arrive to class on time. If you must arrive late or leave early, please do not disrupt class. Please turn off the ringer on your cell phone. I do not have a strict policy on the use of laptops, tablets, and cell phones. You are expected to be paying attention and engaging in class discussions. If your cell phone, etc. is interfering with your ability (or that of another student) to do this, then put it away, or I will ask you to put it away.

Don’t fear failure. Not failure, but low aim, is the crime. In great attempts it is glorious even to fail.

Rules of the Game

Reviewing material from previous courses and looking up definitions and theorems you may have forgotten is fair game. However, when it comes to completing assignments for this course, you should not look to resources outside the context of this course for help. That is, you should not be consulting the web, other texts, other faculty, or students outside of our course in an attempt to find solutions to the problems you are assigned. This includes Chegg and Course Hero. On the other hand, you may use each other, the textbook, me, and your own intuition. If you feel you need additional resources, please come talk to me and we will come up with an appropriate plan of action. Please read NAU’s Academic Integrity Policy.

You will become clever through your mistakes.

Homework

You are allowed and encouraged to work together on homework. However, each student is expected to turn in his or her own work. Prior to the start of class, you will need to capture your handwritten work digitally and then upload a PDF to BbLearn. There are many free smartphone apps for doing this. I use TurboScan on my iPhone. Submitting your work prior to class allows me to see what you accomplished outside of class. In general, late homework will not be accepted. However, you are allowed to turn in up to two late homework assignments with no questions asked. Unless you have made arrangements in advance with me, homework turned in after class will be considered late. When doing your homework, I encourage you to consult the Elements of Style for Proofs. On each homework assignment, please write (i) your name, (ii) name of course, and (iii) Homework number. You can find the list of assignments on the homework page. I reserve the right to modify the homework assignments as I see necessary.

Generally, the written homework assignments will be due on Mondays, but I will always tell you when a given homework assignment is due–so there should never be any confusion. Your homework will always be graded for completion and some subset of the problems will be graded for correctness. Problems that are graded for completeness will be worth 1 point. Problems that are graded for correctness will either be worth 2 points or 4 points depending on the level of difficulty. Generally, computational problems will be worth 2 points while problems requiring a formal proof will be worth 4 points. Each 4-point problem is subject to the following rubric:

Grade Criteria
4 This is correct and well-written mathematics!
3 This is a good piece of work, yet there are some mathematical errors or some writing errors that need addressing.
2 There is some good intuition here, but there is at least one serious flaw.
1 I don't understand this, but I see that you have worked on it; come see me!
0 I believe that you have not worked on this problem enough or you didn't submit any work.

To compute your score on a given homework assignment, I will divide your total points by the total possible points to obtain a percent score. Each homework assignment has the same weight. Your overall homework grade will be worth 35% of your final grade.

I write one page of masterpiece to ninety-one pages of shit.

Exams

There will be two midterm exams and a cumulative final exam. Exam 1 will be a written exam consisting of an in-class portion, and possibly a take-home portion. Exam 1 is tentatively scheduled for Friday, February 26 (week 7) and is worth 25% of your overall grade in the course. Exam 2 will be a 30-minute oral exam taken individually with me (via Zoom or in my office, depending on how the semester proceeds) sometime during the last two weeks of classes. Exam 2 will be worth 15% of your overall grade. The final exam will be on Wednesday, April 28 at 7:30-9:30AM and is worth 25% of your overall grade. The final exam may or may not have a take-home portion. If either of Exam 1 or the Final Exam have a take-home portion, you will have a few days to complete it. Make-up exams will only be given under extreme circumstances, as judged by me. In general, it will be best to communicate conflicts ahead of time.

The impediment to action advances action. What stands in the way becomes the way.

Attendance and Participation

Regular attendance is expected and is vital to success in this course, but you will not explicitly be graded on attendance. Students can find more information about NAU’s attendance policy on the Academic Policies page. You are also expected to respectfully participate and contribute to class discussions. This includes asking relevant and meaningful questions to both the instructor and your peers in class and on our Discord server.

I must not fear.
Fear is the mind-killer.
Fear is the little-death that brings total obliteration.
I will face my fear.
I will permit it to pass over me and through me.
And when it has gone past I will turn the inner eye to see its path.
Where the fear has gone there will be nothing.
Only I will remain.

Extra Credit

The only thing I will award extra credit for is finding typos on course materials (e.g., textbook, exams, syllabus, webpage). This includes broken links on the webpage. However, it does not include the placement of commas and such. If you find a typo, I will add one percentage point to your next exam. You can earn at most two percentage points per exam and at most five percentage points over the course of the semester. They’re is a typo right here.

Basis for Evaluation

In summary, your final grade will be determined by your scores in the following categories.

Category Weight Notes
Homework 35% See above for requirements
Exam 1 25% In-class portion on Friday, February 26, possible take-home portion
Exam 2 15% Individual oral exam taken during last 2 weeks of semester
Final Exam 25% Monday, November 23 at 7:30-9:30AM

It is not the critic who counts; not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, who comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who neither know victory nor defeat.

Department and University Policies

You are responsible for knowing and following the Department of Mathematics and Statistics Policies (PDF) and other University policies listed here (PDF). More policies can be found in other university documents, especially the NAU Student Handbook (see appendices) and the website of the Student Outreach and Support (SOS).

As per Department Policy, cell phones, MP3 players and portable electronic communication devices, including but not limited to smart phones, cameras and recording devices, must be turned off and inaccessible during in-class tests. Any violation of this policy will be treated as academic dishonesty.

Important Dates

Here are some important dates:

  • January 18: Martin Luther King Day (no classes)
  • January 20: Last day to drop a course without a “W”
  • March 14: Last day to drop a course without a petition
  • April 28: Final Exam (7:30-9:30AM)

Getting Help

There are many resources available to get help. First, you are allowed and encouraged to work together on homework. However, each student is expected to turn in his or her own work. You are strongly encouraged to ask questions in our Discord discussion group, as I (and hopefully other members of the class) will post comments there for all to benefit from. You are also encouraged to stop by during my office hours and you can always email me. I am always happy to help you. If my office hours don’t work for you, then we can probably find another time to meet. It is your responsibility to be aware of how well you understand the material. Don’t wait until it is too late if you need help. Ask questions!

Tell me and I forget, teach me and I may remember, involve me and I learn.

Changes to the Syllabus

Any changes to this syllabus made during the term will be properly communicated to the class.

If you want to sharpen a sword, you have to remove a little metal.


Dana C. Ernst

Mathematics & Teaching

  Northern Arizona University
  Flagstaff, AZ
  Website
  928.523.6852
  Twitter
  Instagram
  Facebook
  Strava
  GitHub
  arXiv
  ResearchGate
  LinkedIn
  Mendeley
  Google Scholar
  Impact Story
  ORCID

Current Courses

  MAT 431: Intro to Analysis
  MAT 526: Combinatorics

About This Site

  This website was created using GitHub Pages and Jekyll together with Twitter Bootstrap.

  Unless stated otherwise, content on this site is licensed under a Creative Commons Attribution-Share Alike 4.0 International License.

  The views expressed on this site are my own and are not necessarily shared by my employer Northern Arizona University.

  The source code is on GitHub.

Land Acknowledgement

  Flagstaff and NAU sit at the base of the San Francisco Peaks, on homelands sacred to Native Americans throughout the region. The Peaks, which includes Humphreys Peak (12,633 feet), the highest point in Arizona, have religious significance to several Native American tribes. In particular, the Peaks form the Diné (Navajo) sacred mountain of the west, called Dook'o'oosłííd, which means "the summit that never melts". The Hopi name for the Peaks is Nuva'tukya'ovi, which translates to "place-of-snow-on-the-very-top". The land in the the area surrounding Flagstaff is the ancestral homeland of the Hopi, Ndee/Nnēē (Western Apache), Yavapai, A:shiwi (Zuni Pueblo), and Diné (Navajo). We honor their past, present, and future generations, who have lived here for millennia and will forever call this place home.