Simon Fraser University
Engaging the World

Course Outlines

Fall 2020 - MATH 821 G100

Combinatorics (4)

Class Number: 2834

Delivery Method: Remote

Overview

  • Course Times + Location:

    Sep 9 – Dec 8, 2020: Tue, 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 be delivered online. You are expected to have access to a reliable internet connection. You will need a computer from which you can download course materials and activities and watch live and/or recorded lectures and participate in live tutorials or workshops.

You will need a camera to take photographs of your work. A phone is acceptable.


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:

Access to highspeed internet, webcam.

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.

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 web site 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

TEACHING AT SFU IN FALL 2020

Teaching at SFU in fall 2020 will be conducted primarily through remote methods. There will be in-person course components in a few exceptional cases where this is fundamental to the educational goals of the course. Such course components will be clearly identified at registration, as will course components that will be “live” (synchronous) vs. at your own pace (asynchronous). Enrollment acknowledges that remote study may entail different modes of learning, interaction with your instructor, and ways of getting feedback on your work than may be the case for in-person classes. To ensure you can access all course materials, we recommend you have access to a computer with a microphone and camera, and the internet. In some cases your instructor may use Zoom or other means requiring a camera and microphone to invigilate exams. If proctoring software will be used, this will be confirmed in the first week of class.

Students with hidden or visible disabilities who believe they may need class or exam accommodations, including in the current context of remote learning, are encouraged to register with the SFU Centre for Accessible Learning (caladmin@sfu.ca or 778-782-3112).