Math 390C - Probabilistic Combinatorics


Lectures: Tuesday, Thursday, 11:00-12:30PM, RLM 12.166

Instructor: Ngoc Tran (office 11.164 RLM)

Office hours: by appointment

Prerequisites: undergraduate probability (eg: Ross, Pitman) and consent of instructor

Recommended book: the Probabilistic Method, 3rd edition, Alon and Spencer.

Grading policy: 3 homeworksets for 20% each, final project 40%.

Final project: The final project consists of an oral presentation (about 20 minutes) and a written summary of an assigned paper / book chapter. Please see the list of suggested papers / book chapters in the shared Google doc on Canvas.

Suggestions: Group work and discussions are very welcomed, but please hand in individually written homework and projects. Please feel free to ask questions at all times, and please feel free to make office hours appointments.

Course description : Probabilistic arguments are powerful tools in answering many questions one often encounters in random discrete processes, such as the study of random graphs and networks.
This course covers the basics of the probabilistic method. Throughout the course and as time permits, we shall survey various problems in mathematics, computer science and statistics where the above tools or their variations have been succesfully applied to solve research problems.

Weekly Syllabus

Here is a tentative weekly syllabus. This schedule is subjected to minor changes, such as inclusion or omission of materials.
  1. Week 1: The basic method: tournaments, Ramsey number, expectation, Sperner's theorem, sample and modify

    Homework week 1

  2. Week 2: First moment method: $K_4$ threshold, connectivity threshold, longest increasing subsequence
  3. Homework week 2
  4. Week 3: Second moment method: $K_4$ threshold (cont.), connectivity threshold (cont.), Turan's proof of the Hardy-Ramanujan theorem, Percolation on tree
  5. Homework week 3
  6. Week 4: The local lemma: Ramsey number lower bounds, graph coloring, negative dependencies
  7. Homework week 4
  8. Week 5: Correlation inequalities: FKG, four functions, percolation, XYZ theorem
  9. Lecture notes up to and including week 5 . Homework week 5
  10. Week 6: Jason's inequality, Brun's sieve, triangles in G_{n,p}
  11. Lecture notes up to and including week 6 . Homework week 6
  12. Week 7-8: Large deviation bounds
  13. Homework week 7 Solutions to the first set of homeworks (1 to 3)
  14. Week 8-9: Martingales and tight concentration
  15. Lecture notes up to and including week 8 . Homework week 8
  16. Week 9: Talagrand and Kim-Vu
  17. Lecture notes up to and including week 9 . Homework week 9
  18. Week 10+: VC classes
  19. Week 12+: supplementary topics, presentations of reading project

Policies

Add/drop dates

Please take note of the add/drop deadlines here at the university calendar. There are no provisions to adjust scores due to late enrolment.

Make-ups for homeworks

No late homework or final projects will be accepted.
Should you have serious medical problem or genuine emergency, please obtain a written or electronic letter from the Student Emergency Serivces. Under exceptional circumstances, I will give partial grade, provided you have a C average on previous coursework.

Services for students with disabilities

The University of Texas at Austin provides upon request appropriate academic accommodations for qualified stu- dents with disabilities. For more information, contact Services for Students with Disabilities at 471-6259 (voice) or 232-2937 (video phone)

Academic Integrity

By being enrolled in the class, you have agreed to adhere to the student honor code and the university code of conduct. Violations will be treated as required by the university policy.