Skip to main content

Graph Theory and Cocktail Parties

Science writer Yen Duong tells us why she loves the "friends and strangers" theorem

Nodes representing people in a social network are connected with blue lines

Social connections are rich fodder for the field of graph theory.

This article was published in Scientific American’s former blog network and reflects the views of the author, not necessarily those of Scientific American


In this episode of our podcast My Favorite Theorem, I talked with Yen Duong, who has a Ph.D. in math and now works as a science writer, a little like another math and science writer you might know and love. We were not joined by my cohost Kevin Knudson because we recorded the episode in person at the annual meeting of the National Association of Science Writers. You can listen to the episode here or at kpknudson.com, where there is also a transcript.

Yen Duong. Credit: Yen Duong


On supporting science journalism

If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.


Dr. Duong decided to talk about what she refers to as a gateway math proof, a fact about acquaintances and strangers. As she framed the question, suppose you are trying to form a committee of three people and you want all three to be acquaintances or all three to be strangers. How big does the pool of potential committee members need to be to guarantee that you can form such a committee? Three people wouldn’t work because two of them could know each other and the other could be a stranger to both of them. In fact, a pool of six will be sufficient, as Dr. Duong explains. (For a written rather than spoken explanation, check out her post about it.) The theorem is often phrased in terms of the social dynamics of parties rather than committees, and Dr. Duong likes to tell people about it at parties, so it is a cocktail party theorem on two levels.

This theorem about Ramsey numbers, sometimes called the friends and strangers theorem, is fun because it is accessible, no matter your math background, but leads very quickly into open questions in math. The minimum number of people you need to guarantee a trio of friends or a trio of strangers is called the Ramsey number R(3,3), and proving that it is six is doable with pencil and paper. The equivalent question for four mutual friends or strangers—finding the Ramsey number R(4,4), logically enough—is much more difficult but was solved in the 1950s. For five friends or strangers, the Ramsey number R(5,5) is unknown. If you’d like to learn more about Ramsey numbers and how little we know about them, check out theseposts.

In each episode, we ask our guest to pair their theorem with something: food, beverage, art, music, or other delight in life. Dr. Duong chose broccoli with cheese sauce. You’ll have to listen to the episode to find out why it is the perfect accompaniment to the friends and strangers theorem.

You can find Dr. Duong on her website, her blog Baking and Math, and Twitter. Some of her writing on science and health appears at North Carolina Health News. As we mention in the episode, both she and I started our science writing careers through the AAAS Mass Media Fellowship program. This paid internship places math and science graduate students or recent graduates in news rooms around the country for a summer. Our fellowships were sponsored by the American Mathematical Society. Both of us consider it formative in the direction our careers have taken. You can read about her experience with the Mass Media Fellowship in the Notices of the American Mathematical Society here. If you are a math or science graduate student and think you might be interested in writing about math and science for a general audience, you can learn more about the fellowship and find a link to the application here. Applications are open until January 15, 2019.

You can find more information about the mathematicians and theorems featured in this podcast, along with other delightful mathematical treats, at kpknudson.com and here at Roots of Unity. A transcript is available here. You can subscribe to and review the podcast on iTunes and other podcast delivery systems. We love to hear from our listeners, so please drop us a line at myfavoritetheorem@gmail.com. Kevin Knudson’s handle on Twitter is @niveknosdunk, and mine is @evelynjlamb. The show itself also has a Twitter feed: @myfavethm and a Facebook page. Join us next time to learn another fascinating piece of mathematics.

Previously on My Favorite Theorem:

Episode 0: Your hosts' favorite theorems Episode 1: Amie Wilkinson’s favorite theorem Episode 2: Dave Richeson's favorite theorem Episode 3: Emille Davie Lawrence's favorite theorem Episode 4: Jordan Ellenberg's favorite theorem Episode 5: Dusa McDuff's favorite theorem Episode 6: Eriko Hironaka's favorite theorem Episode 7: Henry Fowler's favorite theorem Episode 8: Justin Curry's favorite theorem Episode 9: Ami Radunskaya's favorite theorem Episode 10: Mohamed Omar's favorite theorem Episode 11: Jeanne Clelland's favorite theorem Episode 12: Candice Price's favorite theorem Episode 13: Patrick Honner's favorite theorem Episode 14: Laura Taalman's favorite theorem Episode 15: Federico Ardila's favorite theorem Episode 16: Jayadev Athreya's favorite theorem Episode 17: Nalini Joshi's favorite theorem Episode 18: John Urschel's favorite theorem Episode 19: Emily Riehl's favorite theorem Episode 20: Francis Su's favorite theorem Episode 21: Jana Rordiguez Hertz's favorite theorem Episode 22: Ken Ribet's favorite theorem Episode 23: Ingrid Daubechies's favorite theorem Episode 24: Vidit Nanda's favorite theorem Episode 25: Holly Krieger's favorite theorem Episode 26: Erika Camacho's favorite theorem Episode 27: James Tanton's favorite theorem Episode 28: Chawne Kimber's favorite theorem Episode 29: Mike Lawler's favorite theorem Episode 30: Katie Steckles' favorite theorem