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 was the son of André Berge and Geneviève Fourcade, and the great-grandson of French President Félix Faure.Claude was the second of six children; his siblings were Nicole, Antoine, Philippe, Edith and Patrick.He married Jane Gentaz on December 29, 1952 and had one child, Delphine, born March 1, 1964. Although Claude Berge was unsure if he wanted study mathematics, instead often leaning towards literature, after studying at the École des Roches [fr] in Verneuil-sur-Avre, he attended the University of Paris to study mathematics and earned his Ph.D. in 1953, advised by André Lichnerowicz.At the University of Paris, Berge wrote several papers including his doctorate thesis paper Sur une théorie ensembliste des jeux alternatifs. In this paper, Berge examines properties of games where there is perfect information available and there are infinite choices for each move.This thesis served as the basis of a 55-page paper published in 1953.

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

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

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.10 years later, Sherlock Holmes and 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.

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

Major Mathematical Works

(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
• 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