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 Ordered 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. 

Összefoglaló

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. 

A 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

2023

J. Barát, Z.L. Blázsik, G. Damásdi. 
Crumby colorings — red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen. Discrete Mathematics Volume 346, Issue 4 (2023) 113281

J. Barát. 
Extremal K_4-minor-free graphs without short cycles. Periodica Mathematica Hungarica Volume 84 (2023) 108–114