Welcome to the homepage of the
The MTA-ELTE Egerváry Research Group (EGRES for short) was founded by András Frank, and is currently led by Tibor Jordán. The group's main field of research is theoretical combinatorial optimization (for a detailed account, see Introduction). EGRES is affiliated with Operations Research Department, Eötvös University, Budapest, and the Hungarian Academy of Sciences.
For more information on our research, see our Technical Reports and Quick Proofs series. Visit our Egres Open website, an open problem collection intended also as a discussion forum for fellow researchers (the old problems page can be found here). For publicaton lists see the individual members pages.
Our mail address is: EGRES Group, Operations Research Department, Eötvös University, Pázmány P. s. 1/C, Budapest, Hungary, H-1117.
A d-dimensional framework is a pair (G, p), where G=(V, E) is a graph and p is a map from V to the d-dimensional Euclidean space. An infinitesimal motion of (G, p) is another map from V to R^d such that moving each point of the framework in that direction does not change the distances corresponding to edges in the first order. The framework is infinitesimally rigid if all of its infinitesimal motions correspond to some isometries of R^d.
Laman (1970) characterized the infinitesimal rigidity of bar-joint frameworks in the plane when the framework is in generic position, that is, when the coordinates of the points are algebraically independent over the field of rationals. Adiprasito and Nevo (2018) recently asked the following question: Which graph classes have infinitesimally rigid realizations for each of its members on a fixed constant number of points in R^d. They showed that triangulated planar graphs have such realizations on 76 points in R^3, however, for each constant c and for d>1, there always exists a graph in the class of generically rigid graphs in R^d that cannot be realized as an infinitesimally rigid bar-joint framework on any c points in R^d.
Based on the above results, it is a natural question whether planar graphs which are generically rigid in the plane have an infinitesimally rigid realization on a constant number of points of the plane. The main result of my talk is that every planar graph which is generically rigid in the plane has an infinitesimally rigid realization on 26 points of the plane. Moreover, given any set of 26 points in the plane such that the coordinates of the points are algebraically independent over the field of rationals, one can find an infinitesimally rigid realization of any rigid planar graph on that set.
Kristóf Bérczi received the Bolyai Research Scholarship managed by the Hungarian Academy of Sciences, and started a research project on Matroid Optimization funded by the Hungarian Scientific Research Fund.
László Végh (LSE) received the Starting Grant of the European Research Council for the project "Scaling Methods for Discrete and Continuous Optimization".
Kristóf Bérczi and Csaba Király were awarded Young Researcher Grants in the New National Excellence Program of the Ministry of Human Capacities.
Péter Madarasi, MSc student of Alpár Jüttner, won first prize in Applied Mathematics at the National Scientific Students' Associations Conference (OTDK).
The Hungarian Academy of Sciences (MTA) will provide financial support for the Egerváry Research Group in the period 2017-22. The leader of the MTA-ELTE research group is Tibor Jordán.
The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications will take place in Budapest on May 22-25, 2017. Details can be found on the home page of the symposium.
The Institute of Mathematics of Eötvös Loránd University is organizing a one-week summer school in June 2017, titled Higher mathematics through problem solving. Details can be found on the home page of the summer school and on the Facebook page.
The Egerváry Research Group organized a workshop in Mátraháza between February 3 and 7. Topics included chip firing, graph orientations, stable allocation problems, and covering problems in graphs.
András Frank has been elected as corresponding member of the Hungarian Academy of Sciences.
A workshop celebrating the 100 years of matching theory in Hungary has been organized at the Hungarian Academy of Sciences on December 14, 2016. link to the home page of the workshop
The 29th Conference of the European Chapter on Combinatorial Optimization will be jointly organized by the Institute of Computer Science and Control of the Hungarian Academy of Sciences and the Faculty of Science of Eötvös Loránd University in Budapest, Hungary on May 26-28, 2016. Details can be found on the home page of the conference.
The Institute of Mathematics of Eötvös Loránd University is organizing a one-week Summer School on Discrete Algorithms and Applications in June 2016. Details can be found on the home page of the summer school and on the Facebook page.
A Magyar Tudomány Ünnepe keretében az MTA Matematikai Tudományok Osztálya "Kombinatorikus optimalizálás: Egerváry Jenő nyomában" címmel tudományos ülést tart, ahol a kutatócsoport tagjai adnak elő. Linkek: meghívó, részletes program
András Frank received the Egerváry Jenő Memorial Award of the Hungarian Operations Research Society.
Three researchers of the group (Alár Jüttner, Tamás Király, Gyula Pap) are recipients of the Bolyai Research Scholarship managed by the Hungarian Academy of Sciences.
András Frank was awarded the Széchenyi Prize by Hungarian President János Áder on March 15, 2015. The award honors those who have made an outstanding contribution to science in Hungary.
The Institute of Mathematics of Eötvös Loránd University is organizing a one-week summer school in June 2015, focusing on the legacy of Paul Erdős. Details can be found on the home page of the summer school and on the Facebook page.
The summer school in Budapest, mentioned below, has a Facebook page with an abundance of information on Hungarian mathematicians, interesting mathematics links, and sightseeing tips for Budapest. Check it out, even if you do not plan to attend the school.
Sándor Kisfaludi-Bak has been awarded the one-year IBM Ph.D. Fellowship.
The Institute of Mathematics of Eötvös Loránd University, Budapest is organizing a one week long Summer school in Mathematics on June 23-27, 2014. Topics include Arborescence packing, Linear algebraic methods in graph theory, Combinatorial rigidity, Combinatorial Nullstellensatz, Finite geometries, Probabilistic methods in discrete geometry, and Geometric algorithms. For details, see the home page of the summer school!
The research group obtained support for 4 years from the Hungarian Scientific Research Fund (OTKA), including two young researcher positions.
We are deeply saddened by the death of Laci Szegő, who passed away on May 15 after a long illness. He was a dear friend and colleague whose mathematical accomplishments and wonderful personality were an inspiration to all of us.
Kristóf Bérczi received the Young Researcher Prize of the Hungarian Academy of Sciences on February 25, 2013.
The current problem of the season on Egres Open is Disjoint strongly connected spanning subgraphs.
After some hiatus, the "Problem of the month" feature of Egres Open returns under the new name "Problem of the season".
The Hungarian Academy of Sciences (MTA) will provide increased financial support for the Egerváry Research Group in the period 2012-2016. EGRES is one of the three supported mathematics research groups.
András Frank's new book Connections in Combinatorial Optimization is now available from Oxford University Press. The book offers a unified treatment of developments in the concepts and algorithmic methods of combinatorial optimization, starting from basic results on graphs, matroids and polyhedral combinatorics, through the advanced topics of connectivity issues of graphs and networks, to the abstract theory and applications of submodular optimization.
We are pleased to report that László Végh received this year's Danny Lewin Best Student Paper Award at STOC for his paper Augmenting undirected node-connectivity by one. Congratulations!
Please visit Egres Open, the new open problem forum of EGRES. In addition to being an open problem collection, it features surveys on selected topics, background information including theorems and definitions, and discussion forums for every page where anyone can comment on the open problems and surveys.
We are pleased to report that Gyula Pap received the Junior Prima Prize in the "Hungarian Science" category. The prize is given every year to 10 young Hungarian researchers for exceptional achievements. Congratulations, Gyuszkó!
There will be a meeting at ELTE on the 5th and 6th of June on the occasion of András Frank's 60th birthday, with talks by some of his former students. You can find the program here.
Tamás Király received the Young Researcher Prize of the Hungarian Academy of Sciences on March 18, 2009.
András Frank received the Szent-Györgyi Prize from the Minister of Education on January 22, 2009.
We at EGRES are all very glad to learn that our colleague Zoltán Király received the Best Paper Award of the 16th Annual European Symposium on Algorithms for his paper "Better and simpler approximation for the stable marriage problem". Zoli, congratulations! Your success is extremely encouraging for the whole group.
In the past four years, the Egerváry Research Group participated in the ADONET European Marie Curie Research Training Network, which enabled the invitation of several young researchers to Budapest. The following researchers have been visiting EGRES within the framework of ADONET: Saverio Caminiti, Hans-Florian Geerdes, Dion Gijswijt, Ambros Gleixner, Gwenaël Joret, Vincent Jost, Lavanya Kannan, Lap Chi Lau, and Nguyen Tien Thanh.
EGRES starts to publish a new online series called EGRES Quick-Proofs, which intends to be a forum for the publication of short proofs, notes, and minor results that are not substantial enough to be published as a separate paper. For more details, see the Quick-Proofs page.
In the next three years, the Hungarian Academy of Sciences (MTA) will provide increased financial support for EGRES, including the funding of 3 full-time research positions.
The ADONET/COST293 Spring School on Combinatorial Optimization and Communication Networks, organized partly by EGRES, will be held in Budapest on 20-24 March, 2006. More information is available on the web page of the spring school.
LEMON (Library of Efficient Models and Optimization in Networks) is a C++ template library aimed at combinatorial optimization tasks, especially those working with graphs and networks. The LEMON project is launched by the EGRES group. The project is led by Alpár Jüttner. LEMON is an open source project.
EGRES participates in Algorithmic Discrete Optimization Network (ADONET), a Marie Curie Research Training Network funded by the European Union FP6 Programme. The network consists of research teams and researchers from Germany, Belgium, the Netherlands, Italy, France, Switzerland, Portugal, the United Kingdom, Austria, and Hungary.