CS388C: Combinatorics and Graph Theory (Fall 2019)

Syllabus: Syllabus.
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: GDC 4.508
Phone: 471-9729
Office Hours: TTh 3:30 - 4:30
TA: Yan Zheng
Email: yanzheng@utexas.edu
Office (for office hours): TA Station (GDC 1.302), Desk 2
Office Hours: MW 5:00 - 6:00.
Required Text: Stasys Jukna, Extremal Combinatorics, with applications in computer science (2nd edition)
Optional Texts: N. Alon and J. H. Spencer, The Probabilistic Method ( ebook available with UT EID)
L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, with applications to geometry and computer science
V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory
L. Guth, Polynomial Methods in Combinatorics
S. Vadhan, Pseudorandomness survey/monograph.
J.H. van Lint and R.M. Wilson, A Course in Combinatorics
Useful References: Richard Stanley's Twelvefold Way for balls in bins.
Scribe notes containing Shannon's counting argument for the existence of functions with large circuit complexity
Salil Vadhan's monograph on pseudorandomness contains chapters on expander graphs and randomness extractors.
S. Hoory, N. Linial, and A. Wigderson, Expander Graphs and Their Applications, a survey.
Excerpts from L. Guth, Polynomial Methods in Combinatorics includes Nikodym sets on pages 11-12.
J.A. Grochow, New applications of the polynomial method: The cap set conjecture and beyond
Lecture notes from my class includes pseudorandomness, codes, expanders, and more.
My four-part tutorial on Extractors and Expanders at the Simons Institute.
My slides on randomness extractors.
Final Exam: The final exam will be held on Wednesday, December 18 from 2:00 pm-5:00 pm in GDC 5.302. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary). If you're taking the course pass/fail, then you do not need to take the final exam. Instead, I will count your homework grade as your final exam grade.

Last modified: December 5, 2019.