Whenever Maria Chudnovsky gets her car fixed, she feels uneasy. Did the mechanic really discern the problem, or did he just tinker until the symptoms vanished? “How do I know,” she says, “that in 15 minutes it won’t break again?”
Chudnovsky, 27, yearns to understand the world completely. Why do storm clouds appear before it rains? Why do we catch cold? What was really wrong with her car? Most of the time, she ends up frustrated. So she takes comfort in the abstract realm of mathematics, where all facts derive from provable universal laws. “I have to understand things all the way,” she says. And when she says “all the way,” she means it. Her single-mindedness helped prove a hypothesis that stumped generations of her predecessors. “Young mathematicians are called promising if they are expected to become at least half as good in 10 years as Maria is now,” says Rutgers mathematician Vasek Chvtal.
Chudnovsky’s area of inquiry is known as graph theory. It doesn’t involve the graphs we’re all familiar with, the ones with x and y axes that are sprinkled through SAT tests and annual reports. Chudnovsky’s graphs are a bunch of dots, some of which are connected by lines. In 2002 she helped prove the perfect-graph conjecture, which states that only two kinds of flaws can make a graph imperfect. She learned of this 40-year-old brain-bender while in college in Israel and worked on it with her adviser and two others after coming to Princeton for graduate study.
What is a perfect graph? Find the largest number of points in a graph that are all connected to one another—for example, a five-pointed star surrounded by a pentagon. Color the points so each is a different color than the ones it’s connected to (for this example you’d need five colors, one for each of the star’s points). Now, how many colors do you need to do the same coloring trick with the entire graph? If those two numbers are the same, the graph is perfect. The conjecture provides a way to distinguish perfect from imperfect graphs without having to color every point. Chudnovsky’s team proved it by grouping perfect graphs into just five classes, then showing that all graphs lacking the two kinds of imperfection-causing flaws fit into one of the five classes.
Graph theory explains why some organizational problems, such as constructing a cellphone network using the fewest transmitters, are harder than others. But Chudnovsky is unconcerned with practical matters. Math, for her, is a way to grasp the essence of things. “It’s like solving a crossword puzzle all day long,” she says.
Five amazing, clean technologies that will set us free, in this month's energy-focused issue. Also: how to build a better bomb detector, the robotic toys that are raising your children, a human catapult, the world's smallest arcade, and much more.