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.

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. Félix François Faure (1841–1899) was Antoinette Faure's father; he was President of France from 1895 to 1899. André Berge married Geneviève in 1924, and Claude was the second of their six children. His five siblings were Nicole (the eldest), Antoine, Philippe, Edith, and Patrick. Claude attended the École des Roches [fr] near Verneuil-sur-Avre, about 110 km (68 mi) west of Paris. This famous private school, founded by the sociologist Edmond Demolins in 1899, attracted students from all over France to its innovative educational program. At this stage in his life, Claude was unsure about the topic in which he should specialize. He said in later life:

"I wasn't quite sure that I wanted to do mathematics. There was often a greater urge to study literature."

His love of literature and other non-mathematical subjects never left him and we shall discuss below how they played a large role in his life. However, he decided to study mathematics at the University of Paris. After the award of his first degree, he continued to undertake research for his doctorate, advised by André Lichnerowicz. He began publishing mathematics papers in 1950. In that year two of his papers appeared, the short paper Sur l'isovalence et la régularité des transformateurs and the major, 30-page paper Sur un nouveau calcul symbolique et ses applications. The symbolic calculus that he discussed in this major paper is a combination of generating functions and Laplace transforms. He then applied this symbolic calculus to combinatorial analysis, Bernoulli numbers, difference equations, differential equations, and summability factors. In 1951 he published a further two short papers, Sur l'inversion des transformateurs and Sur une théorie ensembliste des jeux alternatifs, that announced various results that would be discussed fully in his thesis. He was awarded a doctorate in 1953 for his thesis Sur une théorie ensembliste des jeux alternatifs, under the supervision of André Lichnerowicz.^[1] In this thesis, he examined games where perfect information is available in which, at each move, there are possibly an infinite number of choices. The games are not necessarily finite, with indefinite continuation being allowed. Berge examined the properties of such games with a thorough analysis. A 55-page paper based on his thesis, and with the same title, was published in 1953.

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 French National Centre for Scientific Research (CNRS), and from 1957 to 1964 he was a professor at the Institute of Statistics at the University of Paris. From 1965 to 1967 he directed the International Computing Centre in Rome. He was also associated with the Centre d'Analyse et de Mathématique Sociales (CAMS), a research center of École des hautes études en sciences sociales. He held visiting positions at Princeton University in 1957, Pennsylvania State University in 1968, and New York University in 1985, and was a frequent visitor to the Indian Statistical Institute, Calcutta.^[2][3]

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

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 maximum theorem in optimization and for Berge's lemma, which states that a matching M in a graph G is maximum if and only if there is in G no augmenting path with respect to M.

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]

Berge won the EURO Gold Medal from the Association of European Operational Research Societies in 1989,^[3][11] and (with Ronald Graham) the inaugural Euler Medal from the Institute of Combinatorics and its Applications in 1993.^[3]

(Note: Rough English translation in parentheses)

• 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

• 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

• Mathematical works of Claude Berge
• Claude Berge page at University of Montreal by Gena Hahn
• Obituary by Srinivas Bhogle Archived 2007-03-26 at the Wayback Machine
• Obituary by Václav Chvátal
• Creation and Recreation: A Tribute to the Memory of Claude Berge in Discrete Mathematics, volume 306, October 6 2006
• Chvátal, Vašek (March 15, 1997), "In praise of Claude Berge", Discrete Mathematics, 165–166: 3–9, doi:10.1016/s0012-365x(96)00156-2