Simon Fraser University
Engaging the World

Course Outlines

Fall 2022 - MATH 821 G100

Combinatorics (4)

Class Number: 4152

Delivery Method: In Person

Overview

  • Course Times + Location:

    Sep 7 – Dec 6, 2022: Tue, 10:30 a.m.–12:20 p.m.
    Burnaby

    Sep 7 – Dec 6, 2022: Thu, 10:30 a.m.–12:20 p.m.
    Burnaby

Description

CALENDAR DESCRIPTION:

An introduction to the theory of incidence structures (finite geometries, block designs) and their relation to linear codes. Algebraic techniques - finite group actions, orbit enumeration, generation of orbit representatives. Exact and asymptotic enumeration of labelled and unlabelled structures.

COURSE DETAILS:

This course will cover some of the beautiful and elegant results and techniques in combinatorial enumeration. Enumeration, simply put, is the study of counting, and the course will focus on methods for counting combinatorial objects. I will not assume you have any specific knowledge of this subject. However, I will assume that you are familiar with material from the basic algebra, calculus and discrete mathematics streams in a standard undergraduate program. Specifically, I will expect you to be familiar with basic group theory, linear algebra, Taylor series manipulation of standard functions, and have a basic knowledge of graphs (what they are, how they are represented, trees, etc), generating series and other combinatorial objects. While there are no specific prerequisites, I will assume you have the mathematical sophistication expected of a graduate student, and be able to familiarize yourself with the above basics if you have not yet encountered them.

My hope is that we will roughly (more or less) cover Chapter 1, Chapter 2 (part of), Chapter 3, parts of Chapter 5, and, with some luck, parts of Chapter 8. Roughly, our plan will be the following:

  • We will review some basic ideas fundamental concepts in counting (binomial theorem, the decomposition of binomial numbers etc), as well as basic combinatorial polynomials and their combinatorial interpretation (the Stirling numbers).
  • We will cover partitions and their generating series.
  • We will quickly cover the basics of formal power series, combining them, and discussing when a power series has an inverse.
  • We will cover generating series and their applications to solving recursion equations, finding closed forms for sums and applications to counting various objects.
  • We will cover inclusion-exclusion, the involution principle, the beautiful theorems known Gessel-Viennot-Lindstr¨om Cancellation and (maybe) Tutte’s Matrix Theorem.
  • If time permits, we will cover the basics of symmetric functions.

Grading

  • 6 Assignments (10% each) 60%
  • Final Exam 40%

NOTES:

The assignments will be given out at the end of each odd week of the semester, except the final week, and be due two weeks later (dates are approximate here). The date of the final exam will be announced during the semester.

Instructor reserves the right to make modifications to the outline.

REQUIREMENTS:

This course is delivered in person, on campus. Should public health guidelines recommend limits on in person gatherings, this course may include virtual meetings. As such, all students are recommended to have access to strong and reliable internet, the ability to scan documents (a phone app is acceptable) and access to a webcam and microphone (embedded in a computer is sufficient). 

Materials

REQUIRED READING:

The required text for this course will be the first in the list of recommended texts below, written by Aigner. I will be following this book closely, but may introduce some extra examples throughout the course. I will distribute notes only when I think a topic isn’t adequately covered in the text.

RECOMMENDED READING:

  • M. Aigner, A Course in Enumeration, Springer-Verlag (GTM series), 2007. E-Text available at SFU library.
  • H. Wilf, generatingfunctionology, Academic Press, 1994. Freely available online from the author’s website.
  • R.P. Stanley, Enumerative Combinatorics, Volumes 1 & 2, Cambridge University Press. E-text available for both Volumes 1 & 2 at SFU library.
  • I.P. Goulden and D. M. Jackson, Combinatorial Enumeration, J. Wiley, New York, 1983 (Dover Reprint, 2004).
  • M. Bona, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific Publishing Co., 2011.
  • A. Camina and B. Lewis, An Introduction to Enumeration, Springer, 2011. E-Text available at SFU library.
Texts above not available online are on reserve at SFU library Burnaby campus.

REQUIRED READING NOTES:

Your personalized Course Material list, including digital and physical textbooks, are available through the SFU Bookstore website by simply entering your Computing ID at: shop.sfu.ca/course-materials/my-personalized-course-materials.

Graduate Studies Notes:

Important dates and deadlines for graduate students are found here: http://www.sfu.ca/dean-gradstudies/current/important_dates/guidelines.html. The deadline to drop a course with a 100% refund is the end of week 2. The deadline to drop with no notation on your transcript is the end of week 3.

Registrar Notes:

ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS

SFU’s Academic Integrity website http://www.sfu.ca/students/academicintegrity.html is filled with information on what is meant by academic dishonesty, where you can find resources to help with your studies and the consequences of cheating. Check out the site for more information and videos that help explain the issues in plain English.

Each student is responsible for his or her conduct as it affects the university community. Academic dishonesty, in whatever form, is ultimately destructive of the values of the university. Furthermore, it is unfair and discouraging to the majority of students who pursue their studies honestly. Scholarly integrity is required of all members of the university. http://www.sfu.ca/policies/gazette/student/s10-01.html