Instructor: Swastik
Kopparty (swastik.kopparty@rutgers.edu)
Class Time and Place: Mondays and
Wednesdays 1:40 to 3:00, in Hill 423
Office Hours: Wednesday 3:30-4:30
(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 September 24)
·
Homework 2 (due October 22)
·
Homework 3 (due November 19)
·
Homework 4 (due December 5)
Lecture Schedule
·
September
5: course overview, basic counting problems
·
September
10: linear recurrences, the twelvefold way, Stirling
numbers
·
September
12: Catalan numbers, generating function nuggets
·
September
17: theory of exponential generating functions
·
September
19: permutations
·
September
24: partitions of an integer (notes)
·
September
26: set systems, Hall’s theorem, posets, Dilworth’s
theorem
·
October
1: Sperner’s theorem, LYM inequality, Erdos-Ko-Rado 1
·
October
3: Erdos-Ko-Rado 2, Littlewood-Offord
·
October
8: compressions, Kruskal-Katona
·
October
10: vertex and edge isoperimetry in {0,1}n
(notes)
·
October
15: Ramsey theory
·
October 17: Class
cancelled (makeup class at the end of the semester)
·
October
22: the probabilistic method, linearity of expectation, alterations
·
October
24: Turan’s theorem, Turan
number for C4, the projective plane
·
October 29: NO CLASS
(Hurricane)
·
October 31: NO CLASS
(Hurricane’s aftermath)
·
November
5: linear algebraic methods, few-distance sets, restricted intersections
·
November
7: modular intersections, geometric applications
·
November 12: Class
cancelled (makeup class at the end of the semester)
·
November 14: Class
cancelled (makeup class at the end of the semester)
·
November
19: projections of set systems, Sauer-Shelah lemma,
VC dimension
·
November 21: NO CLASS
(Friday Schedule)
·
November
26: the second moment
·
November
28: entropy, Shearer’s lemma, Bregman’s theorem
·
December
3: the Lovasz local lemma
·
December
5: discrepancy
·
December
10: Baranyai’s theorem (notes)
·
December
12: sunflowers and miscellaneous gems
·
December 13 (1pm –
4pm, Hill 423): Makeup marathon
§ introduction to additive
combinatorics: van der Waerden’s theorem, Roth’s
theorem, Schur’s theorem, Sidon sets, Cauchy-Davenport
theorem
§ topological methods: Borsuk-Ulam theorem, Kneser’s
conjecture