Maria Chudnovsky

Last updated
Maria Chudnovsky
Chudnovsky in 2011.
Born (1977-01-06) January 6, 1977 (age 44)
Leningrad, Soviet Union [1]
Nationality Israeli-American
Alma mater Technion
Princeton University
Known for Graph theory,
Combinatorial optimization
Scientific career
Fields Mathematics
Institutions Princeton University
Thesis Berge Trigraphs and Their Applications.  (2005)
Doctoral advisor Paul Seymour

Maria Chudnovsky (born January 6, 1977) is an Israeli-American mathematician working on graph theory and combinatorial optimization. [2] She is a 2012 MacArthur Fellow. [3]


Education and career

Chudnovsky is a professor in the department of mathematics at Princeton University. She grew up in Russia (attended Saint Petersburg Lyceum 30) and Israel, studying at the Technion, [4] and received her Ph.D. in 2003 from Princeton University under the supervision of Paul Seymour. [5] After postdoctoral research at the Clay Mathematics Institute, [4] she became an assistant professor at Princeton University in 2005, and moved to Columbia University in 2006. By 2014, she was the Liu Family Professor of Industrial Engineering and Operations Research at Columbia. She returned to Princeton as a professor of mathematics in 2015. [2]


External video
Nuvola apps kaboodle.svg Mathematician Maria Chudnovsky: 2012 MacArthur Fellow, MacArthur Foundation [6]

Chudnovsky's contributions to graph theory include the proof of the strong perfect graph theorem (with Neil Robertson, Paul Seymour, and Robin Thomas) characterizing perfect graphs as being exactly the graphs with no odd induced cycles of length at least 5 or their complements. [7] [8] [9] Other research contributions of Chudnovsky include co-authorship of the first polynomial-time algorithm for recognizing perfect graphs (time bounded by a polynomial of degree 9), [10] and of a structural characterization of the claw-free graphs. [11]

Selected publications

Awards and honors

In 2004 Chudnovsky was named one of the "Brilliant 10" by Popular Science magazine. [12] Her work on the strong perfect graph theorem won for her and her co-authors the 2009 Fulkerson Prize. [13] In 2012 she was awarded a "genius award" under the MacArthur Fellows Program. [14] [15]

Personal life

She is a citizen of Israel and a permanent resident of the USA. [2]

In 2012, she married Daniel Panner, a viola player who teaches at Mannes School of Music and the Juilliard School. They have a son named Rafael. [16]

Related Research Articles

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have .

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

George Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University. He earned his B.Sc. from Brandon College in 1959, and his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte.

Paul Seymour (mathematician) British mathematician

Paul D. Seymour is the Albert Baldwin Dod Professor of Mathematics at Princeton University. His research interest is in discrete mathematics, especially graph theory. He was responsible for progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, and claw-free graphs. Many of his recent papers are available from his website.

In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset.

American Institute of Mathematics NSF-funded mathematical institute

The American Institute of Mathematics (AIM) is one of eight NSF-funded mathematical institutes. It was founded in 1994 by John Fry, co-founder of Fry's Electronics, and originally located in the Fry's Electronics San Jose, California location. It was privately funded by Fry at inception, and it obtained NSF funding starting in 2002.

Claude Jacques Berge was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory.

Split graph

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

Claw-free graph

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices.

Bull graph

In the mathematical field of graph theory, the bull graph is a planar undirected graph with 5 vertices and 5 edges, in the form of a triangle with two disjoint pendant edges.

Robin Thomas was a mathematician working in graph theory at the Georgia Institute of Technology.

Jeff Kahn American mathematician

Jeffry Ned Kahn is a professor of mathematics at Rutgers University notable for his work in combinatorics. Kahn received his Ph.D. from The Ohio State University in 1979 after completing his dissertation under his advisor Dijen K. Ray-Chaudhuri.

Skew partition

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

Petersens theorem

In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:

Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.

In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.

Gérard Cornuéjols American mathematician

Gérard Pierre Cornuéjols is the IBM University Professor of Operations Research in the Carnegie Mellon University Tepper School of Business. His research interests include facility location, integer programming, balanced matrices, and perfect graphs.


  1. Interview with a Mathematician
  2. 1 2 3 "Maria Chudnovsky Curriculum Vitae" (PDF). Princeton University. Retrieved 25 May 2015.
  3. "2012 MacArthur Foundation 'Genius Grant' Winners". 1 October 2012. AP. Retrieved 1 October 2012.
  4. 1 2 Interview with Research Fellow Maria Chudnovsky (PDF), Clay Mathematics Institute, 2005.
  5. Maria Chudnovsky at the Mathematics Genealogy Project
  6. "Maria Chudnovsky". MacArthur Fellows Program . MacArthur Foundation. October 2, 2012. Retrieved December 13, 2014.
  7. Mackenzie, Dana (July 5, 2002), "Mathematics: Graph theory uncovers the roots of perfection", Science , 297 (5578): 38, doi:10.1126/science.297.5578.38, PMID   12098683, S2CID   116891342 .
  8. Cornuéjols, Gérard (2002), "The strong perfect graph conjecture", Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002) (PDF), Beijing: Higher Ed. Press, pp. 547–559, MR   1957560, archived from the original (PDF) on 2014-04-07, retrieved 2012-08-11.
  9. Roussel, Florian; Rusu, Irena; Thuillier, Henri (2009), "The strong perfect graph conjecture: 40 years of attempts, and its resolution", Discrete Mathematics , 309 (20): 6092–6113, doi:10.1016/j.disc.2009.05.024, MR   2552645 .
  10. Chudnovsky et al. (2005).
  11. Chudnovsky & Seymour (2005).
  12. Minkel, J. R. (June 29, 2004), "Maria Chudnovsky", Popular Science
  13. "2009 Fulkerson Prizes" (PDF), Notices of the American Mathematical Society : 1475–1476, December 2011.
  14. Lee, Felicia R. (October 1, 2012), "Surprise Grants Transforming 23 More Lives", New York Times
  15. Maria Chudnovsky, MacArthur Foundation, October 2, 2012.
  16. Cohen, Joyce (2014-01-08). "Striking While the Iron Is Hot -". The New York Times. Retrieved 2016-02-03.