It was announced yesterday that Endre Szemerédi is the winner of the 2012 Abel Prize. As we mentioned a few years ago, the Abel Prize is a a fairly new award in math. Unlike the Fields Medal (which famously is for people under 40), the Abel Prize is meant to recognize long, illustrious careers in mathematics. It has quickly become one of the most prestigious awards in math.
It was awarded for:
for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory.
— Abel Prize Citation
Fellow math blogger, Tim Gowers, was in charge of giving a talk for non-mathematicians (i.e. journalists and such) about Dr. Szemerédi’s research. A tough challenge which Dr. Gowers adroitly pulls off. You can read the text on his blog here.
Dr. Szemerédi’s area of research is combinatorics. This is an area (like number theory) which is famous for having many easy to state but extremely difficult to answer questions. We wanted to mention two topics in one of Dr. Szemerédi’s areas of research: extremal combinatorics.
Very roughly, extremal combinatorics is the study of how when structures get very large, order becomes unavoidable. What do we mean? Well, our first example is Ramsey Theory.
First, recall that a graph in math is a collection of vertices (or nodes) which are connected by edges*. For example, the graph with 5 vertices and with edges between every pair of edges is called the complete graph on 5 vertices. It looks like this:
Now imagine you color the edges of the graph with two colors (lets say crimson and cream 🙂 ). The question is: Is it possible to color the edges with two colors in a way to avoid ending up with a triangle which is all one color?**
It’s not too hard to sit down with the complete graph on 5 vertices and create a coloring with crimson and cream which has no triangles with all three edges of the same color. Surprisingly, if you color the complete graph on 6 vertices:
then a monochromatic triangle is unavoidable!
You should try coloring the graph yourself and see if you can avoid a monochromatic triangle. But here’s the proof: Let’s look at the vertex on the far left of the picture of the complete graph on 6 vertices drawn above. There are 5 edges which leave that vertex. Since there are only two colors, one of the colors must be used 3 or more times. Let’s say crimson was used 3+ times. Now let’s look at the edges between those 3+ vertices. If any one of them is crimson, then that makes a crimson triangle with our original vertex. If they are all cream, then those 3 vertices form the corners of a cream triangle! A monochromatic triangle is unavoidable!
Ramsey’s theorem is the following amazing generalization of this result: If you use k colors and are interested in looking for a monochromatic complete graph on m vertices, then if you pick n large enough, then the complete graph on n vertices will always have the monochromatic graph you’re looking for.
In our example above, we used k=2 colors and are looking for a complete graph on m=3 vertices (aka a triangle). What we proved is that if n=6, then you always have the monochromatic triangle we’re looking for (notice that any n>6 will also work!). Ramsey’s theorem greatly generalizes this result to more colors and larger monochromatic subgraphs.
We also need to mention Szemerédi’s theorem. It is in the same spirit as Ramsey’s Theorem. We are now looking for arithmetic progressions in the integers. Remember, an arithmetic progression is a sequence of numbers where you go from one to the next by adding some fixed constant. So, for example, 2,7,12,17 is an arithmetic progression of 4 numbers with a step size of 5.
More generally, say you want to find an arithmetic progression of 4 numbers but you don’t care about the step size. Let’s pick a very small percentage, say 0.000000001%. Then Szemerédi’s theorem says there is a N so that whenever you pick 0.000000001% of the numbers 1,2,3,…,N, then you will always be able to find an arithmetic sequence of 4 numbers!
Once again, in a large enough mathematical object, patterns are unavoidable!
Here’s what Szemerédi’s theorem says: Say you are looking for an arithmetic progression of k numbers (with any step size). Pick a percentage, P%. Now, no matter how small your percentage is, there is a number N so that any subset of 1,2,3, …, N which has more than P% of the N possible elements, must contain an arithmetic progression of k numbers.
Of course Szemerédi’s theorem doesn’t promise that N will be small. In fact, you can imagine that it actually needs to be very, very, very, very big. If we write for the N for k and , then there is a (very big) constant C such that:
See wikipedia’s article for further details.
Besides being amazing in its own right, Szemerédi’s theorem launched a huge amount of new mathematics. Perhaps most famously, the Green-Tao Theorem builds on Szemerédi’s theorem. It proves that the set of prime numbers contains arbitrarily long arithmetic progressions.
* You can imagine that graph theory is super useful for studying networks. For example, the vertices could be the computers and routers at OU and the edges could be the cables connecting them.
** This is sometimes called the Party Problem. If the vertices are individuals and you color an edge between them crimson if they are friends and cream if they are not friends, then we’ve proven that if you invite 6 people to a party, there will be three people who are all friends or all strangers.