# Egerváry Research Group on Combinatorial Optimization (EGRES)

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.

# The program of the next seminar:

## 2019.02.25   Király Csaba   Rigid realizations of planar graphs with few locations in the plane

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.

# News:

## 2018.11.23   Bolyai Scholarship and Support from the Hungarian Scientific Research Fund

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.

## 2017.10.01   ERC Starting Grant for László Végh

László Végh (LSE) received the Starting Grant of the European Research Council for the project "Scaling Methods for Discrete and Continuous Optimization".

## 2017.09.01   ÚNKP Young Researcher Grants

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.

## 2017.08.01   OTDK First Prize

Péter Madarasi, MSc student of Alpár Jüttner, won first prize in Applied Mathematics at the National Scientific Students' Associations Conference (OTDK).

## 2017.07.01   Support by the Hungarian Academy of Sciences

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.

## 2017.04.18   10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications

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.

## 2017.02.08   Summer school in June 2017

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.

## 2017.02.08   Mátraháza Workshop

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.

## 2017.01.01   MTA membership

András Frank has been elected as corresponding member of the Hungarian Academy of Sciences.

## 2016.12.14   100 years of matching theory in Hungary

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

## 2016.02.03   ECCO 2016

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.

## 2016.01.27   Summer school in June 2016

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.

## 2015.11.11   Kombinatorikus optimalizálás: Egerváry Jenő nyomában

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

## 2015.06.10   Egerváry Jenő Memorial Award

András Frank received the Egerváry Jenő Memorial Award of the Hungarian Operations Research Society.

## 2015.06.09   Bolyai Scholarships

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.

## 2015.03.15   Széchenyi Prize

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.

## 2015.02.19   Summer school in June 2015

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.

## 2014.05.14   Summer school 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.

## 2014.05.06   IBM Ph.D. Fellowship

Sándor Kisfaludi-Bak has been awarded the one-year IBM Ph.D. Fellowship.

## 2014.03.20   Summer school at the Institute of Mathematics of Eötvös University

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!

## 2013.10.02   Support from the Hungarian Scientific Research Fund

The research group obtained support for 4 years from the Hungarian Scientific Research Fund (OTKA), including two young researcher positions.

## 2013.05.15   Laci Szegő (1972-2013)

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.

## 2013.02.26   Young Researcher Prize

Kristóf Bérczi received the Young Researcher Prize of the Hungarian Academy of Sciences on February 25, 2013.

## 2013.01.04   Problem of the season, Winter 2012/13

The current problem of the season on Egres Open is Disjoint strongly connected spanning subgraphs.

## 2012.07.13   Problem of the season on Egres Open

After some hiatus, the "Problem of the month" feature of Egres Open returns under the new name "Problem of the season".

## 2011.09.08   Support from the Hungarian Academy of Sciences

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.

## 2011.03.03   Connections in Combinatorial Optimization - new book by András Frank

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.

## 2010.06.08   László Végh wins STOC Best Student Paper Award

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!

## 2009.12.18   Egres Open website launched

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.

## 2009.12.05   Gyula Pap wins the Junior Prima prize

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

## 2009.05.27   FA60 Meeting

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.

## 2009.03.18   Young Researcher Prize

Tamás Király received the Young Researcher Prize of the Hungarian Academy of Sciences on March 18, 2009.

## 2009.01.22   Szent-Györgyi Prize

András Frank received the Szent-Györgyi Prize from the Minister of Education on January 22, 2009.

## 2008.07.02   Best Paper Award of ESA 2008 awarded to Zoltán Király

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.

## 2006.08.15   EGRES Quick-Proofs

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.

## 2006.08.15   Increased support from the Hungarian Academy of Sciences

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.

## 2006.02.06   Spring School Announcement

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.

## 2003.11   LEMON

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.