Combinatorica
Encyclopedia
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ó Babai
, László Lovász
, and Alexander Schrijver. The advisory board consists of Ronald Graham
, András Hajnal
, Gyula O. H. Katona
, Miklós Simonovits
, and Vera Sós. It is published by the János Bolyai Mathematical Society
and Springer Verlag. The following members of the Hungarian School of Combinatorics have strongly contributed to the journal as authors, or have served as editors: Miklós Ajtai
, József Beck
, András Frank
, Péter Frankl
, Zoltán Füredi
, András Hajnal
, Gyula Katona
, László Pyber
, Miklós Simonovits
, Vera Sós, Endre Szemerédi
, Tamás Szőnyi, Éva Tardos
, Gábor Tardos
.
M. Grotschel, L. Lovasz, A. Schrujver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1(1981), 169–197.
J. Beck:, Roth
's estimate of the discrepancy of integer sequences is nearly sharp, Combinatorica, 1(1981), 319–325.
N. Karmarkar
: A New Polynomial Time Algorithm for Linear Programming, Combinatorica, 4(1984), 373–395.
M. Szegedy
: The solution of Graham's greatest common divisor problem, Combinatorica, 6(1986), 67--71.
E. Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, 5(1985), 247–256.
M. El-Zahar, N. W. Sauer: The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica, 5(1985), 121–126.
B. Bollobás: The chromatic number of random graphs, Combinatorica, 8(1988), 49–55.
N. Robertson, P. D. Seymour, R. Thomas: Hadwiger's conjecture for K6-free graphs, Combinatorica, 13 (1993), 279–361.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, publishing papers in the fields of combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
. It started in 1981, with László Babai
László Babai
László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields...
and László 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....
as the editors-in-chief 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...
as honorary editor-in-chief. The current editors-in-chief are László Babai
László Babai
László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields...
, László 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....
, and Alexander Schrijver. The advisory board consists of Ronald Graham
Ronald Graham
Ronald Lewis Graham is a mathematician credited by the American Mathematical Society as being "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years"...
, András Hajnal
András Hajnal
András Hajnal is an emeritus professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.-Biography:Hajnal was born on 13 May 1931, in Hungary....
, Gyula O. H. Katona
Gyula O. H. Katona
Gyula O. H. Katona is a Hungarian mathematician known for his work in combinatorial set theory, and especially for the Kruskal–Katona theorem and his elegant proof of the Erdős–Ko–Rado theorem...
, Miklós Simonovits
Miklós Simonovits
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...
, and Vera Sós. It is published by the János Bolyai Mathematical Society
János Bolyai Mathematical Society
The János Bolyai Mathematical Society is the Hungarian mathematical society, named after János Bolyai, a 19th century Hungarian mathematician, a co-discoverer of non-Euclidean geometry. It is the professional society of the Hungarian mathematicians, applied mathematicians, and mathematics teachers...
and Springer Verlag. The following members of the Hungarian School of Combinatorics have strongly contributed to the journal as authors, or have served as editors: Miklós Ajtai
Miklós Ajtai
Miklós Ajtai is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden...
, József Beck
József Beck
József Beck is a Harold H. Martin Professor of Mathematics at Rutgers University.His contributions to combinatorics include the partial colouring lemma and the Beck–Fiala theorem in discrepancy theory, the algorithmic version of the Lovász local lemma, the two extremes theorem in combinatorial...
, András Frank
András Frank
András Frank is a Hungarian mathematician, working in combinatorics, especially in graph theory, and combinatorial optimisation...
, Péter Frankl
Péter Frankl
----Péter Frankl is a Hungarian mathematician and street performer. Frankl studied Mathematics in University Paris Diderot and has lived in Japan since 1988, where he sometimes appears on NHK. Though not as popular as he once was, he still performs juggling in public spaces around Tokyo...
, Zoltán Füredi
Zoltán Füredi
Zoltán Füredi is a Hungarian mathematician, working in combinatorics, mainly in discrete geometry and extremal combinatorics. He was a student of Gyula O. H. Katona. He is a corresponding member of the Hungarian Academy of Sciences...
, András Hajnal
András Hajnal
András Hajnal is an emeritus professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.-Biography:Hajnal was born on 13 May 1931, in Hungary....
, Gyula Katona
Gyula O. H. Katona
Gyula O. H. Katona is a Hungarian mathematician known for his work in combinatorial set theory, and especially for the Kruskal–Katona theorem and his elegant proof of the Erdős–Ko–Rado theorem...
, László Pyber
László Pyber
László Pyber is a Hungarian mathematician.He works in combinatorics and group theory. He is a researcher at the Alfréd Rényi Institute of Mathematics, Budapest.He received the title the Doctor of Science from the Hungarian Academy of Sciences...
, Miklós Simonovits
Miklós Simonovits
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...
, Vera Sós, Endre Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
, Tamás Szőnyi, Éva Tardos
Éva Tardos
Éva Tardos is a Hungarian mathematician, winner of the Fulkerson Prize , and professor of Computer Science at Cornell University.Research Interests:...
, Gábor Tardos
Gábor Tardos
Gábor Tardos is a Hungarian mathematician, currently a professor and Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science...
.
Notable publications in the Combinatorica
- A paper by Martin Grötschel, László LovászLászló LovászLá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....
, and Alexander Schrijver on the ellipsoid methodEllipsoid methodIn mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The...
.
M. Grotschel, L. Lovasz, A. Schrujver: The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1(1981), 169–197.
- Jozsef BeckJózsef BeckJózsef Beck is a Harold H. Martin Professor of Mathematics at Rutgers University.His contributions to combinatorics include the partial colouring lemma and the Beck–Fiala theorem in discrepancy theory, the algorithmic version of the Lovász local lemma, the two extremes theorem in combinatorial...
's Fulkerson PrizeFulkerson PrizeThe Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
winner paper on the discrepancy of hypergraphs.
J. Beck:, Roth
Klaus Roth
Klaus Friedrich Roth is a British mathematician known for work on diophantine approximation, the large sieve, and irregularities of distribution. He was born in Breslau, Prussia, but raised and educated in the UK. He graduated from Peterhouse, Cambridge in 1945...
's estimate of the discrepancy of integer sequences is nearly sharp, Combinatorica, 1(1981), 319–325.
- Karmarkar's algorithmKarmarkar's algorithmKarmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time...
solving linear programming problems in polynomial time.
N. Karmarkar
Narendra Karmarkar
Narendra K. Karmarkar is an Indian mathematician, renowned for developing Karmarkar's algorithm. He is listed as an ISI highly cited researcher.- Biography :...
: A New Polynomial Time Algorithm for Linear Programming, Combinatorica, 4(1984), 373–395.
- Szegedy's solution of Graham problem on common divisors
M. Szegedy
Mario Szegedy
Mario Szegedy is a Hungarian computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago...
: The solution of Graham's greatest common divisor problem, Combinatorica, 6(1986), 67--71.
- Eva TardosÉva TardosÉva Tardos is a Hungarian mathematician, winner of the Fulkerson Prize , and professor of Computer Science at Cornell University.Research Interests:...
's Fulkerson PrizeFulkerson PrizeThe Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
winner paper.
E. Tardos, A strongly polynomial minimum cost circulation algorithm, Combinatorica, 5(1985), 247–256.
- The proof of El-Zahar and Norbert Sauer of the Hedetniemi's conjectureHedetniemi's conjectureIn graph theory, Hedetniemi's conjecture, named after Stephen T. Hedetniemi, concerns the connection between graph coloring and the tensor product of graphs...
for 4-chromatic graphs.
M. El-Zahar, N. W. Sauer: The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica, 5(1985), 121–126.
- BollobásBéla BollobásBéla Bollobás FRS is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory and percolation. As a student, he took part in the first three International Mathematical Olympiads, winning two gold medals...
's asymptotic value of the chromatic number of random graphs.
B. Bollobás: The chromatic number of random graphs, Combinatorica, 8(1988), 49–55.
- Another Fulkerson PrizeFulkerson PrizeThe Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
winner paper by Neil RobertsonNeil Robertson (mathematician)G. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...
, Paul Seymour, and Robin ThomasRobin Thomas (mathematician)Robin Thomas is a mathematician working in graph theory at the Georgia Institute of Technology.Thomas received his doctorate in 1985 from Charles University in Prague, Czechoslovakia , under the supervision of Jaroslav Nešetřil...
, proving Hadwiger's conjectureHadwiger conjecture (graph theory)In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph...
in the case k=6.
N. Robertson, P. D. Seymour, R. Thomas: Hadwiger's conjecture for K6-free graphs, Combinatorica, 13 (1993), 279–361.
External links
- Combinatorica's homepage.
- Combinatorica on-line at Springer.