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 anti-hole.
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 anti-hole." 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 anti-hole 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 "perfect-graph 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 = Y0 M b where b is a scaling exponent, and Y0 is a taxon- and character-specific normalization constant." The focus of this research is "interactions between individuals and their environments," in particular a body-size 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 co-workers (PNAS 152302199, 8-12 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 so-called 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 short-range activation ("a behavioural tendency to drop corpses with a probability that increases with the density of corpses in the immediate neighbourhood") and long-range 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 activation-inhibition 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 1708-1711 (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 934-936, 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' male-detector 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 Agrawal-Kayal-Saxena prime-detection 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 six-figure 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."
Math in the Media Archive
Comments: Email Webmaster