## Thursday, July 11, 2013

### Combinatorics use to not get any respect. But because of Erdos...

(This blog is based on things I heard at the Erdos 100th Bday Conference)

I have spend the last week at the Erdos 100th bday conference. One point that was made many times: the acceptance of Combinatorics by the mathematics community and Erdos's effect on that.

In the 1950's combinatorics was seen as recreational but not as serious math. In the 1970's you could get a PhD in it but it was still seen as suspect. Even at the time of Erdos's death (September 1996) it was still not that well regarded. Now it is, as evidenced by Szemeredi getting the Abel Prize (Gowers and Tao getting the Fields Medal is also evidence, though not as strong since one could argue that they are not really combinatorists). What changed?

1. I would have thought Szemeredi's theorem (1975) would have turned people around on combinatorics. It didn't. Roth proved the k=3 case in the 1950's, using Fourier Analysis (Real Math'') but Szemeredi's proof of the general case was purely combinatorial'' and hence of less interest. Furstenberg's proof that used Ergodic theory helped put it on the mathematical map (is the Mathematical map a bijection?) but combinatorics still was not well regarded.
2. Erdos got many people interested in combinatorics and the connections of it to other areas such as number theory. He had incredibly good taste in problems in that the problems he suggested often lead to deep mathematics of interest, and to more problems of interest. His emphasis on asymptotics, which now seems so natural, was revolutionary at the time and later had applications to computer science. His constant pushing for better and better results, his concept of Proof from THE BOOK his encouraging epsilons and deltas to pursue mathematics, all had a profound affect on mathematics and mathematicians.
3. One of the reasons for the disdain was that it was seen as recreational math. This was damming for two reasons (1) the problems were not important, and (2) the proofs were easy. Both are unfair. This may have been true at one time but they became less true over time.
1. Problems not important: P vs NP is certainly important. Ramsey Theory reveals hidden
regular structure and is important. Much of the work that has gone into better bounds
on the VDW numbers is very important and involves deep mathematics.
2. Proofs are easy: People are using Fourier analysis and ergodic theory and others tools that are rather difficult. Here we have the No true Scotsman Fallacy where people claim that if it uses these tools then its not combinatorics. This raises the question of if a field is defined by its methods or by its problems. In any case, people are solving problems in combinatorics using hard methods. But even among so-called easy proofs, they often exhibit the NP-phenomena where they are easy to verify and hence LOOK easy, but are hard to come up with.
4. One of the reasons for the respect is computer science. Just as Continuous math was just the right tool for physics, discrete math is just the right tool for computer science. This lead to a rich source of problems for combinatorists that in turn lead to interesting techniques.
5. Erdos stressed asymptotics which was just the right approach for computer science.
How much was Erdos responsible for the respect combinatorics has now? For those who believe in The Great Person theory of history, one person CAN make a difference and perhaps Erdos is one of those people. Would combinatorics have moved into the mainstream without Erdos? I think combinatorics would have gotten respect in year n where n might be large. With Erdos, n is smaller. Perhaps much smaller. I leave it to the reader to work out the proper asymptotics.

1. no true scotsman fallacy is also known as "moving the goalposts" & happens in technology fields [eg CS] where technology moves quickly. its also an example of a kuhnian paradigm shift in the technical/mathematical sciences. for more on the changing status of combinatorics over time, see also Erdos 100, tribute to a brilliant contrarian

2. also more about the historical context/progess/trend of acceptance of combinatorics from another angle, [automated] mathematical proofs, in adventures & commotions in automated theorem proving

3. Um, I'd say P vs NP does not "belong" to combinatorics - and hence probably can't be used to strengthen the argument for interesting problems in combinatorics - but belongs to computation(al complexity), which is not just a subfield of combinatorics.

Also, although computer scientists (including myself) nearly all view combinatorics as important because it is the "right" underlying math for computation, I'm not sure if this is viewpoint is quite as universal amongst "mainstream" mathematicians (analysts, algebraists, topologists, geometers, dynamicists, ...), many of whom also view computer science with some disdain. However, combinatorics is of increasing importance in many fields of mathematics, viz. simplicial sets in algebraic topology, symbolic dynamics, algebraic combinatorics in commutative algebra and representation theory, and I'm sure there are many more examples.

4. Looks like combinatorics has also overtaken logic as the mathematical foundation of cs (a developement which would be much to the regret of J. McCarthy). The P-NP problem is now mainly considered to be a problem of combinatorics and not of logic (recursion theory). And finite model theory is logic on the surface, but combinatorics in the workings. Clearly the fields of logic and combinatorics are not disjoint, but it looks like cs-logic is becoming more combinatorial than the other way round. By the way, also logic is also at the bottom of the hierarchy of respected mathematical fields. And Cohen was the only mathematician (many say that he was not even a true scotsman, sorry, I meant true logician) who was awarded a fields medal for his work in logic.

5. Where this ignorance of parents ("pure" mathematicians) against their children ("recreational" mathematicians) comes from? Not from real life - parents love children even if (and because) they are so "trivial" :-) Most probably, this comes from the axiom "cute, elegant proof = trivial, easy to come up proof". Unfortunately, this is THE axiom also for many computer scientists (have heard from many of them that combinatorics is too "trivial"). Could, for example, results with cute, elegant (hence, "trivial") proofs go through the "FOCS/STOC filter"? I mean, interesting results, but whose proofs were made by the authors as simple as possible (not simpler, of course). I doubt ... So, it will tent for a while until Erdős' "The Book" has a part about CS.

6. At the end of the day math is math. If someone gives proof for some problem in field A via techniques from field B, will we not accept it?