Combinatorics, Lecture 1 (26 Sep 2019)

John Baez is teaching a course on combinatorics this quarter. I’m taking detailed notes and texing them up. I’m also going to start blogging them. Credit to Tim Hosgood for the pictures.

Prehistory of the course

Larry Harper taught this course in the past. John is going to be talking about combinatorial species. He previously talked about species in his quantum gravity seminar. Textbooks referenced in the course:

What is combinatorics?

There are a ton of answers to this question. So whatever you say, its probably wrong. Here are some possible answers:

  • The art of counting.
  • The study of structures on finite sets.
  • The study of the category of finite sets.

Let F denote the category where the objects are finite sets, and the morphisms are functions.

Any finite set X has a cardinality |X|, the number of elements, and “counting” means computing |X|. Why do we care about cardinality? It turns out that two sets X and Y are isomorphic in F if and only if |X| = |Y|. If you are asking whether or not sets X and Y are isomorphic, you’re asking if there is a function f \colon X \to Y which has an inverse f^{-1} \colon Y \to X. There could be a lot of isomorphisms, you might worry about finding a specific one. But counting reduces this problem to something simpler: a yes or no question of equality in the set of natural numbers, ℕ.

So counting reduces a question about a category to a question about a set. This is an example of something mathematicians do a lot, “decategorification”. If you want to get good at counting , you have to learn a lot about the category of finite sets. To prove things about numbers, we will go in the opposite direction, turn it into a statement about F, i.e. “categorification”.

If you haven’t already, you should read Categorification by Baez and Dolan, especially the parable of the shepherd in the introduction.

Examples of structures you can put on finite sets

If k is a natural number, there is a structure called a k-coloring of a finite set X. It is given by a function c \colon X \to {1, \dots, k}. You think of the set {1, …, k} as a set of colors, and the function as assigning each point of X to a color.

A 3-colored 4-element set.

You could ask how many k-colorings are there for some finite set X? The answer is k^{|X|}. In general, we define Y^X = {f \colon X \to Y}. Really, this is the definition of exponentiation in ℕ.

Here are some other relationships between F and ℕ:

  • |X × Y| = |X| |Y|, where × is the cartesian product
  • |X ∐ Y| = |X| + |Y|, where ∐ is disjoint union, and + is addition
  • |∅| = 0, ∅ is called the “initial object” of F
  • |{x}| = 1, {x} is called a “terminal object” of F

Notice that there is a unique initial object, but there are tons of terminal objects in F.

A pointed finite set is a finite set X equipped with a chosen point, i.e. a function p \colon \{x\} \to X. You think of the image of the unique point x to be a distinguished element of X.

A pointed 4-element set.

Note that this is similar to the first example because its expressed as a function, but its different because it is a function into X.

Question: how many ways are there to choose a point in X? Answer: |X|.

A partition of a finite set X is a collection of disjoint, non-empty subsets X_i \subseteq X, such that X = \bigcup X_i.

Question: how many partitions does X have? Answer: if |X|=n, it’s the n-th Bell number.

This is not really an answer unless we know what a Bell number is. Let’s try just working out a few.

How many partitions of a 1-element set are there? Just 1.

The only partition of a 1-element set. Somewhat difficult to draw effectively.

How many partitions of a 2-element set are there? 2.

The two possible partitions of a 2-element set.

Nice pattern so far, let’s continue.

How many partitions of a 3-element set are there? 5.

The five possible partitions of a 3-element set.

Hmm, ok….

But we skipped something, we didn’t ask how many partitions of the empty set there are. You might think there are none, because if the parts of a partition must be nonempty, then you can’t form any parts from the empty set. However, there is nothing in the definition which says that the set of parts must be non-empty! So there is one partition of the empty set, the one with no parts. I won’t bother drawing it.

Species

In general, what is a kind of structure that you can put on a finite set? André Joyal, a famous category theorist, answered this. He called it a species. Remember, we have the category F of finite sets and functions, but we need another category to define species.

Let S be the category with finite sets for objects, and bijections for the morphisms. A species is a functor G \colon S \to F.

In more elementary terms, it is a family of finite sets indexed by S. Each finite set X gets a set G(X), which we think of as the set of all structures of a given kind which you can put on X. For example, if our species is “3-colorings”, then G(X) = \{1, 2, 3\}^X.

You might ask why we define species this way in particular, functors S to F. So far we’ve only mentioned objects in our elementary description, but a functor must also send morphisms to morphisms. So for some f \colon X \to Y in S (a bijection), G gives us G(f) \colon G(X) \to G(Y). Returning to our 3-colorings example, from any 3-coloring of X, we can use f to obtain a 3-coloring of Y: G(f)(c) = c \circ f^{-1}.

Furthermore, for G to be a functor, we need G(f \circ g) = G(f) \circ G(g) and G(1_X) = 1_{G(X)}.

For 3-colorings, we can compute:

G(f \circ g)(c) = c \circ (f \circ g)^{-1}
= c \circ (g^{-1} \circ f^{-1})
= (c \circ g^{-1}) \circ f^{-1}
= G(f) (c \circ g^{-1})
= G(f) (G(g) (c))
= G(f) \circ G(g) (c)

What about pointed sets? Let H \colon S \to F have H(X) = {ways of picking a point of X } = X. If we picked a point in X, and we have a bijection f \colon X \to Y, we can use that to pick a point in Y. This gives our function H(f) \colon H(X) \to H(Y).

Puzzles

  • What is the number of partitions on an n-element set?
  • How many triangulations of a convex polygon with n vertices are there? (by “triangulation” I mean drawing new edges between the vertices so that every open space has exactly 3 edges at its boundary)
A triangulation of a pentagon.

Next Time

In the lecture 2, we’ll talk about the relationship between species and generating functions, and operations on species.

2 thoughts on “Combinatorics, Lecture 1 (26 Sep 2019)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s