Archive

Posts Tagged ‘Combinatorics’

The power of negative thinking, part I. Pattern avoidance

May 26, 2015 2 comments

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… 🙂

Advertisements

Grading Gian-Carlo Rota’s predictions

November 27, 2014 3 comments

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

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

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

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

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

Grading on a curve

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

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

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

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

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

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

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

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

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

Rota’s predictions on combinatorial problems:

In his paper, Rota writes:

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

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

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

2)  Percolation Theory.  The study of percolation completely exploded since 1969 and is now a subject of numerous articles in both probability, statistical physics and combinatorics, as well as several research monographs.  One connection is given by an observation that p-percolation on a complete graph 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-.

The final grade

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

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

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

May 28, 2013 4 comments

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?

May 14, 2013 1 comment

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?

August 19, 2012 3 comments

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.

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

Computational combinatorics

July 25, 2012 Leave a 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…

Britannica, Wikipedia and Combinatorics

March 16, 2012 Leave a comment

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 (F1) 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.