Math 108. Topics in Combinatorics: The probabilistic method.

Winter 2008

· Instructor:         Sergi Elizalde

· Lectures:           TuTh 10:00-11:50 in Kemeny 244

· X-period: W 3:00-3:50

· Office Hours:    Tu 11:50-12:30, Th 1:30-3:30, and by appointment

· Office:               Kemeny 332

· Email:

· Phone:               646-8191

---

Course description

The probabilistic method is a powerful tool to tackle many problems in discrete mathematics. Roughly speaking, here is how the method works: in order to prove that a certain object with some desired properties exists, one shows that a random object selected from an appropriate probability space has the desired properties with positive probability.
This method uses randomness to prove theorems that involve no probability themselves, and that would otherwise be very difficult to prove.
The probabilistic method has recently been developed intensively and it has become a very useful tool in Combinatorics and Theoretical Computer Science.

This course is based on a course taught by Joel Spencer while visiting MIT a few years ago.

---

Homework

· Problem Set 1. Due on Tuesday, Jan. 22.

· Problem Set 2. Due on Tuesday, Feb. 5.

· Problem Set 3. Due on Tuesday, Feb. 19.

· Problem Set 4. Due on Tuesday, Mar. 4.

---

Textbook

The textbook for this course is The Probabilistic Method by Noga Alon and Joel Spencer, 2^nd edition, J. Wiley and Sons, New York, 2000. (Available at Wheelock Books.)

Another useful source are these notes by Jiri Matousek and Jan Vondrák.

---

Topics

Here’s a tentative list of topics that I will try to cover.

• Chapter 1. The basic method. Examples.
  - Ramsey’s Theorem.
  - Tournaments.
  - 2-colorable families. Upper and lower bounds.
  - The Erdös-Ko-Rado Theorem.
  
  
• Chapter 2. Linearity of expectation.
  - Dominating sets.
  - Sum-free subsets.
  - Hamiltonian paths in tournaments.
  - Large deviations.
  - Ranking the vertices of a tournament.
  - Balancing vectors.
  - Balancing lights.
  
  
• Chapter 3. Alterations.
  - Ramsey numbers.
  - Independent sets.
  - The Heilbronn problem.
  
  
• Chapter 4. The second moment method.
  - Prime divisors.
  - Random graphs.
  - Clique number.
  
  
• Chapter 8. The Poisson paradigm.
  - Janson’s inequality.
  - Brun’s sieve.
  - Random graphs: isolated points, connectivity.
  
  
• Chapter 5. The Lovász Local Lemma.
  - The lemma.
  - Property B.
  - Lower bounds for Ramsey numbers.
  
  
• Chapter 10. Random graphs.
  - Subgraphs.
  - Clique number.
  - Chromatic number.
  - The evolution of random graphs.
  - Birth processes.
  - The giant component.
  
  
• Chapter 14.
  - Liar game.

---

Homework, exams, and grading

The grade will be based on the homework and a project presentation. There will be no exams.
The homework will consist of a problem set every two weeks. You are encouraged to collaborate on the homework, but the solutions must be written individually.
The project will consist of preparing a topic, individually or in groups of 2 or 3, and presenting it in class. Here is a list of suggested projects.

---

Students with disabilities: Students with disabilities enrolled in this course that may need disability-related classroom accommodations are encouraged to make an office appointment to see me before the end of the second week of the term. All discussions will remain confidential, although the Student Accessibility Services office may be consulted to discuss appropriate implementation of any accommodation requested.

Last modified on Mar 3, 2008.