CS388C: Combinatorics and Graph Theory (Fall 2019)

Logistics: TTh 2:00 - 3:30
GDC 2.210
Unique Number: 50675
Course web page: http://www.cs.utexas.edu/~diz/388C
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: GDC 4.508
Phone: 471-9729
Office Hours: TBD
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. This should be similar to the 2014 version of the course.
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.
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. Finally, we will use some elementary linear algebra. This is succinctly reviewed in Section 13.1 of the text. Succinct review of the other topics above are available in the text in Sections 1.1 and 3.1. 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.

Last modified: April 24, 2019