Claude Berge

Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory.

Biography and professional history

Claude Berge's parents were André Berge and Geneviève Fourcade. André Berge (1902–1995) was a physician and psychoanalyst who, in addition to his professional work, had published several novels. He was the son of René Berge, a mining engineer, and Antoinette Faure.

Berge married Jane Gentaz (born 7 January 1925) on 29 December 1952; they had one child, Delphine, born on 1 March 1964. In 1952, before the award of his doctorate, Berge was appointed as a research assistant at the Centre National de la Recherche Scientifique. In 1957 he spent time in the United States as a visiting professor at Princeton University. He took part in the Economics Research Project there, which was under contract with the Office of Naval Research. While in Princeton he undertook work that was presented in the paper "Two theorems in graph theory" published in the Proceedings of the National Academy of Sciences of the United States of America. This was one of his first papers on graph theory, his earlier work being on the theory of games and combinatorics. He was writing his famous book Théorie des graphes et ses applications (Graph theory and applications) at this time and had just published his book on the theory of games, Théorie générale des jeux à n personnes (General theory of games with n players) (1957). Returning to France from the United States, Berge took up the position of Director of research at the Centre national de la recherche scientifique. Also, in 1957 he was appointed as a professor in the Institute of Statistics of the University of Paris. Théorie des graphes et ses applications was published in 1958 and, remarkably, in the following year his third book, Espaces topologiques, fonctions multivoques (Topological Spaces, Multi-Valued Functions), was published. For a mathematician in their early thirties to publish three major books within as many years is a truly outstanding achievement.

Beginning in 1952 he was a research assistant at the

The period around 1960 seems to have been particularly important and fruitful for Berge. Through the book Théorie des graphes et ses applications he had established a mathematical name for himself. In 1959 he attended the first graph theory conference ever in Dobogókő, Hungary, and met the Hungarian graph theorists. He published a survey paper on graph coloring, where he introduced the ideas that soon led to perfect graphs. In March 1960 he talked about this at a meeting in Halle in East Germany. In November of the same year, he was one of the ten founding members of the OuLiPo (Ouvroir de Litt´erature Potentiel). And in 1961, with his friend and colleague Marcel-Paul Schützenberger, he initiated the Séminaire sur les problèmes combinatoires at the University of Paris (which later became the Équipe combinatoire du CNRS). At the same time, Berge achieved success as a sculptor.

In 1994 Berge wrote a 'mathematical' murder mystery for Oulipo. In this short story, Who killed the Duke of Densmore (1995), the Duke of Densmore has been murdered by one of his six mistresses, and Sherlock Holmes and Dr. Watson are summoned to solve the case. Watson is sent by Holmes to the Duke's castle but, on his return, the information he conveys to Holmes is very muddled. Holmes uses the information that Watson gives him to construct a graph. He then applies a theorem of György Hajós to the graph, which produces the name of the murderer. Other clever contributions of Berge to Oulipo are described in.^[4][3]

Another of Berge's interests was in art and sculpture. He described his early sculptures, made in part from stones found in the river Seine, in his book Sculptures multipètres (1962). Bjarne Toft writes:^[5]

In our modern everyday life, we are surrounded and bombarded by (too) beautiful, flawless pictures, sculptures, and designs. In this stream, Claude Berge's sculptures catch our attention, with their authenticity and honesty. They are not pretending to be more than they are. Berge catches again something general and essential, as he did in his mathematics. The sculptures may at first seem just funny, and they certainly have a humorous side. But they have strong personalities in their unique style – you come to like them as you keep looking at them – whether one could live with them if they came alive is another matter!

— Bjarne Toft

Mathematical contributions

Berge wrote five books, on game theory (1957), graph theory and its applications (1958), topological spaces (1959), principles of combinatorics (1968) and hypergraphs (1970), each being translated in several languages. These books helped bring the subjects of graph theory and combinatorics out of disrepute by highlighting the successful practical applications of the subjects.^[6] He is particularly remembered for two conjectures on perfect graphs that he made in the early 1960s but were not proved until significantly later:

• A graph is perfect if and only if its complement is perfect, proven by László Lovász in 1972 and now known as the perfect graph theorem,^[7] and
• A graph is perfect if and only if neither it nor its complement contains an
  induced cycle of odd length at least five, proven by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas in work published in 2006 and now known as the strong perfect graph theorem.^[8]

Games were a passion of Claude Berge throughout his life, whether playing them – as in favorites such as chess, backgammon, and Hex – or exploring more theoretical aspects. This passion governed his interests in mathematics. He began writing on game theory as early as 1951, spent a year at the Institute for Advanced Study in Princeton, New Jersey in 1957, and the same year produced his first major book, Théorie générale des jeux à n personnes. Here, one not only comes across names such as John von Neumann and John Nash, as one would expect, but also names such as Dénes Kőnig, Øystein Ore, and Richardson. Indeed, the book contains much graph theory, namely the graph theory useful for game theory; it also contains much topology, namely the topology of relevance to game theory. Thus, it was natural that Berge quickly followed up on this work with two larger volumes, Théorie des graphes et ses applications and Espaces topologiques, fonctions multivoques. The first one is a masterpiece, with its unique blend of general theory, theorems – easy and difficult, proofs, examples, applications, diagrams. It is a personal manifesto of graph theory, rather than a complete description, as attempted in the book by Kőnig. It would be an interesting project to compare the first two earlier books on graph theory, by André Sainte-Laguë and Kőnig, respectively, with the book by Berge. It is clear that Berge's book is more leisurely and playful than Kőnig's, in particular. It is governed by the taste of Berge and might well be subtitled 'seduction into graph theory' (to use the words of Gian-Carlo Rota from the preface to the English translation of Berge's book). Among the main topics in this book are factorization, matchings, and alternating paths. Here Berge relies on the fundamental paper of Tibor Gallai. Gallai was one of the greatest graph theorists – he was to some degree overlooked – but not by Berge. Gallai was among the first to emphasize min-max theorems and LP-duality in combinatorics.

He is also known for his

Art

In addition to mathematics, Claude Berge enjoyed literature, sculpture, and art. Berge co-founded the French literary group Oulipo with novelists and other mathematicians in 1960 to create new forms of literature. In this association, he wrote a murder mystery based on a mathematical theorem: Who killed the Duke of Densmore? In an adaptation of this story, the Duke of Densmore is killed by an explosion. Ten years later, Sherlock Holmes and Dr. Watson are called to investigate this unsolved case. Using the testimonies of the Duke's seven ex-wives and his knowledge of interval graphs, Holmes is able to determine which one made multiple visits to the Duke and was able to plant the bomb.^[9][10]

Awards and honors

Berge won the

• Théorie générale des jeux à n personnes (General theory of games for n players), 1957, trans. in Russian, 1961
• Théorie des graphes et ses applications, Wiley, 1958, trans. English, Russian, Spanish, Romanian, Chinese. English translation: The Theory of Graphs and its Applications, Wiley, 1964
• Espaces topologiques, fonctions multivoques, 1959, trans. in English, 1963. English translation Topological Spaces: Including a Treatment of Multi-Valued Functions, Vector Spaces and Convexity, Dover Books, 2010.
• Programmes, jeux et réseaux de transport, with A. Ghouila-Houri, Wiley, 1962, trans. English, Spanish, German, Chinese. English Translation: Programming, Games and Transportation Networks, Wiley, 1965
• Graphes parfaits (Perfect graphs), 1963
• Principes de Combinatoire, Wiley, 1968. English translation: Principles of Combinatorics, Academic Press, 1971^[12]
• Graphes et Hypergraphes, in 1969 and 1970, trans. in English, Japanese. English translation: Graphs and Hypergraphs, North-Holland Publishing Company, 1973.
• Hypergraphes. Combinatoires des ensembles finis (Hypergraphs. Combinatorial finite sets), Gauthier-Villars, 1987, trans. English

Literary work

• Sculptures Multipètres, 1961
• La Reine Aztèque (Aztec Queen), 1983
• Qui a tué le Duc de Densmore? (Who Killed the Duke of Densmore?) 1994
• Raymond Queneau et la combinatoire (Raymond Queneau and combinatorics), 1997

References