MATH 21-301 Combinatorics - Fall 2020

Course info:

Details:	Course syllabus
Class:	MWF 1:20-2:10pm on Zoom
Instructors:	Alan Frieze    @: alan (random.math.cmu.edu )
	Kaave Hosseini    @: kaavehosseini (cmu.edu)
Office hours:	Thursdays 1-2:40pm
TA:	Zimu Xiang @:zimux (andrew.cmu.edu )

Course description:

The purpose of this course is to introduce a few important tools in combinatorics. These tools have a wide range of spectacular applications in Mathematics and Computer Science. Most of the motivating problems we discuss here are about sets and graphs. The course is divided to two parts. Part one is taught by Kaave Hosseini and Part two by Alan Frieze. A rough outline of the course is as follows.

Outline:

Part 1:
	Basic techniques (inclusion-exclusion, double counting, pigeon-hole principle)
	Extremal graph theory
	Cauchy Schwarz and 4-cycle counting
	Basic Probabilistic Combinatorics and Ramsey Theory
	Linear Algebraic techniques in Combinatorics
Part 2:
	Advanced Probabilistic combinatorics: Chernoff's bound and Lovasz Local Lemma
	Poset theory
	Combinatorial Games
	Generating functions
	Polya theory

Class format:

The lectures will be presented online over Zoom. Attendance is not mandatory but highly encouraged. The lectures will be recorded and their link will be uploaded on Piazza.

Prerequisits:

You should be comfortable with linear algebra, basics of discrete mathematics and graph theory, and discrete probability. More importantly, a high degree of mathematical maturity and ability to understand and write rigorous proofs is necessary.

Homework:

Homework assignments will be posted on Piazza. There will be a new homework almost every week. Homework assignments can be solved individually, or in groups of 2 or 3 (you can form a different group for every assignment). However, every individual should write their own solution several hours after group discussions, and list their group members. It’s encouraged to type your solutions in LATEX, however, clear and legible hand-written solutions are also accepted. You should upload your homework to Gradescope before its due date.

Online Platforms:

Piazza: We use Piazza platform as a discussion environment. Students are welcome to ask/answer questions. Here is the sign-up link.
Gradescope: Grade scope is used to grade homeworks and exams. You can use the "regrade" feature of gradescope to ask for a regrade.

Lecture notes:

Will be gradually updated and uploaded in the Resources section of Piazza.

Exams:

Resources:

Extremal Combinatorics	Stasys Jukna
Techniques in combinatorics	Timothy Gowers
Linear algebra methods in combinatorics	László Babai and Péter Frankl