MATH 158Extremal Combinatorics and Graph Theory

4 units · MATH · UC San Diego

Extremal combinatorics is the study of how large or small a finite set can be under combinatorial restrictions. We will give an introduction to graph theory, connectivity, coloring, factors, and matchings, extremal graph theory, Ramsey theory, extremal set theory, and an introduction to probabilistic combinatorics. Topics include Turan’s theorem, Ramsey’s theorem, Dilworth’s theorem, and Sperner’s theorem. Credit not offered for MATH 158 if MATH 154 was previously taken. If MATH 154 and MATH 158 are concurrently taken, credit is only offered for MATH 158. A strong performance in MATH 109 or MATH 31CH is recommended.