Instructor Info

Name: Maria Angelica Cueto
Email: cueto.5@osu.edu
Office: Math Tower (MW) 636
Office Phone: 688 5773

Office Hours

M-W 10:30am-12:00pm
in Math Tower (MW) 636,
or by appointment.

Time and Location

Lecture: M-W-F 3:00pm-3:55pm
in Bolz Hall (BO) 120.

This is part one of a year-long graduate course on Enumerative Combinatorics and related fields. Our main goal is to address two questions: what does it mean to count and how can we effectively do so. Emphasis will be given to classical fun examples. Highlights and connections to other fields of mathematics and applications will be discussed throughout the semester.

The course will be divided in two parts. In the first part, we will study Basic Structures of enumeration, Sieve Methods and Generating functions. In the second part, we will discuss the structure of partially ordered sets, lattices, Möbius functions, and applications of enumerative aspects of geometric combinatorics, such as hyperplane arrangements. Additional topics will include the basics of matroid theory, and the geometry of polytopes, triangulations and Ehrhart theory.

Tentative list of topics: basic counting principles, generating functions, recurrence relations, lattice polytopes, Ehrhart theory, combinatorial species, tree enumeration, Sieve methods, Catalan numbers, posets, Möbius inversion, hyperplane arrangements, triangulations of polytopes, and matroids.

Prerequisites: Solid background in undergraduate linear algebra is assumed. Some experience with basic algebra and functions of one complex variable would be extremely helpful. We will review things according to the participants' background.

Syllabus and references

 Main textbook: Enumerative Combinatorics, Volume I, Second Edition, by Richard Stanley (Cambridge Studies in Advanced Mathematics). A draft of the book is available here.

Other textbooks and resources: (access requires connection via an OSU proxy, e.g., by being on campus)
  • A course in enumeration by Martin Aigner. Available online through OSU library.
  • An introduction to hyperplane arrangements (lecture notes) by Richard Stanley. Available here.
  • Computing the continuous discretely: integer-point enumeration in polyhedra by Matthias Beck and Sinai Robins. Available online through OSU library.
  • Triangulations: structures for algorithms and applications by Jesús De Loera, Jörg Rambau and Francisco Santos. Available online through OSU library.
  • Algebraic Combinatorics: walks, trees, tableaux, and more by Richard Stanley. Available online through OSU library.
  • Matroid theory by James Oxley.

Back to Top

Mathematical Software

 Mathematical software can be very useful for enumeration and to study combinatorial objects (including polyhedra). Here are some useful packages:

Back to Top

Homework

 There will be 8-10 homework problem sets (with due dates roughly every 1-2 weeks). These will be posted as the semester progresses.
Participants are encourage to work in teams, but individual solutions must be submitted for grading and credit. The best homework solutions will be posted (with author's permission).

Back to Top

Tentative Schedule

The following is the schedule of topics that we plan to cover each week (it is subject to change). For a list of topics cover each class, see the corresponding handwritten notes in the section entitled Lectures.

WeekTopics
1 Introduction to counting and overview; binomial coefficients and identities.
2 Some fundamental integer sequences; multinomial identities; Lattice paths.
3 q-analogs of binomial and multinomial coefficients, inversions.
4 Sieve methods; Inclusion-exclusion; The Gessel-Viennot theorem.
5 Applications of Geseel-Viennot's Theorem: binomial determinats, Hankel matrices, partitions and plane partitions.
6 Inversions on multisets; Formal Series; Generating functions; convergence; infinite products; compositions.
7 Linear Recurrences; Rational Generating Functions; Fibonacci numbers
8 Combinatorial interpretations of linear recurrences; Non-linear recurrences; Partition identities;
9 More partition identities; Catalan numbers; Exponential generating functions for derangements and involutions
10-11 Basics of polyhedral geometry; introduction to Ehrhart theory; Pick's Theorem; Triangulations of polytopes and pointed cones
12-13 Posets; Lattices and their refinements.
14-15 The incidence algebra of a poset; The zeta and Möbius functions for posets; computational methods for Möbius functions ; the Möbius inversion formula.
16 Hyperplane arrangements.

Back to Top

Lectures
  • Lecture 1 (Introduction, course overview and examples), August 21, 2019.
  • Lecture 2 (Power sets, binomial coefficients and Pascal's triangle), August 23, 2019.
  • Lecture 3 (More binomial identites, k-integer compositions, weak k-compositions and the slack variable method), August 26, 2019.
  • Lecture 4 (Multisets and multinomial coefficients), August 28, 2019.
  • Lecture 5 (Multinomial identities, lattices paths and q-analogs: q-binomial and q-multinomial coefficients), August 30, 2019.
  • Lecture 6 (q-binomial and q-multinomial coefficients; q-Pascal recurrence; counting subspaces of finite dimensional vector spaces over finite fields), September 4, 2019.
  • Lecture 7 (Inversions of permutations and q-factorial numbers), September 6, 2019.
  • Lecture 8 (Principle of Inclusion-exclusion and examples), September 9, 2019.
  • Lecture 9 (Generalized principle of Inclusion-exclusion; derangements), September 11, 2019.
  • Lecture 10 (Lindström-Gessel-Viennot's Lemma; examples), September 13, 2019.
  • Lecture 11 (Applications of Lindström-Gessel-Viennot's Lemma: Binomial determinants and Hankel matrices), September 16, 2019.
  • Lecture 12 (Introduction to partitions and their counting), September 18, 2019.
  • Lecture 13 (Counting plane partitions using Lindström-Gessel-Viennot's Lemma), September 20, 2019.
  • Lecture 14 (Involutions on multiset partitions and q-multinomial coefficients), September 23, 2019.
  • Lecture 15 (Generating functions and the algebra of formal power series), September 25, 2019.
  • Lecture 16 (More on formal power series: convergence of sequences of series, infinite products, compositions, binomial series), September 27, 2019.
  • Lecture 17 (Binomial series, formal derivatives and integration, infinite products, exponential and logarithms of series), September 30, 2019.
  • Lecture 18 (Fibonacci numbers and Fibonacci polynomials), October 2, 2019.
  • Lecture 19 (Linear recurrence relations and ordinary generating functions), October 4, 2019.
  • Lecture 20 (Linear recurrence relations and their combinatorial interpretation through weighted compositions), October 7, 2019.
  • Lecture 21 (Non-linear recurrences and exponential generating functions; partition identities), October 9, 2019.
  • Lecture 22 (More partition identities: Euler's odd/distinct thereom, Euler's pentagonal theorem; counting partitions with bounded length and height via q-binomial coefficients), October 14, 2019.
  • Lecture 23 (Catalan numbers and their combinatorial interpretations), October 16, 2019.
  • Lecture 24 (Exponential generation functions, derangements and involutions), October 18, 2019.
  • Lecture 25 (Basics on polyhedral geometry: polyhedral cones, polytopes, dimension, V- and H-representations, f-vectors), October 21, 2019.
  • Lecture 26 (Introduction to Ehrhart theory for lattice polytopes: main results and explicit formulas for standard simplices), October 23, 2019.
  • Lecture 27 (Construction of Ehrhart polynomials for lattice polytopes from their Ehrhart series and Pick's theorem: Ehrhart theory for lattice polygons), October 25, 2019.
  • Lecture 28 (Proof of Pick's theorem for special triangles; Ehrhart theory for lattice polygons; rationality of the moment generating function for rational simplicial cones), October 28, 2019.
  • Lecture 29 (Proof of Ehrhart series theorem and Stanley's non-negativity for simplicial lattice polytopes, and how to triangulate polytopes and pointed cones without using new vertices or rays), October 30, 2019.
  • Lecture 30 (Proof of Ehrhart series, Ehrhart polynomial and Stanley's Non-negativity Theorems for both lattice and rational polytopes), November 1, 2019.
  • Lecture 31 (Basics on posets: definitions, examples and some induced structures; new posets from old), November 4, 2019.
  • Lecture 32 (Duality, antichains, order ideales, chains, finite graded posets and their generating functions), November 6, 2019.
  • Lecture 33 (More on graded posets: new graded posets from old, computations of rank, Whitney numbers and generating functions for the n-chains, the Boolean algebra Bn, the q-Boolean algebra Bn(q), the Set-Partitions Πn of [n], and divisors Dn of n; Stirling numbers of the second kind and the recurrence relations; Lattices: definitions of meets and joins, examples), November 8, 2019.
  • Lecture 34 (More on lattices: basic properties, meet-, join-semilattices, upper-, lower-semimodular and modular lattices), November 13, 2019.
  • Lecture 35 (More on modular lattices; Distributive lattices, examples), November 15, 2019.
  • Lecture 36 (Classification of finite distributive lattices via order ideals; geometric lattices and main examples), November 18, 2019.
  • Lecture 37 (Incidence algebras of locally finite posets; main example: the zeta function of a finite poset), November 20, 2019.
  • Lecture 38 (The Zeta and Möbius functions of a locally finite poset and their counting properties; Möbius Inversion), November 22, 2019.
  • Lecture 39 (Computing Möbius functions: chains and products, applications: Principle of Inclusion-Exclusion, Möbius function in Number Theory; Weisner and CrossCut Theorems by example), November 25, 2019.
  • Lecture 40 (Combinatorics of Hyperplane arrangements I: definition of the intersection poset and its properties, essentialization of (affine) arrangements, the characteristic and Poincaré polynomials of an arrangement), December 2, 2019.
  • Lecture 41 (Combinatorics of Hyperplane arrangements II: How to compute the Characteristic polynomial of an arrangement: Whitney's Theorem and Deletion-Restriction. Applications to topology: counting regions and relatively bounded regions of real arrangements), December 4, 2019.

Back to Top