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, combinatorilists 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 (English translation) 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.

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 Knuth, Doron 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.

The answer

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 controversies, often 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.

Computational combinatorics

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 10⁶, 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…

Britannica, Wikipedia and Combinatorics

All right, as we just learned, Britannica is done publishing.  Wikipedia won.  It wasn’t much of a contest, really.  We all expected this a long time ago.  Even if WP wasn’t as big as it is now (English language WP has about 4 mil pages), looking up there is noticeably faster than figuring out which volume of Britannica has your information.  So should we celebrate or commiserate?  I think neither, but we should instead turn this crisis into an opportunity.

First, how to think of the Britannica?  I say, as a series of historical documents, written by some of the best writers and scientists.  The case in point: Combinatorics article, which exists both in WP and in Britannica (the webpage has a free access this month).  Let’s review:

1) The Britannica Combinatorics article is overly long and incomplete at the same time, somewhat biased, very out of date, and barely coherent.  Lots of little examples are mentioned (multinomial coefficients, PBIB, etc.) and a few big things (graph theory, Ramsey theory, combinatorical geometry).  Nothing remotely recent (like algebraic combinatorics), most references from the 1960s and a couple of 1980s textbooks which are “accessible to laymen” (a lovely turn of phrase).  Sort of reminds me of this bridge - nice, useful in the past, but ultimately useless nowdays.

2) The Wikipedia Combinatorics article was in a horrible shape only about 3 years ago.  As a big WP fan, I was upset over this, and over the 1998 winter break largely rewrote the page myself.  The current version is still about 95% the same as I made it.  Rather than give silly examples and historical discussions, I simply made it into a portal with wikilinks to relevant subfields and few sentences describing each.  I thought I would get back to the article and write some more, but never did.  Sorry!

So, what gives?  Neither version is really a winner.  The Britannica article is outdated.  The WP article by itself has very little information.  The real difference can be seen only by going along the links – the total scope and quality of WP articles in combinatorics is noticeably better.  Still, some areas have WP pages which are not well written and/or have little information.  In summary, neither article gives a picture of the field.  If I were to choose a well written and accessible Combinatorics encyclopedia article, I would suggest Enumerative and Algebraic Combinatorics by Zeilberger, Extremal and Probabilistic Combinatorics by Alon and Krivelevich, and other articles from The Princeton Companion in Mathematics (Ed. by Tim Gowers).   

On the other hand, if viewed as a historical document Britannica article has a number of hidden treasures.  Written (at least in part) by Grünbaum (I am guessing in the 1960s), it correctly predicts the future growth of the extremal cominatorics and discrete geometry.  It is off base when it come to some other areas, like Polya’s theory which is rarely taught now and viewed as old fashioned.  Still, the page gives a window into the 1960 (or 1980?) thinking of what combinatorics is about.  In fact, even the name of the article was different – until recently it was “Combinatorial Analysis”.

My favorite “hidden gem” is the section on Partition Theory.  Check out theorem (F₁) there, which has both the statement and the proof (!).  This is common for WP (see e.g. this page), but rather unique for the Britannica.  It so happens, this section was originally written by Percy MacMahon in the 1911 Britannica (which is out of copyright now).  His version was up to date and beautifully written, later corrupted and shortened but never completely disappeared.  In fact, compared to 1911, new mistakes were introduced, e.g. an unpleasant typo in the section title “The Ferrer diagram” which I noticed in the 1960 edition managed to survive all these decades (they are named after Norman Ferrers).

Finally, my modest suggestion.  Treat the Britannica as a historical treasure that is up for sale (not unlike this one, sold in 1998).  After all, it dates back to 1768, three times older than this “Historic Cultural Monument” in my neighborhood.  The Britannica currently sells its digital version, but I bet this line of income will also dry up.  We (the people) should simply buy the whole thing and make it free and publicly available on the web.  Make sure to have available on the web all editions, not just the latest one.  This would give an instant window of how the same subject was treated over time.  Perhaps UNESCO?  Google?  Microsoft?  (it’s better than your Encarta, really!)  Amazon?  NSF?  Anyone with money?  I bet it’s cheap…

P.S.  A side comment – I want to praise Harald Helfgott’s recent serious effort to overhaul the Number Theory WP article.