Leonardo Network News

The Newsletter of the International Society for the Arts, Sciences and Technology and of L'Observatoire Leonardo des Arts et Technosciences

Leonardo Honorary Editor Claude Berge Dies; His Strong Perfect Graph Conjecture Proved

Leonardo Honorary Editor Claude Berge died 30 June 2002. Berge, who in 1967 was a founding editor of Leonardo, is known as one of the fathers of modern graph theory and remembered in particular for his work on the Strong Perfect Graph Conjecture. He also was a sculptor and, along with Leonardo Honorary Editor Francois Le Lionnais, Raymond Queneau and others, a founder of the OuLiPo, which sought to explore the connections between literature and mathematics. For information on OuLiPo see <http://worldserver2.oleane.com/fatrazie/oulipo.htm> or <http://www.nous.org.uk/oulipo.html>.

In 1960 Berge made a bold conjecture in graph theory known as the Strong Perfect Graph Conjecture (SPGC). The proof of the theory, by mathematicians Paul Seymour, G. Neil Robertson and Robin Thomas, was recently reported by Dana Mackenzie in the 5 July 2002 issue of Science magazine (Vol. 297, p. 38), some 42 years after Berge made the conjecture. The solution is of particular interest as it is applicable to complex networks such as cell phone systems.

In such a network the graph consists of nodes connected by links. Imagine coloring each node a given color. Each link connects two nodes. Quoting from Mackenzie's article:

In a cell phone network, the nodes are transmitters, the lines connect any two transmitters whose ranges overlap and the colors correspond to channels. Coloring the network amounts to assigning channels so that no adjacent transmitters broadcast on the same channel. The phone company would want to use the smallest number of channels, which is called the chromatic number "chi" of the network. . . . Any group of nodes that are all connected to one another must be different colors. Graph theorists call such a dense web of nodes a clique. Thus in any graph, chi has to be at least as large as the biggest clique, a number known as omega. In a perfect graph, in fact, chi and omega are exactly equal.

Berge noticed that every imperfect graph contained either an "odd hole" or an "odd anti-hole." "An odd hole is a ring of an odd number of (at least 5) nodes each linked to its two neighbors but not to any other node in the ring. An anti-hole is the reverse: each node is connected to every other node in the ring except its neighbors." Berge conjectured that any graph without these two flaws would be perfect. Such graphs are called Berge Graphs. This SPFG is the conjecture proved by Seymour, Robertson and Thomas. Berge learned of the proof shortly before his death.

For further information see <http://www.leonardo.info>.

Leonardo Network News Coordinator: Andrea Blum E-mail: <isast@well.com>

Fig. 1.

Toyin Loye, Street Performers, silkscreen, 70 × 100 cm, 2001.

© Toyin Loye

New in Virtual Africa: Toyin Loye

Featured in OLATS's Virtual Africa Gallery, Nigerian artist Toyin Loye (Fig. 1) speaks about his work:

"I have stories to tell and I have chosen paint to express it. My painting has always been a manifestation of my life experience—growing up in a very rich culture of visual and oral expressions.

"Born to a royal house in Ijebu Jesa (1959) southwest of Nigeria where homage is daily paid to ancestors, gods and hundreds of spirits who are roaming about or even guiding and reshaping our daily lives. Where spirituality fills the poverty of the mind. The spirits and symbolisms of animals and birds are sacredly invoked as a bridge to ancestors and deities, in order to attain spiritual enlightenment and desired solutions.

"When I was young I remembered the old man, otherwise known as the man of wisdom, in his multi-colored dress who was always coming around to tell us tales while we all sat under the big iroko tree. The bats are flying in the sky. The owls are making those sacred songs and the moon glowed like diamonds in the sky.

"Life in the village...