Fall 2024 - MATH 821 G100

Combinatorics (4)

Class Number: 3867

Delivery Method: In Person

Overview

  • Course Times + Location:

    Sep 4 – Dec 3, 2024: 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 cover some of the beautiful and elegant results and techniques in combinatorial enumeration. Enumeration, simply put, is the mathematics of counting, and the course will focus on methods for counting and analyzing parameters of combinatorial objects. We will explore the interplay of combinatorics, analysis, and probability theory with a  goal of understanding how to predict the large scale behaviour of discrete objects. 

Prerequisite knowledge. 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, analysis and discrete mathematics streams in a standard undergraduate program. Specifically, I will expect you to be familiar with Taylor series manipulation of standard functions, elementary complex analysis, elementary probability, and have a basic knowledge of graphs (what they are, how they are represented, trees, etc). Although 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. 

Topics. We will learn techniques to determine the generating function of a class of combinatorial class in a systematic way and then learn how to examine the generating function in order to determine counting formulas, and ultimately distributions of basic parameters of objects, such as various tree parameters, and the expected number of parts in an integer composition. We will be able to see, somewhat analytically, why normal distributions arise very naturally in combinatorics. We will also look at two case studies: maps (a type of graph) and random walks.

The foundation is the encyclopedic text Analytic Combinatorics, (Flajolet and Sedgwick 2009), but we will approach the subject using Analytic Combinatorics: A Multidimensional Approach (Mishna 2019) and Course Notes.  PDF versions of all texts will be provided to students. 

Project. There will be a project comprising a 10-12 page report and a poster presentation on a topic related to the course, ideally tailored to the interests of the student.

Grading

  • 4 Assignments (10% each) 40%
  • Project (document and poster presentation) 30%
  • Final Exam 30%

NOTES:

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:

MATH 821 Course notes


P. Flajolet, R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009 Online access via SFU Library


M. Mishna, Analytic Combinatorics: A Multidimensional Approach, Chapman and Hall/CRC, 2019 Online access via SFU Library


RECOMMENDED READING:

M. Aigner, A Course in Enumeration, Springer-Verlag (GTM series), 2007. Online access via SFU Library


H. Wilf, generatingfunctionology, Academic Press, 1994. Online access via the author's website

R.P. Stanley, Enumerative Combinatorics, Volume 2, Cambridge University Press. Online access via SFU Library

M. Bona, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific Publishing Co., 2011. Available at W.A.C. Bennett Library (Burnaby) Stacks (QA 164 B66 2011) 

A. Camina and B. Lewis, An Introduction to Enumeration, Springer, 2011 Online access via SFU Library

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

RELIGIOUS ACCOMMODATION

Students with a faith background who may need accommodations during the term are encouraged to assess their needs as soon as possible and review the Multifaith religious accommodations website. The page outlines ways they begin working toward an accommodation and ensure solutions can be reached in a timely fashion.