Math in the Media

Also see the Blog on Math Blogs

Mathematical Digest

Short Summaries of Articles about Mathematics
in the Popular Press

"On the Threshold," by Brian Hayes. American Scientist, January-February 2003, pages 12-17.

The threshold is the boundary between solvable and unsolvable problems. Hayes devotes most of the article to the problem of graph-coloring with three colors: That is, can a graph's vertices be colored with three colors so that no two vertices of the same color are connected by an edge? Naturally, as the number of edges in a graph increases (keeping the number of vertices fixed), so too does the chance that the answer is no. In addition to discussing the graph-coloring threshold for the number of edges in a graph, Hayes shows how the solvability-unsolvability boundary relates to phase transitions in physics.

--- Mike Breen