CS 491:Tutorial in the Probabilistic Method

Fall 2026

Instructor: Enrique Treviño
Lectures: T 9:00 - 9:50 pm in BR 123
Office Hours: MWF 9:00-9:50am and T from 1pm to 2:20pm.
Office: Brown Hall 123
Email:
Phone Ext.: #6187

Announcements

Announcements go here.

Course Description

The probabilistic method is a powerful tool used throughout discrete mathematics. Roughly speaking, the method works by showing that a random object selected from a suitable probability space possesses a desired property with positive probability. This allows us to prove the existence of mathematical objects that may be very difficult to construct explicitly.

The probabilistic method has become a central tool in modern combinatorics and theoretical computer science, and we will study a variety of classical and contemporary applications.

Student Learning Outcomes

Learn the basic principles of the probabilistic method.
Use probabilistic arguments to prove existence results.
Understand applications to graph theory and Ramsey theory.
Apply linearity of expectation and moment methods.
Learn the Lovász Local Lemma and its applications.
Study random graphs and related probabilistic models.
Develop and present mathematical expositions.

Textbook

The Probabilistic Method by Noga Alon and Joel Spencer, 2nd edition, Wiley, 2000.

Additional supplementary notes will be provided throughout the semester.

Topics We Will Cover

Chapter 1 The basic probabilistic method.

Ramsey's theorem.
Tournaments.
Erdős-Ko-Rado theorem.

Chapter 2: Linearity of expectation.

Dominating sets.
Sum-free subsets.
Hamiltonian paths in tournaments.

Chapter 3: Alterations.

Ramsey numbers.
Independent sets.
The Heilbronn problem.

Chapter 4: The second moment method.

Prime divisors.
Random graphs.
Clique number.

Chapter 5: The Lovász Local Lemma.
Chapter 8: The Poisson paradigm.
Chapter 10: Random graphs.
Chapter 14: The liar game.

Grading

Homework 70%
Project Presentation 30%

Homework

The course will have four intensive homework assignments. The four assignments are in the homework page.

Students are encouraged to work together while discussing the problems. However, all submitted solutions must be written independently and in the student's own words.

Homework assignments will emphasize proof-writing and creative applications of probabilistic techniques.

Project Presentation

Each student (or small group of students) will prepare a topic related to the probabilistic method and give a presentation to the class near the end of the semester. Here is a list of suggested projects.

Description of instructional time and expectations:

This course meets 1 time per week for 1.0 hours per week. The course carries 1.0 course credit (equivalent to four semester credit hours). Students are expected to devote a minimum of 12 hours of total work per week (in-class time plus out-of-class work) to this course.

Academic Honesty

Please read the College's information on Academic Honesty. If a student cheats in an exam, quiz or homework assignment, I will proceed with charging the student with the Academic Honesty Judicial Board. The usual (first) penalty is a 0 in the assignment on which the cheating occured plus some ethics lectures the student would take. The second penalty is usually suspension.

AI policy

Any use of AI on homework will be an automatic zero. You cannot use AI for anything.

Academic Resources, Protocols, and Policies

Click here: Academic Resources, Protocols, and Policies

Last modified on September 14, 2026.