Instructor: Swastik
Kopparty (__swastik.kopparty@rutgers.edu__)

Class Time and Place: Tuesdays and
Thursdays 1:40 to 3:00, in Hill 423

Office Hours: Mondays 3pm-4pm (Hill
432)

Prerequisites: Basic linear
algebra, some discrete probability and mathematical maturity.

Reference books: Enumerative
Combinatorics (Stanley), The Probabilistic Method (Alon
& Spencer), Extremal Combinatorics (Jukna), A
Course in Combinatorics (van Lint and Wilson).

__Syllabus__

We will study basic
topics in Combinatorics, including enumeration, symmetry, polyhedral
combinatorics, partial orders, set systems, Ramsey theory, discrepancy,
additive combinatorics and quasirandomness. There
will be emphasis on general techniques, including probabilistic methods,
linear-algebra methods, analytic methods, topological methods and geometric
methods.

There will be problem sets every
2-3 weeks. There are no exams.

__Homework__

·
Homework 1 (due October 3)

·
Homework 2 (due October 26)

·
Homework 3 (due November 16)

·
Homework 4 (due December 12)

__Lecture Schedule__

·
September
5: basic counting problems, the twelve-fold way, inclusion-exclusion

·
September
7: Stirling numbers, linear recurrences, generating
functions

·
September
12: Bell numbers, Catalan numbers

·
September
14: more Catalan numbers

·
September
19: exponential generating functions, exponential formula

·
September
21: partitions of an integer

·
September
26: set systems, Hall’s theorem, posets, Dilworth’s
theorem

· September 28: the max-flow min-cut
theorem

· October 3: Class Cancelled (Makeup
class to be scheduled)

· October 5: Class Cancelled (Makeup
class to be scheduled)

· October 10: Sperner’s
theorem, Littlewood-Offord, Erdos-Ko-Rado

· October 12: Erdos-Ko-Rado
2, introduction to isoperimetric theorems

· October 17: Kruskal-Katona

· October 19: Kruskal
Katona continued, Harper’s theorem

· October 24: Katona’s
intersection theorem, Ramsey theorem

· October 26: Ramsey theorem
continued

· October 31: the probabilistic
method

· November 2: linearity of
expectation

· November 7: alterations

· November 9: the second moment method

· November 14: more application of
probabilistic methods

· November 16: the Lovasz Local Lemma

· November 21: introduction to linear
algebraic methods, Fisher’s inequality

· November 23: NO CLASS
(Thanksgiving)

· November 28: two-distance sets, Ray
Chaudhuri Wilson inequality

· November 30: Frankl Wilson
inequality, geometric applications

· December 5: more applications

· December 7: VC dimension, Sauer-Shelah Lemma epsilon-nets

· December 12: discrepancy