Combinatorics is what BSM is most renowned for. For decades Budapest has been the mathematics hub of the world, especially for combinatorics. Paul Erdős, the greatest mathematician of the twentieth century, revolutionized the field of combinatorics; by the way, he was one of the founders of BSM.
Combinatorics is the mathematics of arrangements of things. An example of a fact from combinatorics is "The number of ways to tile a 2-by-n board with dominoes is given by the nth Fibonacci number." Another example is that there are no more than five regular (Platonic) solids.
I took a combinatorics class at my college last year, and I absolutely loved it to bits; thus I am taking a level-2 combinatorics class here in Budapest. The class focuses on hypergraphs: things that are like graphs, except that each edge, rather than consisting of two points, can be a set of any number of points. In the course of studying hypergraphs, other topics also come up.
One of my favorite topics was the following: Given a set of n objects, consider the subsets of size k, and partition them into families so that, within each family, every pair of subsets has an object in common. What is the smallest number of families for which this is possible? This is known as the Kneser problem. This can be stated in terms of hypergraphs, and also in terms of traditional graphs. It turns out that the answer is n–2k+2, but proving it is not easy. The proof takes a huge detour into the land of topology, considering the n objects as points on a sphere and covering the sphere with the subset families. Or something.
Another topic I especially liked was the probability method. This method, pioneered by Erdős, is used to prove the existence of a given kind of structure. Using principles from probability, you show that the probability of a random structure being of the desired type is greater than zero; this means that at least one such structure must exist. For example, Erdős used the probability method to prove the existence of a certain edge-coloring on the complete graph. [More specifically, this gave a lower bound for the Ramsey number R(n).] In general, the flaw of this method is that it cannot construct the thing for you; it can only tell you that it exists somewhere.
2 comments:
Do you have a finite Erdos number now as a result of BSM? (Or did you already? I can't remember).
Also, I read some mathematician somewhere suggesting that now that Fermat's Last Theorem has been (inelegantly, but still) proved, authors should use finding Ramsey numbers as the generic "impossible mathematical feat".
In order to have a finite Erdős number, it is necessary to have published a paper with someone with a finite Erdős number. I have not done this; I am not doing any research in BSM, only taking classes.
Erdős may have been the first to use Ramsey numbers as an example of an impossible mathematical feat. There is a story that Erdős famously told: If an "evil spirit" comes and promises to destroy the earth unless humanity gives him the fifth Ramsey number, then our best course of action will be to organize all of our mathematicians, computer scientists, and anyone else who can help come up with the number. If, on the other hand, the spirit asks for the sixth Ramsey number, then our best choice will be to develop our military technology and try to destroy the spirit.
Post a Comment