Bleg: Great combinatorial applications

I am currently writing up a syllabus for a combinatorics course. I want to show the students that combinatorics is not just a collection of puzzles, but that it has connections to lots of interesting problems. Because the prerequisites for this course are fairly minimal (calculus and linear algebra), I think I’d do best to talk about applied uses. So, this is a request for cool applications of combinatorial techniques, which I can explain in a single lecture or less. Cool applications within math are also welcome, if they can be explained at a low level.

Details: The audience is mixed undergrad-grad. The undergrads will probably mostly be math majors, but I hope to haul in some engineers and computer scientists. I plan to organize the course into four main topics (which means none of them can be covered in depth):

  • Generating functions and enumeration
  • Graph theory
  • Posets
  • Combinatorial geometry

Two things I am not doing: Symmetric functions and representation theory, because we’ll have a separate course on that, and asymptotics, because that would increase the prerequisites significantly.


17 thoughts on “Bleg: Great combinatorial applications

  1. I’m flattered, but this is extremely unlikely. I doubt the university would pay for a camera person for this class, and I wouldn’t have the time to edit it. Plus I’d need to get my student’s permission if their images or voices appeared.

    I might post lecture notes. I’ve never done that before, and I’m not sure that it would be worthwhile for this course, where I probably wouldn’t say much that isn’t already written somewhere else. At a minimum, I will write up notes for anything I discuss which is not in the text (van Lint and Wilson); that will probably include anything that is suggested in this discussion

  2. For graph theory, you should include max-flow/min-cut and applications to solving the marriage problem (and generally optimizing matchings, as applied by medical schools)

  3. I like generating functions, so if I taught a course of this sort I’d go into depth on those, perhaps secretly or not-so-secretly explaining that generating functions are decategorified species, and that many constructions done with generating functions can be done with the species themselves.

    One nice thing about species is that they allow one to see that the concept of “finite set equipped with some structure” (e.g. a coloring, an ordering, a tree structure) is not just a fuzzy metamathematical concept, but a precise mathematical concept. And, to a reasonably large extent, this concept is what combinatorics studies.

    But this is just me! I’m sure you’ll have more fun being you.

  4. Flajolet and Sedgewick’s Analytic Combinatorics has a nice section where they talk about using generating functions to decide how likely a certain string of nucleotides is in a random piece of DNA. I thought it was pretty cool.

  5. Generating functions will certainly be on the menu!

    I’m not sure whether category theory will. Mark Haiman taught a great course like this where he used category theory freely: Presenting the theory of species, and also proving the equivalence of categories between finite posets and finite distributive lattices. But I think he may have had a more category-friendly audience than I will.

    The place where species are most useful is talking about composition of generating functions, and I already have a lecture planned on that. I’ll think I’ll try writing that up with and without species and see which looks better.

    Everyone else, thanks for the suggestions!

  6. There are ways to talk about species that don’t hit the audience over the head with category theory, but still let the few who care know that generating functions play the same role for species that natural numbers do for finite sets. Or in other words: a generating function is a generating function of something, and that something can be studied as a mathematical entity on its own.

    Without some inkling of this, generating functions look sort of like a ‘trick’.

  7. One of the things that most impressed me from my first combinatorics class was the chromatic polynomial of a graph:

    Here’s an “application” that only requires you to know that the chromatic function is a monic polynomial whose degree is the number of vertices:

    Q: To celebrate his graduation, Xavier will be going out to dinner with his family a certain number of times (say x). In addition to his family, he has 5 friends each of whom he wants to invite to exactly one dinner. For certain pairs of these friends, however, it would be awkward to invite them both to the same dinner. He has already figured out that this can only work if there are at least 3 dinners, and that there would be respectively 18 or 168 distinct ways to solve the problem for x = 3 or x = 4. Now his family decides on a dinner at each of their favorite restaurants: Italian, Thai, Tex-Mex, Indian, and Chinese. In how many ways can he gracefully invite each of his 5 friends to one of the 5 family dinners?

  8. Here’s a real application I just finished involving some basic combinatorial construction. Maybe it’s too elementary for your course—I don’t know—but it took me and a very smart student quite a while to get it exactly right. Also, it’s an algorithm problem, really, so while it’s pretty much “find a recursive function” it may be out of scope for a math combinatorics course…

    I am building a scheduler, and have a set T of tasks that are ready to run right now. Each task requires some capacity resources given by a function r : T -> R, and there’s some amount k : R of the resource available. Further, there’s some difference function – : R -> R -> R that subtracts resources in a monotonically non-increasing way, and some boolean test function >= : R -> R -> B that returns true iff the resource on its left is greater than or equal to that on the right. (Note that I am being very vague about the resources, as they may vary from problem to problem.)

    OK, problems:

    1. Give an algorithm for constructing the set of all maximal subsets of T that can be immediately scheduled subject to the given resource bound. A subset T’ of T is maximal if no other task from T can be added to T’ without exceeding the available resource.

    2. Assume that the subsets T’ must be constructed efficiently, using only the set operation insert : T -> P(T) -> P(T) that inserts an element into an existing set, starting with the empty set. No subset or other set operations are allowed.

    3. Instead of a set of tasks, assume that I start with a sequence T of tasks and want to generate a sequence of subsequences. Generate the subsequences T’ in lexicographic increasing order on T.

    I have a solution if you want it, but I suspect you will find it fairly quickly.

    Hope this helps!

  9. What do you mean by asymptotics? I was going to suggest covering extremal combinatorics/probabilistic method (stuff involving Ramsey theory or Lovasz Local Lemma.) That stuff is super cool!

  10. umbral calculus? this stuff is so beautiful, and undervalued. students that are comfortable with linear algebra can appreciate this. my personal favorite is one of the foundational papers of rota, where he writes on sequences of binomial type.

    rook polynomials? this serves to illustrate the power of the “deletion-contraction” type recurrences that you will surely cover in the graph theory portion of the course.

    q-binomial theorem, partition identities.

    by combinatorial geometry do you mean this in the sense of rota (i.e., matroids!)?

  11. I second the suggestion of the stable marriage problem. It’s a lovely result with significant real-life applications (not to mention scope for anthropological speculation). The one time I taught it, my students really enjoyed it.

    Arrow’s impossibility theorem is another nice easy applied result, which only depends on a bit of poset theory for the setup.

    Probabilistic proofs of existence are something which I think are pretty interesting, and stretch students’ minds a bit. It’s not the most interesting result, but one example is the proof of the existence of tournaments with many Hamiltonian paths. (An advantage is that you can make the probabilistic argument without actually using any probability. Though I would, for my own use, welcome better suggestions!)

  12. Purely in terms of applications, one of the major ways of doing register allocation in computer science is via graph colouring (and analysis of graph colouring is how register allocation is shown to be NP complete). That’s 20-odd years old. About 5 years ago it was shown that a particular non-executable program representation (SSA form) always gives rise to chordal graphs, which means that greedy graph colouring algorithms can be used to obtain optimal colourings. (The NP-completeness hasn’t gone away, the conversion from coloured SSA form to coloured executable form can require extending the graph or modifying the colouring in ways which sometimes “blow up” exponentially.)

    Unfortunately this probably doesn’t have much that’s interesting to talk about on the graph theory side of things, so it’s just a listable example.

Comments are closed.