GeoScape

ERC Advanced Grant
From Geometry to Combinatorics and Back: Escaping the Curse of Dimensionality  (GeoSpace)
September 2020 - August 2025  

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 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, the Schur-Erdős problem, and to the development of improved algorithms for clustering and property testing in huge graphs.

Publications

2021

J. Fox, J. Pach, A. Suk:.Sunflowers in set systems of bounded dimension

P. Frankl, J. Pach : On well-connected sets of strings

P. Frankl, J. Pach, D. Pálvölgyi.: Exchange properties of finite set-systems

J. Pach, G. Tardos, G. Tóth: Disjointness graphs of segments in the space

J. Fox, J. Pach, A. Suk: On the number of edges of separated multigraphs

J. Pach, I. Tomon: Erdős-Hajnal-type results for monotone paths

M. Kaufmann, J. Pach, G. Tóth, T. Ueckerdt: The number of crossings in multigraphs with no empty lens

J. Barát, Z.L. Blázsik, G. Damásdi: Crumby colorings — red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen

J. Barát, G. Tóth: Saturated 2-planar drawings with few edges

J. Barát: Extremal K_4-minor-free graphs without short cycles

J. Fox, J. Pach, A. Suk: Quasiplanar graphs, string graphs, and the Erdős-Gallai problem

J. Karl, G. Tóth: A slightly better bound on the crossing number in terms of the pair-crossing number

J. Pach, G. Tardos, G. Tóth:Disjointness graphs of short polygonal chains

P. Erdős, E. Makai, Jr., J. Pach: Nearly equal distances in the plane, II

2022

N. Alon, D. Elboim, J. Pach, G. Tardos: Random necklaces require fewer cuts

M. Czett, J. Barát: The horizon of 2-dichromatic oriented graphs

N. Frankl, D. Woodruff: On some non-rigid unit distance patterns

N. Frankl, A. Kupavskii, A. Sagdeev: Max-norm Ramsey Theory

N. Frankl, T. Hubai, D. Pálvölgyi: Almost-monochromatic sets and the chromatic numberof the plane

N. Frankl, A. Kupavskii: Nearly k-distance sets

N. Frankl, A. Kupavskii, A. Sagdeev: Solution to a conjecture of Schmidt and Tuller on linear packings and coverings