CS388C: Combinatorics and Graph Theory (Spring 2023)

Logistics: MW 2:00 - 3:30, GDC 1.406 (in person only)
Unique Number: 52530
Course web page: http://www.cs.utexas.edu/~diz/388C
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: GDC 4.508
Phone: 512-471-9729
Office Hours: MTh 3:30 - 4:30
TA: Vinayak Kumar
Email: vmkumar@utexas.edu
Office Hours: TuF 3:30 - 4:30 in GDC 1.302, Desk 5.
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
L. Guth, Polynomial Methods in Combinatorics
S. Vadhan, Pseudorandomness survey/monograph
J.H. van Lint and R.M. Wilson, A Course in Combinatorics
Y. Zhao, Graph Theory and Additive Combinatorics
Videos of my lectures on Extractors and Expanders at the Simons Pseudorandomness Boot Camp.
Content: This graduate course is an introduction to combinatorics and graph theory. We will survey a variety of topics, emphasizing those methods relevant to computer science. One underlying theme will be that it is often not hard to use the probabilistic method to show the existence of useful combinatorial objects; we will have to work harder to give efficient deterministic constructions of these objects. Often our objects of interest will be pseudorandom, in the sense that they are fixed, deterministic objects with random-like properties. A related theme will be the interplay between structure and randomness.

This course should be similar to the 2019 version of the course. A tentative list of topics follows.

Topic Reference Approximate Time
Counting and Probability Jukna, Chapters 1, 3 1 week
Ramsey Theory Jukna, Chapters 4, 25, 26 1 week
Probabilistic Method Jukna, Chapters 18-20 1-2 weeks
Graph Regularity Zhao, Chapter 2 1 week
Linear Algebra Method Jukna, Chapters 13-14 1-2 weeks
Expander Graphs Jukna, Chapter 15 1-2 weeks
Random Walks Jukna, Chapter 23 1 week
Designs Jukna, Chapter 12 1 lecture
Codes Jukna, Chapter 17 2 weeks
Polynomial Method Jukna, Chapter 16 1-2 weeks
Additive Combinatorics Jukna, Sections 25.3, 25.4 1 week
Randomness Extractors Vadhan, Chapter 6 1-2 weeks

Prerequisites: Graduate standing or consent of instructor. Many students find this course difficult, so a first-rate math background is highly recommended. See the Review Sheet for material you're expected to know. In particular, a strong knowledge of elementary probability is essential. For students wishing to review probability, I recommend the first two chapters (except Section 2.6) of
R. Meester, A Natural Introduction to Probability Theory.
See also Section 3.1 of the text.

Equally important are problem-solving skills, an understanding of elementary proof techniques, and knowledge of basic counting. For general problem-solving and proof techniques, I recommend Chapters 2 and 3 of
P. Zeitz, The Art and Craft of Problem Solving,
and for basic counting I recommend Sections 6.1 and 6.2 of the same book. See also Section 1.1 of the text.

Familiarity with finite fields is extremely useful. We will also use some elementary linear algebra, succinctly reviewed in Section 13.1 of the text.

Students outside of computer science should be familiar with the notion of polynomial-time computability, e.g., by reading Section 1.1 of C. Papadimitriou, "Computational Complexity." Alternatively, you can read Chapters 1-3.4 of Avi Wigderson's book Mathematics and Computation.

Grading: 50%: Homework
50%: Final exam
Final Exam: The final exam will be held on Saturday, April 29, from 1:00 pm - 3:00 pm in RLP 1.104. 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 credit/NC and scored at least 60% on the homework, then you can pass the course without taking the final exam.
Homework
policy:
Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web.

Submission policy: Each student has two late days that they can use during the semester with no penalty (one assignment two days late, or two assignments one day late). Once late days are used up, no credit will be given for late assignments. A day here means 24 hours. The weekend doesn't count, so Friday to Monday counts as one day. I may not allow late days for certain assignments.
Canvas: We will use Canvas, which contains Ed Discussion. Homeworks and grades will be posted on Canvas. We will use Ed Discussion for class discussion. Instead of emailing questions to the teaching staff, please post your question to Ed Discussion.
Laptops/Phones: The use of laptops and mobile devices is generally prohibited, but I will allow the use of tablets if you use them only for class-related purposes. All phones must be silenced.
Students with
Disabilites:
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.
Additional Class
Policies

This class will follow the standard policies described in the CS Department Code of Conduct.

Last modified: January 16, 2023.