| M501-M502 Introduction to Combinatorial Theory |
|---|
Credits -- M501 3 (3-0-0); M502 3 (3-0-0)
Term Offered -- M501 - Fall; M501 - Spring
Prerequisite -- M301, M369 or equivalent
- Possible Texts --
- Introductory Combinatorics by R.A. Brualdi, supplemented by material from Graph Theory, A Development from the 4-Color Problem by M. Aigner (graphs), and Combinatorial Designs by Ian Anderson.
- Description --
- Combinatorial theory is widely regarded as a delightful branch of mathematics. It contains some of the cleverest proofs in all of abstract reasoning, and has a broad range of applications. As the mathematical basis of theoretical computer science, combinatorial theory has enjoyed a huge surge of interest and popularity over the last 25 years, and is a very active research area.
Our one-year sequence in combinatorial theory divides into three parts: counting, graphs, and algebraic combinatorics. The counting segment of the course includes elementary counting, binomial identities, generating functions, recurrence relations, counting numbers (Stirling, Catalan), Ramsey theory, inclusion-exclusion, mobius inversion, and Polya counting.
The section on graph theory covers basic concepts, connectivity, planarity, colorings, bipartite and non-bipartite matchings, transversals, network flows, Latin squares, factors, hamiltonian cycles, and extremal graph theory. These are the central ideas of graph theory, and incidently include all the necessary tools for understanding the 1976 proof (by Appel and Haken) of the famous 4-color theorem.
The section on algebraic combinatorics introduces some structures that are both combinatorial and algebraic. These include balanced incomplete block designs used in statistics, linear codes used in communications, and Hadamard matrices and finite geometries used in weighing schemes, design of tournaments, and certain security schemes.