August 21, 2006 ------------ Math 846 Topics in Combinatorics: a collection of _different_ fundamental topics in combinatorics. Richard A. Brualdi TR 9:30 - 10:45 AM GENERAL OUTLINE --------------- I. Some basic combinatorics concerning existence, construction, enumeration, and extremality. II. Combinatorial properties of (0,1) and integral matrices. III. Young tableaux and the RSK correspondence. MORE DETAILED OUTLINE --------------------- PART I: 1. Marriage Theorem and extensions - for submodular functions too. 2. Dilworth's theorem for posets 3. Mobius inversion and some applications 4. Orthogonal latin squares, finite projective planes, Smetaniuk's solution of the Evans conjecture. 5. Tournaments and the Graham/Pollack theorem 6. Polya Counting and applications 7. Permutation Patterns PART II: 1. Existence/Construction of (0,1)- and integral matrices: symmetric matrices and tournament matrices too: e.g., Gale-Ryser theorem, Landau's theorem, Erdos/Gallai theorem, ... . 2. Some combinatorial properties and parameters of these matrices: e.g., term rank, width (connection with finite projective planes), Part III: 1. Young tableaux and Kostka numbers. 2. The RSK correspondence (insertion and recording tableaux). 3. Construction questions from the RSK correspondence. NOTE: I will be gone the week of October 22-27. REFERENCE BOOKS --------------- 1. Combinatorics of Permutations by M. Bona 2. Introductory Combinatorics, 4th edition by R.A. Brualdi 3. Combinatorial Matrix Theory by R.A. Brualdi and H.J. Ryser 4. Matrices of Sign Solvable Linear Systems by R.A. Brualdi and B.L. Shader 5. Combinatorial Matrix Classes by R.A. Brualdi 6. Young Tableaux by W. Fulton 7. A Course in Combinatorics, 2nd edition by J. van Lint and R.M. Wilson