Combinatorial Analysis

Course Information

Main Objective of the Course:

1. Exposure to Extremal, Probabilistic and Enumerative Combinatorics
2. Role/use of probability, analysis and algebra in combinatorics

Textbook:

No required text, but a few are recommended on this page

HWs, Tests and Final:

1. Homeworks will be collected and graded.
2. Tests and the Final Exam are OPEN NOTES only. All students are expected to comply with the Georgia Tech Honor Code

Schedule

• Jan 7 Overview of the course

  Examples from Extremal Combinatorics

• Jan 9 Overview and Introduction (contd.)

  Property B, Probabilistic Method

• Jan 11 Mantel's theorem, R(3,3)

• Homework 1 (Due: Jan. 18th)
• Jan 14 Binomial coefficients and identities

  Combinatorial Proofs Handout 1

• Jan 18 Lucas theorem, "soup can" problems

• Homework 2 (Due: Jan. 30th)
• Jan 23 Probabilistic Method: Szele's theorem, Ramsey number lower bound

• Jan 25 Probabilistic Method (contd.): Ramsey upper bound, van den Waerden, Turan bounds

• Jan 28 Probabilistic Method (contd.): Zarankiewicz problem and Deletion Method

• Jan 30 Alterations: Bound on dominating sets, Hamming code

• Feb 1 Generating Functions: Catalan and Bell numbers

• Supplement 1 (For Practice Only)
• Feb 11 TEST 1

  Copy of Test 1

• Feb 18 Polyominoes, Conclusion of Gen. Fns.

• Feb 20 Inclusion-Exclusion: Derangements, Euler Phi Fn, Mobius Fn.

• Homework 3 (Due: March 6th)
• Feb 27 Counting binary bracelets, Burnside's Lemma

• Mar 1 Lovasz Local Lemma and Applications

• Mar 4 Local Lemma (contd.)

• Mar 6 Hall's Theorem and Birkoff's Theorem

• Mar 8 Min Max Theorems

• Mar 13 Konig-Egervary and Sperner Theorems

• Homework 4 (Due: March 27th)
• Mar 15 Matchings, Sunflowers

• 18-22 Sunshine and real flowers: Spring Break

• Mar 25 Sunflower Lemma and Some Exercises

• Supplement 2 (For Practice Only)
• Mar 27 Intersecting Families and Erdos-Ko-Rado