Introduction to Combinatorics I

Catalog description

Combinatorics studies discrete structures arising in mathematics, computer science, and many areas of application. Key topics include counting objects with specific properties (e.g., trees) and proving the existence of structures (e.g., matchings of all vertices in a graph). We cover basic questions in graph theory, including extremal graph theory (how large a graph must be to have a certain subgraph) and Ramsey theory (large objects are forced to have structure). An introduction to network flow theory and variations on matching theory, including theorems of Dilworth, Hall, König, and Birkhoff, are discussed. Methods of enumeration (inclusion/exclusion, Möbius inversion, and generating functions) are applied to problems of counting permutations, partitions, and triangulations. Students will be expected to be comfortable writing proofs. More experience with proofs may be gained by first taking a 3000-level MATH course.