Chudnovsky in 2011.
|Alma mater|| Technion |
|Known for|| Graph theory,|
|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.She is a 2012 MacArthur Fellow.
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,and received her Ph.D. in 2003 from Princeton University under the supervision of Paul Seymour. After postdoctoral research at the Clay Mathematics Institute, 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.
|Mathematician Maria Chudnovsky: 2012 MacArthur Fellow, MacArthur Foundation|
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.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), and of a structural characterization of the claw-free graphs.
In 2004 Chudnovsky was named one of the "Brilliant 10" by Popular Science magazine.Her work on the strong perfect graph theorem won for her and her co-authors the 2009 Fulkerson Prize. In 2012 she was awarded a "genius award" under the MacArthur Fellows Program.
She is a citizen of Israel and a permanent resident of the USA.
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.
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.