 |
Ezen az oldalon az NKFI Elektronikus Pályázatkezelő Rendszerében nyilvánosságra hozott projektjeit tekintheti meg.
vissza »
|
 |
Projekt adatai |
|
|
| azonosító |
133864 |
| típus |
KKP |
| Vezető kutató |
Pach János |
| magyar cím |
Alacsony dimenziós kombinatorika |
| Angol cím |
Low Dimensional Combinatorics |
| magyar kulcsszavak |
Szemialgebrai halmaz, VC-dimenzió, topológiai gráfok, 0-1 mátrixok, extremális hipergráf-elmélet, metszetgráfok, |
| angol kulcsszavak |
Semi-algebraic set, VC dimension, topological graphs, 0-1 matrices, extremal hypergraph theory, intersection graphs, string graphs |
| megadott besorolás |
| Matematika (Műszaki és Természettudományok Kollégiuma) | 100 % | | Ortelius tudományág: Kombinatorika |
|
| zsűri |
'Élvonal' Kutatói Kiválósági Program |
| Kutatóhely |
HUN-REN Rényi Alfréd Matematikai Kutatóintézet |
| résztvevők |
Bezdek András
Horváth Márton
Naszódi Márton
Tardos Gábor
Tóth Géza
|
| projekt kezdete |
2020-04-01 |
| projekt vége |
2021-02-28 |
| aktuális összeg (MFt) |
58.056 |
| FTE (kutatóév egyenérték) |
3.92 |
| állapot |
lezárult projekt |
magyar összefoglaló 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.
| angol összefoglaló 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.
|
|
|
|
|
|
|
|
|
|
