CS388C: Combinatorics and Graph Theory (Fall 2007)

Logistics: TTh 11-12:30
TAY 3.144
Unique Number: 56780
Course web page: http://www.cs.utexas.edu/~diz/388C
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: TAY 3.134
Phone: 471-9729
Office Hours: WF 2:30-3:30, or by appointment.
TA: Xin Li
Email: lixints@cs.utexas.edu
Office (for office hours): ENS 31NQ Desk #1
Office (for all other purposes): TAY 3.108
Phone: 471-9520
Office Hours: M 2-3
Required Text: Stasys Jukna, "Extremal Combinatorics, with applications in computer science"
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. A list of topics follows.

Topic Reference Approximate Time
Counting Jukna, Chapters 1, 3 1 week
Matching Theory Jukna, Chapter 5 1 week
Pigeonhole Principle Jukna, Chapter 4 1 week
Ramsey Theory Jukna, Chapter 27 1 week
Probabilistic Method Jukna, Chapters 17-21 2 weeks
Linear Algebra Method Jukna, Chapters 14-15 1-2 weeks
Designs Jukna, Chapter 13 1 lecture
Coding Theory Sudan's lecture notes 2 weeks
Randomized Algorithms Jukna, Chapters 24 1 lecture
Expander Graphs Hoory-Linial-Wigderson survey 1-2 weeks
Randomness Extractors Vadhan slides 1-2 weeks

Prerequisites: Graduate standing or consent of instructor. Many students find this course difficult, so a strong math background is highly recommended. In particular, a good 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 strong 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."
Grading: 30%: Homework
25%: Midterm
45%: Final exam
Exams: The midterm will be held in class on October 11. The final exam will be cumulative and held on Monday, December 17 from 9am-noon. No make-up exams will be given, so plan accordingly. For the midterm, you may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides); for the final you may bring two such sheets. No calculators are allowed (they won't be necessary).
Homework
policy:
Collaboration policy: I encourage you to discuss homework problems with your classmates. However, you must write up your own solutions. Furthermore, you must acknowledge any collaboration by writing the names of your collaborators on the front page of the assignment.

Citation policy: If you 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.

Submission policy: Homeworks are due at the beginning of class. Late homeworks should be submitted directly to the TA.

Late 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 (so it begins and ends at 11am). However, an assignment due Thursday may be handed in Monday by 11am for two late days.

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.

Last modified: October 4, 2007