Course Info

Title: MAT 526: Topics in Combinatorics
Semester: Fall 2016
Credits: 3
Section: 1
Time: MWF at 11:30-12:20AM
Location: AMB 207

Instructor Info

  Dana C. Ernst, PhD
  AMB 176
  10:15-11:15 MWF and 9-10 TTh (or by appointment)
  dana.ernst@nau.edu
  928.523.6852
  dcernst.github.io/teaching/mat526f16

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. Letter grade only.

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

Learning Management System

We will make limited use of Bb Learn this semester, which is Northern Arizona University’s default learning management system (LMS). Most course content (e.g., syllabus, course notes, homework, etc.) will be housed here on our course webpage that lives outside of BbLearn.

Homework

You are allowed and encouraged to work together on homework. Yet, each student is expected to turn in their own work. In general, late homework will not be accepted. However, you are allowed to turn in one late homework assignment with no questions asked. Unless you have made arrangements in advance with me, homework turned in after class will be considered late.

Generally, the written homework assignments will be due on Wednesdays, 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 25% of your final grade. If you utilize any resources other than our textbook or course notes, I expect you to cite your sources. Better yet, try to complete your homework without relying on external resources.

Exams

There will be 3 midterm exams and a cumulative final exam. Exam 1 and Exam 2 will be written exams and may include a take-home portion. These exams are tentatively scheduled for Friday, October 7 and Friday, November 18, respectively, and each is worth 20% of your overall grade. Exams 1 and 2 are likely to have take-home components. Exam 3 will be an oral exam taken individually in my office. The questions for the oral exam will predominately come from homework problems. Exam 3 will last roughly 30 minutes. Your score on Exam 3 together with your performance on the presentation of in-class theorems (see below) will be worth 10% of your overall grade. Students will schedule to take Exam 3 during December 5-15. The final exam will be on Wednesday, December 14 at 10:00-12:00 and is worth 25% of your overall grade. 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.

Presentations

A couple times each week, I will ask individuals to prepare the proof of a theorem, or possibly a detailed description of an example, that will be presented to the class. You are allowed to consult outside resources when preparing for these presentations (but you should cite your sources). The goal will be for each student to present 2-3 times. All presentations will be graded using the rubric below.

Grade Criteria
4 Completely correct and clear proof or solution. Yay!
3 Proof has minor technical flaws, some unclear language, or lacking some details. Essentially correct.
2 A partial explanation or proof is provided but a significant gap still exists to reach a full solution or proof.
1 Minimal progress has been made that includes relevant information & could lead to a proof or solution.
0 You were completely unprepared.

Your overall performance during presentations together with your score on Exam 3, will be worth 10% of your overall grade.

Basis for Evaluation

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

Category Weight
Homework 25%
Exam 1 (written) 20%
Exam 2 (written) 20%
Exam 3 (oral) and Presentations 10%
Final Exam 25%

Grade Determination

In general, you should expect the grades to adhere to the standard letter-grade cutoffs:

A 100-90%, B 80-89%, C 70-79%, D 60-69%, F 0-59%.

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 Office of Student Life.

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.

Class Etiquette

Students are expected to treat each other with respect. Students are also expected to promote a healthy learning environment, as well as minimize distracting behaviors. In particular, you should be supportive of other students while they are making presentations. Moreover, 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.

Important Dates

Here are some important dates:

  • Monday, September 5: Labor Day (no classes)
  • Thursday, September 8: Last day to drop/add (no W appears on transcript)
  • Friday, November 4:: Last day to withdraw from a course (W appears on transcript)
  • Friday, November 11: Veteran’s Day (no classes)
  • Thursday, November 24-Friday, November 25: Thanksgiving Holiday (no classes)
  • Wednesday, December 14: Final Exam

Changes to the Syllabus

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


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 226: Discrete Math
  MAT 690: CGT

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 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.