Why is it important to study combinatorics?

Question

I was having a discussion with my friend Sayan Mukherjee about why we need to study combinatorics which admittedly, is not our favorite subject because we see very less motivation for it (I am not saying that there does not exist motivation for studying it, it's just that I have not found it).

Here are some of the "uses" of combinatorics that we could come up with:

1. Counting - the number of ways in which we can perform a finite sequence of operations and how objects can be arranged or selected. For example,the number of ways in which we can select $k$ odd and even elements from the set $S=\{1,2,\dots, 2n\}$ so that at most 3 odd elements consecutive elements could occur in the section.

2. Drawing bijections- The classic Stars and bars problem provides us key ideas to count the number of integral solutions to equations of the form $x_1+x_2+\dots x_n=k$.

3. The Seven Bridges of Königsberg which captivated me as a child.

I have refrained from mentioning recursions and generating functions as I see them more as tools.

But I am looking for more motivation; counting, as described in problems seems to be tip of the iceberg and I will appreciate more examples where combinatorics and graph theory can be powerful tools. Can we please have a list of uses of combinatorics? I am not looking for applications to industry, just pure math.

It is not essential that the answers be pitched at high-school level; additional info will certainly be fun to revisit!

Answer 1

As requested, here is a list of applications of combinatorics to other topics in pure mathematics.

• Counting is used extensively in the original proof of Chebyshev's theorem, which you can find in Chapter 5 of (the free online version of) this book. Chebyshev's theorem is the first part of the prime number theorem, a deep result from analytic number theory.

• In group theory, the pigeonhole principle is used to show that every element of a finite group has an order. One could argue that the proof that every finite integral domain is a field stems from similar logic.

• A proof of Brouwer's fixed point theorem using the pigeonhole principle and Sperner's lemma is given here.

• UPDATE: Graphs in Finite Group Theory. I know of several examples where graphs appear in finite group theory: prime graphs, character degree graphs, and commuting graphs. Prime graphs (about which I have written several MSE answers, e.g. $[1]$,$[2]$) concern the set of element orders in a finite group, character degree graphs have to do with the degrees of a group's irreducible characters, and commuting graphs illustrate which elements commute with which other elements. $$$$ Most of the time, the application of graph theory to finite group theory is linguistic - that is, these graphs arise naturally from group theoretic questions that are best formulated using graph theoretic language. In other words, one doesn't commonly see theorems from graph theory being used to solve problems in finite group theory, even when the aforementioned graphs are the subject of research. Sometimes, however, graph theory may also be applied more directly, as can be seen in this paper of mine, for example.

Answer 2

We might wonder: How important is "importance"? :)

But for a more serious general response to the concerns that perhaps underlie your question, it is well worth reading this wonderful piece by Sir Timothy Gowers in which he talks about two cultures or styles of mathematics, problem-solving vs theory-building, exemplified it might seem at first sight by e.g. combinatorialists vs topos theorists (the latter is my example). Gowers goes on to defend the mathematical interest and importance of combinatorics, and seeks explicitly to “counter the suggestion that the subject of combinatorics has very little structure and consists of nothing but a large number of problems”.

Answer 3

The entire modern world relies on combinatorial algorithms. If you want to make a program faster, you need combinatorics. If you want to understand modern programming, you need combinatorics. Without combinatorics, some programs that now take a split second would require weeks.

Cellphone communications -- Error correcting codes, wavelet and fourier optimizations.
Game programming -- polygon optimization
This website -- comment hierarchies

Anyplace you have a hundred or more pieces of data -- which is pretty much every site, store, program, place, or project -- there is likely some combinatorial improvement being used. Especially in programs. If it's fast, there are combinatorics helping out.

Answer 4

Another important application of combinatorics is in representation theory, symmetric functions, and the study of varieties with lots of symmetries (Grassmannians, flag varieties, toric varieties, symmetric varieties, spherical varieties).

In general, objects with enough symmetries can often be described by discrete (often finite) data. Combinatorics comes into play in order to parameterize the data and, more generally, because relationships between objects are often described in terms of combinatorics of the data.

As a simple example, suppose you want to study $k$-dimensional subspaces of an $n$-dimensional vector space $V$. One way to understand such a subspace $W$ is to consider a "flag" of $V$, which is a sequence of subspaces $$0 = V_0 \subset V_1 \subset \dots \subset V_i \subset \dots \subset V_n = V,$$ with $\dim(V_i) = i$. You can divide the different subspaces $W$ based on the weakly increasing sequence of numbers $$0 = \dim(W \cap V_0) \leq \dim(W \cap V_1) \leq \dots \leq \dim(W \cap V_i) \leq \dots \leq \dim(W \cap V_n) = k,$$ with the restriction that at each stage the dimension can go only up 1 or stay the same. An equivalent way to describe the position of $W$ relative to the flag is to give a sequence of length $n$ consisting of $k$ 1's and $n-k$ 0's, with a $1$ occurring in the $i$-th position exactly when $\dim(W \cap V_i) > \dim(W \cap V_{i-1})$.

A simple observation is that the number of different "cells" that you have divided the subspaces into is equal to $n \choose k$, since this counts the number of such strings of 0's and 1's. This is only the beginning of a rich interplay between combinatorics and geometry. The moral is that if you want to study an object with symmetries, you are very likely to encounter some interesting combinatorics along the way.

Answer 5

You left out statistics. If you're dealing with finite sets of possible events, a lot of statistical questions come down to combinatorics. If you e.g. have $n$ random variables $X_n$ with finite domains, and want to find the distribution of $X_1+\ldots+X-n$, you have to figure out in which ways the possible outcomes of $X_1,\ldots,X_n$ can sum up to a specific value.

Lots of high-school combinatorics is done with such applications in mind, i.e. the infamous

You pick so-and-so many objects from an urn containing this-and-that what is the probability that you picked objects with some-property-of-selection

Answer 6

I would like to mention about recursions and generating functions (the tools that you refer to). Recursion relations (or difference equations) is (more or less) equivalent to the differential equations in physics or any other scientific domain. To roughly understand difference equations they are defined over an integral domain whereas differential equations are over a real domain (the difference is much more fundamental than this since a differential equation can also be defined on an integer domain, u can look up this).

The recursion equation is the functional equation of any system helping in enumeration. As an example Catalan numbers have nearly 150 different applications (discussed in Richard P. Stanley's book in Enumerative Combinatorics), there is even a complete volume on Catalan number written Thoamas Koshy.

Generating functions is a brilliant tool to solve recurrences. This is a beautiful mathematical device to find a closed form equation to the recursive relations. If you are computer science student (or programmer) you will hardly be needing these tools.

If you are computer science major (which Im guessing you are) you will rarely be needing these tools(G.F.'s that is) but recursion equations are something that you will never escape, and plus its helluva fun too!!!

Answer 7

Combinatorics turns out to be pretty important for group theory and probability. It's also relevant for topology, analysis, etc.