## How Combinatorics became legitimate (according to László Lovász and Endre Szemerédi)

* Simons Foundation* has a series of fantastic interviews with leading mathematicians (ht Federico Ardila). Let me single out the interviews with László Lovász and Endre Szemerédi. Avi Wigderson asked both of them about the history of combinatorics and how it came into prominence. Watch parts 8-9 in Lovász’s interview and 10-11 in Szemerédi’s interview to hear their fascinating answers.

**P.S.** See also my old blog posts on what is combinatorics, how it became legitimate and how to watch math videos.

## What if math dies?

Over the years I’ve heard a lot about the apparent complete uselessness and inapplicability of modern mathematics, about how I should always look for applications since without them all I am doing is a pointless intellectual pursuit, blah, blah, blah. I had strangers on the plane telling me this (without prompting), first dates (never to become second dates) wondering if “*any formulas changed over the last 100 years, and if not what’s the point*“, relatives asking me if I ever “*invented a new theorem*“, etc.

For whatever reason, everyone always has an opinion about math. Having never been accused of excessive politeness I would always abruptly change the subject or punt by saying that the point is “*money in my Wells Fargo account*“. I don’t even have a Wells Fargo account (and wouldn’t want one), but what’s a small lie when you are telling a big lie, right?

Eventually, you do develop a thicker skin, I suppose. You learn to excuse your friends as well meaning but uneducated, journalists as maliciously ignorant, and strangers as bitter over some old math learning experience (which they also feel obliged to inform you about). However, you do expect some understanding and respect from fellow academics. “*Never compare fields*” Gian-Carlo Rota teaches, and it’s a good advice you expect sensible people to adhere. Which brings me to this:

#### The worst idea I’ve heard in a while

In a recent interview with Glenn Loury, a controversial UPenn law professor Amy Wax proposed to reduce current mathematics graduate programs to one tenth or one fifteenth of their current size (start at 54.30, see also * partial transcript*). Now, I get it. He is a proud member of the “intellectual dark web“, while she apparently hates liberal education establishment and wants to rant about it. And for some reason math got lumped into this discussion. To be precise, Loury provoked Wax without offering his views, but she was happy to opine in response. I will not quote the discussion in full, but the following single sentence is revealing and worth addressing:

If we got rid of ninety percent of the math Ph.D. programs, would we really be worse off in any material respect? I think that’s a serious question.

She followed this up with “*I am not advocating of getting rid of a hundred percent of them*.” Uhm, thanks, I guess…

#### The inanity of it all

One is tempted to close ranks and ridicule this by appealing to authority or common sense. In fact, just about everyone — from Hilbert to Gowers — commented on the importance of mathematics both as an intellectual endeavor and the source of applications. In the US, we have about 1500-2000 new math Ph.D.’s every year, and according to the AMS survey, nearly all of them find jobs within a year (over 50% in academia, some in the industry, some abroad).

In fact, our math Ph.D. programs are the envy of the world. For example, of the top 20 schools worldwide between 12 and 15 are occupied by leading US programs depending on the ranking (see e.g. here or there for recent examples, or more elsewhere). Think about it: math requires no capital investment or infrastructure at all, so with the advent of personal computing, internet and the arXiv, there are little or no entry barriers to the field. Any university in the world can compete with the US schools, yet we are still on the top of the rankings. It is bewildering then, why would you even want to kill these super successful Ph.D. programs?

More infrastructurally, if there are drastic cuts to the Ph.D. programs in the US, who would be the people that can be hired to teach mathematics by the thousands of colleges whose students want to be math majors? The number of the US math majors is already over 40,000 a year and keep growing at over 5% a year driven in part by the higher salary offerings and lifetime income (over that of other majors). Don’t you think that the existing healthy supply and demand in the market for college math educators already determined the number of math Ph.D.’s we need to produce?

Well, apparently Wax doesn’t need convincing in the importance of math. “*I am the last person to denigrate pure mathematics. It is a glory of mankind*…” She just doesn’t want people doing new research. Or something. As in “enough already.” Think about it and transfer this thought to other areas. Say — *no new music is necessary* — Bach and Drake said it all. Or — *no new art is necessary — *Monet and Warhol were so prolific, museums don’t really have space for new works. Right…

#### Economics matters

Let’s ask a different question: why would you want to close Ph.D. programs when they **actually make money**? Take UCLA. We are a service department, which makes a lot of money from teaching all kinds of undergraduate math courses + research grants both federal, state and industrial. Annually, we graduate over 600 students with different types of math/stat majors, which constitutes about 1.6% of national output, the most of all universities.

Let’s say our budget is $25 mil (I don’t recall the figures), all paid for. That would be out of UCLA budget of $7.5 billion of which less than 7% are state contributions. Now compare these with football stadiums costs which are heavily subsidized and run into hundreds of millions of dollars. If you had to cut the budget, is math where you start?

#### Can’t we just ignore these people?

Well, yes we can. I am super happy to dismiss hurried paid-by-the-word know-nothing journalists or some anonymous YouTube comments. But Amy Wax is neither. She is smart and very accomplished: summa cum laude from Yale, M.D. cum laude from Harvard Medical School, J.D. from Columbia Law School where she was an editor of *Columbia Law Review*, argued 15 cases in the US Supreme Court, is a named professor at UPenn Law School, has dozens of published research papers in welfare, labor and family law and economics. Yep.

One can then argue — she knows a lot of other stuff, but *nothing* about math. She is clearly controversial, and others don’t say anything of that nature, so who cares. That sounds right, but so what? Being known as controversial is like license to tell “the truth”… er… what they really think. Which can include silly things based on no research into our word. This means there are numerous other people who probably also think that way but are wise enough or polite enough not to say it. We need to fight this perception!

And yes, sometimes these people get into positions of power and decide to implement the changes. Two cases are worth mentioning: the **University of Rochester** failed attempt to close its math Ph.D. program, and the **Brown University fiasco**. The latter is well explained in the “*Mathematical Apocrypha Redux*” (see the relevant section here) by the inimitable Steven Krantz. Rating-wise, this was a disaster for Brown — just read the Krantz’s description.

The Rochester story is rather well documented and is a good case of study for those feeling too comfortable. Start with this *Notices* article, proceed to *NY Times*, then to protest description, and this followup in the *Notices* again. Good news, right? Well, I know for a fact that other administrators are also making occasional (largely unsuccessful) moves to do this, but I can’t name them, I am afraid.

#### Predictable apocalypse

Let’s take Amy Wax’s proposal seriously, and play out **what would happen if 90-93% of US graduate programs in mathematics are closed on January 1, 2020**. By law. Say, the US Congress votes to deny all federal funds to universities if they maintain a math Ph.D. program, except for the top 15 out of about 180 graduate programs according to *US News*. Let’s ignore the legal issues this poses. Just note that there are various recent and older precedents of federal government interfering with state and private schools (sometimes for a good cause).

Let’s just try to quickly game out what would happen. As with any post-apocalyptic fiction, I will not provide any proofs or reasoning. But it’s all “reality based”, as two such events did happened to mathematicians in the last century, one of them deeply affecting me: the *German “academic reforms”* in late 1930s (see e.g. here or there), and the *Russian exodus* in early 1990s (see e.g. here or there, or there). Another personally familiar story is an implosion of mathematics at Bell Labs in late 1990s. Although notable, it’s on a much smaller scale and to my knowledge has not been written about (see the discussion here, part 6).

**First**, there will be huge exodus of distinguished mathematics faculty from school outside of the 15 schools. These include members of the National Academy of Sciences, numerous ICM speakers, other award winners, etc. Some will move overseas (Canada, Europe, Japan, China, etc.), some will retire, some leave academia. Some will simply stop doing research given the lack of mathematical activity at the department and no reward for doing research.

**Second**, outside of top 15, graduate programs in other subjects notice falling applications resulting in their sliding in world ranking. These include other physical sciences, economics and computer science. Then biological and social sciences start suffering. These programs start having their own exodus to top 15 school and abroad.

**Third**, given the sliding of graduate programs across the board, the undergraduate education goes into decline across the country. Top US high school students start applying to school abroad. Many eventually choose to stay in these countries who welcome their stem excellence.

**Fourth**, the hitech, fintech and other science heavy industries move abroad closer to educated employees. United States loses its labor market dominance and starts bleeding jobs across all industries. The stocks and housing market dip down.

**Fifth**, under strong public pressure the apocalyptic law is repealed and all 180 Ph.D. programs are reinstated with both state and federal financial support. To everyone’s surprise, nobody is moving back. Turns out, destroying is much faster and easier than rebuilding, as both Germany and Russia discovered back in the 20th century. From that point on, January 1, 2020 became known as the day the math died.

#### Final message:

Dear Amy Wax and Glenn Loury! Please admit that you are wrong. Or at least plead ignorance and ask for forgiveness. I don’t know if you will ever see this post or have any interest in debating the proposition I quoted, but I am happy to do this with you. Any time, any place, any style. Because the future of academia is important to all of us.

## Just combinatorics matters

I would really like everyone to know that every time you say or write that something is “just combinatorics” somebody rolls his eyes. Guess who?

Here is a short collection of “just combinatorics” quotes. It’s a followup on my “What is Combinatorics?” quotes page inspired by the “What is Combinatorics?” blog post.

## You should watch combinatorics videos!

Here is my collection of links to *Combinatorics* *videos,* which I assembled over the years, and recently decided to publish. In the past few years the number of videos just exploded. We clearly live in a new era. This post is about how to handle the transition.

#### What is this new collection?

I selected over 400 videos of lectures and seminars in Combinatorics, which I thought might be of interest to a general audience. I tried to cover a large number of areas both within Combinatorics and related fields. I have seen many (but not all!) of the talks, and think highly of them. Sometimes I haven’t seen the video, but have heard this talk “live” at the same or a different venue, or read the paper, etc. I tried to be impartial in my selection, but I am sure there is some bias towards some of my favorite speakers.

The collection includes multiple lectures by Noga Alon, Persi Diaconis, Gil Kalai, Don Knuth, László Lovász, János Pach, Vic Reiner, Paul Seymour, Richard Stanley, Terry Tao, Xavier Viennot, Avi Wigderson, Doron Zeilberger, and many many others. Occasionally the speakers were filmed giving similar talks at different institutions, so I included quick links to those as well so the viewer can choose.

Typically, these videos are from some workshops or public lecture series. Most are hosted on the institution websites, but a few are on YouTube or Vimeo (some of these are broken into several parts). The earliest video is from 1992 and the most recent video was made a few days ago. Almost all videos are from the US or Canada, with a few recent additions from Europe. I also added links to a few introductory lectures and graduate courses on the bottom of the page.

#### Why now?

Until a couple of years ago, the videos were made only at a few conference centers such as Banff, MSRI and IAS. The choice was sparse and the videos were easy to find. The opposite is true now, on both counts. The number of recorded lectures in all areas is in tens of thousands, they are spread across the globe, and navigating is near impossible unless you know exactly what you are looking for. In fact, there are so many videos I really struggled with the choice of which to include (and also with which of them qualify as Combinatorics). I am not sure I can maintain the collection in the future – it’s already getting too big. Hopefully, some new technology will come along (see below), but for now this will do.

#### Why Combinatorics?

That’s what I do. I try to think of the area as broad as possible, and apologize in advance if I omitted a few things. For the subarea division, I used as a basis my own Wikipedia entry for Combinatorics (weirdly, you can listen to it now in a robotic voice). The content and the historical approach within sub-areas is motivated by my views here on what exactly is Combinatorics.

#### Why should you start watching videos now?

First, because you can. One of the best things about being in academia is the ability (in fact, necessity) to learn. You can’t possibly follow everything what happens in all fields of mathematics and even all areas of combinatorics. Many conferences are specialized and the same people tend to meet a year after year, with few opportunities for outsiders to learn what’s new over there. Well, now you can. Just scroll down the list and (hopefully) be amazed at the number of classical works (i.e. over 5 y.o.) you never heard of, the variety of recent developments and connections to other fields. So don’t just watch people in your area from workshops you missed for some reason. Explore other areas! You might be surprised to see some new ideas even on your favorite combinatorial objects. And if you like what you see, you can follow the links to see other videos from the same workshops, or search for more videos by the same speaker…

Second, you should start watching because it’s a very different experience. You already know this, of course. One can pause videos, go back and forward, save the video to watch it again, or stop watching it right in the beginning. This ability is to popular, Adam Sandler even made an awful movie about it… On the other hand, the traditional model of lecture attendance is where you either listen intently trying to understand in real time *and* take notes, or are bored out your mind but can’t really leave. It still has its advantages, but clearly is not always superior. Let me elaborate on this below.

#### How to watch videos?

This might seem like a silly question, but give me a chance to suggest a few ideas…

0) Prepare for the lecture. Make sure to have enough uninterrupted time. Lock the door. Turn off the cell phone. Download and save the video (see below). Download and save the slides. Search for them if they are not on the lecture website (some people put them on their home pages). Never delete anything – store the video on an external hard drive if you are running out of space. Trust me, you never know when you might need it again, and the space is cheap anyway…

Some years ago I made a mistake by not saving Gil Kalai’s video of a talk titled “Results and Problems around Borsuk’s Conjecture”. I found it very inspiring — it’s the only talk I referenced it in my book. Well, apparently, in its infinite wisdom, PIMS lost the video and now only the audio is available, which is nearly useless for a blackboard talk. What a shame!

1) Use 2 devices. Have the video on a big screen, say, a large laptop or a TV hooked to your laptop. If the TV is too far, use a wireless mouse to operate a laptop from across the room or something like a Google stick to project from a far. Then, have the slides of the talk opened on your tablet if you like taking computer notes or just like scrolling by hand gestures, or on your other laptop if you don’t. The slides are almost universally in .pdf and most software including the Adobe Reader allows to take notes straight in the file.

Another reason to have slides opened is the inability for some camera people to understand what needs to be filmed. This is especially severe if they just love to show the unusual academic personalities, or are used to filming humanities lectures where people read at the podium. As a result, occasionally, you see them pointing a camera to a slide full of formulas for 2 seconds (and out of focus), and then going back for 2 minutes filming a speaker who is animatedly pointing to the screen (now invisible), explaining the math. Ugh…

2) If the subject is familiar and you feel bored with the lengthy introduction, scroll the slides until you see something new. This will give you a hint to where you should go forward in the video. And if you did miss some definition you can pause the video and scroll the slides to read it.

3) If there are no slides, or you want to know some details which the speaker is purposefully omitting, pause the video and download the paper. I do this routinely while listening to talks, but many people are too shy to do this out of misplaced fear that others might think they are not paying attention. Well, there is no one to judge you now.

4) If you are the kind of person who likes to ask questions to clarify things, you still can. Pause the video and search the web for the answer. If you don’t find it, ask a colleague by skype, sms, chat, email, whatever. If everything fails – write to the speaker. She or he might just tell you, but don’t be surprised if they also ignore your email…

5) If you know others who might be interested in the video lecture, just make it happen. For example, you can organize a weekly seminar where you and your graduate students watch the lectures you choose (when you have no other speakers). If students have questions, pause the video and try to answer them. In principle, if you have a good audience the speaker may agree to answer the questions for 5-10 min over skype, after you are done watching. Obviously, I’ve never seen this happen (too much coordination?). But why not try this – I bet if you ask nicely many speakers would agree to this.

6) If you already know a lot about the subject, haven’t been following it recently but want to get an update, consider binge watching. Pick the most recent lecture series and just let it run when you do house shores or ride a subway. When things get interesting, you will know to drop everything and start paying attention.

#### Why should you agree to be videotaped?

Because the audience is ready to see your talks now. Think of this as another way of reaching out with your math to a suddenly much broader mathematical community (remember the “broad impact” section on your NSF grant proposal?). Let me just say that there is nothing to fear – nobody is expecting you to have acting skills, or cares that you have a terrible haircut. But if you make a little effort towards giving a good talk, your math will get across and you might make new friends.

Personally, I am extremely uncomfortable being videotaped – the mere knowledge of the camera filming makes me very nervous. However I gradually (and grudgingly) concluded that this is now a part of the job, and I have to learn how to do this well. Unfortunately, I am not there yet…

Yes, I realize that many traditionalists will object that “something will be missing” when you start aiming at giving good video talks at the expense of local audience. But the world is changing if hasn’t changed already and you can’t stop the tide. This happened before, many times. For example, at some point all the big Hollywood studios have discovered that they can make movies simpler and make a great deal more money overseas to compensate for the loss in the US market. They are completely hooked now, and no matter what critics say this global strategy is likely irreversible. Of course, this leaves a room for a niche market (say, low budget art-house movies), but let’s not continue with this analogy.

#### How to give video lectures?

Most people do nothing special. Just business as usual, hook up the mike and hope it doesn’t distort your voice too bad. That’s a mistake. Let me give a number of suggestions based mostly on watching many bad talks. Of course, the advice for giving regular talks apply here as well.

0) Find out ahead of time if you get filmed and where the camera is. During the lecture, don’t run around; try to stand still in full view of the camera and point to the screen with your hands. Be animated, but without sudden moves. Don’t use a laser pointer. Don’t suddenly raise your voice. Don’t appeal to the previous talks at the same workshop. Don’t appeal to people in the audience – the camera can rarely capture what they say or do. If you are asked a question, quickly summarize it so the viewer knows what question you are answering. Don’t make silly off-the-cuff jokes (this is a hard one).

1) Think carefully whether you want to give a blackboard or a computer talk. This is crucial. If it’s a blackboard talk, make sure your handwriting is clear and most importantly BIG. The cameras are usually in the very back and your handwriting won’t be legible otherwise. Unless you are speaking the Fields Institute whose technology allows one to zoom into the high resolution video, nobody might be able to see what you write. Same goes for handwritten slides unless they are very neat, done on a laptop, and the program allows you to increase their size. Also, the blackboard management becomes a difficult issue. You should think through what results/definitions should stay on the blackboard visible to the camera at all times and what can be safely deleted or lifted up if the blackboard allows that.

2) If it’s a computer talk, stick to your decision and make a lot of effort to have the slides look good. Remember, people will be downloading them… Also, make every effort NOT to answer questions on a blackboard next to the screen. The lightning never works – the rooms are usually dimmed for a computer talk and no one ever thinks of turning the lights on just for 30 seconds when you explain something. So make sure to include all your definition, examples, etc, in the slides. If you don’t want to show some of them – in PowerPoint there is a way to hide them and pull them up only if someone asks to clarify something. I often prepare the answers to some standard questions in the invisible part of my slides (such as “What happens for other root systems?” or “Do your results generalize to higher dimensions?”), sometimes to unintended comedic effect. Anyhow, think this through.

3) Don’t give the same videotaped talk twice. If you do give two or more talks on the same paper, make some substantial changes. Take Rota’s advice: “Relate to your audience”… If it’s a colloquium talk, make a broad accessible survey and include your results at the end. Or, if it’s a workshop talk, try to make an effort to explain most proof ideas, etc. Make sure to have long self-explanatory talk titles to indicate which talk is which. Follow the book industry lead for creating subtitles. For example use “My most recent solution of the Riemann hypothesis, an introduction for graduate students” or “The Pythagorean theorem: How to apply it to the Langlands Program and Quantum Field Theory”.

4) Download and host your own videos on your website alongside your slides and your relevant paper(s), or at least make clear links to them from your website. You can’s trust anyone to keep your files. Some would argue that re-posting them on YouTube will then suffice. There are two issues here. First, this is rarely legal (see below). Second, as I mentioned above, many viewers would want to have a copy of the file. Hopefully, in the future there will be a copyright-free arXiv-style video hosting site for academics (see my predictions below).

5) In the future, we would probably need to consider having a general rule about adding a file with errata and clarifications to your talk, especially if something you said is not exactly correct, or even just to indicate, post-factum, whether all these conjectures you mentioned have been resolved and which way. The viewers would want to know.

For example, my student pointed out to me that in my recent Banff talk, one of my lemmas is imprecise. Since the paper is already available, this is not a problem, but if it wasn’t this could lead to a serious confusion.

6) Watch other people’s videos. Pay attention to what they do best. Then watch your own videos. I know, it’s painful. Turn off the sound perhaps. Still, this might help you to correct the worst errors.

7) For advanced lecturers – try to play with the format. Of course, the videos allow you to do things you couldn’t do before (like embedding links to papers and other talks, inserting some Java demonstration clips, etc.), but I am talking about something different. You can turn the lecture into an artistic performance, like this amazing lecture by Xavier Viennot. Not everyone has the ability or can afford to do this, but having it recorded can make it worthwhile, perhaps.

#### Know your rights

There are some delicate legal issues when dealing with videos, with laws varying in different states in the US (and in other countries, of course). I am not an expert on any of this and will write only as I understand them in the US. Please add a comment on this post if you think I got any of this wrong.

1) Some YouTube videos of math lectures look like they have been shut by a phone. I usually don’t link to those. As I understand the law on this, anyone can film a public event for his/her own consumption. However, you and the institution own the copyright so the YouTube posting is illegal without both of yours explicit permission (written and signed). You can fight this by sending a “cease and desist” letter to the person who posted the video, but contacting YouTube directly might be more efficient – they have a large legal department to sort these issues.

2) You are typically asked to sign away your rights before your talk. If an institution forgot to do this, you can ask to take your talk down for whatever reason. However, even if you did sign the paper you can still do this – I doubt the institution will fight you on this just to avoid bad publicity. A single email to the IT department should suffice.

3) If the file with your talk is posted, it is (obviously) legal for you to download it, but not to post it on your website or repost elsewhere such as YouTube or WordPress. As far as I am concerned, you should go ahead and post it on your university website anyway (but not on YT or WP!). Many authors typically post all their papers on their website even if they don’t own a copyright on them (which is the case or virtually all papers before 2000). I am one of them. The publishers just concluded that this is the cost of doing business – if they start going after people like us, the authors can revolt. The same with math videos. The institutions probably won’t have a problem with your university website posting as long as you acknowledge the source. But involving a third party creates a host of legal problems since these internet companies are making money out of the videos they don’t own a copyright for. Stay away from this.

4) You can the edit the video by using numerous software, some of which is free to download. Your can remove the outside noise, make the slides sharper, everything brighter, etc. I wouldn’t post a heavily edited video when someone else owns a copyright, but a minor editing as above is ok I think.

5) If the institution’s website does not allow to download the video but has a streaming option (typically, the Adobe Flash or HTML5), you can still legally save it on your computer, but this depends on what software you choose. There are plenty of software which capture the video being played on your computer and save it in a file. These are 100% legal. Other websites play the videos on *their* computers and allow you to download afterwards. This is probably legal at the institutions, but a gray area at YouTube or Vimeo which have terms of service these companies may be violating. Just remember – such videos can only be legal for personal consumption. Also, the quality of such recording is typically poor – having the original file is much better.

#### What will happen in the future?

Yes, I will be making some predictions. Not anything interesting like Gian-Carlo Rota’s effort I recently analyzed, but still…

1) Watching and giving video lectures will become a norm for everyone. The ethical standards will develop that everyone gets to have the files of videos they made. Soon enough there will be established some large well organized searchable (and not-for-profit!) math video depositories arXiv-style where you can submit your video and link to it from your website and where others can download from. Right now companies like DropBox allow you to do this, but it’s for-profit (your have to pay extra for space), and it obviously needs a front like the arXiv. This would quickly make my collection a thing of the past.

2) Good math videos will become a “work product”, just like papers and books. It is just another venue to communicate your results and ideas. People will start working harder on them. They will become a standard item on CVs, grant applications, job promotions, etc. More and more people will start referencing them just like I’ve done with Kalai’s talk. Hopefully part 1) will happen soon enough so all talks get standard and stable links.

3) The video services will become ubiquitous. First, all conference centers will acquire advanced equipment in the style of the Banff Center which is voice directed and requires no professional involvement except perhaps at the editing stage. Yes, I am thinking of you, MFO. A new library is great, but the talks you could have recorded there are priceless – it’s time to embrace the 21st century….

Second, more and more university rooms will be equipped with the cameras, etc. UCLA already has a few large rooms like that (which is how we make the lamely named BruinCasts), but in time many department will have several such rooms to hold seminars. The storage space is not an issue, but the labor cost, equipment and the broadband are. Still, I give it a decade or two…

4) Watching and showing math videos will become a standard part of the research and graduate education. Ignore the doomsayers who proclaim that this will supplant the traditional teaching (hopefully, not in our lifetime), but it’s clear already there are unexplored educational benefits from this. This should be of great benefit especially to people in remote locations who don’t have access to such lectures otherwise. Just like the Wikipedia has done before, this will even the playing field and help the talent to emerge from unlikely places. If all goes well, maybe the mathematics will survive after all…

**Happy watching everyone! **

## Grading Gian-Carlo Rota’s predictions

In this post I will try to evaluate Gian-Carlo Rota‘s predictions on the future of Combinatorics that he made in this 1969 article. He did surprisingly well, but I am a tough grader and possibly biased about some of the predictions. Judge for yourself…

#### It’s tough to make predictions, especially about the future

It is a truth universally acknowledged that humans are very interested in predicting the future. They do this incessantly, compiling the lists of the best and the worst, and in general can’t get enough of them. People tend to forget wrong predictions (unless they are outrageously wrong). This allows a person to make the same improbable predictions over and over and over and over again, making news every time. There are even professional prognosticators who make a living writing about the future of life and technology. Sometimes these predictions are rather interesting (see here and there), but even the best ones are more often wrong than right…

Although rarely done, analyzing past predictions is a useful exercise, for example as a clue to the truthiness of the modern day oracles. Of course, one can argue that many of the political or technology predictions linked above are either random or self-serving, and thus not worth careful investigation. On the other hand, as we will see below, Rota’s predictions are remarkably earnest and sometimes even brave. And the fact that they were made so long ago makes them uniquely attractive, practically begging to be studied.

Now, it has been 45 years since Rota’s article, basically an eternity in the life span of Combinatorics. There, Rota describes Combinatorics as “*the least developed branches of mathematics*“. A quick review of the last few quotes on this list I assembled shows how much things have changed. Basically, the area moved from an ad hoc collection of problems to a 360-degree panorama of rapidly growing subareas, each of which with its own deep theoretical results, classical benchmarks, advanced tools and exciting open problems. This makes grading rather difficult, as it suggests that even random old predictions are likely to be true – just about anything people worked on back in the 1960 has been advanced by now. Thus, before turning to Rota, let’s agree on the grading scale.

#### Grading on a curve

To give you the feel for my curve, I will use the celebrated example of the 1899-1901 postcards in the En L’An 2000 French series, which range from insightful to utter nonsense (click on the titles to view the postcards, all available from Wikimedia).

**•** * Electric train*. Absolutely. These were introduced only in 1940s and have been further developed in France among other countries. Note the aerodynamic shape of the engine. Grade:

**A**.

**•** * Correspondance cinema. *Both the (silent) cinema and phonograph were invented by 1900; the sound came to movie theaters only in 1927. So the invention here is of a home theater for movies with sound. Great prediction although not overly ambitious. Grade:

**A-**.

**•** ** Military cyclists**. While bicycle infantry was already introduced in France by 1900, military use of motorcycles came much later. The idea is natural, but some designs of bikes from WW2 are remarkably similar. Some points are lost due to the lack of widespread popularity in 2000. Grade:

**B+**.

**•** ** Electric scrubbing**. This is an electric appliance for floor cleaning. Well, they do exist, sort of, obviously based on different principles. In part due to the modern day popularity, this is solid prediction anyway. Grade:

**B**.

**•** * Auto-rollers*. Roller skates have been invented in 18th century and by 1900 became popular. So no credit for the design, but extra credit for believing in the future of the mean of transportation now dominated by rollerblades. Thus the author’s invention is in the category of “motorized personal footwear”. In that case the corresponding modern invention is of the electric skateboard which has only recently become available, post-2000 and yet to become very popular. Grade:

**B-**.

**•** ** Barber**. The author imagines a barber operating machinery which shaves and cuts customer’s hair. The design is so ridiculous (and awfully dangerous), it’s a good thing this never came about. There are however electric shavers and hair cutters which are designed very differently. Grade:

**C**.

* • Air cup*. The Wright brothers’ planes had similar designs, so no credit again. The author assumes that personal air travel will become commonplace, and at low speeds and heights. This is almost completely false. However, unfortunately, and hopefully only very occasionally, some pilots do enjoy one for the road. Grade:

**D**.

**•** * Race in Pacific*. The author imagines that the public spectacle of horse racing will move underwater and become some kind of fish racing. Ridiculous. Also a complete failure to envision modern popularity of auto racing which already began in Paris in 1887. Grade:

**F**.

#### Rota’s predictions on combinatorial problems:

In his paper, Rota writes:

Fortunately, most combinatorial problems can be stated in everyday language. To give an idea of the present state of the field, we have selected a few of the many problems that are now being actively worked upon.

We take each of these “problems” as a kind of predictions of where the field is going. Here are my (biased and possibly uninformed) grades for each problem he mentions.

**1) ** **The Ising Problem****.** I think it is fair to say that since 1969 combinatorics made no contribution in this direction. While physicists and probabilists continue studying this problem, there is no exact solution in dimension 3 and higher. Grade: **F**.

**2) ** ** Percolation Theory.** The study of percolation completely exploded since 1969 and is now a subject of numerous articles in both probability, statistical physics and combinatorics, as well as several research monographs. One connection is given by an observation that

*p*-percolation on a complete graph

*K*gives the Erdős–Rényi random graph model. Even I accidentally wrote a few papers on the subject some years ago (see one, two and three). Grade:

_{n}**A**.

**3)** * The Number of Necklaces, and Polya’s Problem.* Taken literally, the necklaces do come up in combinatorics of words and free Lie algebra, but this context was mentioned by Rota already. As far as I can tell, there are various natural (and interesting) generalizations of necklaces, but none surprising. Of course, if the cyclic/dihedral group action here is replaced by other actions, e.g. the

*symmetric group*, then modern developments are abundant. But I think it’s a reach too far, since Rota knew the works of Young, MacMahon, Schur and others but does not mention any of it. Similarly, Polya’s theorem used to be included in all major combinatorics textbooks (and is included now, occasionally), but is rarely taught these days. Simply put, the g.f. implications haven’t proved useful. Grade:

**D**.

**4)** * Self-avoiding Walk.* Despite strong interest, until recently there were very few results in the two-dimensional case (some remarkable results were obtained in higher dimensions). While the recent breakthrough results (see here and there) do use some interesting combinatorics, the authors’ motivation comes from probability. Combinatorialists did of course contribute to the study of somewhat related questions on enumeration of various classes of polyomino (which can be viewed as self-avoiding cycles in the grid, see e.g. here). Grade:

**C**.

**5)** ** The Traveling Salesman Problem.** This is a fundamental problem in optimization theory, connected to the study of Hamiltonian cycles in Graph Theory and numerous other areas. It is also one of the earliest NP-hard problems still playing a benchmark role in Theoretical Computer Science. No quick of summary of the progress in the past 45 years would give it justice. Note that Rota’s paper was written before the notions of NP-completeness. In this light, his emphasis on algorithmic complexity and allusions to Computability Theory (e.g. unsolvable problems) are most prescient. So are his briefly mentioned connections to topology which are currently a popular topic. Well done! Grade:

**A+**.

**6)** * The Coloring Problem.* This was a popular topic way before Rota’s article (inspired by the Four Color Theorem, the chromatic polynomial, etc.), and continues to be even more so, with truly remarkable advances in multiple directions. Note Rota’s mentioning of matroids which may seem extraneous here at first, but in fact absolutely relevant indeed (in part due to Rota’s then-ongoing effort). Very good but unsurprising prediction. Grade:

**A-**.

**7) ** * The Pigeonhole Principle and Ramsey’s Theorem.* The Extremal Graph Theory was about to explode in many directions, with the the Erdős-Stone-Simonovits theorem proved just a few years earlier and the Szemerédi regularity lemma a few years later. Still, Rota never mentions Paul Erdős and his collaborators, nor any of these results, nor potential directions. What a missed opportunity! Grade:

**B+**.

#### Rota’s predictions on combinatorial areas:

In the concluding section “The Coming Explosion”, Rota sets this up as follows:

Before concluding this brief survey, we shall list the main subjects in which current work in combinatorial theory is being done.

Here is a list and more of my comments.

**1)** ** Enumerative Analysis.** Sure. But this was an easy prediction to make given the ongoing effort by Carlitz, Polya, Riordan, Rota himself and many other peope. Grade:

**A-**.

**2)** * Finite Geometries and Block Designs.* The subject was already popular and it did continue to develop but perhaps at a different pace and directions than Rota anticipated (Hadamard matrices, tools from Number Theory). In fact, a lot of later work was connection with with Group Theory (including some applications of CFSG which was an ongoing project) and in Coding Theory (as Rota predicted). Grade:

**B-**.

**3)** ** Applications to Logic.** Rota gives a one-sentence desctiption:

The development of decision theory has forced logicians to make wide use of combinatorial methods.

There are various important connections between Logic and Combinatorics, for example in Descriptive Set Theory (see e.g. here or more recent work by my future UCLA colleague there). Note however, that Infinitary Combinatorics was already under development, after the Erdős-Rado theorem (1956). Another very interesting and more recent connection is to Model Theory (see e.g. here). But the best interpretation here I can think of here are the numerous applications to Game Theory, which already existed (Nash’s equilibrium theorem is from 1950) and was under rapid development. Either way, Rota was too vague in this case to be given much credit. Grade: **C**.

**4)** ** Statistical Mechanics.** He mentions the Ising model again and insists on “close connections with number theory”. One can argue this all to be too vague or misdirected, but the area does indeed explode in part in the directions of problems Rota mentions earlier. So I am inclined to give him benefit of the doubt on this one. Grade:

**A-**.

#### The final grade

In total, Rota clearly got more things right than wrong. He displayed an occasional clairvoyance, had some very clever insights into the future, but also a few flops. Note also the near complete lack of self-serving predictions, such as the Umbral Calculus that Rota was very fond of. Since predictions are hard, *successes* have a great weight than failures. I would give a *final grade* somewhere between **A-** and **B+** depending on how far into the future do we think he was making the predictions. Overall, good job, Gian-Carlo!

**P.S.** Full disclosure: I took a few advanced classes with Gian-Carlo Rota as a graduate student cross registering from Harvard to MIT, and he may have graded my homeworks (this was in 1994-1996 academic years). I don’t recall the final grades, but I think they were good. Eventually Rota wrote me a letter of recommendation for a postdoc position.

UPDATE (October 16, 2019)

I would still give a failing grade for * Race in Pacific*. But having seen

*The Aquama*n, the similarities are too eerie to ignore, so this prediction needs an upgrade. Say,

**D-**.

## Who named Catalan numbers?

**The question.** A year ago, on this blog, I investigated Who computed Catalan numbers. Short version: it’s Euler, but many others did a lot of interesting work soon afterwards. I even made a Catalan Numbers Page with many historical and other documents. But I always assumed that the dubious honor of naming them after Eugène Catalan belongs to Netto. However, recently I saw this site which suggested that it was E.T. Bell who named the sequence. This didn’t seem right, as Bell was both a notable combinatorialist and mathematical historian. So I decided to investigate who did the deed.

**First**, I looked at Netto’s *Lehrbuch der Combinatorik* (1901). Although my German is minuscule and based on my knowledge of English and Yiddish (very little of the latter, to be sure), it was clear that Netto simply preferred counting of Catalan’s brackets to triangulations and other equivalent combinatorial interpretations. He did single out Catalan’s work, but mentioned Rodrigues’s work as well. In general, Netto wasn’t particularly careful with the the references, but in fairness neither were were most of his contemporaries. In any event, he never specifically mentioned “Catalan Zahlen”.

**Second**, I checked the above mentioned 1938 Bell’s paper in the *Annals*. As I suspected, Bell mentioned “*Catalan’s numbers*” only in passing, and not in a way to suggest that Catalan invented them. In fact, he used the term “*Euler-Segner sequence*” and provided careful historical and more recent references.

**Next** on my list was John Riordan‘s *Math Review* MR0024411, of this 1948 Motzkin’s paper. The review starts with “The Catalan numbers…”, and indeed might have been the first time this name was introduced. However, it is naive to believe that this MR moved many people to use this expression over arguably more cumbersome “Euler-Segner sequence”. In fact, Motzkin himself is very careful to cite Euler, Cayley, Kirkman, Liouville, and others. My guess is this review was immediately forgotten, but was a harbinger of things to come.

Curiously, Riordan does this again in 1964, in a *Math Review* on an English translation of a popular mathematics book by A.M. Yaglom and I.M. Yaglom (published in Russian in 1954). The book mentions the sequence in the context of counting triangulations of an *n*-gon, without calling it by any name, but Riordan recognizes them and uses the term “Catalan numbers” in the review.

**The answer.** To understand what really happened, see this Ngram chart. It clearly shows that the term “Catalan numbers” took off after 1968. What happened? Google Books immediately answers – Riordan’s *Combinatorial Identities* was published in 1968 and it used “the Catalan numbers”. The term took off and became standard within a few years.

**What gives?** It seems, people really like to read books. Intentionally or unintentionally, monographs tend to standardize the definitions, notations, and names of mathematical objects. In his notes on *Mathematical writing*, Knuth mentions that the term “NP-complete problem” became standard after it was used by Aho, Hopcroft and Ullman in their famous *Data Structures and Algorithms* textbook. Similarly, Macdonald’s *Symmetric Functions and Hall Polynomials* became a standard source of names of everything in the area, just as Stanley predicted in his prescient review.

The same thing happened to Riordan’s book. Although now may be viewed as tedious, somewhat disorganized and unnecessarily simplistic (Riordan admitted to dislike differential equations, complex analysis, etc.), back in the day there was nothing better. It was lauded as “excellent and stimulating” in *P.R. Stein’s review,* which continued to say “*Combinatorial identities* is, in fact, a book that must be *read*, from cover to cover, and several times.” We are guessing it had a tremendous influence on the field and cemented the terminology and some notation.

**In conclusion.** We don’t know why Riordan chose the term “Catalan numbers”. As Motzkin’s paper shows, he clearly knew of Euler’s pioneer work. Maybe he wanted to honor Catalan for his early important work on the sequence. Or maybe he just liked the way it sounds. But Riordan clearly made a conscious decision to popularize the term back in 1948, and eventually succeeded.

UPDATE (Feb. 8, 2014) Looks like Henry Gould agrees with me (ht. Peter Luschny). He is, of course, the author of a definitive bibliography of Catalan numbers. Also, see this curious argument against naming mathematical terms after people (ht. Reinhard Zumkeller).

UPDATE** **(Aug 25, 2014)**:** I did more historical research on the subject which is now reworked into an article History of Catalan Numbers.

UPDATE (Oct 13, 2016)**:** I came across a quote from Riordan himself (see below) published in this book review. In light of our investigation, this can be read as a tacit admission that he misnamed the sequence. Note that Riordan seemed genially contrite yet unaware of the fact that Catalan learned about the sequence from Liouville who knew about Euler and Segner’s work. So the “temporary blindness” he is alleging is perhaps misaddressed…

“Nevertheless, the pursuit of originality and generality has its perils. For one

thing, the current spate of combinatorial mappings has produced the feeling

that multiplicity abounds. Perhaps the simplest example is the continuing

appearances of the Catalan numbers [..] Incidentally, these numbers

are named after E. Catalan because of a citation in Netto’s *Kombinatorik*, in

relation to perhaps the simplest bracketing problem, proposed in 1838. An

earlier appearance, which I first learned from Henry Gould, is due to the

Euler trio, Euler-Fuss-Segner, dated 1761. There are now at least forty

mappings, hence, forty diverse settings for this sequence; worse still, no end

seems in sight. In this light, the Catalan (or Euler-Fuss-Segner) originality

may be regarded as temporary blindness.”

## Combinatorial briefs

I tend to write longish posts, in part for the sake of clarity, and in part because I can – it is easier to express yourself in a long form. However, the brevity has its own benefits, as it forces the author to give succinct summaries of often complex and nuanced views. Similarly, the lack of such summaries can provide plausible deniability of understanding the basic points you are making.

This is the second time I am “inspired” by the *Owl *blogger who has a Tl;Dr style response to my blog post and rather lengthy list of remarkable quotations that I compiled. So I decided to make the following Readers Digest style summaries of this list and several blog posts.

#### 1) Combinatorics has been sneered at for decades and struggled to get established

In the absence of *History of Modern Combinatorics* monograph, this is hard to prove. So here are selected quotes, from the above mentioned quotation page. Of course, one should reade them in full to appreciate and understand the context, but for our purposes these will do.

Combinatorics is the slums of topology – Henry Whitehead

Scoffers regard combinatorics as a chaotic realm of binomial coefficients, graphs, and lattices, with a mixed bag of ad hoc tricks and techniques for investigating them. [..] Another criticism of combinatorics is that it “lacks abstraction.” The implication is that combinatorics is lacking in depth and all its results follow from trivial, though possible elaborate, manipulations. This argument is extremely misleading and unfair. – Richard Stanlеy (1971)

The opinion of many first-class mathematicians about combinatorics is still in the pejorative. While accepting its interest and difficulty, they deny its depth. It is often forcefully stated that combinatorics is a collection of problems which may be interesting in themselves but are not linked and do not constitute a theory. – László Lovász (1979)

Combinatorics [is] a sort of glorified dicethrowing. – Robert Kanigel (1991)

This prejudice, the view that combinatorics is quite different from ‘real mathematics’, was not uncommon in the twentieth century, among popular expositors as well as professionals. – Peter Cameron (2001)

Now that the readers can see where the “traditional sensitivities” come from, the following quote must come as a surprise. Even more remarkable is that it’s become a conventional wisdom:

Like number theory before the 19th century, combinatorics before the 20th century was thought to be an elementary topic without much unity or depth. We now realize that, like number theory, combinatorics is infinitely deep and linked to all parts of mathematics. – John Stillwell (2010)

Of course, the prejudice has never been limited to Combinatorics. Imagine how an expert in Partition Theory and *q*-series must feel after reading this quote:

[In the context of Partition Theory] Professor Littlewood, when he makes use of an algebraic identity, always saves himself the trouble of proving it; he maintains that an identity, if true, can be verified in a few lines by anybody obtuse enough to feel the need of verification. – Freeman Dyson (1944), see here.

#### 2) Combinatorics papers have been often ostracized and ignored by many top math journals

This is a theme in this post about *the Annals*, this MO answer, and a smaller theme in this post (see *Duke* paragraph). This bias against Combinatorics is still ongoing and hardly a secret. I argue that on the one hand, the situation is (slowly) changing for the better. On the other hand, if some journals keep the proud tradition of rejecting the field, that’s ok, really. If only they were honest and clear about it! To those harboring strong feelings on this, listening to some breakup music could be helpful.

#### 3) Despite inherent diversity, Combinatorics is one field

In this post, I discussed how I rewrote Combinatorics *Wikipedia* article, largely as a collection of links to its subfields. In a more recent post mentioned earlier I argue why it is hard to define the field as a whole. In many ways, Combinatorics resembles a modern nation, united by a language, culture and common history. Although its borders are not easy to define, suggesting that it’s not a separate field of mathematics is an affront to its history and reality (see two sections above). As any political scientist will argue, nation borders can be unhelpful, but are here for a reason. Wishing borders away is a bit like French “race-ban” – an imaginary approach to resolve real problems.

Gowers’s “two cultures” essay is an effort to describe and explain cultural differences between Combinatorics and other fields. The author should be praised both for the remarkable essay, and for the bravery of raising the subject. Finally, on the *Owl’s* attempt to divide Combinatorics into “conceptual” which “has no internal reasons to die in any foreseeable future” and the rest, which “will remain a collection of elementary tricks, [..] will die out and forgotten [sic].” I am assuming the *Owl* meant here most of the “Hungarian combinatorics”, although to be fair, the blogger leaves some wiggle room there. Either way, “First they came for Hungarian Combinatorics” is all that came to mind.

## What is Combinatorics?

Do you think you know the answer? Do you think others have the same answer? Imagine you could go back in time and ask this question to a number of top combinatorialists of the past 50 years. What would they say? Would you agree with them at all?

Turns out, these answers are readily available. I collected them on this page of quotes. The early ones are uncertain, defensive, almost apologetic. The later ones are bolder, prouder of the field and its status. All are enlightening. Take your time, read them all in order.

#### Why bother?

During my recent MIT visit, Jacob Fox showed me this blog which I found to be rather derogatory in its treatment of combinatorics and notable combinatorialists. This brought me back to my undergraduate days in Moscow, reminded of the long forgotten but back then very common view of combinatorics as “second rate mathematics”. In the US, I always thought, this battle has been won before my time, back in the 1980s. The good guys worked hard and paved the road for all younger combinatorialists to walk on, and be proud of the field. But of course the internet has its own rules, and has room for every prejudice known to men.

While myself uninterested in engaging in conversation, I figured that there got to be some old “war-time” replies which I can show to the Owl blogger. As I see it, only the lack of knowledge can explain these nearsighted generalizations the blogger is showing. And in the age of *Google Scholar*, there really is no excuse for not knowing the history of the subject, and its traditional sensitivities.

But while compiling the list of quotes linked above, I learned a few things. I learned how tumultuous was the history of combinatorics, with petty fights and random turns into blind alleys. I learned how myopic were some of the people, and how clever and generous were others. I also discovered that there is a good answer to the question in the title (see below), but that answer is *not* a definition.

#### What do authorities say?

Not a lot, actually. The AMS MSC (which I love criticizing) lists Combinaorics as 05, on par with about 70 fields, such as Number Theory (11), Geometry (51), Probability (60) and Computer Science (68). It is also on the same level as Nonassociative rings (17), *K*-theory (19) and Integral equations (51), which are perfectly fine areas, just much smaller. It is one of the 32 categories on the arXiv, but who knows how these came about.

At the level of NSF, it is one of the 11 Disciplinary Research Programs, no longer lumped with “Algebra and Number Theory” (which remain joined at the hip according to NSF). Around the country, Combinatorics is fairly well represented at the top 100 universities, even if breaking “top 10” barrier remains difficult. Some are firmly in the “algebraic” camp, some in “probabilistic/extremal”, some have a lot of Graph Theory experts, but quite a few have a genuine mix.

This all reminded me of a story how I found out “*What is mathematics*“. It started with me getting a Master of Arts degree from Harvard. It arrived by mail, and made me unhappy. I thought they made a mistake, that I should have been given Master of Sciences. So I went to the registrar office, asked to see the director and explained the problem. The director was an old lady, who listened carefully, and replied “let me check”. She opened some kind of book, flipped a few pages and declared: “Yes, I see. No mistake made. Mathematics is an Art.” Seeing my disappointed face, she decided to console me “Oh, don’t worry, dear, it’s *always* been that way at Harvard…”

#### What the experts are saying.

About the title question, I mean. Let’s review the quotes page. Turns out, a lot of things, often contradicting each other and sometimes themselves. Some are cunning and ingenuous, while others are misleading or plain false. As the management maxim says, “where you stand depends on where you sit”. Naturally, combinatorialists in different areas have a very different view on the question.

Few themes emerge. First, that combinatorics is some kind of discrete universe which deals with discrete “configurations”, their existence and counting. Where to begin? This is “sort of” correct, but largely useless. Should we count logic, rectifiable knots and finite fields in, and things like Borsuk conjecture and algebraic combinatorics out? This is sort of like defining an elephant as a “large animal with a big trunk and big ears”. This “descriptive” definition may work for Webster’s dictionary, but if you have never seen an elephant, you really don’t know how big should be the ears, and have a completely wrong idea about what is a trunk. And if you have seen an elephant, this definition asks you to reject a baby elephant whose trunk and ears are smaller. Not good.

Second theme: combinatorics is defined by its tools and methods, or lack of thereof. This is more of a wishful thinking than a working definition. It is true that practitioners in different parts of combinatorics place a great value on developing new extensions and variations of the available tools, as well as ingenuous ad hoc arguments. But a general attitude, it seems, is basically “when it comes to problem solving, one can use whatever works”. For example, our recent paper proves unimodality results for the classical Gaussian coefficients and their generalizations via technical results for Kronecker coefficients, a tool never been used for that before. Does that make our paper “less combinatorial” somehow? In fact, some experts openly advocate that the more advanced the tools are, the better, while others think that “term ‘combinatorial methods’, has an oxymoronic character”.

Third theme: combinatorics is “special” and cannot be defined. Ugh… This reminds me of an old (1866), but sill politically potent Russian verse (multiple English translations) by Tyutchev. I can certainly understand the unwillingness to define combinatorics, but saying it is not possible is just not true.

Finally, a piecemeal approach. Either going over a long list of topics, or giving detailed and technical rules why something is and something isn’t combinatorics. But this bound to raise controversy, like who decides? For example, take PCM’s “few constraints” rule. Really? Somebody thinks block designs, distance-regular graphs or coding theory have too few constraints? I don’t see it that way. In general, this is an encyclopedia style approach. It can work on Wikipedia which is constantly updated and the controversies are avoided by constant search for a compromise (see also my old post), but it’s not a definition.

#### My answer, after Gian-Carlo Rota.

After some reading and thinking, I concluded that Gian-Carlo Rota’s 44 y.o. explanation in “Discrete thoughts” is exactly right. Let me illustrate it with my own (lame) metaphor.

Imagine you need to define Russia (*not* Tyutchev-style). You can say it’s the largest country by land mass, but that’s a description, not a definition. The worst thing you can do is try to define it as a “country in the North” or via its lengthy borders. You see, Russia is huge, spead out and disconnected. It lies to the North of China but has a disconnected common border, it has a 4253 mile border with Kazakhstan (longer than the US-Canada border excluding Alaska), surrounding the country from three sides, it lies North-West of Japan, East of Latvia, South-West of Lithuania (look it up!), etc. It even borders North Korea, not that this tiny border is much in use. Basically, Russian borders are complicated and are a result of numerous wars and population shifts; they have changed many times and might change again.

Now, Rota argues that Combinatorics is similarly formed by the battles, and can only be defined as such. It is a large interconnected field concentrated (but not coinciding!) around basic discrete tools and problems, but with tentacles reaching deep into “foreign territory”. Its current shape is a result of numerous “wars” – the borderline problems are tested on which tools are more successful, and whoever “wins”, gets to absorb a new subfield. For example, in its “war” with topology, combinatorics “won” graph theory and “lost” knot theory (despite a strong combinatorial influence). In other areas, such as computer science and discrete probability, Rota argues there a lot of cooperation, a mutually beneficial “joint governance” (all lame metaphors are mine). But as a consequence, if one is to define Combinatorics (or Russia), the historical-cultural approach would go best. Not all that different from Sheldon’s approach to define Physics “from the beginning”.

#### Summary.

In conclusion, let’s acknowledge that Combinatorics can indeed be defined in the same (lengthy historical) manner as a large diverse country, but such definition would be neither short nor enlightening, more like a short survey. As Danny Kleitman writes, in practice this lack of a clear and meaningful definition of the subject “never bothered him”, and we agree. I think it’s time to stop worrying about that. But if someone makes blank general statements painting all of combinatorics in a certain way, this is just indefensible.

UPDATE (May 29, 2013)

I thought I would add a link to this article by Gian-Carlo Rota, titled “What ‘is’ mathematics?” This was originally distributed by email on October 7, 1998. For those too young to remember the Fall of 1998, Bill Clinton’s testimony was released on September 21, 1998, with its infamous “It depends on what the meaning of the word ‘is’ is” quote. Rota’s email never mentions this quote, but is clearly influenced by it.

UPDATE (August 5, 2015)

Since this article was written, Russian borders changed again, and not in a way I could have imagined (or supported). I am guessing, Combinatorics boundaries also changed. See e.g. our latest blog post titled The power of negative thinking on the use of Computability in Enumerative Combinatorics.

## Who computed Catalan numbers?

I became rather interested in the early history of Catalan numbers after reading multiple somewhat contradictory historical accounts. Now that I checked the sources, most of which are available online (see my Catalan Numbers page), I think I understand what happened. While I conclude that Euler deserve most of the credit, as I see it, what really happened is a bit more complicated. Basically, this is a story of research collaboration, only fragments of which are known.

*Warning:* I am assuming you are familiar with basic results on Catalan numbers, which allows me to concentrate on the story rather than the math.

#### Conventional wisdom

All sources basically agree that Catalan numbers are named after Eugène Catalan (1814–1894), though they were computed by Leonhard Euler. There are several narratives in the literature, which are variations on the following statements, neither of which is really correct:

**1.** The problem was introduced by Segner in his 1758 article and solved by Euler in an unsigned article in the same journal volume.

**2.** The problem was introduced by Euler in his 1758 unsigned article and solved by Segner by a recurrence relation in the same volume.

**3.** The problem was introduced/solved by Euler in a 1751 letter to Goldbach, but Segner’s paper is the first published solution.

**4.** Although the problem was raised by Euler and/or Segner, neither of which found a proof. The first proof was given by Lamé in 1838.

Let me delay the explanation of what I think happened. Please be patient!

#### People and places

There are three heroes in this story: Leonhard Euler (1707–1783), Christian Goldbach (1690–1764), and Johann von Segner (1704–1777). Goldbach was the most senior of the three, he moved to St. Petersburg in 1725, tutored Tsarevich Peter II, and lived in Russia for the rest of his life. When young Euler arrived to St. Petersburg in 1727, Goldbach became his mentor, lifelong friend and a correspondent for over 35 years. Of the numerous letters between them, many were edited and published by Euler’s former assistant, a mathematician and grandson-in-law Nicolas Fuss (1755–1826).

Segner was a physician by trade, but in 1732 became interested in mathematics. In 1735 he was appointed the first mathematics professor at the University of Göttingen (not a big deal at the time). Euler left Russia in 1741 to a position at the Berlin Academy, and joined the court of Frederick the Great of Prussia, at which point he became a frequent correspondent with Segner. Their relationship, perhaps, was closer to a friendly competition than a true friendship between Euler and Goldbach. Although Segner and Euler were contemporaries, Euler rose to prominence very quickly and had a lot of political sway. For example, he slyly engineered Senger’s position at the University of Halle in Saxony, where Segner moved in 1755. Unfortunately, only letters from Segner to Euler survived (159 of them) and these have yet to be digitized.

In 1756, Frederick II overrun the Saxony as a part of initial hostilities of the Seven Year’s War, which put Prussia and Russia on different sides. But Euler continued to publish in Russia, where he was widely respected. When Russian troops marched through Berlin in 1760 (not for the last time), he did not leave the city. Later, when his personal estate was marauded, he was eventually compensated by Catherine the Great (whose court he joined in 1766).

#### Letter exchange between Euler and Goldbach

*** First letter:** September 4, 1751 letter, from Euler to Goldbach.

Near the end of the letter, Euler writes matter of factly, that he figured out the numbers of triangulations of the polygons with at most 10 sides. Evidently, he does this by hand, and then takes ratios of successive number to guess the general product formula. He writes:

Die Induction aber, so ich gebraucht, war ziemlich mühsam, doch zweifle ich nicht, dass diese Sach, nicht sollte weit leichter entwickelt werden können.

He continues to guess (correctly) a closed algebraic formula for the g.f. of the Catalan numbers sequence.

*** Second letter:** October 16, 1751 letter, from Goldbach to Euler.

Here Goldbach suggests there is a way to verify Euler’s g.f. formula by algebraic manipulations. Essentially, he rewrote Euler’s formula for the g.f. for Catalan numbers as a quadratic equation for power series. He the checks the equation for the first few coefficients.

*** Third letter:** December 4, 1751 letter, from Goldbach to Euler.

Here Euler uses the binomial theorem to show that the generating function formula indeed implies his product formula for the Catalan numbers.

#### Papers by Euler and Segner

*** Segner’s paper** in *Novi **Commentarii, *volume 7 (dated 1758/59, but published only in 1761).

Here Segner finds and proves the standard quadratic relation between Catalan numbers. He starts by attributing the problem to Euler and mentioning the first few Catalan numbers that Euler calculated. He then uses this quadratic equation to calculate the first 18 Catalan numbers, but makes an arithmetic mistake, thus miscalculating the last 6.

*** Euler’s paper** in the same volume (unsigned, but universally attributed to Euler). My fan translation into English.

Euler describes the number of triangulations problem, mentions Segner’s recurrence relation, and then his direct inductive formula for Catalan number, which he rewrites as a conventional product of *n-2* fractions. He then uses this formula to correct and extend Segner’s table.

#### What happened (my speculation) :

This was a collaborative research effort. First, Euler introduced the number of triangulations problem, which perhaps came from his map making work both in Russia and in Berlin (he hints to that in his “summary”). Euler labored to compute by hand the first few Catalan numbers by using ad hoc methods; he correctly calculated them up to 1430 triangulations of a 10-gon. He used these numbers to guess a simple product formula for the Catalan numbers by observing a pattern in successive ratios, and a closed form algebraic formula for the g.f. He clearly realized that the proof of both is needed, but thought this was a difficult problem, at which point he writes to Goldbach. In his reply, Goldbach suggested how to verify the analytic formula, but Euler took a different route and showed that one formula implies the other. From a modern point of view, this was an open exchange of ideas between friends and collaborators, even if dominated by Euler’s genius.

Some years later, Euler evidently suggested this problem to Segner, but never informed him of the product formula which he guessed back then. While Euler’s letters to Segner did not survive, it is clear from Segner’s writing that he knew of some Euler’s calculations, but not the product formula (there is no way he would have made a mistake in the table otherwise), nor even the 1430 value (the largest number reported by Euler to him seemed to be 429). No wonder Segner did not prove Euler’s product formula – he simply did not know what he should be proving, so presented his results as a method for computing Catalan numbers.

Finally, when Euler saw Segner’s work, he immediately realized its value as the last missing piece. Essentially, Segner’s recurrence is exactly what remained in the sequence

combinatorial interpretation **→** recurrence relation** →** algebraic equation** →** closed algebraic formula **→ **product formula,

where the first step is due to Segner, the second and third are easy and closely related to Goldbach’s approach, while the last step is due to Euler himself. Those who teach undergaduates this particular proof, know how much of a pain to teach this last step. As I understand, despite the war and geography, Euler continued editing the volumes of the St. Petersburg based *Novi **Commentarii. *In what should have been the “Summary” of Segner’s article, he included his formula as a way to both gently correct Segner and show the superiority of his product formula. I should mention that Euler’s Latin original sugarcoated this. It is a pity that Euler never published anything else on the subject.

#### What happened next:

This is much better documented. First, in response to a question by Johann Pfaff, the above mentioned Nicolas Fuss published in 1791 a generalization of Segner’s recurrence relation, and converted it to a higher order algebraic equation for the g.f., thus generalizing Euler’s algebraic formula. This allowed Liouville to give a product formula for this generalization using the Lagrange inversion formula, which was later rediscovered by Kirkman, Cayley and others.

The problem was then studied French mathematician and promoter of Reform Judaism Olry Terquem (1782–1862). As hinted by Liouville in a foonote to Lamé’s article, Terquem knew of both Euler’s and Segner’s articles, but not of the algebraic formulas. He seem to have succeeded in proving that the recurrence relation implies the product formula, thus “achieving it with the help of some properties of factorials”. In in 1838, he suggested the problem to Joseph Liouville (1809–1882), who in turn suggested the problem to a number of people, some of whom became to actively work on the subject. Liouville’s colleague at École Polytechnique, Gabriel Lamé (1795–1870), quickly found an elegant combinatorial solution building on Segner’s approach. Liouville extracted mathematical content from the letter Lamé wrote to him, and quickly published it (English translation), in the *Journal de Mathématiques* which he started two years earlier. This became the first published complete proof of the product formula for Catalan numbers.

In the following year, other colleagues joint the effort (Binet, Catalan, Rodrigues), and their effort was also published by Liouville. In the following 175 years the problem has been repeatedly rediscovered and generalized (notably, by Bertrand in 1887, in the context of the ballot problem). A small portion of these papers is listed here. Henry Gould’s 2007 count gives 465 publications, surely undercounting the total.

#### What’s in a name?

Curiously, Catalan’s own contribution was helpful, but not crucial. Netto singled him out in his 1901 monograph, as he favorited Catalan’s language of *parenthesized expressions* over the less formal discussion of *polygon triangulations*. Catalan himself called them “Segner numbers“. Given that Euler already has plenty of numbers named after him, it’s too late to change this name. We are stuck with *Catalan numbers*!

**Note:** This post is not a piece of research in History of Mathematics, which is a serious field with high standards for quality and rigor. This is merely a speculation, my effort to put together some pieces of the story which do not seem to fit otherwise.

**Update **(Feb 28, 2013)**: **S. Kotelnikow’s 1766 contribution is removed as he seem to have proved absolutely nothing.

**Update **(Feb 5, 2014)**: **While Netto did indeed single out Catalan’s work, we now believe that it was Riordan solely responsible for the name (see this blog post).

**Update **(Aug 25, 2014)**:** I did more historical research on the subject which is now reworked into an article History of Catalan Numbers.