Claude Berge, who passed away on 30 June 2002 at the age of 76, was one of the modern founders of combinatorics and graph theory.
Berge will be remembered for his wonderful books and his famous conjectures on perfect graphs. During an astonishingly productive period between 1957 and 1970, Berge wrote five books: on Game Theory (1957), Graph Theory and Its Applications (1958), Topological Spaces (1959), Principles of Combinatorics (1968) and Graphs and Hypergraphs (1970). Each book, originally written in French, was a classic, and was quickly translated into English and half a dozen other languages. Berge, as Gian-Carlo Rota wrote, ‘carried the word farther and more effectively than anyone anywhere’.
Berge’s books also achieved something even more important: they helped rescue graph theory and combinatorics from, what was sneeringly called, the ‘slum of mathematics’. Vacek Chvatal, now one of the most respected names in combinatorics, writes: ‘Up to the 1950’s, many mathematicians considered combinatorics and graph theory somewhat disreputable. Berge did a lot to change this perception’. Berge made his subject more respectable by writing about dozens of successful practical applications of graphs, and by writing in a truly magical vein. ‘I recall the pleasure of reading the disparate examples from his book which made it impossible to forget the material’, Rota wrote. ‘Soon after reading, I would be one of the many who unknotted themselves from the tentacles of the continuum and joined the rebel army of the discrete’.
Berge was a reluctant mathematician to start with. ‘I wasn’t quite sure that I wanted to do mathematics. There was often a greater urge to study literature’, Berge confessed in one of his last interviews. Indeed, the literary urge always stayed. Among the many thousand references to Berge that I found on Google, at least a third deal with his association with OULIPO, a French literary group that he co-founded with novelists and other mathematicians in 1960 to create new forms of literature.
One of Berge’s more successful experiments at OULIPO was to write a ‘mathematical’ murder mystery: the Duke of Densmore had been killed by one of his six jealous mistresses, and Holmes and Watson are called in to investigate. Holmes sends off Watson first to the Duke’s castle and Watson, as always, returns with a very confused narrative. But Watson’s account is enough for Holmes to pick up a pencil, sketch something in which points are joined by lines, and reveal the name of the assassin.
Berge was of course assuming that Sherlock Holmes knew that interval graphs were ‘triangulated’. It would be tedious here to show that every interval graph is triangulated or that every triangulated graph is ‘perfect’. But these were the kinds of rather elementary, but beautiful, mathematical discoveries that Berge loved to make. ‘I don’t relish heavy mathematics; I am not even sure that I am sufficiently good at it’, Berge told his interviewer, ‘but what I really enjoy is to sketch things with a paper and pencil, and discover patterns and configurations. We then try to understand how these configurations emerge, and look for special structures or properties that might characterize such configurations. That’s combinatorics to me’.
It must doubtlessly have been a similar exercise with paper and pencil that led Berge to formulate his two famous perfect graph conjectures: the first that a graph is perfect if and only if its complement is perfect, and the second (more difficult) assertion that a graph is perfect if and only if neither it nor its complement contains a chordless cycle whose length is odd and at least five.
There is a romance associated with these conjectures that is unparalleled in the contemporary history of graph theory. Berge first announced these twin conjectures at a European conference in 1960, and first wrote them down only in 1963 in a paper surprisingly published at the Indian Statistical Institute, Kolkata, where Berge was a frequent visitor for about two decades. The brilliant Laszlo Lovasz, who was first ‘spotted’ by the legendary Paul Erdos on one of his customary visits to Hungarian high schools to look for nascent talent, resolved the easier conjecture in 1971. Sadly, Lovasz’s triumph ended the career of D. R. Fulkerson, who was within a whisker of proving the conjecture himself till he decided that the conjecture was false and started looking for counter-examples. When Fulkerson received a postcard from Berge informing him of Lovasz’s proof, he completed his own proof in a matter of hours! A defeated Fulkerson only lived a few more months; just long enough to gracefully acknowledge in a Math Prog paper that Lovasz was the deserving winner.
The second perfect graph conjecture remained unconquered for over 40 years; it was only in May 2002, after over 500 papers on perfect graphs were published, that we heard that M. Chudnovsky and P D Seymour from Princeton have completed a proof of the conjecture. Berge was still alive when the news of the resolution of his more difficult conjecture came in, although he was reportedly very ill. He must have felt happy to see the end of this four-decade long adventure during his lifetime, although I do not think that the proof itself would have given him any great pleasure. Berge was very much a product of the old school and ‘clean’ and ‘pretty’ proofs mattered to him almost as much as the proof itself. I remember asking him once in Paris what he thought of the just- proved four-colour theorem. ‘I would say that the theorem is 70% true!’, he replied hardly hiding his contempt for proofs that use computers to enumerate all possible graphical structures.
It is interesting to speculate why Berge never seriously attempted to prove his own conjectures. Perhaps he did and discovered that the conjectures, certainly the harder one, required proof techniques that he did not really relish. Berge, especially in the second half of his career, apparently favoured only a certain genre of mathematics. But he still actively encouraged and supported younger mathematicians, even when they ventured well beyond his proclaimed preferences. That is why he had at least 25 outstanding first-generation students and perhaps twice as many such second-generation students. This is a truly formidable progeny set. I wonder how many top Indian professors can claim this distinction.
The multi-faceted Berge — in its obituary Le Monde hailed his ‘remarkably curious and eclectic spirit’ — could also have been a sculptor. His residence at 10 rue Galvani in Paris’ 17th arrondissement was like an unkempt museum with his own sculpture competing for space with the many Chinese works of art that he so adored. A visit to the Berge residence would find him curled up on a sofa, smoking his favourite pipe and gazing intently and lovingly at an objet d’art.
Being one of Berge’s foreign students in France, it was my privilege to be invited to his house for Christmas dinners. I have the most wonderful memories of these dinners. Berge could either be in a good mood or sulking like a spoilt child. On one occasion he was inconsolable when his wife served us red wine that was excessively chilled. ‘It shouldn’t be less than 18 degrees C’, he kept grumbling. Thankfully, his spirits improved a little after he found that the steak was done just right.
Berge was kind and caring, even if he was occasionally an eccentric professor. He loved playing games, especially chess at which he was quite good; although it was hard to accept his claim of having once beaten a French national champion. Berge spoke sufficiently good, and often charmingly amusing, English. He once told me that ‘the decision is between the hands of the French embassy’. Even though it is almost 15 years since I last met Berge, his passing away saddens me. It will also sadden his many Indian colleagues and students because he was an exceptionally warm and affectionate professor.
–This tribute first appeared in Current Science Vol. 83, No. 7, 10 October 2002
Srinivas Bhogle is currently with CSIR’s Fourth Paradigm Institute in Bangalore, and also teaches big data analytics to M.Sc. students at Bangalore’s St Joseph’s College. Earlier he worked for TEOCO Software Pvt Ltd ( ~9 years) and Cranes Software International Limited (~2 years). His longest stint (~22 years) was with National Aerospace Laboratories. Bhogle has been a student of University of Paris V (Ph.D, in 1983) and Indian Statistical Institute, Kolkata (B.Stat. in 1977, M.Stat. in 1978)
Published with the author’s permission