Miklós Simonovits
Encyclopedia
Miklós Simonovits is a Hungarian mathematician who currently works at the Rényi Institute of Mathematics
in Budapest
and is a member of the Hungarian Academy of Sciences
. He is on the advisory board of the journal Combinatorica
. He is best known for his work in extremal graph theory
. Among other things, he discovered the method of progressive induction which he used to describe graphs which do not contain a predetermined graph and the number of edges is close to maximal. With Lovász
, he gave a randomized algorithm
using O(n7 log2 n)
separation calls to approximate the volume of a convex body within a fixed relative error.
Simonovits was also one of the most frequent collaborators with Paul Erdős
, co-authoring 21 papers with him.
Alfréd Rényi Institute of Mathematics
The Alfréd Rényi Institute of Mathematics is the research institute in mathematics of the Hungarian Academy of Sciences. It was created in 1950 by Alfréd Rényi, who directed it until his death. Since its creation, the institute has been the center of mathematical research in Hungary. It received...
in Budapest
Budapest
Budapest is the capital of Hungary. As the largest city of Hungary, it is the country's principal political, cultural, commercial, industrial, and transportation centre. In 2011, Budapest had 1,733,685 inhabitants, down from its 1989 peak of 2,113,645 due to suburbanization. The Budapest Commuter...
and is a member of the Hungarian Academy of Sciences
Hungarian Academy of Sciences
The Hungarian Academy of Sciences is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest.-History:...
. He is on the advisory board of the journal Combinatorica
Combinatorica
Combinatorica is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorary editor-in-chief. The current editors-in-chief are László...
. He is best known for his work in extremal graph theory
Extremal graph theory
Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth...
. Among other things, he discovered the method of progressive induction which he used to describe graphs which do not contain a predetermined graph and the number of edges is close to maximal. With Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
, he gave a randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
using O(n7 log2 n)
separation calls to approximate the volume of a convex body within a fixed relative error.
Simonovits was also one of the most frequent collaborators with Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, co-authoring 21 papers with him.