MAD 4204: Introduction to Combinatorics II
University of Florida, Spring 2011
MWF4 (10:40–11:30) in Little Hall 201
My information:
Office: Little Hall 412Office hours: M5 (11:45–12:35), T8 (3:00–3:50), W5 (11:45–12:35), and by appointment
Office phone: (352) 392-0281 extension 245
Email: vatter at ufl dot edu
Text:
A Walk Through Combinatorics, 2nd edition, by Miklós BónaCourse Content:
Trees, matchings, planar graphs, Ramsey theory, pattern-avoiding permutations, the probabilistic method, posets, lattices, combinatorial algorithms, computational complexity. We will cover chapters 10–18 of the textbook.Grading:
We will have (roughly) weekly homework, three in-class midterm exams (on February 9, March 2, and April 13), and a comprehensive final project.
Homework will count for 30% of the final grade, the midterms for 50% of the final grade, and the final project for 20% of the final grade. No scores will be dropped.
The final grades will be curved, but will be no tougher than the 10-point scale: 90%–100% will be at least some form of A, 80–90% will be at least some form of B, etc. After each midterm, you will receive a projected grade.
If you have a disagreement with the grading of one of your solutions, I ask that you submit a written request for reconsideration within one month.
Schedule of Lectures:
| Lecture | Date | Topics | Sections |
|---|---|---|---|
| 1 | W 1/5 | The Matrix-Tree Theorem | Section 10.4 |
| 2 | F 1/7 | The Matrix-Tree Theorem | Section 10.4 |
| 3 | M 1/10 | The Matrix-Tree Theorem | Section 10.4 |
| 4 | F 1/14 | Bipartite graphs Homework #1 assigned: pdf or tex |
Sections 11.1 and 11.2 |
| M 1/17 | Class canceled for MLK Day | ||
| 5 | W 1/19 | Hall's Marriage Theorem | Section 11.3 |
| 6 | F 1/21 | Coloring Homework #1 due Homework #2 assigned: pdf or tex |
Section 11.4 |
| 7 | M 1/24 | Discussion of Homework #1 | |
| 8 | W 1/26 | Tutte's Theorem Homework #2 due Homework #3 assigned: pdf or tex |
Section 11.5 |
| 9 | F 1/28 | Planar graphs & Kurotowski's Theorem | Section 12.1 |
| 10 | M 1/31 | The Five Color Theorem | Section 12.3 |
| 11 | W 2/2 | Ramsey Theory | Section 13.1 |
| 12 | F 2/4 | The Happy Ending problem | Section 13.2 |
| 13 | M 2/7 | The Erdős-Szekeres Theorem about increasing and decreasing subsequences in a permutation | n/a |
| W 2/9 | Midterm #1: pdf or zip | ||
| 14 | F 2/11 | The notion of probability | Section 15.1 |
| 15 | M 2/14 | Upper and lower bounds for the diagonal Ramsey numbers | Sections 13.1 and 15.2 |
| 16 | F 2/18 | Expected values Homework #4 assigned: pdf or tex | Section 15.4 |
| 17 | M 2/21 | Partially ordered sets | Section 16.1 |
| 18 | W 2/23 | Dilworth's Theorem | Section 16.1 |
| 19 | F 2/25 | The incidence algebra, and Möbius functions of posets
Homework #4 due Homework #5 assigned: pdf or tex |
Lecture notes |
| 20 | M 2/28 | Common Möbius functions | Lecture notes |
| W 3/2 | Homework #5 due Midterm #2 |
||
| 21 | F 2/28 | Discussion of Midterm #2 | |
| 3/5–12 | Spring Break | ||
| 22 | M 3/14 | Möbius functions of products | See M 2/28 |
| 23 | W 3/16 | Möbius functions of lattices Homework #6 assigned: pdf or tex |
Lecture notes |
| 24 | F 3/18 | The set partition lattice | See W 3/16 |
| 25 | W 3/23 | Groups, permutation groups, automorphism groups | Lecture notes |
| 26 | F 3/25 | Enumeration under group action (Póyla theory) Homework #6 due Homework #7 assigned: pdf or tex |
Lecture notes |
| 27 | M 3/28 | Enumeration under group action (Póyla theory) | Lecture notes |
| 29 | W 3/30 | Sorting with stacks and queues Homework #8 assigned: pdf or tex |
Lecture notes |
| 30 | F 4/1 | 231-avoiding and 321-avoiding permutations Homework #7 due |
Lecture notes |
| 31 | M 4/4 | Permutation classes Course evaluation period begins |
Lecture notes |
| 32 | W 4/6 | Juxtapositions Homework #8 due Homework #9 assigned: pdf or tex Final project assigned: pdf or tex Please remember to fill out the course evaluation |
Lecture notes |
| 33 | F 4/8 | The separable permutations Please remember to fill out the course evaluation |
Lecture notes |
| 34 | M 4/11 | Asymptotics of permutation classes Please remember to fill out the course evaluation |
Lecture notes |
| W 4/13 | Midterm #3 Homework #9 due Please remember to fill out the course evaluation |
||
| 35 | F 4/15 | 0/1 Matrices Course evaluation period ends |
Lecture notes |
| 36 | M 4/18 | The Stanley-Wilf Conjecture | Lecture notes |
| 37 | W 4/20 | Rearrangements | Lecture notes |
| W 4/27 | Final project due: pdf or tex |