Claude Berge


Claude Jacques Berge 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 was a physician and psychoanalyst who, in addition to his professional work, had published several novels. He was the son of the René Berge, a mining engineer, and Antoinette Faure. Félix François Faure was Antoinette Faure's father; he was President of France from 1895 to 1899. André Berge married Geneviève in 1924 and Claude, the subject of this biography, was the second of their six children. His five siblings were Nicole, Antoine, Philippe, Edith, and Patrick. Claude attended the École des Roches near Verneuil-Sur-Avre about 110 km 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 which 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. 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 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 which 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 Ⓣ at this time and had just published his book on the theory of games Théorie générale des jeux à n personnes Ⓣ. Returning to France from the United States, Berge took up the position on 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 Ⓣ was published. For a mathematician in their early thirties to publish three major books within as many years is a truly outstanding achievement.
In 1994 Berge wrote a 'mathematical' murder mystery for Oulipo. In this short story Who killed the Duke of Densmore, the Duke of Densmore has been murdered by one of his six mistresses, and Holmes and 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..
Beginning in 1952 he was a Research Assistant at the French National Centre for Scientific Research, 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, 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.
The period around 1960 seems to have been particularly important and fruitful for Berge. Through the book Th´eorie des graphes et ses applications he had established a mathematical name for himself. In 1959 he attended the first graph theory conference ever in Dobogok˝o, Hungary, and met the Hungarian graph theorists. He published a survey paper on graph coloring. It 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. And in 1961, with his friend and colleague Marco Sch¨utzenberger, he initiated the S´eminaire sur les probl`emes combinatoires de l’Universit´e de Paris. 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, the Duke of Densmore has been murdered by one of his six mistresses, and Holmes and 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 .
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. Bjarne Toft writes :-
“In our modern everyday life, we are surrounded and bombarded by 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!”

Mathematical contributions

Berge wrote five books, on game theory, graph theory and its applications, topological spaces, principles of combinatorics and hypergraphs, 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:
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 of Advanced Study
at Princeton in 1957, and the same year produced his first major book Th´eorie
g´en´erale des jeux `a n personnes . Here, one not only comes across names such
as von Neumann and Nash, as one would expect, but also names like K¨onig, 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´eorie des graphes et ses applications
and Espaces topologiques, fonctions multivoques . Th´eorie des graphes et ses
applications is a master piece, 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¨onig . It would be an interesting project to compare the first two earlier books on graph theory, by Sainte-Lagu¨e and K¨onig respectively, with
the book by Berge . It is clear that Berge’s book is more leisurely and playful
than K¨onig’s, in particular. It is governed by the taste of Berge and might well be
subtitled ‘seduction into graph theory’. Among the main topics in are factorization,
matchings and alternating paths. Here Berge relies on the fundamental paper of
Gallai . Tibor Gallai is one of the greatest graph theorists – he is 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.

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

Awards and honors

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

Reviews of his books

'''Review by: Frank Harary.'''

'''The American Mathematical Monthly 70 (1) (1963), 106-107.'''

This is the English translation of "Théorie des graphes et ses applications," Dunod, Paris, 1958. Congratulations are in order to Alison Doig of the London School of Economics and Political Science on a most competent translating job. Occasionally cultural differences between the French and the British are noticeable, as in the Introduction where "II est tres remarquable... " is translated: "It is a matter of common observation.. ". The French book was reviewed by R A Good in The American Mathematical Monthly 68 76-77. The first and last sentences of Good's review state: "The tentacles of the theory of graphs steadily grow more numerous and penetrate more deeply into many phases of mathematics. All in all, in this book we have an up-to-date exposition, by one of the developers himself, of an intriguing theory capable of handling a fascinating potpourri of situations."
In our review of the French book in Mathematical Reviews 21, 309, we noted: "This is the second book on graph theory ever written. The previous book is the already classical: Denes König, 'Theorie der endlichen und unendlichen Graphen'. There are however several books on combinatorial analysis and topology which contain a chapter on graph theory. There has recently been a resurgence of interest in both the theory and application of graphs, whence the author obtains the title of his book. The book contains a considerable number of new results on graph theory which have been discovered since the book of Denes König, and is therefore a most welcome addition to the mathematical literature." The most noticeable change is that Appendices III, IV and V have been omitted in translation. Appendix IV in the original book stated 14 unsolved problems. Of these, Problem 4 was solved recently by Chong-Yun Chao, Problem 11 was solved in our previous review, and Problems 12-14 ask the reader to settle the Four-Colour-Conjecture. The accuracy of the references has been improved. Unfortunately some of them still refer to several papers. The inclusion of an author index in this English translation would have been very welcome. At the present time, the existing or announced books on graph theory are as follows: 1. Denes König, original in German, being translated into English. 2. Claude Berge, original in French, English translation herewith reviewed. 3. 0ystein Ore, Theory of Graphs, American Mathematical Society Colloquium Publications 38, 1962. 4. 0ystein Ore, Graphs and their uses, forthcoming in the School Mathematics Study Group series. In addition, several other graph theorists are actively engaged in writing their own versions of the fundamentals, foundations, and elements of graph theory. It is to be hoped that with all of these contributions to the field, as well as those books on graph theory written primarily for an audience of electrical engineers, operations researchers, or social scientists, two developments will become more pronounced: each scholar who finds it convenient to use structural or combinatorial concepts in his own research will not feel obliged to rediscover graph theory for himself, ab initio. this elegant theory with its applications within mathematics to topology, logic, algebra, and combinatorial analysis will eventually become an undergraduate course at most modern universities.

'''Review by: Rufus Isaacs.'''

'''Operations Research 7 (5) (1959), 681-682.'''

The term graph, the subject of this book, has not the common connotation of a plot or curve but refers to an established but esoteric mathematical usage. A graph is a set of points, certain pairs of which are connected by arcs. These arcs may or may not be oriented, that is, have an associated definite direction from one endpoint to the other. Possibly a new name to dispel confusion would be apropos. We offer theory of linkages. The geometric aspect of the above definition is of course not the heart of the matter; graphs can be symbolic diagrams of a rich variety of situations. The points can represent almost any kind of object and the arcs almost any type of interrelation between them. Thus we should expect the subject to abound in diverse applications, and Berge's book does. Thumbing through the volume, one is fascinated by the variegated array of illustrations, and the diverse examples attest to the very eclectic contents. The research analyst will find much to charm as well as instruct him. Hitherto the standard work was Denes König's 'Theorie der endlichen und unendlichen Graphen'. One read here of a branch of classical mathematics that struck out in many directions but penetrated deeply in few, the minor efforts of many major mathematicians. A purview of the subject can be had from a glance at a sampling of the more renowned problems. An Euler line is one that covers every arc of a graph and can be drawn without lifting the pencil or retracing. It stems from the famous problem of the seven bridges of Königsberg as recounted in most histories of mathematics and is popularly described as being the starting point of topology. A Hamilton line is nearly a dual concept: it need not cover all the arcs but must pass over each vertex once and only once. In both cases the problem is to ascertain conditions under which it is possible to draw the appropriate line. The Euler problem is rather easy, but the Hamilton problem is still unsolved. One of the most famous of all unsolved problems is that of map coloring: to show that four colors suffice to color any planar map so that adjacent countries are always of distinct hue. It becomes a question of graph theory if we let each vertex represent a country, connecting them by an arc when the corresponding countries have a mutual borderline. The cream of such older problems is elegantly treated in Berge's book. But along with them are the current advances in the subject. The disciple of operations research will recognize much material and many names; a good proportion is American. For example, there is a chapter on transportation networks. It includes the Ford-Fulkerson algorithms , and the theorems of Hoffman and Gale . As usual, the applications are astonishingly diverse. Besides questions of optimizing transport and routing, the same techniques are fitted to the problem of minimal covering, some combinatorial teasers, problems in set theory, and linear programming. The methods continue to solve problems in some subsequent chapters; in one on couplages we find a problem typical of the applied scope of this theory. In what are called simple graphs, the vertices are divided into two sets such that all arcs connect only members of one set with points of the other. A couplage is a subset of these arcs, with no two having a common endpoint. The problem: to find a maximum couplage. What is an application? Let one of the two sets of vertices above represent a set of workers, and the other, jobs to be done. A connecting arc is drawn when a worker is capable of fulfilling that job. Then a maximum couplage corresponds to a maximal scheme of assigning workers to suitable jobs. A second, but more trivial application, deserves to be quoted on less technical grounds:
“Dans un collège mixte américain, toute jeune fille a mm "boy-friends," et tout garçon a mm "girl-friends"; est-il possible de faire danser simultanément chaque jeune fille avec un de ses boy-friends et chaque garçon avec une de ses girl-friends?”
There is a chapter on game theory ; others deal with matrices and trees. There is an appendix on electrical circuit theory and some allied non-electrical problems. Always there is stimulating diversity. In the chapter entitled Facteurs, for instance, three consecutive examples run: Voyage around the World ; The Knight's Tour of the Chessboard ; and - a quick plunge to modern times and queuing problems - The Bookbinding Problem . The operations analyst will benefit from this work in acquiring an arsenal of new and imaginative techniques. Even should he never have occasion to use them, his wits cannot be but sharpened owing to the remarkable way seemingly disparate concepts are linked by common underlying ideas.

Selected publications

Major Mathematical Works