Mathematical Digest Short Summaries of Articles about Mathematics in the Popular Press "On the Threshold," by Brian Hayes. American Scientist, JanuaryFebruary 2003, pages 1217. The threshold is the boundary between solvable and unsolvable problems. Hayes devotes most of the article to the problem of graphcoloring 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 graphcoloring threshold for the number of edges in a graph, Hayes shows how the solvabilityunsolvability boundary relates to phase transitions in physics.  Mike Breen
