Enumerative Combinatorics and Partially Ordered Sets

Instructor: Rafael S. González D'León
Email: rafael.gonzalezl@usa.edu.co
Homepage: http://dleon.combinatoria.co
Office Hours: By appointment.

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.

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:
FechaTema
Mon 01/20What is combinatorics?
Wed 01/22Basic enumeration principles. Permutations and factorial numbers
Mon 01/27Subsets and binomial coefficients
Wed 01/29Compositions and week compositions
Mon 02/03Compositions and week compositions
Wed 02/05Selecciones con repeticiones y composiciones
Mon 02/10Selecciones con repeticiones y composiciones
Wed 02/12Recurrences
Mon 02/17Recurrences
Wed 02/19The method of the auxiliary equation to solve recurrences
Mon 02/24The method of the auxiliary equation to solve recurrences
Wed 02/26Test 1
Mon 03/02Generating functions
Wed 03/04Generating functions
Mon 03/09Catalan numbers
Wed 03/11Set partitions and Stirling numbers
Mon 03/16The Principle of Inclusion-Exclusion (PIE)
Wed 03/18Basic concepts in the theory of partially ordered sets (posets)
Wed 03/25Operations between posets
Mon 03/30Lattices
Wed 04/01Lattices
Mon 04/13Incidence algebras and the Möbius function
Wed 04/15The Möbius inversion formula
Mon 04/20Techniques to compute the Möbius function. Labelings and shellability
Wed 04/22Test 2
Mon 04/27REU section. Basic notions in graph theory. Graph coloring and the chromatic polynomial
Wed 04/29REU section
Mon 05/04REU section
Wed 05/06REU section
Mon 05/11REU section
Wed 05/13REU section

Code of Conduct

Students should consult the students rights and responsibilities outlined in the Student manual (Reglamente estudiantil). Any ofense to the code of conduct of the university will result in the disciplinary procedures stated in the manual.

Changes to this Syllabus

This syllabus may have some changes during the semester. It is responsibility of the students to visit frequently the webpage of the course for up to date information.