A new kind of counting

February 06, 2009

Zoom Image

Left and centre: A map of Germany and the corresponding representation as a net. Right (top): A simplified Sudoku... [more]

Left and centre: A map of Germany and the corresponding representation as a net. Right (top): A simplified Sudoku consisting of three by three boxes ("Magic Square"). Right (bottom): The corresponding representation as a net. The digit "1" corresponds to the colour "red", "2" corresponds to the colour "blue", and "3" corresponds to the colour "yellow" [less]

Left and centre: A map of Germany and the corresponding representation as a net. Right (top): A simplified Sudoku consisting of three by three boxes ("Magic Square"). Right (bottom): The corresponding representation as a net. The digit "1" corresponds to the colour "red", "2" corresponds to the colour "blue", and "3" corresponds to the colour "yellow"

© Max Planck Institute for Dynamics and Self-Organization

© Max Planck Institute for Dynamics and Self-Organization

Whether sudoku, a map of Germany or solid bodies - in all of these cases, it’s all about counting possibilities. In the sudoku, it is the permitted solutions; in the solid body, it is the possible arrangements of atoms. In the map, the question is how many ways the map can be colored so that adjacent countries are always shown in a different color. Scientists depict these counting problems as a network of lines and nodes. Consequently, they need to answer just one question: How many different ways are there to color in the nodes with a certain number of colors? The only condition: nodes joined by a line may not have the same color. Depending on the application, the color of a node is given a completely new significance. In the case of the map, "color" actually means color; with sudoku the "colors" represent different figures.

Zoom Image

Two out of the 1152 different possibilities of colouring the nodes of the same net with four given colours. Nodes that... [more]

Two out of the 1152 different possibilities of colouring the nodes of the same net with four given colours. Nodes that are connected by a line must have different colours. [less]

Two out of the 1152 different possibilities of colouring the nodes of the same net with four given colours. Nodes that are connected by a line must have different colours.

© Max Planck Institute for Dynamics and Self-Organization

© Max Planck Institute for Dynamics and Self-Organization

"The existing algorithm copies the whole network for each stage of the calculation and only changes one aspect of it each time," explains Frank van Bussel of the Max Planck Institute for Dynamics and Self-Organization (MPIDS). Increasing the number of nodes dramatically increases the calculation time. For a square lattice the size of a chess board, this is estimated to be many billions of years. The new algorithm developed by the Göttingen-based scientists is significantly faster. "Our calculation for the chess board lattice only takes seven seconds," explains Denny Fliegner from MPIDS.

This is how it’s done: With the new method, the researchers move through the network node by node. As if the computer program were short-sighted, it only ever looks at the next node point and not at the whole network. At the first node point, it cannot finalize the color selection as it would have to know how all the other nodes are connected to each other. However, instead of answering this question, the program notes down a formula for the first lattice point which contains this uncertainty as an unknown quantity. As it progresses through the network, all the connections become visible and the unknown quantities are eliminated. Having arrived at the final node point, the program’s knowledge of the network is complete.

This new method can be used on much more complicated cases than the existing standard algorithm. "We can now answer many questions in physics, graph theory and computer science that have hitherto been practically unsolvable," says Marc Timme from MPIDS. "For example, our method can be applied to antiferromagnetic solids," he adds. In these solid bodies, every atom has an internal rotational pulse, called spin, which can have different values. Usually, adjacent atoms exhibit different spins. It is now possible to calculate the number of possible spin arrangements, which will allow physicists to draw conclusions about the fundamental characteristics of the thermodynamics of solid bodies.