
Perfect Graphs and the "Strong Perfect Graph Conjecture" are the topic of a News Focus piece by Dana Mackenzie in the July 5 2002 Science. As Mackenzie explains it the definition involves two invariants of a graph. The first, omega, is the size of the biggest clique (set of nodes each of which is one step away from all the others). The second, chi, is the number of colors it takes to color the nodes so that no two adjacent nodes are the same color.
The two essential imperfections: an odd hole and an odd antihole. 
So chi is always bigger than omega; if the numbers are equal, the graph is perfect. Mackenzie: "A perfect graph is like a perfect chocolate cake: It might be easy to describe, but it's hard to produce a recipe." A conjecture due to Claude Berge (CNRS, Paris) has been around since 1960: every imperfect graph contains either an "odd hole" or an "odd antihole." This is the Strong Perfect Graph Conjecture (SPGC). The odd hole is "a ring of an odd number (at least 5) of nodes, each linked to its two neighbors but not to any other node in the ring." The odd antihole is "the reverse: Each node is connected to every other node in the ring except its neighbors." The news is that a proof of the SPGC has been announced by Paul Seymour (Princeton), G. Neil Robertson (OSU) and Robin Thomas (Georgia Tech). The proof is worth $10,000 (put up by fellow "perfectgraph aficionado" Gerard Cornuejols) and "the early betting is that they will collect the prize."
Algorithmic Architecture is the title of a Science in Culture piece by Martin Kemp (History of Art, Oxford) in the August 8 2002 Nature. The work he examines is a temporary pavilion erected in Hyde Park by Toyo Ito and Cecil Balmond, who "are forging new modes of building that subvert the dominant box of modernist architecture." Ito, the architect, wants to "integrate these two types of body," the "virtual body of electron flow" and "the primitive body in which water and air flow still craves for beautiful light and wind." Balmond, the engineer, is more mathematical. "He delves into pythagorean harmonics, sacred geometry, Islamic tiling, tantric numbers, the mathematics of symmetry and assymetry, chaos theory and fractals for interlocking insights into the magic of form and number." Tantric numbers? The building itself is a 17 x 17 x 4.5 meter parallelipiped, "but ... the floor and walls dissolve into an intricate web of interpenetrating squares, triangles and irregular polygons generated by an algorithm." "The pavilion serves, in effect, as a laboratory for a structural aesthetic which would have been inconceivable in an earlier era."
Home on the Fractal Range. "Fractal geometry predicts varying body size scaling relationships for mammal and bird home ranges" by John Haskell (Utah State, Logan), Mark Ritchie (Syracuse) and Han Olff (Wageningen), is a "letter to Nature" for August 1, 2002. Here is the context: "physiological characteristics of organisms, Y, often vary with body size, M, according to power functions of the general form: Y = Y_{0} M ^{b} where b is a scaling exponent, and Y_{0} is a taxon and characterspecific normalization constant." The focus of this research is "interactions between individuals and their environments," in particular a bodysize scaling law for the home range, H, the area used by an animal in its daily and seasonal movements. The authors marshall known proportionalities and estimates of their own to come up with the scaling law:
Ants vote for Wolfram. "Simple rules lie behind the most sophisticated processes in the universe" was one reporter's take on Stephen Wolfram's New Kind of Science. Recent work by G. Theraulaz and coworkers (PNAS 152302199, 812 July, 2002), picked up by Peter Hammerstein and Olof Leimar in the July 11 2002 Nature ("Ants on a Turing Trail") gives an elegant example of this phenomenon: "how the behaviour of individual workers of the ant Messor sancta produces spatial patterns in a colony's disposal of corpses  the socalled ant cemeteries." Here is the behavior, under the conditions of the experiment: "Instead of quickly choosing one or a few fixed locations for piles of corpses, the ants formed many clusters, some of which grew while others disappeared after some effort had already been made to build them. The number of clusters first grew, reaching a maximum after three hours. Later it decreased and remained constant when a stable spatial pattern was finally established." Theraulaz and his team developed a mathematical model, implementing the shortrange activation ("a behavioural tendency to drop corpses with a probability that increases with the density of corpses in the immediate neighbourhood") and longrange inhibition ("the ants' tendency to pick up corpses and carry them for considerable distances") which suffice to generate all of the ants' complicated behavior. Hammerstein and Leimar speculate that similar simple activationinhibition models could explain complicated patterns in morphogenesis and other collective processes.
Neurons do Math, in the brains of monkeys and frogs, at least. This is the message of Single brain cells count a Nature Science Update for September 6, 2002. The update, by John Whitfield, describes two recent sets of experiments. Monkeys: A. Nieder, D.J. Freedman and E.K. Miller (Science, 297 17081711 (2002)) "showed groups of dots to macaques, and recorded the output from individual neurons in the monkeys' prefrontal cortex. ... The neurons ignore the dots' size, shape and arrangement and hone in on their number. Each cell's response peaks at its preferred number and tails off on either side." Frogs: C.J. Edwards, T.B. Alder and G.J. Rose (Nature Neuroscience 5 934936, available online) sampled neurons in the brains of female frogs (Hyla regilla) to understand how they distinguished between the aggressive calls and the advertisement calls of males of their species. The only difference between the two calls is their speed. "Female frogs' maledetector neurons fire only after they hear five or more rapid pulses, Rose and his colleagues find. If the pulses are too close or too far apart, the counter resets to zero  as if the nerve cells measure the spaces between pulses, rather than the sounds themselves."
More primes in the Times. George Johnson gives us a meditation on prime numbers and their distribution ("From Here to Infinity: Obsessing With the Magic of Primes") in the September 3 2002 New York Times. He takes off from the news of the AgrawalKayalSaxena primedetection algorithm, visits the Pulchritudinous Primes site at Monash University ("Upon looking at these numbers, one has the feeling of being in the presence of the inexplicable secrets of creation." Don Zagier) while listening to something that might have come from the Prime Number Listening Guide, checks all the large numbers he can think of (none of theme are prime), remembers the autistic twins in Oliver Sacks's "The Man Who Mistook His Wife for a Hat" ("he observed the brothers one day at a state mental hospital as they sat in apparent rapture exchanging sixfigure primes that they seemed to pull from their heads") and how they ended up, after they had been separated and somewhat normalized, "as clueless as the rest of us."
Tony Phillips
Stony Brook
Comments: Email Webmaster 
© Copyright
, American Mathematical Society

