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: W 2:15-3:45.
TA: Abhishek Bhowmick
Email: bhowmick[AT]cs[DOT]utexas[DOT]edu
Office (for office hours): GDC 1.302, Desk 1
Office (for all other purposes): GDC 4.504B
Office Hours: MF 10:00-10:45.
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. A list of topics follows.

Topic Reference Approximate Time
Counting and Probability Jukna, Chapters 1, 3 1 week
Matching Theory Jukna, Chapter 5 1 lecture
Pigeonhole Principle Jukna, Chapter 4 1 week
VC Dimension Jukna, Chapter 10 1 lecture
Ramsey Theory Jukna, Chapters 4, 25, 26 1 week
Probabilistic Method Jukna, Chapters 18-20 2 weeks
Linear Algebra Method Jukna, Chapters 13-14 1-2 weeks
Polynomial Method Jukna, Chapter 16 1 week
Designs Jukna, Chapter 12 1 lecture
Codes Jukna, Chapter 17 1-2 weeks
Expander Graphs Jukna, Chapter 15 1-2 weeks
Random Walks Jukna, Chapter 23 1 week
Randomness Extractors TBD 1-2 weeks
Additive Combinatorics Jukna, Sections 25.3, 25.4 1 lecture

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."
Grading: 25%: Homework
25%: Midterm
40%: Final exam
10%: Participation
Exams: The midterm will be held in class on March 6. The final exam will be cumulative and held on Saturday, May 10 from 7-10pm in GDC 5.302. 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: While you should first think about homework problems on your own, I encourage you to discuss the problems with your classmates. However, you must write up your own solutions. In particular, nobody should email partial or full solutions to anybody. Furthermore, you must acknowledge any collaboration by writing the names of your collaborators 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: 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 2pm). However, an assignment due Thursday may be handed in Monday by 11am for two late days.

Canvas: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza.
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: January 27, 2013