## CS388C: Combinatorics and Graph Theory (Spring 2014)

 Logistics: TTh 2:00 - 3:30 GDC 2.210 Unique Number: 54000 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. 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" 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 course should be similar to the 2007 version. 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 14.1 of the text. Succinct review of the other topics above are available in the text in Sections 1.1, 17.1, and 17.2. 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." 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.