### Archive

Posts Tagged ‘Combinatorics’

## The problem with combinatorics textbooks

Every now and then I think about writing a graduate textbook in Combinatorics, based on some topics courses I have taught. I scan my extensive lecture notes, think about how much time it would take, and whether there is even a demand for this kind of effort. Five minutes later I would always remember that YOLO, deeply exhale and won’t think about it for a while.

#### What’s wrong with Combinatorics?

To illustrate the difficulty, let me begin with two quotes which contradict each other in the most illuminating way. First, from the Foreword by Richard Stanley on (his former student) Miklós Bóna’s “A Walk Through Combinatorics” textbook:

The subject of combinatorics is so vast that the author of a textbook faces a difficult decision as to what topics to include. There is no more-or-less canonical corpus as in such other subjects as number theory and complex variable theory. [here]

Second, from the Preface by Kyle Petersen (and Stanley’s academic descendant) in his elegant “Inquiry-Based Enumerative Combinatorics” textbook:

Combinatorics is a very broad subject, so the difficulty in writing about the subject is not what to include, but rather what to exclude. Which hundred problems should we choose? [here]

Now that this is all clear, you can probably insert your own joke about importance of teaching inclusion-exclusion. But I think the issue is a bit deeper than that.

I’ve been thinking about this when updating my “What is Combinatorics” quotation page (see also my old blog post on this). You can see a complete divergence of points of view on how to answer this question. Some make the definition or description to be very broad (sometimes even ridiculously broad), some relatively narrow, some are overly positive, while others are revoltingly negative. And some basically give up and say, in effect “it is what it is”. This may seem puzzling, but if you concentrate on the narrow definitions and ignore the rest, a picture emerges.

Clearly, these people are not talking about the same area. They are talking about sub-areas of Combinatorics that they know well, that they happen to learn or work on, and that they happen to like or dislike. Somebody made a choice what part of Combinatorics to teach them. They made a choice what further parts of Combinatorics to learn. These choices are increasingly country or culture dependent, and became formative in people’s mind. And they project their views of these parts of Combinatorics on the whole field.

So my point is — there is no right answer to “What is Combinatorics?“, in a sense that all these opinions are biased to some degree by personal education and experience. Combinatorics is just too broad of a category to describe. It’s a bit like asking “what is good food?” — the answers would be either broad and bland, or interesting but very culture-specific.

#### Courses and textbooks

How should one resolve the issue raised above? I think the answer is simple. Stop claiming that Combinatorics, or worse, Discrete Mathematics, is one subject. That’s not true and hasn’t been true for a while. I talked about this in my “Unity of Combinatorics” book review. Combinatorics is comprised of many sub-areas, see the Wikipedia article I discussed here (long ago). Just accept it.

As a consequence, you should never teach a “Combinatorics” course. Never! Especially to graduate students, but to undergraduates as well. Teach courses in any and all of these subjects: Enumerative Combinatorics, Graph Theory, Probabilistic Combinatorics, Discrete Geometry, Algebraic Combinatorics, Arithmetic Combinatorics, etc. Whether introductory or advanced versions of these courses, there is plenty of material for each such course.

Stop using these broad “a little bit about everything” combinatorics textbooks which also tend to be bulky, expensive and shallow. It just doesn’t make sense to teach both the five color theorem and the Catalan numbers (see also here) in the same course. In fact, this is a disservice to both the students and the area. Different students want to know about different aspects of Combinatorics. Thus, if you are teaching the same numbered undergraduate course every semester you can just split it into two or three, and fix different syllabi in advance. The students will sort themselves out and chose courses they are most interested in.

#### My own teaching

At UCLA, with the help of the Department, we split one Combinatorics course into two titled “Graph Theory” and “Enumerative Combinatorics”. They are broader, in fact, than the titles suggest — see Math 180 and Math 184 here. The former turned out to be quite a bit more popular among many applied math and non-math majors, especially those interested in CS, engineering, data science, etc., but also from social sciences. Math majors tend to know a lot of this material and flock to the latter course. I am not saying you should do the same — this is just an example of what can be done.

I remember going through a long list of undergraduate combinatorics textbooks a few years ago, and found surprisingly little choice for the enumerative/algebraic courses. Of the ones I liked, let me single out Bóna’s “Introduction to Enumerative and Analytic Combinatorics and Stanley’s “Algebraic Combinatorics“. We now use both at UCLA. There are also many good Graph Theory course textbooks of all levels, of course.

Similarly, for graduate courses, make sure you make the subject relatively narrow and clearly defined. Like a topics class, except accessible to beginning graduate students. Low entry barrier is an advantage Combinatorics has over other areas, so use it. To give examples from my own teaching, see unedited notes from my graduate courses:

Combinatorics of posets (Fall 2020)

Combinatorics and Probability on groups (Spring 2020)

Algebraic Combinatorics (Winter 2019)

Discrete and Polyhedral Geometry (Fall 2018) This is based on my book. See also videos of selected topics (in Russian).

Combinatorics of Integer Sequences (Fall 2016)

Combinatorics of Words (Fall 2014)

Tilings (Winter 2013, lecture-by-lecture refs only)

#### In summary

In my experience, the more specific you make the combinatorics course the more interesting it is to the students. Don’t be afraid that the course would appear be too narrow or too advanced. That’s a stigma from the past. You create a good course and the students will quickly figure it out. They do have their own FB and other chat groups, and spread the news much faster than you could imagine…

Unfortunately, there is often no good textbook to cover what you want. So you might have to work a little harder harder to scout the material from papers, monographs, etc. In the internet era this is easier than ever. In fact, many extensive lecture notes are already available on the web. Eventually, all the appropriate textbooks will be written. As I mentioned before, this is one of the very few silver linings of the pandemic…

P.S. (July 8, 2021) I should have mentioned that in addition to “a little bit about everything” textbooks, there are also “a lot about everything” doorstopper size volumes. I sort of don’t think of them as textbooks at all, more like mixtures of a reference guide, encyclopedia and teacher’s manual. Since even the thought of teaching from such books overwhelms the senses, I don’t expect them to be widely adopted.

Having said that, these voluminous textbooks can be incredibly valuable to both the students and the instructor as a source of interesting supplementary material. Let me single out an excellent recent “Combinatorial Mathematics” by Doug West written in the same clear and concise style as his earlier “Introduction to Graph Theory“. Priced modestly (for 991 pages), I recommend it as “further reading” for all combinatorics courses, even though I strongly disagree with the second sentence of the Preface, per my earlier blog post.

## The Unity of Combinatorics

April 10, 2021 1 comment

I just finished my very first book review for the Notices of the AMS. The authors are Ezra Brown and Richard Guy, and the book title is the same as the blog post. I had mixed feelings when I accepted the assignment to write this. I knew this would take a lot of work (I was wrong — it took a huge amount of work). But the reason I accepted is because I strongly suspected that there is no “unity of combinatorics”, so I wanted to be proved wrong. Here is how the book begins:

One reason why Combinatorics has been slow to become accepted as part of mainstream Mathematics is the common belief that it consists of a bag of isolated tricks, a number of areas: [very long list – IP] with little or no connection between them. We shall see that they have numerous threads weaving them together into a beautifully patterned tapestry.

Having read the book, I continue to maintain that there is no unity. The book review became a balancing act — how do you write a somewhat positive review if you don’t believe into the mission of the book? Here is the first paragraph of the portion of the review where I touch upon themes very familiar to readers of this blog:

As I see it, the whole idea of combinatorics as a “slow to become accepted” field feels like a throwback to the long forgotten era. This attitude was unfair but reasonably common back in 1970, outright insulting and relatively uncommon in 1995, and was utterly preposterous in 2020.

After a lengthy explanation I conclude:

To finish this line of thought, it gives me no pleasure to conclude that the case for the unity of combinatorics is too weak to be taken seriously. Perhaps, the unity of mathematics as a whole is an easier claim to establish, as evident from [Stanley’s] quotes. On the other hand, this lack of unity is not necessarily a bad thing, as we would be amiss without the rich diversity of cultures, languages, open problems, tools and applications of different areas.

Enjoy the full review! And please comment on the post with your own views on this alleged “unity”.

Ezra “Bud” Brown gave a talk on the book illustrating many of the connections I discuss in the review. This was at a memorial conference celebrating Richard Guy’s legacy. I was not aware of the video until now. Watch the whole talk.

## What math stories to tell and not to tell?

Storytelling can be surprisingly powerful. When a story is skillfully told, you get an almost magical feeling of being a part of it, making you care deeply about protagonists. Even if under ordinary circumstances you have zero empathy for the Civil War era outlaws or emperor penguins of Antarctica, you suddenly may find yourself engrossed with their fortune. This is a difficult skill to master, but the effects are visible even when used in earnest by the beginners.

Recently I started thinking about the kind of stories mathematicians should be telling. This was triggered by Angela Gibney‘s kind invitation to contribute an article on math writing to the Early Career Collection in the Notices of the AMS. So I looked at a few older articles and found them just wonderful. I am not the target audience for some of them, but I just kept reading them all one after another until I exhausted the whole collection.

My general advice — read the collection! Read a few pieces by some famous people or some people you know. If you like them, keep on reading. As I wrote in this blog post, you rarely get an insight into mathematician’s thinking unless they happen to write an autobiography or gave an interview. While this is more of a “how to” genre, most pieces are written in the first person narrative and do tell some interesting stories or have some curious points of view.

It is possible I am the last person to find out about the collection. I am not a member of the AMS, I don’t read the Notices, and it’s been a long time since anyone considered me “early career”. I found a few articles a little self-centered (but who am I to judge), and I would quibble with some advice (see below). But even those articles I found compelling and thought-provoking.

Having read the collection, I decided to write about mathematical storytelling. This is not something that comes naturally to most people in the field. Math stories (as opposed to stories about mathematicians) tend to be rather dry and unexciting, especially in the early years of studying. I will blog my own article some other time, but for now let me address the question in the title.

#### Stories to tell

With a few notable exceptions, just about all stories are worth telling. Whether in your autobiography or in your personal blog, as long as they are interesting to somebody — it’s all good. Given the lack of good stories, or any math stories really, it’s a good bet somebody will find your stories interesting. Let me expound on that.

Basically, anything personal works. To give examples from the collection, see e.g. stories by Mark Andrea de Cataldo, Alicia Prieto-Langarica, Terry Tao and John Urschel. Most autobiographies are written in this style, but a short blog post is also great. Overcoming an embarrassment caused by such public disclosure can be difficult, which makes it even more valuable to the readers.

Anything historical works, from full length monographs on history of math to short point of view pieces. Niche and off the beaten path stories are especially valuable. I personally like the classical History of Mathematical Notations by Florian Cajori, and Combinatorics: Ancient & Modern, a nice collection edited by Robin Wilson and John Watkins, with a several articles authored by names you will recognize. Note that an oral history can be also very valuable, see the kind of stories discussed by László Lovász and Endre Szemerédi mentioned in this blog post and Dynkin’s interviews I discussed here.

Anything juicy works. I mean, if you have a story of some famous mathematician doing something unusual (good or bad, or just plain weird), that attracts attention. This was the style of Steven Krantz’s two Math Apocryphia books, with many revealing and embarrassing anecdotes giving a sense of the bygone era.

Anything inspirational works. A beautiful example of this style is Francis Su’s Farewell Address as MAA President and part of his moving follow up book (the book has other interesting material as well). From the collection, let me single out Finding Your Reward by Skip Garibaldi which also aims to inspire. Yet another example is Bill Thurston‘s must read MO answer “What’s a mathematician to do?

Any off the beaten path math style is great. Think of “The Strong Law of Small Numbers” by Richard Guy, or many conjectures Terry Tao discusses in his blog. Think of “Missed opportunities” by Freeman Dyson, “Tilings of space by knotted tiles” by Colin Adams, or “One sentence proof… ” by Don Zagier (see also a short discussion here) — these are all remarkable and memorable pieces of writing that don’t conform to the usual peer review paradigm.

Finally, anything philosophical or metamathematical finds an audience. I am thinking of “Is it plausible?” by Barry Mazur, “Theorems for a Price” by Doron Zeilberger, “You and Your Research” by Richard Hamming, “Mathematics as Metaphor” by Yuri Manin, or even “Prime Numbers and the Search for Extraterrestrial Intelligence” by Carl Pomerance. We are all in search of some kind of answers, I suppose, so reading others thinking aloud about these deep questions always helps.

#### Practice makes perfect

Before I move to the other side, here is a simple advice on how to write a good story. Write as much as possible! There is no way around this. Absolutely no substitute, really. I’ve given this advice plenty of times, and so have everyone else. Let me conclude by this quote by Don Knuth which is a bit similar to Robert Lazarsfeld‘s advice. It makes my point much better and with with more authority that I can ever provide:

Of equal importance to solving a problem is the communication of that solution to others. The best way to improve your writing skills is to practice, practice, practice.

Seize every opportunity to write mini-essays about the theoretical work you are doing. Compose a blog for your friends, or even for yourself. When you write programs, write literate programs.

One of the best strategies to follow while doing PhD research is to prepare weekly reports of exactly what you are doing. What questions did you pursue that week? What positive answers did you get? What negative answers did you get? What are the major stumbling blocks that seem to be present at the moment? What related work are you reading?

Donald Knuth – On Writing up Research (posted by Omer Reingold), Theory Dish, Feb 26, 2018

#### Don’t be a journalist

In this interesting article in the same collection, Jordan Ellenberg writes:

Why don’t journalists talk about math as it really is? Because they don’t know how it really is. We do. And if we want the public discourse about math to be richer, broader, and deeper, we need to tell our own stories.

He goes on to suggest that one should start writing a blog and then pitch some articles to real newspapers and news magazines. He gives his own bio as one example (among others) of pitching and publishing in mainstream publications such as Slate and the New York Times. Obviously, I agree with the first (blog) part (duh!), but I am rather negative on the second part. I know, I know, this sounds discouraging, but hear me out.

First, what Jordan is not telling you is how hard he had to work on his craft before getting to the point of being acceptable to the general audience. This started with him getting Summa Cum Laude A.B. degree from Harvard in both Math and English (if I recall correctly), and then publishing a well-received novel, all before starting his regular Slate column. Very few math people have this kind of background on which they can build popular appeal.

Second, this takes away jobs from real journalists. Like every highly competitive intellectual profession, journalism requires years of study and practice. It has its own principles and traditions, graduate schools, etc. Call it a chutzpah or a Dunning–Kruger effect, but just because you are excellent in harmonic analysis doesn’t mean you can do even a mediocre job as a writer. Again — some people can do both, but most cannot. If anything, I suspect a negative correlation between math and writing skills.

Here is another way to think about this. Most people do realize that they don’t need to email their pretty iPhone pictures of a Machu Picchu sunrise to be published by the National Geographic. Or that their cobbler family recipe maybe not exactly be what Gourmet Magazine is looking for. Why would you think that writing is much easier then?

Third, this cheapens our profession to some degree. You really don’t need a Ph.D. in algebraic number theory and two perfect scores at the IMO to write about Powerball or baseball. You need a M.S. in statistics and really good writing skills. There are plenty of media sites which do that now, such as 538. There is even the whole DDJ specialization with many practitioners and a handful of Pulitzer prizes. Using quantitative methods is now mainstream, so what exactly are you bringing to the table?

Fourth, it helps to be honest. Jordan writes: “Editors like an angle. If there’s a math angle to a story in the news, pitch it! As someone with a degree in math, you have something to offer that most writers don’t.” This is true in the rare instances when, say, a Fields medal in your area is awarded, or something like that. But if it’s in an area far away from yours, then, uhm, you got nothing over many thousands of other people.

Now, please don’t take this as “don’t comment on current affairs” advice. No, no — please do! Comment away on your blog or on your podcast. Just don’t take jobs away from journalists. Help them instead! Write them emails, correct their mistakes. Let them interview you as an “expert”, whatever. Part of the reason the math related articles are so poor is because of mathematicians’ apathy and frequent disdain to the media, not because we don’t write newspaper articles — it’s really not our job.

Let me conclude with an anecdote about me reaching out to a newspaper. Once upon a time, long ago, flights used to distribute real newspapers to the passengers. I was sitting in the back and got a Wall Street Journal which I read out of boredom during takeoff. There was an article discussing the EU expansion and the fact that by some EU rules, the headquarters need a translator from every language to every other language. The article predicted dark days ahead, since it’s basically impossible to find people who can translate some smaller languages, such as from Maltese to Lithuanian. The article provided a helpful graph showing the number of translators needed as a function of the number of countries and claimed the exponential growth.

I was not amused, cut out the article, and emailed the author upon arrival, saying that with all my authority as an assistant professor at MIT, I promise that n(n-1) grows polynomially, not exponentially. I got back a surprisingly apologetic reply. The author confessed he was a math major in college, but was using the word without thinking. I don’t know if WSJ ever published a correction, but I bet the author will not be using this word so casually anymore, and if he ever advanced to the editorial position will propagate this knowledge to others. So there — that’s my personal contribution to improving public discourse…

#### Don’t be an apologist

In another beautifully written article in the Early Career collection, Izzet Coskun gives “advice on how to communicate mathematics quickly in informal settings”. He writes:

Whether before a promotion committee, at a party where one might meet future politicians or future parents of future colleagues, in the elevator on the way up to tea, or in the dean’s office at a job interview, we often have the opportunity to explain our work to a general audience. The time we have is usually short [..] Our audience will not be familiar with our terminology. Communicating mathematics in such settings is challenging.

He then gives a lot of very useful practical advice on how to prepare to such “math under a minute” conversation, how to be engaging, accessible, etc. It’s an all around good advice. However, I disagree. Here is my simple advice: Don’t Do It! If it’s a dean and this is a job interview, feel free to use any math jargon you want — it’s not your fault your field is technical, and the dean of sciences is used to it anyway. Otherwise, just say NO.

It’s true that sometimes your audience is friendly and is sincere in their interest in your work. In that case no matter what you say will disappoint them. There is a really good chance they can’t understand a word of what you say. They just think they can, and you are about to disillusion them.

But more often than not, the audience is actually not friendly, as was the case of a party Izzet described in his article. Many people harbor either a low regard or an outright resentment towards math stemming from their school years or some kind of “life experience”. These folks simply want to reinforce their views, and no matter what you say that will be taken as “you see, math is both hard, boring and useless”.

One should not confuse the unfriendlies with stupid or uneducated people. On the contrary, a lot of educated people think this way. A prime example is Amy Wax with her inimitable quote:

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.

I discussed this quote at length in this blog post. There, I tried to answer her question. But after a few back-and-force emails (which I didn’t make public), it became clear that she is completely uninterested in the actual learning of what math is and what it does. She just wants to have her own answer validated by some area practitioners. Oh, well…

So here is the real reason why I think answering such people is pointless. No matter what you say, you come across as an apologist for the field. If people really want to understand what math is for, there are plenty of sources. In fact, have several bookshelves with extremely well written book-length answers. But it’s not your job to educate them! Worse, it is completely unreasonable to expect you to answer in “under one minute”.

Think about reactions of people when they meet other professionals. Someone says “I develop new DNA based cancer treatments” or “I work on improving VLSI architecture”, or “I device new option pricing strategies”. Is there a follow up request to explain it in “under one minute”? Not really. Let me give you a multiple choice. Is that because people think that:

a) these professions are boring compared to math and they would rather hear about the latter?

b) they know exactly what these professionals do, but math is so darn mysterious?

c) they know these professions are technical and hard to understand, but even children can understand math, so how hard can that be?

d) these professions are clearly useful, but what do math people do — solve quadratic equations all day?

If you answered a) or b) you have more faith in humanity than I do. If you answered c) you never spoke to anyone about math at a party. So d) is the only acceptable answer, even if it’s an exaggeration. Some people (mostly under 7) think that I “add numbers all day”, some people (mostly in social sciences) think that I “take derivatives all day”, etc., you get the point. My advice — don’t correct them. This makes them unhappy. Doesn’t matter if they are 7 or 77 — when you correct them the unhappiness is real and visible…

So here is a summary of how I deal with such questions. If people ask what I do, I answer “I do math research and I teach“. If they ask what kind of research I say “advanced math“. If they ask for details I tell them “it’s complicated“. If they ask why, I tell them “because it takes many years of study to even understand the math lingo, so if I tell you what I do this sounds like I am speaking a foreign language“.

If they ask what are the applications of my research (and they always do), I tell them “teaching graduate classes“. If they ask for “practical” applications, whatever that means, I tell them “this puts money into my Wells Fargo account“. At this point they move on exhausted by the questions. On the one hand I didn’t lie except in the last answer. On the other — nobody cares if I even have a WF account (I don’t, but it’s none of their business either).

One can ask — why do I care so much? What’s so special about my work that I am so apprehensive? In truth, nothing really. There are other aspects of my identity I also find difficult discussing in public. The most relevant is “What is Combinatorics?” which for some reason is asked over and over as if there is a good answer (see this blog post for my own answer and this Wikipedia article I wrote). When I hear people explaining what it is, half the time it sounds like they are apologizing for something they didn’t do…

There are other questions relevant to my complex identity that I am completely uninterested in discussing. Like “What do you think of the Russian President?” or “Who is a Jew?“, or “Are you a Zionist?” It’s not that my answers are somehow novel, interesting or controversial (they are not). It’s more like I am afraid to hear responses from the people who asked me these questions. More often than not I find their answers unfortunate or plain offensive, and I would rather not know that.

Let me conclude on a positive note, by telling a party story of my own. Once, during hors d’oeuvres (remember those?), one lady, a well known LA lawyer, walked to me and said: “I hear you are a math professor at UCLA. This is so fascinating! Can you tell me what you do? Just WOW me!” I politely declined along the lines above. She insisted: “There has to be something that I can understand!” I relented: “Ok, there is one theorem I can tell you. In fact, this result landed me a tenure.” She was all ears.

I continued: “Do you know what’s a square-root-of-two?” She nodded. “Well, I proved that this number can never be a ratio of two integers, for example it’s not equal to 17/12 or anything like that.” “Oh, shut-the-F-up!” she exclaimed. “Are you serious? You can prove that?” — she was clearly suspicious. “Yes, I can“, I confirmed vigorously, “in fact, two Russian newspapers even printed headlines about that back a few years ago. We love math over there, you know.”

But of course!“, she said, “American media never writes about math. It’s such a shame! That’s why I never heard of your work. My son is much too young for this, but I must tell my nieces — they love science!” I nodded approvingly. She drifted away very happy, holding a small plate of meat stuffed potato croquettes, enriched with this newly acquired knowledge. I do hope her nieces liked that theorem — it is cool indeed. And the proof is so super neat…

## 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.

## The power of negative thinking, part I. Pattern avoidance

In my latest paper with Scott Garrabrant we disprove the Noonan-Zeilberger Conjecture. Let me informally explain what we did and why people should try to disprove conjectures more often.  This post is the first in a series.  Part II will appear shortly.

#### What did we do?

Let F ⊂ Sk be a finite set of permutations and let Cn(F) denote the number of permutations σ ∈ Sn avoiding the set of patterns F. The Noonan-Zeilbeger conjecture (1996), states that the sequence {Cn(F)} is always P-recursive. We disprove this conjecture.  Roughly, we show that every Turing machine T can be simulated by a set of patterns F, so that the number aof paths of length n accepted by by T is equal to Cn(F) mod 2.  I am oversimplifying things quite a bit, but that’s the gist.

What is left is to show how to construct a machine T such that {an} is not equal (mod 2) to any P-recursive sequence.  We have done this in our previous paper, where give a negative answer to a question by Kontsevich.  There, we constructed a set of 19 generators of GL(4,Z), such that the probability of return sequence is not P-recursive.

When all things are put together, we obtain a set F of about 30,000 permutations in S80 for which {Cn(F)} is non-P-recursive.  Yes, the construction is huge, but so what?  What’s a few thousand permutations between friends?  In fact, perhaps a single pattern (1324) is already non-P-recursive.  Let me explain the reasoning behind what we did and why our result is much stronger than it might seem.

#### Why we did what we did

First, a very brief history of the NZ-conjecture (see Kirtaev’s book for a comprehensive history of the subject and vast references).  Traditionally, pattern avoidance dealt with exact and asymptotic counting of pattern avoiding permutations for small sets of patterns.  The subject was initiated by MacMahon (1915) and Knuth (1968) who showed that we get Catalan numbers for patterns of length 3.  The resulting combinatorics is often so beautiful or at least plentiful, it’s hard to imagine how can it not be, thus the NZ-conjecture.  It was clearly very strong, but resisted all challenges until now.  Wilf reports that Richard Stanley disbelieved it (Richard confirmed this to me recently as well), but hundreds of papers seemed to confirm its validity in numerous special cases.

Curiously, the case of the (1324) pattern proved difficult early on.  It remains unresolved whether Cn(1324) is P-recursive or not.  This pattern broke Doron Zeilberger’s belief in the conjecture, and he proclaimed that it’s probably non-P-recursive and thus NZ-conjecture is probably false.  When I visited Doron last September he told me he no longer has strong belief in either direction and encouraged me to work on the problem.  I took a train back to Manhattan looking over New Jersey’s famously scenic Amtrack route.  Somewhere near Pulaski Skyway I called Scott to drop everything, that we should start working on this problem.

You see, when it comes to pattern avoidance, things move from best to good to bad to awful.  When they are bad, they are so bad, it can be really hard to prove that they are bad.  But why bother – we can try to figure out something awful.  The set of patterns that we constructed in our paper is so awful, that proving it is awful ain’t so bad.

#### Why is our result much stronger than it seems?

That’s because the proof extends to other results.  Essentially, we are saying that everything bad you can do with Turing machines, you can do with pattern avoidance (mod 2).  For example, why is (1324) so hard to analyze?  That’s because it’s even hard to compute both theoretically and experimentally – the existing algorithms are recursive and exponential in n.  Until our work, the existing hope for disproving the NZ-conjecture hinged on finding an appropriately bad set of patterns such that computing {Cn(F)} is easy.  Something like this sequence which has a nice recurrence, but is provably non-P-recursive.  Maybe.  But in our paper, we can do worse, a lot worse…

We can make a finite set of patterns F, such that computing {Cn(F) mod 2} is “provably” non-polynomial (Th 1.4).  Well, we use quotes because of the complexity theory assumptions we must have.  The conclusion is much stronger than non-P-recursiveness, since every P-recursive sequence has a trivial polynomial in n algorithm computing it.  But wait, it gets worse!

We prove that for two sets of patterns F and G, the problem “Cn(F) = Cn(G) mod 2 for all n” is undecidable (Th 1.3).  This is already a disaster, which takes time to sink in.  But then it gets even worse!  Take a look at our Corollary 8.1.  It says that there are two sets of patterns F and G, such that you can never prove nor disprove that Cn(F) = Cn(G) mod 2.  Now that’s what I call truly awful.

#### What gives?

Well, the original intuition behind the NZ-conjecture was clearly wrong.  Many nice examples is not a good enough evidence.  But the conjecture was so plausible!  Where did the intuition fail?  Well, I went to re-read Polya’s classic “Mathematics and Plausible Reasoning“, and it all seemed reasonable.  That is both Polya’s arguments and the NZ-conjecture (if you don’t feel like reading the whole book, at least read Barry Mazur’s interesting and short followup).

Now think about Polya’s arguments from the point of view of complexity and computability theory.  Again, it sounds very “plausible” that large enough sets of patterns behave badly.  Why wouldn’t they?  Well, it’s complicated.  Consider this example.  If someone asks you if every 3-connected planar cubic graph has a Hamiltonian cycle, this sounds plausible (this is Tait’s conjecture).  All small examples confirm this.  Planar cubic graphs do have very special structure.  But if you think about the fact that even for planar graphs, Hamiltonicity is NP-complete, it doesn’t sound plausible anymore.  The fact that Tutte found a counterexample is no longer surprising.  In fact, the decision problem was recently proved to be NP-complete in this case.  But then again, if you require 4-connectivity, then every planar graph has a Hamiltonian cycle.  Confused enough?

Back to the patterns.  Same story here.  When you look at many small cases, everything is P-recursive (or yet to be determined).  But compare this with Jacob Fox’s theorem that for a random single pattern π, the sequence {Cn(π)} grows much faster than originally expected (cf. Arratia’s Conjecture).  This suggests that small examples are not representative of complexity of the problem.  Time to think about disproving ALL conjectures based on that evidence.

If there is a moral in this story, it’s that what’s “plausible” is really hard to judge.  The more you know, the better you get.  Pay attention to small crumbs of evidence.  And think negative!

#### What’s wrong with being negative?

Well, conjectures tend to be optimistic – they are wishful thinking by definition.  Who would want to conjecture that for some large enough a,b,c and n, there exist a solution of an + bn = cn?  However, being so positive has a drawback – sometimes you get things badly wrong.  In fact, even polynomial Diophantine equations can be as complicated as one wishes.  Unfortunately, there is a strong bias in Mathematics against counterexamples.  For example, only two of the Clay Millennium Problems automatically pay \$1 million for a counterexample.  That’s a pity.  I understand why they do this, just disagree with the reasoning.  If anything, we should encourage thinking in the direction where there is not enough research, not in the direction where people are already super motivated to resolve the problem.

In general, it is always a good idea to keep an open mind.  Forget all this “power of positive thinking“, it’s not for math.  If you think a conjecture might be false, ignore everybody and just go for disproof.  Even if it’s one of those famous unsolved conjectures in mathematics.   If you don’t end up disproving the conjecture, you might have a bit of trouble publishing computational evidence.  There are some journals who do that, but not that many.  Hopefully, this will change soon…

#### Happy ending

When we were working on our paper, I wrote to Doron Zeilberger if he ever offered a reward for the NZ-conjecture, and for the disproof or proof only?  He replied with an unusual award, for the proof and disproof in equal measure.  When we finished the paper I emailed to Doron.  And he paid.  Nice… 🙂

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.

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 Kn 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: 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-.

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 Aquaman, the similarities are too eerie to ignore, so this prediction needs an upgrade.  Say, D-.

## What do math journals do? What will become of them in the future?

Recently, there has been plenty of discussions on math journals, their prices, behavior, technology and future.   I have been rather reluctant to join the discussion in part due to my own connection to Elsevier, in part because things in Combinatorics are more complicated than in other areas of mathematics (see below), but also because I couldn’t reconcile several somewhat conflicting thoughts that I had.  Should all existing editorial boards revolt and all journals be electronic?  Or perhaps should we move to “pay-for-publishing” model?  Or even “crowd source refereeing”?  Well, now that the issue a bit cooled down, I think I figured out exactly what should happen to math journals.  Be patient – a long explanation is coming below.

#### Quick test questions

I would like to argue that the debate over the second question is the general misunderstanding of the first question in the title.  In fact, I am pretty sure most mathematicians are quite a bit confused on this, for a good reason.  If you think this is easy, quick, answer the following three questions:

1)  Published paper has a technical mistake invalidating the main result.  Is this a fault of author, referee(s), handling editor, managing editor(s), a publisher, or all of the above?  If the reader find such mistake, who she/he is to contact?

2)  Published paper proves special case of a known result published 20 years earlier in an obscure paper.  Same question.  Would the answer change if the author lists the paper in the references?

3) Published paper is written in a really poor English.  Sections are disorganized and the introduction is misleading.  Same question.

Now that you gave your answers, ask a colleague.  Don’t be surprised to hear a different point of view.  Or at least don’t be surprised when you hear mine.

#### What do referees do?

In theory, a lot.  In practice, that depends.  There are few official journal guides to referees, but there are several well meaning guides (see also here, here, here,  here §4.10, and a nice discussion by Don Knuth §15).  However, as any editor can tell you, you never know what exactly did the referee do.  Some reply within 5 min, some after 2 years.  Some write one negative sentence, some 20 detailed pages, some give an advice in the style “yeah, not a bad paper, cites me twice, why not publish it”, while others a brushoff “not sure who this person is, and this problem is indeed strongly related to what I and my collaborators do, but of course our problems are much more interesting/important  – rejection would be best”.  The anonymity is so relaxing, doing a poor job is just too tempting.  The whole system hinges on the shame, sense of responsibility, and personal relationship with the editor.

A slightly better questions is “What do good referees do?”  The answer is – they don’t just help the editor make acceptance/rejection decision.  They help the authors.  They add some background the authors don’t know, look for missing references, improve on the proofs, critique the exposition and even notation.  They do their best, kind of what ideal advisors do for their graduate students, who just wrote an early draft of their first ever math paper.

In summary, you can’t blame the referees for anything.  They do what they can and as much work as they want.  To make a lame comparison, the referees are like wind and the editors are a bit like sailors.  While the wind is free, it often changes direction, sometimes completely disappears, and in general quite unreliable.  But sometimes it can really take you very far.  Of course, crowd sourcing refereeing is like democracy in the army – bad even in theory, and never tried in practice.

#### First interlude: refereeing war stories

I recall a curious story by Herb Wilf, on how Don Knuth submitted a paper under assumed name with an obscure college address, in order to get full refereeing treatment (the paper was accepted and eventually published under Knuth’s real name).  I tried this once, to unexpected outcome (let me not name the journal and the stupendous effort I made to create a fake identity).  The referee wrote that the paper was correct, rather interesting but “not quite good enough” for their allegedly excellent journal.  The editor was very sympathetic if a bit condescending, asking me not to lose hope, work on my papers harder and submit them again.  So I tried submitting to a competing but equal in statue journal, this time under my own name. The paper was accepted in a matter of weeks.  You can judge for yourself the moral of this story.

A combinatorialist I know (who shall remain anonymous) had the following story with Duke J. Math.  A year and a half after submission, the paper was rejected with three (!) reports mostly describing typos.  The authors were dismayed and consulted a CS colleague.  That colleague noticed that the three reports were in .pdf  but made by cropping from longer files.   Turns out, if the cropping is made straightforwardly, the cropped portions are still hidden in the files.  Using some hacking software the top portions of the reports were uncovered.  The authors discovered that they are extremely positive, giving great praise of the paper.  Now the authors believe that the editor despised combinatorics (or their branch of combinatorics) and was fishing for a bad report.  After three tries, he gave up and sent them cropped reports lest they think somebody else considers their paper worthy of publishing in the grand old Duke (cf. what Zeilberger wrote about Duke).

Another one of my stories is with the  Journal of AMS.  A year after submission, one of my papers was rejected with the following remarkable referee report which I quote here in full:

The results are probably well known.  The authors should consult with experts.

Needless to say, the results were new, and the paper was quickly published elsewhere.  As they say, “resistance is futile“.

#### What do associate/handling editors do?

Three little things, really.  They choose referees, read their reports and make the decisions.  But they are responsible for everything.  And I mean for everything, both 1), 2) and 3).  If the referee wrote a poorly researched report, they should recognize this and ignore it, request another one.  They should ensure they have more than one opinion on the paper, all of them highly informed and from good people.  If it seems the authors are not aware of the literature and referee(s) are not helping, they should ensure this is fixed.  It the paper is not well written, the editors should ask the authors to rewrite it (or else).   At Discrete Mathematics, we use this page by Doug West, as a default style to math grammar.  And if the reader finds a mistake, he/she should first contact the editor.  Contacting the author(s) is also a good idea, but sometimes the anonymity is helpful – the editor can be trusted to bring bad news and if possible, request a correction.

B.H. Neumann described here how he thinks the journal should operate.  I wish his views held widely today.  The  book by Krantz, §5.5, is a good outline of the ideal editorial experience, and this paper outlines how to select referees.  However, this discussion (esp. Rick Durrett’s “rambling”) is more revealing.  Now, the reason most people are confused as to who is responsible for 1), 2) and 3), is the fact that while some journals have serious proactive editors, others do not, or their work is largely invisible.

#### What do managing editors and publishers do?

In theory, managing editors hire associate editors, provide logistical support, distribute paper load, etc.  In practice they also serve as handling editors for a large number of papers.  The publishers…  You know what the publishers do.  Most importantly, they either pay editors or they don’t.  They either charge libraries a lot, or they don’t.  Publishing is a business, after all…

#### Who wants free universal electronic publishing?

Good mathematicians.  Great mathematicians.  Mathematicians who write well and see no benefit in their papers being refereed.  Mathematicians who have many students and wish the publishing process was speedier and less cumbersome, so their students can get good jobs.  Mathematicians who do not value the editorial work and are annoyed when the paper they want to read is “by subscription only” and thus unavailable.  In general, these are people who see having to publish as an obstacle, not as a benefit.

#### Who does not want free universal electronic publishing?

Publishers (of course), libraries, university administrators.  These are people and establishments who see value in existing order and don’t want it destroyed.  Also: mediocre mathematicians, bad mathematicians, mathematicians from poor countries, mathematicians who don’t have access to good libraries (perhaps, paradoxically).  In general, people who need help with their papers.  People who don’t want a quick brush-off  “not good enough” or “probably well known”, but those who need advice on the references, on their English, on how the papers are structured and presented, and on what to do next.

#### So, who is right?

Everyone.  For some mathematicians, having all journals to be electronic with virtually no cost is an overall benefit.  But at the very least, “pro status quo” crowd have a case, in my view.  I don’t mean that Elsevier pricing policy is reasonable, I am talking about the big picture here.  In a long run, I think of journals as non-profit NGO‘s, some kind of nerdy versions of Nobel Peace Prize winning Médecins Sans Frontières.  While I imagine that in the future many excellent top level journals will be electronic and free, I also think many mid-level journals in specific areas will be run by non-profit publishers, not free at all, and will employ a number of editorial and technical stuff to help the authors, both of papers they accept and reject.  This is a public service we should strive to perform, both for the sake of those math papers, and for development of mathematics in other countries.

Right now, the number of mathematicians in the world is already rather large and growing.  Free journals can do only so much.  Without high quality editors paid by the publishers, with a large influx of papers from the developing world, there is a chance we might loose the traditional high standards for published second tier papers.  And I really don’t want to think of a mathematics world once the peer review system is broken.  That’s why I am not in the “free publishing camp” – in an effort to save money, we might loose something much more valuable – the system which gives foundation and justification of our work.

#### Second interlude: journals vis-à-vis combinatorics

I already wrote about the fate of combinatorics papers in the Annals, especially when comparison with Number Theory.  My view was gloomy but mildly optimistic.  In fact, since that post was written couple more combinatorics papers has been accepted.  Good.  But let me give you a quiz.  Here are two comparable highly selective journals – Duke J. Math. and Composito Math.  In the past 10 years Composito published exactly one (!) paper in Combinatorics (defined as primary MSC=05), of the 631 total.  In the same period, Duke published 8 combinatorics papers of 681 total.

Q: Which of the two (Composito or Duke) treats combinatorics papers better?

A: Composito, of course.

The reasoning is simple.  Forget the anecdotal evidence in the previous interlude.  Just look at the “aim and scope” of the journals vs. these numbers.  Here is what Compsito website says with a refreshing honesty:

By tradition, the journal published by the foundation focuses on papers in the main stream of pure mathematics. This includes the fields of algebra, number theory, topology, algebraic and analytic geometry and (geometric) analysis. Papers on other topics are welcome if they are of interest not only to specialists.

Translation: combinatorics papers are not welcome (as are papers in many other fields).  I think this is totally fair.  Nothing wrong with that.  Clearly, there are journals which publish mostly in combinatorics, and where papers in none of these fields would be welcome.  In fact there is a good historical reason for that.  Compare this with what Duke says on its website:

Published by Duke University Press since its inception in 1935, the Duke Mathematical Journal is one of the world’s leading mathematical journals. Without specializing in a small number of subject areas, it emphasizes the most active and influential areas of current mathematics.

See the difference?  They don’t name their favorite areas!  How are the authors supposed to guess which are these?  Clearly, Combinatorics with its puny 1% proportion of Duke papers is not a subject area that Duke “emphasizes”.  Compare it with 104 papers in Number Theory (16%) and 124 papers in Algebraic Geometry (20%) over the same period.  Should we conclude that in the past 10 years, Combinatorics was not “the most active and influential”, or perhaps not “mathematics” at all? (yes, some people think so)  I have my own answer to this question, and I bet so do you…

Note also, that things used to be different at Duke.  For example, exactly 40 years earlier, in the period 1963-1973, Duke published 47 papers in combinatorics out of 972 total, even though the area was only in its first stages of development.  How come?  The reason is simple: Leonard Carlitz was Managing Editor at the time, and he welcomed papers from a number of prominent combinatorialists active during that time, such as Andrews, Gould, Moon, Riordan, Stanley, Subbarao, etc., as well as a many of his own papers.

#### So, ideally, what will happen to math journals?

That’s actually easy.  Here are my few recommendations and predictions.

1)  We should stop with all these geography based journals.  That’s enough.  I understand the temptation for each country, or university, or geographical entity to have its own math journal, but nowadays this is counterproductive and a cause for humor.  This parochial patriotism is perhaps useful in sports (or not), but is nonsense in mathematics.  New journals should emphasize new/rapidly growing areas of mathematics underserved by current journals, not new locales where printing presses are available.

2)  Existing for profit publishers should realize that with the growth of arXiv and free online competitors, their business model is unsustainable.  Eventually all these journals will reorganize into a non-profit institutions or foundations.  This does not mean that the journals will become electronic or free.  While some probably will, others will remain expensive, have many paid employees (including editors), and will continue to provide services to the authors, all supported by library subscriptions.  These extra services are their raison d’être, and will need to be broadly advertised.  The authors would learn not to be surprised of a quick one line report from free journals, and expect a serious effort from “expensive journals”.

3)  The journals will need to rethink their structure and scope, and try to develop their unique culture and identity.  If you have two similar looking free electronic journals, which do not add anything to the papers other than their .sty file, the difference is only the editorial board and history of published papers.  This is not enough.  All journals, except for the very top few, will have to start limiting their scope to emphasize the areas of their strength, and be honest and clear in advertising these areas.  Alternatively, other journals will need to reorganize and split their editorial board into clearly defined fields.  Think  Proc. LMS,  Trans. AMS, or a brand new  Sigma, which basically operate as dozens of independent journals, with one to three handling editors in each.  While highly efficient, in a long run this strategy is also unsustainable as it leads to general confusion and divergence in the quality of these sub-journals.

4)  Even among the top mathematicians, there is plenty of confusion on the quality of existing mathematics journals, some of which go back many decades.  See e.g. a section of Tim Gowers’s post about his views of the quality of various Combinatorics journals, since then helpfully updated and corrected.  But at least those of us who have been in the area for a while, have the memory of the fortune of previously submitted papers, whether our own, or our students, or colleagues.  A circumstantial evidence is better than nothing.  For the newcomers or outsiders, such distinctions between journals are a mystery.  The occasional rankings (impact factor or this, whatever this is) are more confusing than helpful.

What needs to happen is a new system of awards recognizing achievements of individual journals and/or editors, in their efforts to improve the quality of the journals, attracting top papers in the field, arranging fast refereeing, etc.   Think a mixture of Pulitzer Prize and J.D. Power and Associates awards – these would be a great help to understand the quality of the journals.  For example, the editors of the Annals clearly hustled to referee within a month in this case (even if motivated by PR purposes).  It’s an amazing speed for a technical 50+ page paper, and this effort deserves recognition.

Full disclosure:  Of the journals I singled out, I have published once in both  JAMS  and  Duke.  Neither paper is in Combinatorics, but both are in Discrete Mathematics, when understood broadly.

## 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.

## How do you solve a problem like the Annals?

The Annals of Mathematics has been on my mind in the past few days (I will explain why some other day). More precisely, I was wondering

Does the Annals publish articles in Combinatorics? If not, why not?  If yes, what changed?

What’s coming is a lengthy answer to this question, and a small suggestion.

### The numbers

I decided to investigate by searching the MR on MathSciNet (what else?)  For our purposes, Combinatorics is defined as “Primary MSC = 05”).  For a control group, I used Number Theory (“Primary MSC = 11”).   I chose a break point date to be the year 2000, a plausible dividing line between the “old days” and “modern times”.  I got the following numbers.

All MR papers:  about 2.8 mil, of which 1 mil after 2000.   In the Annals: 5422, of which 742 after 2000.

Combinatorics papers:  about 88k, of which 41k after 2000.  In the Annals: 18, of which 13 after 2000.

Number Theory papers:  about 58k, of which 29k after 2000.   In the Annals: 225, of which 129 after 2000.

So any way you slice it, as a plain number, as percentage of all papers, before 2000, after 2000, or in total – NT has about 10 times as many papers as Combinatorics.  The bias seems transparent, no?

Well, there is another way to look at the numbers.  MR finds that about 3% of all papers are in Combinatorics (which includes Graph Theory, btw).  The percentage of Combinatorics in the Annals is about 0.3%  Oops…  But the percentage in recent years clearly picked up – since 2000, 13 Combinatorics papers constitute about 1.7% of all Annals papers.  Given that there are over 50 major “areas” of mathematics (according to MSC), and Combinatorics is about 4.1% of all published papers since 2000, this is slightly below average, but not bad at all.

So what exactly is going on?  Has Combinatorics finally reached the prominence it deserves?  It took me awhile to figure this out, so let me tell this slowly.

### The people

Let’s looks at individual combinatorialists.  Leonard Carlitz authored about 1000 papers, none in the Annals.  George Andrews wrote over 300 and Ron Graham over 450 papers, many classical ones.  Both аre former presidents of AMS.  Again, none in the Annals.  The list goes on:  W.T. Tutte, Gian-Carlo Rota, Richard Stanely, Don KnuthDoron Zeilberger, Béla Bollobás, János Pach, etc. – all extremely prolific, and neither published a single paper in the Annals.  These are just off the top of my head, and in no particular order.

The case of Paul Erdős is perhaps the most interesting.  Between 1937 and 1955, he published 25 papers in the Annals in a variety of fields (Analysis, Number Theory, Probability, etc.)  Starting 1956, over the span of 40 years, he published over 1000 papers and none in the Annals.  What happened?  You see, in 1956 he coauthored a paper with Alfréd Rényi titled “On some combinatorical problems”, his very first paper with MSC=05.   Their pioneer paper “On the evolution of random graphs” came just four years later.  Nothing was ever the same again.  Good bye, the Annals!  Coincidence?  Maybe a little.  But from what I know about Erdős’s biography, his interests did shift to Combinatorics about that time…

Now, in NT and other fields things are clearly different.  After many trials, two champions I found are Manjul Bhargava (6 out of his 21 papers were published in the Annals), and Hassler Whitney (19 out of 65), both with about 30% rate.

In fact, it is easier to list those who have published Combinatorics papers in the Annals.  Here is the list of all 18 papers, as it really holds the clue to answering our initial question.  A close examination of the list shows that the 13 papers since 2000 are quite a bit diverse and interconnected to other areas of mathematics.  Some, but not most, are solutions to major open problems.  Some, but not most, are in a popular area of extremal/probabilistic combinatorics, etc.  Overall, a good healthy mix, even if a bit too small in number.

Note that in other fields things are different.  Check out Discrete Geometry (52C), a beautiful and rapidly growing area of mathematics.  Of the about 1800 papers since 2000, only three appeared in the Annals: one retracted (by Biss), and two are solutions of centuries old problems (by Hales and by Musin), an impossibly high standard.  One can argue that this sample is too small.  But think about it – why is it so small??

In summary, the answer to the first question is YES, the Annals does now publish Combinatorics papers.  It may look much warmer towards NT, but that’s neither important, nor the original question.  As for what caused the change, it seems, Combinatorics has become just like any other field.  It is diverse in its problems, has a long history, has a number of connections and applications to other fields, etc.  It may fall short on the count of faculty at some leading research universities, but overall became “normal”.  Critically, when it comes to Combinatorics, the old over the top criterion by the Annals (“must be a solution of a classical problem”), is no longer applied.  A really important contribution is good enough now.  Just like in NT, I would guess.

### The moral

I grew up (mathematically) in a world where the Annals viewed Combinatorics much the same way it viewed Statistics – as a foreign to mathematics fields with its own set of journals (heck, even its own annals).  People rarely if ever submitted their papers to the Annals, because neither did the leaders of the field.  Things clearly have changed for the better.  Now the Annals does publish papers in Combinatorics, and will probably publish more if more are submitted.  The main difference with Statistics is obvious – statisticians worked very hard to separate themselves from Mathematics, to create a separate community with their own departments, journals, grants, etc.  They largely succeeded.  Combinatorialists on the other hand, worked hard to become a part of mainstream Mathematics, and succeeded as well, to some extent.  The change of attitude in the Annals is just a reflection on that.

The over-representation of NT is also easy to explain.  I argued on MO that there is a bit of first-mover advantage going on, that some fields of mathematics feel grandfathered and push new fields away.  While clearly true, let’s ask who benefits?  Not the people in the area, which then has higher expectations for them (as in “What? No paper is the Annals yet?”).  While it may seem that as a result, an applicant in NT might get an unfair advantage over that in Combinatorics, the hiring committees know better.  This is bad for the Annals as well.  In these uncertain times of hundreds of mathematics journals (including some really strange), various journal controversiesoften misused barely reasonable impact factors, and new journals appearing every day, it is good to have some stability.  Mathematics clearly needs at least one journal with universally high standards, and giving preferences to a particular field does not help anyone.

### The suggestion

It seems, combinatorialists and perhaps people in other fields have yet to realize that the Annals is gradually changing in response to the changing state of the field(s).  Some remain unflinching in their criticism.  Notably, Zeilberger started calling it “snooty” in 1995, and continues now: “paragon of mathematical snootiness” that will “only publish hard-to-understand proofs” (2007),  “high-brow, pretentious” (2010).  My suggestion is trivial – ignore all that.  Combinatorialists should all try to send their best papers to the top journals in Math, not just in the field (which are plenty).  I realize that the (relative) reward may seem rather small, there is a lot of waiting involved, and the rejection chances are high, but still – this is important for the field.  There is clearly a lot of anxiety about this among job applicants, so untenured mathematicians are off the hook.  But the rest of us really should do this with our best work.  I trust the editors will notice and eventually more Combinatorics papers will get published.

P.S.  BTW, it is never too late.  Of the 100+ papers by Victor Zalgaller, his first paper in the Annals appeared in 2004, when he was 84, exactly 65 years after his very first paper appeared in Russia in 1939.

Categories: Journals, Mathematics

## Computational combinatorics

July 25, 2012 1 comment

Say, you have written a paper. You want to submit it to a journal. But in what field? More often than not, the precise field/area designation for this paper is easy to determine, or at least easy to place it into some large category. Even if the paper is in between fields, this is often well regarded and understood situation, nothing wrong with that. Say, the paper is resolving a problem in field X with tools from field Y. Submit to X-journal unless the application is routine and the crux of the innovation is in refining the tools. Then submit to Y-journal.

However, when it comes to CS, things are often less clear. This is in part because of the novelty of the subject, and in part due to the situation in CS theory, which is in constant flux and search for direction (a short Wikipedia article is as rather vague and unhelpful, even more so than these generic WP articles tend to be).

The point of this post is to introduce/describe the area of “Computational Combinatorics“. Although Google returns 20K hits for this term (including experts, courses, textbooks), the meaning is either obscure or misleading. We want to clarify what we mean, critique everyone else, and make a stake for the term!

1) What I want computational combinatorics to mean is “theoretical CS aspects of combinatorics” (and to a lesser extend “practical..”), which is essentially part of combinatorics but the tools and statements use compute science terminology (for a concise description of complexity aspects, see dated but excellent survey by David Shmoys and Eva Tardos). I will give a recent example below, but basically if you want to prove a negative result in combinatorics (as in “one should not expect a nice formula for the number of 3-colorings or perfect matchings of a general graph”), then CS language (and basic tools) is a way to go. When people use “computational combinatorics” to mean “basic results in combinatorics that are useful for further studies of computer science”, they are being misleading. A proper name for such course is “Introduction to Combinatorics” or “Combinatorics for Computer Scientists”, etc.

2) In two recent papers, Jed Yang and I proved several complexity results on tilings. To explain them, let me start with the following beautiful result by Éric Rémila, built on earlier papers by Thurston, Conway & Lagarias, and Kenyon & Kenyon:

Tileability of a simply connected region in the plane with two types of rectangles can be decided in polynomial time.

First, we show that when the number of rectangles is sufficiently large (originally about 106, later somewhat decreased), one should not expect such a result. Formally, we prove that tileability is NP-hard in this case. We then show that in 3-dim the topology of the region gives no advantage. Among other results, we prove that tileability of contractible regions with 2x2x1 slabs is
NP-complete, and counting 2x1x1 domino tilings of contractible regions is #P-complete.

Now, the CS Theory point of view on these types of results changed drastically over time. Roughly, 30 years ago they were mainstream. About 20 years ago they were still of interest, but no longer important. Nowadays they are marginal at best – the field has moved on. My point is that the result are of interest in Combinatorics and Combinatorics only. Indeed, it has long been observed that applying combinatorial group theory to tilings (as done by Thurston, Rémila, etc.) is more of an art than a science. Although we believe that already for three general rectangles in the plane the problem is intractable, proving such a result is exceedingly difficult. Our various results solve weak versions of this problem.

3) The ontology (classification) in mathematics has always been a mess (this is not unusual). For example, combinatorial enumeration is the same as enumerative combinatorics. On the other hand, as far as I can tell, analytic geometry has nothing to do with geometric analysis. There is also no “monotonicity” to speak about: even though group theory is a part of algebra, the geometric group theory is neither a part of geometric algebra, nor of algebraic geometry, although traditionally contains combinatorial group theory. Distressingly, there are two completely different (competing) notions of “algebraic combinatorics” (see here and there), and algebraic graph theory which is remarkably connected to both of these. The list goes on.

4) So, why name a field at all, given the mess we have? That’s mostly because we really want to incorporate the CS aspects of combinatorics as a legitimate branch of mathematics. Theory CS is already over the top combinatorial (check out the number of people who believe that P=?NP will be resolved with combinatorics), but when a problem arises in combinatorics from within, this part of combinatorics needs a name to call home. I propose using the term computational combinatorics, in line with computational group theory, computational geometry, computational topology, etc., as a part of the loosely defined computational mathematics. I feel that the adjective “computational” is broad and flexible enough to incorporate both theoretical/complexity aspects as well as some experimental work, and combinatorial software development (as in WZ theory), compared to other adjectives, such as “algorithmic”, “computable”, “effective”, “computer-sciency”, etc. So, please, AMS, next time you revise your MSC, consider adding “Computational Combinatorics” as 05Fxx.

P.S. A well known petition asks for graph theory to have its own MSC code (specifically, 07), due to the heavy imbalance in the number of graph theory vs. the rest of combinatorics papers. Without venturing an opinion, let me mention that perhaps, adding a top level “computational combinatorics” subfield of combinatorics will remedy this as well – surely some papers will migrate there from graph theory. Just a thought…