ERC Advanced Grant​
From Geometry to Combinatorics and Back: Escaping the Curse of Dimensionality  (GeoScape)
2020. Szeptember - 2025. Augusztus

A kutatások fő célkitűzése a kombinatorika néhány nevezetes megoldatlan problémájának vizsgálata olyan gráf- és hipergráfosztályok esetén, melyek fontos szerepet játszanak geometriai, algebrai és gyakorlati alkalmazásokban. Ezeket a struktúrákat nem sújtja a „magas dimenzió átka": beágyazhatóak valamely korlátos dimenziós térbe, Vapnik-Chervonenkis (VC)-dimenziójuk alacsony vagy leírhatóak rövid algebrai formulával. A csoport vezetője -- munkatársaival és hallgatóival együtt -- jelentős szerepet játszott a modern kombinatorika eszközeinek geometriai alkalmazásában. A jelen projekt célja ezzel ellentétes irányú.  Olyan geometriai technikák kidolgozására és alkalmazására törekszik, melyekkel fontos speciális esetekben elintézhető több hírhedten bonyolult kombinatorikus probléma (1) korlátos fokú szemialgebrai gráfokra és hipergráfokra, (2) korlátos VC-dimenziós gráfokra és hipergráfokra, (3) rendezett gráfokra, 0-1 mátrixokra illetve síkba vagy más felületekbe ágyazott gráfokra. A pályázatban ismertetett kérdésekkel kapcsolatos felfedezések várhatóan közelebb visznek több olyan klasszikus probléma elintézéséhez, mint az Erdős-Hajnal sejtés, a Danzer-Rogers sejtés vagy a Schur-Erdős probléma, és hozzásegítenek olyan hatékony algoritmusok kidolgozásához, melyek alkalmazhatóak nagy hálózatokra vonatkozó klaszterezési és tulajdonságtesztelési feladatok megoldásánál. 

Kutatócsoport weboldala 

Publikációk

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

L. Fang, H, Huang, J. Pach, G. Tardos, J. Zuo.Linear orderings of the edges of a graph

G. Kucheriya, G. Tardos.A characterization of edge-ordered graphs with almost linear extremal functions

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

A. Golovanov, A. Kupavskii, A. Sagdeev.Odd-distance and right-equidistant sets in the maximum and Manhattan metrics

N. Frankl, A. Kupavskii, A. Sagdeev.Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings

J. Karl, G. Tóth.Crossing lemma for the odd-crossing number

Cs. Bíró, J. Lehel, G. Tóth.Helly-type theorems for the ordering of the vertices of a hypergraph

J. Barát, Z.L. Blázsik.Quest for graphs of Frank number 3

Á. Ambrus, M. Csikós, G. Kiss, J. Pach, G. Somlai.Optimal embedded and enclosing isosceles triangles

J. Barát, A. Gyárfás, G. Tóth.Monochromatic spanning trees and matchings in ordered complete graphs

J. Pach, G. Tardos.Where have all the grasshoppers gone?

A. Kupavskii, A. Sagdeev, D. Zakharov.Cutting corners

V. Kirova, A. Sagdeev.Two-colorings of normed spaces without long monochromatic unit arithmetic progressions

J. Barát, D. Gerbner, A. Halfpap.On the number of A-transversals in hypergraphs

2023

G. Ambrus, M. Balko, N. Frankl, A. Jung, M. Naszódi.On Helly numbers of exponential lattices

J. Barát, Z.L. Blázsik.General sharp upper bounds on the total coalition number

J. Böttcher, N. Frankl, D.M. Cecchelli, O. Parzcyk, J. Skokan.Graphs with large minimum degree and no small odd cycles are 3-colourable