Clases
Mondays 6:00-8:00 pm y Wednesday 4:00-6:00 pm.Literature
Combinatorics: The art of counting. Bruce Sagan.Preliminary version available in https://users.math.msu.edu/users/bsagan/Books/Aoc/aoc.pdf
A First Course in Discrete Mathematics. Ian Anderson.
Lecture notes in Spanish ( PDF).
Course Contents
Combinatorics is the area of mathematics that studies the enumeration and structure of families of discrete objects.This course will be comprised of two parts:
In the first part of the course we will give an introduction to the theory of combinatorial enumeration, the theory of partially ordered sets (posets) and some basic concepts in graph theory. From the enumerative point of view we will cover the basic enumeration principles, permutations and factorial numbers, subsets and binomial coefficients, compositions and weak compositions, set partitions and Stirling numbers, Fibonacci numbers and Catalan numbers, recurrences, generating functions, and the Principle of Inclusion-Exclusion (PIE). From the theory of partially ordered sets, we will cover basic definitions, lattices, Möbius functions, the Möbius Inversion Theorem. We will also cover the basic definition of a graph, the graph coloring problem and the chromatic polynomial. The first part of the course will be in English, however, we will only assume a basic level in the language. The main goal is to provide the students with the skill to have access to the literature that in general is published in English.
The second part of the course will be centered on giving an introduction to how research is done in Combinatorics. Here the students will have the opportunity to work in small parts of a current research project where we will study an application of the concepts previously studied in class. The students will have the opportunity to make computational experiments, propose conjectures and work towards proving such conjectures.
Examination and Grading
Tests (40%)
There will be 2 tests of 20% each. These will be announced at least one week in advance.Homework (30%)
There will be three problem sets (each worth 10%) to be handed in at the end of each term. To work on the homework problems is crucial for your understanding of the material presented in class. Be sure to separate enough time each week to think and write your solutions. It is recommended that you think and attempt every problem on your own before seeking any help. You are encouraged to discuss the material of the course with your classmates, however you must write your own solutions using your own words. Each homework will be graded by a random selection of a few problems (5%) and by a quiz (5%) where you should write your own solution for a randomly selected problem from the set.Final Research Project (30%)
In the final project we will select one or two problems that we will work as a group. Specific parts of the project will be then assigned to smaller subgroups. The goal of the subgroup is to understand the problem, generate computational data and draw conclusions that might allow you to propose conjectural statements. You will try to prove some of these statements using the skills acquired in the first part of the course.Problem Sessions
There will be various in-class problem sessions during the semester whose goal is to reinforce the concepts learned during a given week. During the problem sessions you are strongly encouraged to share what you have learned and to learn from your fellow class mates (share and learn).Syllabus
This is an approximate schedule of the course containing the syllabus:| Fecha | Tema |
|---|---|
| Mon 01/20 | What is combinatorics? |
| Wed 01/22 | Basic enumeration principles. Permutations and factorial numbers |
| Mon 01/27 | Subsets and binomial coefficients |
| Wed 01/29 | Compositions and week compositions |
| Mon 02/03 | Compositions and week compositions |
| Wed 02/05 | Selecciones con repeticiones y composiciones |
| Mon 02/10 | Selecciones con repeticiones y composiciones |
| Wed 02/12 | Recurrences |
| Mon 02/17 | Recurrences |
| Wed 02/19 | The method of the auxiliary equation to solve recurrences |
| Mon 02/24 | The method of the auxiliary equation to solve recurrences |
| Wed 02/26 | Test 1 |
| Mon 03/02 | Generating functions |
| Wed 03/04 | Generating functions |
| Mon 03/09 | Catalan numbers |
| Wed 03/11 | Set partitions and Stirling numbers |
| Mon 03/16 | The Principle of Inclusion-Exclusion (PIE) |
| Wed 03/18 | Basic concepts in the theory of partially ordered sets (posets) |
| Wed 03/25 | Operations between posets |
| Mon 03/30 | Lattices |
| Wed 04/01 | Lattices |
| Mon 04/13 | Incidence algebras and the Möbius function |
| Wed 04/15 | The Möbius inversion formula |
| Mon 04/20 | Techniques to compute the Möbius function. Labelings and shellability |
| Wed 04/22 | Test 2 |
| Mon 04/27 | REU section. Basic notions in graph theory. Graph coloring and the chromatic polynomial |
| Wed 04/29 | REU section |
| Mon 05/04 | REU section |
| Wed 05/06 | REU section |
| Mon 05/11 | REU section |
| Wed 05/13 | REU section |