Low Dimensional Combinatorics  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
133864
Type KKP
Principal investigator Pach, János
Title in Hungarian Alacsony dimenziós kombinatorika
Title in English Low Dimensional Combinatorics
Keywords in Hungarian Szemialgebrai halmaz, VC-dimenzió, topológiai gráfok, 0-1 mátrixok, extremális hipergráf-elmélet, metszetgráfok,
Keywords in English Semi-algebraic set, VC dimension, topological graphs, 0-1 matrices, extremal hypergraph theory, intersection graphs, string graphs
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Combinatorial analysis
Panel 'Foreront' Research Excellence Program
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Bezdek, András
Horváth, Márton
Naszódi, Márton
Tardos, Gábor
Tóth, Géza
Starting date 2020-04-01
Closing date 2021-02-28
Funding (in million HUF) 58.056
FTE (full time equivalent) 3.92
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

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, Vapnyik-Cservonyenkisz (VC)-dimenziójuk alacsony vagy leírhatóak rövid algebrai formulával. A pályázó -- 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.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

Az extremális gráf- és hipergráfelmélet számos alapvető eredményét várható geometriai alkalmazásaik motiválták. Így például a Ramsey-elmélet megszületését a konvex sokszögekkel kapcsolatos Erdős-Szekeres-féle úgynevezett “happy end probléma” inspirálta, de végsősoron ez vezetett a Turán-tétel felfedezéséhez is. Erdős híres számelméleti kérdései és az n pont közötti távolságok eloszlására vonatkozó sejtései hasonló szerepet játszottak a struktúrális gráfelmélet létrejöttében és egyebek között Szemerédi regularitási lemmájának felfedezésében. Noha ezeket az elméleteket és technikákat geometriai kérdések kezelésére fejlesztették ki, az eredeti problémákra való közvetlen alkalmazásuk ritkán adott optimális eredményt.

Mi lehet ennek a paradox jelenségnek a hátterében? Az elmúlt tíz évben elért eredményeink azt sugallják, hogy a fenti geometriai konfigurációkhoz köthető kombinatorikai struktúrák (gráfok és hipergráfok) gyakran – bizonyos jól definiált értelemben -- alacsony dimenziósak; például leírásuk bonyolultsága, Vapnyik-Cservonyenkisz vagy Dushnik-Miller dimenziójuk kicsi. Jelen pályázatban efféle konfigurációk speciális geometriai, topológiai és statisztikus tulajdonságait kutatjuk abból a célból, hogy közelebb jussunk az eredeti kombinatorikai feladatok megoldásához.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A kombinatorika a matematika egyik alapvető ága, amely az elmúlt néhány évtizedben szinte példátlanul gyorsan fejlődött. Ez részben az extremális kombinatorika az additív számelméletben, az információelméletben és a számítógéptudományban való látványos alkalmazásainak köszönhető. Az extremális és véletlen kombinatorika aszimptotikus eredményei rendkívül hatékony eszközöknek bizonyultak nagy hálózatok, például az internet-gráf, agytérképek, szociális hálózatok és integrált áramkörök strukturális és algoritmikus vizsgálatánál. A modern kombinatorika számos fontos kérdésének megválaszolására ma már mély algebrai, topológiai és valószínűségi módszerek állnak rendelkezésre, de sok alapvető probléma máig teljesen nyitott. Ezek közül vizsgálunk néhányat, így a klasszikus Schur-Erdős-problémát, a Ramsey-problémát, az Erdős-Hajnal-sejtést, a Zarankiewicz-problémát, a Danzer-Rogers-problémát és a Karzanov-Lomonoszov-sejtést.

Egy régi pszichológiai elmélet, a híres statisztikusig, Galtonig visszavezethető “nagy öt modell” szerint egy ember személyisége meglepően pontosan leírható mindössze öt tényező segítségével. Bizonyára sok a kivétel, sok ember nem “5-dimenziós”, de számos lélektani és szociális jelenség megmagyarázható ezzel a modellel. Ehhez hasonló módon kívánjuk megközelíteni a kombinatorika néhány fontos megoldatlan problémáját. Olyan gráfok és hipergráfok vizsgálatára szorítkozunk, melyek bizonyos értelemben korlátos dimenziósak: (1) korlátos bonyolultságú szemialgebrai hiprgráfok, vagy (2) Vapnyik-Cservonyenkisz dimenziójuk kicsi; vagy (3) leírhatóak korlátos számú lineáris rendezés segítségével, vagyis a nekik megfelelő részben rendezett halmazok Dushnik-Miller dimenziója korlátos. Hozzá szeretnénk járulni a szemialgebrai kombinatorika megalapozásához. Egy speciális kontextusban kiterjesztjük a valószínűségi módszert, és kezdeményezzük a rendezett gráfok illetve a topológiai gráfok elméletének kiépítését. Eredményeinknek algoritmikus következményei is vannak.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.

A kombinatorika a matematika egyik alapvető ága, amely az elmúlt néhány évtizedben szinte példátlanul gyorsan fejlődött. Az extremális és véletlen kombinatorika aszimptotikus eredményei rendkívül hatékony eszközöknek bizonyultak nagy hálózatok, például az internet-gráf, agytérképek, szociális hálózatok és integrált áramkörök strukturális és algoritmikus vizsgálatánál. A modern kombinatorika számos fontos kérdésének megválaszolására ma már mély algebrai, topológiai és valószínűségi módszerek állnak rendelkezésre, de sok alapvető probléma máig teljesen nyitott.

Egy régi pszichológiai elmélet, a híres statisztikusig, Galtonig visszavezethető “nagy öt modell” szerint egy ember személyisége meglepően pontosan leírható mindössze öt tényező segítségével. Bizonyára sok a kivétel, sok ember nem “5-dimenziós”, de számos lélektani és szociális jelenség megmagyarázható ezzel a modellel. Ehhez hasonló módon kívánjuk megközelíteni a kombinatorika néhány fontos megoldatlan problémáját. Olyan gráfok és hipergráfok vizsgálatára szorítkozunk, melyek bizonyos jól definiált értelemben korlátos dimenziósak. Ez lehetővé teszi hatékony geometriai és alacsony dimenziós topológiai módszerek és a részben rendezett halmazok elméletének használatát. Ezzel a megközelítéssel vagy ellenpéldát találunk Hozzá szeretnénk járulni a szemialgebrai kombinatorika megalapozásához. Egy speciális kontextusban kiterjesztjük a valószínűségi módszert, és kezdeményezzük a rendezett gráfok illetve a topológiai gráfok elméletének kiépítését. Eredményeinknek algoritmikus következményei is vannak.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

The main goal of the proposed work is to attack some hard combinatorial 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 Vapnik-Chervonenkis (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 hypergraphs 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.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

Several fundamental results in extremal graph and hypergraph theory were motivated by their prospective geometric applications. For example, the Erdős-Szekeres Happy Ending Problem about convex polygons has inspired Ramsey theory, and, in a roundabout way, also led to the discovery of Turán’s theorem. Erdős’s famous number-theoretic questions and his celebrated conjectures about the distribution of distances among n points have served as a driving force behind a lot of research in structural graph theory, culminating in Szemerédi’s regularity theory. Although many of these theories and techniques were developed to deal with geometric questions, their direct applications to the original problems rarely yield optimal results.

What is behind this paradoxical phenomenon? Our results during the past ten years suggest that the combinatorial structures (graphs and hypergraphs) associated with the underlying geometric arrangements are frequently low dimensional in some well-defined sense: for example, their “description complexity,” their Vapnik-Chervonenkis dimension or Dushnik-Miller dimension is small. In this proposal, we explore the special geometric, topological, and statistical properties of these arrangements to make progress on the original combinatorial problems.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

Combinatorics is a fundamental mathematical discipline whose study has experienced unprecedented growth during the past few decades. Its rapid development can be partially explained by spectacular applications of extremal combinatorics in additive number theory, information theory, theoretical computer science, and elsewhere. Asymptotic results in extremal and probabilistic combinatorics have proved to be powerful tools in the structural and algorithmic analysis of huge networks such as the internet graph, brain maps, social networks, and integrated circuits. We have deep, well developed algebraic, topological, and probabilistic techniques to tackle some important questions in modern combinatorics, but many basic problems remained open. We plan to approach some of them, including the classical Schur-Erdős problem, Ramsey problem, the Erdős-Hajnal conjecture, the Zarankiewicz problem, the Danzer-Rogers problem, and the Karzanov-Lomonosov conjecture.

According to an old psychological theory, the Big Five Model, which goes back to the statistician, Galton, human personality can be described with a remarkable precision by 5 factors. Surely, there will be a lot of outliers, a lot of people who are not “5-dimensional”, but a number of behavioral and social phenomena can be reasonably well explained using this model. We propose a similar approach to some notoriously difficult unsolved problems in combinatorics.. We restrict our attention to graphs or hypergraphs that are in some well-defined sense bounded-dimensional: They are (1) semi-algebraic with bounded complexity; they have bounded (2) Vapnik-Chervonenkis dimension; or they can be described using a bounded number of linear orders, that is, the (3) Dushnik-Miller dimension of the associated partially ordered set is bounded by a constant. In the process, we plan to build a new semi-algebraic combinatorial theory, we plan to stretch the limits of the probabilistic method in a special setting, and attempt to lay the foundations of the extremal theories of ordered graphs and topological graphs. Our results also have algorithmic consequences.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.

Combinatorics is a fundamental mathematical discipline whose study has experienced unprecedented growth during the past few decades. Asymptotic results in extremal and probabilistic combinatorics have proved to be powerful tools in the structural and algorithmic analysis of huge networks such as the internet graph, brain maps, social networks, and integrated circuits. We have deep, well developed algebraic, topological, and probabilistic techniques to tackle some important questions in modern combinatorics, but many basic problems remained open.

According to an old psychological theory, the Big Five Model, which goes back to the statistician, Galton, human personality can be described with a remarkable precision by 5 factors. Surely, there will be a lot of outliers, many people who are not “5-dimensional”, but a number of behavioral and social phenomena can be reasonably well explained using this model. We propose a similar approach to some notoriously difficult famous conjectures in combinatorics. We restrict our attention to graphs or hypergraphs that are in some well-defined sense bounded-dimensional. This will allow us to use a variety of techniques from geometry, low dimensional topology, and the theory of partially ordered sets. The effort is likely to lead either to the discovery of counterexamples to these conjectures, or to provide valuable evidence supporting their validity. The first option would represent a major breakthrough, while in the second case we would gain important structural information about geometric arrangements.





 

Final report

 
Results in Hungarian
Egy Schur típusú korlátot bizonyítunk Ramsey számokra, ha minden színosztály szemi-algebrailag definiált korlátos komplexitással. Nandakumar egy egyenlőszárú háromszögekre vonatkozó sejtését bizonyítjuk. Megjavítjuk a metszés-kritikus gráfok metszési számára vonatkozó felső korlátot. Megmutatjuk, hogy egy üreg konvex burkának lezártja d dimenzióban egy d-szimplex. A híres Metszési Lemma-t általánosítjuk multigráfokra. Kuzmin és Warmuth tömörítési sémákra vonatkozó sejtésére adunk ellenpéldát. Megkezdjük a Turán típusú extremális elmélet kidolgozását él-rendezett gráfokra. Kidolgozunk egy elméletet véges fák konvergenciájára és határértékére. Megmutatjuk, hogy a téglatesteknek van Rupert átjárója minden olyan irányban ami nem párhuzamos egy lappal. Megmutatjuk, hogy véges sok körnek a gömbfelületen vagy a hiperbolikus síkban van poligonális parkettázása melyre minden oldal pontosan egy kört tartalmaz. Közel kerültünk az Erdős-Rado r-napraforgó sejtés bizonyításához korlátos VC-dimenziójú családok esetén. Sikerült definíciót adni a konkáv függvények John-függvényére. Ezt alkalmazva belátunk egy log-konkáv függvények családjának pontonkénti minimumáról szóló tételt. Elemi eszközökkel belátunk egy kvantitatív Helly-típusú tételt, melyből sok hasonló tétel következik. Egy racionális politópok fedési sugarának meghatározására szolgáló algoritmust alkalmazva a "Magányos Futó Sejtés" egy változatának egy nyitott esetét sikerült belátni.
Results in English
We prove a Schur type bound on the Ramsey number if each color class is defined semi-algebraically with bounded complexity. We prove a conjecture of Nandakumar regarding isosceles triangles. We improve the crossing number bound of crossing-critical graphs. We prove the closure of the convex hull of a hollow in d dimension is a d-simplex. We prove multigraph versions of the famous Crossing Lemma. We give a counterexample to a conjecture of Kuzmin and Warmuth regarding compression schemes. We start to build the Turán type extremal theory of edge-ordered graphs. We develop a theory for the convergence and limits of finite trees. We show rectangular boxes have Rupert's passages in every direction non-parallel to the faces. We prove finitely many circles on the sphere or in the hyperbolic plane admit a polygonal tiling such that each face contains exactly one circle. We come close to proving the Erdős-Rado r-sunflower conjecture for families of bounded VC dimension. We give a definition of the John ellipsoid of logarithmically concave functions. As an application, we show a bound on the integral of of the pointwise minimum of log-concave functions. We study a quantitative Helly type question, and obtain a general bound from which answers follow to several similar problems. We apply an algorithm determining the covering radius of rational polytopes to solve the first open case of a variant of the Lonely Runner Conjecture.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=133864
Decision
Yes





 

List of publications

 
Balázs Csikós, Amr Elnashar, Márton Horváth: D'Atri spaces and the total scalar curvature of hemispheres, tubes and cylinders, https://arxiv.org/abs/2110.03678, 2021
Jenő Lehel, Géza Tóth: On the hollow enclosed by convex sets, Geombinatorics, 2021
Michael Kaufmann, Janos Pach, Geza Toth, Torsten Ueckerdt: The number of crossings in multigraphs with no empty lens, Journal of Graph Algorithms and Applications, vol. 25, no. 1, pp. 383–396., 2021
János Pach, Gábor Tardos, Géza Tóth: Crossings Between Non-homotopic Edges, n book: Graph Drawing and Network Visualization, 28th International Symposium, GD 2020, Vancouver, BC, Canada, September 16–18, 2020, Revised Selected Papers (pp.359-371), 2020
János Barát, Géza Tóth: Improvement on the Crossing Number of Crossing-Critical Graphs, Discrete & Computational Geometry, 2020
Attila Sali, Gábor Simonyi, Gábor Tardos: Partitioning Transitive Tournaments into Isomorphic Digraphs, Order 38 (2), 211-228., 2021
Dömötör Pálvölgyi, Gábor Tardos: Unlabeled compression schemes exceeding the VC-dimension, Discrete Applied Mathematics, 276, 102–107., 2020
DÁNIEL GERBNER, ABHISHEK METHUKU, DÁNIEL T. NAGY, DÖMÖTÖR PÁLVÖLGYI, GÁBOR TARDOS, AND MÁTÉ VIZER: TURÁN PROBLEMS FOR EDGE-ORDERED GRAPHS, arxiv, 2021
Grigory Ivanov, Márton Naszódi: Functional John Ellipsoids, arxiv, 2020
Grigory Ivanov, Márton Naszódi: A Quantitative Helly-type Theorem: Containment in a Homothet, arxiv, 2021
Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi, Matthias Schymura: Computing the covering radius of a polytope with an application to lonely runners, arxiv, 2021
Márton Naszódi, Moritz Venzin: Covering convex bodies and the Closest Vector Problem, arxiv, 2021
Jacob Fox, János Pach, and Andrew Suk: On the number of edges of separated multigraphs, arxiv, 2021
Jacob Fox, János Pach, and Andrew Suk: Sunflowers in set systems of bounded dimension, arxiv, 2021
Péter Frankl, János Pach: Shattered matchings in intersecting hypergraphs, arxiv, 2020
GERGELY KISS, JÁNOS PACH, AND GÁBOR SOMLAi: MINIMUM AREA ISOSCELES CONTAINERS, Journal of Information Processing Vol.28 759–765, 2020
Dániel Korándi, János Pach, István Tomon: Large homogeneous submatrices, SIAM J. Discrete Mathematics, 2020
Andreas F. Holmsen, Hossein Nassajian Mojarrad János Pach, Gábor Tardos: Two extensions of the Erdős–Szekeres problem, arxiv, 2020
János Pach , Gábor Tardos and Géza Tóth: Disjointness graphs of segments in the space, Combinatorics, Probability and Computing Volume 30 , Issue 4 , July 2021 , pp. 498 - 512, 2020
Gábor Elek, Gábor Tardos: Convergence and limits of finite trees, Combinatorica to appear, 2021
Jacob Fox, János Pach, and Andrew Suk: The Schur-Erdős problem for semi-algebraic colorings, Israel Journal of Mathematics volume 239, pages 39–57., 2020
A. Bezdek, Z. Guan, M. Hujter and A. Joos: Cubes and Boxes Have Rupert's Passages in Every Nontrivial Direction, Amer. Math. Monthly 128(6): 534-542, 2021
A. Bezdek: Separating circles on the sphere by polygonal tilling, Beiträge zur Algebra und Geometrie / Contributions to Algebra and Geometry, 2021





 

Events of the project

 
2020-09-28 13:58:14
Résztvevők változása




Back »