Maria Chudnovsky | |
---|---|

Chudnovsky in 2011. | |

Born | Leningrad, Soviet Union ^{ [1] } | January 6, 1977

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] }

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 | |
---|---|

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] }

- Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina (2005), "Recognizing Berge graphs",
*Combinatorica*,**25**(2): 143–186, doi:10.1007/s00493-005-0012-8, MR 2127609, S2CID 2229369 . - Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs",
*Surveys in Combinatorics 2005*, London Mathematical Society Lecture Note Series,**327**, Cambridge: Cambridge Univ. Press, pp. 153–171, CiteSeerX 10.1.1.112.4130 , doi:10.1017/CBO9780511734885.008, ISBN 9780511734885, MR 2187738 . - Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem",
*Annals of Mathematics*,**164**(1): 51–229, arXiv: math/0212070 , doi:10.4007/annals.2006.164.51, S2CID 119151552 . - Chudnovsky, Maria; Sivaraman, Vaidy (2018), "Odd Holes in Bull-Free Graphs",
*SIAM Journal on Discrete Mathematics*,**32**(2): 951–955, arXiv: 1704.04262 , doi:10.1137/17M1131301, MR 3794342, S2CID 1657094

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] }

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] }

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.

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 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.

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.

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).

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.

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.

**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.

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.

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 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.

- ↑ Interview with a Mathematician
- 1 2 3 "Maria Chudnovsky Curriculum Vitae" (PDF). Princeton University. Retrieved 25 May 2015.
- ↑ "2012 MacArthur Foundation 'Genius Grant' Winners".
*1 October 2012*. AP. Retrieved 1 October 2012. - 1 2
*Interview with Research Fellow Maria Chudnovsky*(PDF), Clay Mathematics Institute, 2005. - ↑ Maria Chudnovsky at the Mathematics Genealogy Project
- ↑ "Maria Chudnovsky".
*MacArthur Fellows Program*. MacArthur Foundation. October 2, 2012. Retrieved December 13, 2014. - ↑ 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 . - ↑ 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. - ↑ 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 . - ↑ Chudnovsky et al. (2005).
- ↑ Chudnovsky & Seymour (2005).
- ↑ Minkel, J. R. (June 29, 2004), "Maria Chudnovsky",
*Popular Science* - ↑ "2009 Fulkerson Prizes" (PDF),
*Notices of the American Mathematical Society*: 1475–1476, December 2011. - ↑ Lee, Felicia R. (October 1, 2012), "Surprise Grants Transforming 23 More Lives",
*New York Times* - ↑ Maria Chudnovsky, MacArthur Foundation, October 2, 2012.
- ↑ Cohen, Joyce (2014-01-08). "Striking While the Iron Is Hot - NYTimes.com".
*The New York Times*. Retrieved 2016-02-03.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.