(Every year the MacArthur Foundation names 20-30 fellows. Each is granted $500,000 for what has been unofficially called the "genius" award. To date, more than 900 individuals have been named fellows for a combination of their intellect, persistence and creativity. Occasionally, Stuff of Genius will focus on one of these MacArthur fellows in a series called "900 Geniuses.")
Most people agonize over planning the seating chart for their wedding and its reception. Where do you put your father's third wife in relation to your single mother? Can your erratic aunt sit next to a table of your sorority sisters without an incident starting? Instead of turning to a wedding planner for help, mathematician Maria Chudnovsky used what she knows best for building her seating chart: graph theory.
Chudnovsky's work in mathematics has developed models to discover practical solutions to problems that are as diverse as urban planning, or constructing her own wedding's seating chart. For her contributions to graph theory and the proof of the "Strong Perfect Graph Theorem," the MacArthur Foundation chose Chudnovsky as a recipient of their fellowship in 2012.
When explaining graph theory Chudnovsky makes it clear that it has nothing to do with the traditional x and y axes we learn in school and see in countless PowerPoint presentations. Graph theory problems use dots and lines, ultimately looking like some formula Will Hunting would secretly solve on an MIT blackboard. The dots represent objects abstractly and the lines are "edges" that record connections between certain pairs of dots. Graph theory's been used for network design, molecular biology and organizational problems. Applications to social networking seem obvious as well, given that you can use graph theory to measure people and their relationships to one another.
Chudnovsky's work is mostly theoretical; she studies abstract concepts in graph theory, but these can sometimes be used for modeling real life relationships and their properties. For example, Chudnovsky's use of graph theory when planning her wedding found the most favorable circumstances for arranging friends and family, encouraging their best behavior. For this she used a well-know "graph coloring" model that is a classical notion in graph theory. It partitions the "dots" of the graph into as few sets as possible (each set is called a "color"), such that no two dots in the same set have an edge between them. In this case, the colors represented tables at the reception.
Chudnovsky's MacArthur Fellowship helps to spread the word about graph theory, increasing awareness of its capabilities. Her work is now being discussed in popular science publications, not to mention a Comforpedic ad campaign that references her expertise to sell their product. Chudnovsky's use of graph theory may have important implications for solving not only the connections between objects, but also the relationships between people.
Lots more information
- Hofius, Sarah. "Young Scientists Prove 'Popular.'" USA Today. 2004.
- Lamb, Evelyn. "Perfect Graphs and Perfect Harmony: Meet 2 of the 2012 MacArthur 'Genius' Fellows." Scientific American. (Accessed on 9/18/2013). http://www.scientificamerican.com/article.cfm?id=macarthur-genius-grants.
- MacArthur Foundation. Meet the Class of 2012: Maria Chudnovsky." 10/2/2012. (Accessed on 9/18/2013). http://www.macfound.org/fellows/862/
- Mackenzie, Dana. "Graph Theory Uncovers the Roots of Perfection." Science. 2002.
- Minkel, JR. "Maria Chudnovsky." Popular Science. 2004.
- Perry, D. "Simmons Gets Expert Help in ComforPedic Ad Campaign." Furniture/Today. Vol. 37. No. 34. Page. 12. 2013.