Maria Chudnovsky, IEOR - "Perfection and Beyond"

Distinguished Colloquium Series in Interdisciplinary and Applied Mathematics
Wednesday, February 25, 2015

Seminar: 5:00PM, 750 CEPSR
Costa Engineering, Columbia University

Join us for refreshments in the APAM Department,
Room 200 Mudd, from 4:30-5:00 PM.

Maria Chudnovsky

Department of Industrial Engineering & Operations Research, Columbia University

"Perfection and Beyond"

ABSTRACT: A graph is a mathematical construct that represents information about connections between pairs of objects. As a result, graphs are widely used as a modeling tool in engineering, social sciences, and other fields.

About 10 years ago one of the central open problems in graph theory at the time, the Strong Perfect Graph Conjecture, was solved. The proof used structural graph theory methods, and spanned 155 journal pages. The speaker was part of the team of authors of this mathematical beast. In this talk we will explain the problem, describe some of the ideas of the proof (that has since been shortened somewhat), and discuss related problems that have been a subject of more recent research.

BIO: Maria Chudnovsky received her B.A. and M.Sc. form the Technion, and a PhD from Princeton University in 2003. Her research interests are in graph theory and combinatorics. She is an editorial board member of the Journal of Graph Theory, SIAM Journal on Discrete Mathematics, and Discrete Mathematics.  Dr. Chudnovsky was a part of a team of four researchers that proved the strong perfect graph theorem, a 40-year-old conjecture that had been a well-known open problem in both graph theory and combinatorial optimization. For this work, she was awarded the Ostrowski foundation research stipend in 2003, and the prestigious Fulkerson prize in 2009. She was also named one of the "brilliant ten" young scientists by the Popular Science magazine. In 2012, Dr Chudnovsky received the MacArthur Foundation Fellowship, a five-year $500,000 "genius" grant to individuals who show exceptional creativity in their work and the prospect for still more in the future. In 2014, she was an invited speaker at the International Congress of Mathematicians

(Download poster)

Applied Physics & Applied Mathematics Department
Fu Foundation School of Engineering & Applied Science
Columbia University
500 W. 120th Street, 200 S.W. Mudd
Mail Code: 4701
New York, NY 10027
Phone: 212-854-4457
Fax: 212-854-8257

Maps & Directions

Columbia University makes every effort to accommodate individuals with disabilities. If you require disability accommodations to attend an event at Columbia University, please contact Disability Services at 212-854-2388 at least 10 days in advance of the event.

500 W. 120th St., Mudd 200, MC 4701 New York, NY 10027 / Phone: 212-854-4457 / Fax: 212-854-8257 / Email:

©2012 Columbia University