GeoScape

ERC Advanced Grant​
From Geometry to Combinatorics and Back: Escaping the Curse of Dimensionality  (GeoScape)
2020. Szeptember - 2027. Február

NEWS!  Erdős Center Special Semester

From January 1 through June 30, 2027, the Erdős Center at the Rényi Institute of Mathematics (Budapest) will host a Special Semester on Ordered Combinatorics. As part of the program, we will organize two schools for PhD students and postdocs, several conferences, and a weekly seminar series. A number of young researchers and senior participants will be in residence throughout the semester.

On January 18-22, 2027, we will organize a Winter School on Order and Structure in Geometry . The following week, on January 25–29, 2027, we will hold a major workshop on the same subject. Confirmed speakers include Matija Bucic (Univ. Wien),  Gábor Damásdi (Rényi), James Davies (Leipzig), Jacob Fox (Stanford),  Rachel Greenfeld (Northwestern), Alfredo Hubard (Paris), Máté Matolcsi (Rényi), Bojan Mohar (Ljubljana), Hugo Parlier (Luxembourg), József Solymosi (UBC), Andrew Suk (UC San Diego), Bartosz Walczak (Krakow) . Our Summer School and Conference on  Ordered Combinatorial Structures will be held on June 14-18 and June 21-25, 2027, resp. The opening lecture will be given by Noga Alon (Princeton). For more information about the program and on how to apply for postdoc positions, contact János Pach or Gábor Tardos.

NEWS!  Graph Drawing 2027

The 35th International Symposium on Graph Drawing and Network Visualization will be organized in Budapest, September 13-17, 2027. One of the keznote speakers will be László Lovász. For more information, contact János Pach or Géza Tóth. 

Summary

The main goal of the present project is to attack some hard problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures escape the "curse of dimensionality”: they can be embedded in a bounded-dimensional space, or they have a small VC-dimension, or a short algebraic description. The work of the principal investigator, his collaborators, and students has played a significant role in the introduction of modern combinatorial tools in geometry. In the present project, he aims to explore the reverse direction: to develop and apply geometric techniques to settle important special cases of notoriously difficult combinatorial problems on (1) bounded degree semi-algebraic graphs and hypergraphs, (2) graphs and hypergraph of bounded VC-dimension, (3) ordered graphs, 0-1 matrices, and graphs embedded in the plane or in other surfaces. Progress on the problems described in the proposal is expected to lead closer to the solution of some classical problems, such as the Erdős-Hajnal conjecture, the Danzer-Rogers conjecture, and the Schur-Erdős problem, and to the development of improved algorithms for clustering and property testing in huge graphs.

Website of the group

List of publications