 |
Local properties and colorings: from graphs to measure spaces
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
109731 |
| Type |
PD |
| Principal investigator |
Kun, Gábor |
| Title in Hungarian |
Lokális tulajdonságok és színezések: gráfoktól a mértékterekig |
| Title in English |
Local properties and colorings: from graphs to measure spaces |
| Keywords in Hungarian |
gráf, Lovász Local Lemma, derékbőség, von Neumann probléma, kromatikus szám |
| Keywords in English |
graph, Lovasz Local Lemma, girth, von Neumann problem, chromatic number |
| Discipline |
| Mathematics (Council of Physical Sciences) | 100 % | | Ortelius classification: Combinatorial analysis |
|
| Panel |
Natural Sciences Committee Chairs |
| Department or equivalent |
Alfréd Rényi Institute of Mathematics |
| Starting date |
2013-09-01 |
| Closing date |
2014-02-28 |
| Funding (in million HUF) |
6.505 |
| FTE (full time equivalent) |
0.40 |
| 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 lokális statisztikák vizsgálata és a tulajdonság-tesztelés az elmúlt
évtizedekben számos területen kulcsszerepet játszott: a legsikeresebb történet
a számelmélet, ergodelmélet és diszkrét matematika kölcsönös megtermékenyítése volt
Szemerédi tételével kapcsolatban. A ritka struktúrák egyaránt fontos szerepet játszanak a
valószínűség-számításban, diszkrét matematikában, csoportelméletben és számítástudományban.
A pályázat a gráflimeszek és a tulajdonságtesztelés elméletének legújabb eredményeire épít.
A pályázat három általános célja diszkrét tételek átvitele mérhető esetre,
tetszőleges gráfok (és graphingok) approximálása végesekkel, és kombinatorikus
módszerek alkalmazása nem diszkrét kérdésekre. A pályázat fő kérdései a következők:
(1) A Neumann probléma dinamikai változata
Bizonyítandó, hogy egy nem amenábilis csoport minden mértéktartó, majdnem szabad
hatásának van egy olyan Borel részrelációja, amit egy majdnem szabad F2-hatás indukál!
(2) Mérhető Lovász Local Lemma
A cél a Lovász Local Lemma egy olyan mérhető változata, ami a lemma feltételeinek
teljesülése és mértéktartó constraintek esetén egy mérhető kiértékelést (színezést)
garantál.
(3) Az Aldous-Lyons sejtés
Approximálható-e minden graphing (pontosabban graphingok ekvivalenciaosztálya,
azaz véletlen unimoduláris hálózat) véges gráfokkal Benjamini-Schramm értelemben?
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.
(1) A Neumann probléma dinamikai változata
Bizonyítandó, hogy egy nem amenábilis csoport minden mértéktartó, majdnem szabad
hatásának van egy olyan Borel részrelációja, amit egy majdnem szabad F2-hatás indukál!
A Neumann probléma eredeti változata azt kérdezte, hogy van-e minden nem amenábilis
csoportnak nemkommutatív, szabad részcsoportja. Erre Olshanskiy mutatott ellenpéldát.
Később a következő geometriai csoportelméleti megoldást találták: egy végesen
generált csoport pontosan akkor nem amenábilis ha a Cayley gráfjának a 4-reguláris fa
Lipschitz részgráfja. Gaboriau és Lyons egy gyenge dinamikai változatot talált, belátva, hogy
minden nem amenábilis csoportnak LÉTEZIK olyan mértéktartó, majdnem szabad hatása, ami által
generált ekvivalencia-reláció egy Borel részrelációját egy mértéktartó, majdnem szabad F2-hatás generálja.
A pályázó erre egy alternatív bizonyítást adott a következő eredményét használva:
(2) Mérhető Lovász Local Lemma
A cél a Lovász Local Lemma egy olyan mérhető változata, ami a lemma feltételeinek
teljesülése és mértéktartó constraintek esetén egy mérhető kiértékelést (színezést)
garantál. A pályázó belátta ennek egy gyenge változatát. Egy erős változatból, melyben
a constraint méretek nem korlátosak, következne a Neumann probléma dinamikai változata.
(3) Az Aldous-Lyons sejtés
Approximálható-e minden graphing (pontosabban graphingok ekvivalenciaosztálya,
azaz véletlen unimoduláris hálózat) véges gráfokkal Benjamini-Schramm értelemben?
A pályázat a következő, könnyebbnek tűnő kérdést támadja előbb: van-e olyan graphing, ami
nem közelíthető véges gráfokkal Benjamini-Schramm értelemben?
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!
Az Aldous-Lyons sejtés a pályázat leghíresebb problémája: világszerte ismert a legjobb egyetemeken és matematikai kutatóintézetekben.
A pozitív (sőt a negatív) válasz is áttörő eredmény lenne. Következne belőle egy ritka regularitási lemma és az, hogy minden csoport szofikus.
Az első egy klasszikusabb probléma, ami szintén széles érdeklődésre tart számot, míg a második a gráflimeszek elméletének egy jelentős mérföldkövévé válhat.
A diszkrét matematikában Magyarország hagyományosan erős. A pályázat erősítené ezt a pozíciót, továbbá a diszkrét matematika alkalmazásaira
is kihatna, különösen valószínűség-számításban, csoportelméletben és számítástudományban. Ezek a területek egyre közelebb kerülnek egymáshoz, részterületeik várhatóan összeolvadnak a következő évtizedekben, ahogyan ez a számelmélet, ergodelmélet és diszkrét matematika
esetében is történt Szemerédi tétele kapcsán. Fontos, hogy a magyar matematikusok ebben jobban részt vegyenek.
A pályázó cikkeket fog írni a kutatásáról és konferenciákon előadni. Mindhárom problémában benne rejlik a publikálás lehetősége egy vezető folyóiratban (Annals, Inventiones, Duke...), és jelentős részeredmények már nyilvánvalóan publikálhatóak vezető kombinatorikai folyóiratokban (Combinatorica, J. Comb. Theory A, J. Comb. Theory B). A pályázó négy-öt erős cikket tervez három év alatt, ebből legalább egyet vezető folyóiratban és egyet vezető számítástudományi konferencián (STOC, FOCS, SODA). Siker esetén a pályázó letelepedne Magyarországon és önálló kutatóvá válna a vezető egyetemeken és kutatóintézetekben (pl. University of Cambridge, the Institute for Advanced Study (Princeton), Rutgers University és Courant Institute) eltöltött évek után, ami a magyar matematika egy nagy nyeresége lenne.
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 nagy hálózatok egyre nagyobb szerepet játszanak mindennapi életünkben: Az internet és a facebook mindennapi eszközeinkké váltak. A nagy hálózatok a tudományban sem kevésbé fontosak: nem csak társadalomtudományokban fordulnak elő, de neuronhálózatok vizsgálatában, a fizikában, számítástudományban és a matematikában is. Ezek a látszólag távoli területek ugyanazzal a kihívással szembesülnek: Hogyan értsünk meg egy nagy hálózatot ha csak egy kis részét látjuk? És hogyan modellezzünk egy nagy hálózatot egy hozzá hasonló kisebbel?
A pályázat ezekkel a problémákkal foglalkozik matematikai és számítástudományi eszközokkel. Fő célja a kis hálózatok vizsgálatában használt eszlözök átvitele nagy hálózatokra. A kutatás erősen multidiszciplináris természetű: elsősorban matematikai problémákat kíván megoldani számítástudományi eszközökkel.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The study of local statistics and the notion of property testing
played a central role in many fields in the last couple of decades: The
most successful story was the cross-fertilization of ideas in number theory,
ergodic theory and discrete mathematics related to Szemerédi's
theorem on arithmetic progressions. Sparse structures are similarly
intensively studied in probability theory, group theory, discrete mathematics
and computer science, too. The proposal builds on developments in the theory
of graph limits and property testing of sparse graphs and graphings.
The three general goals of this research proposal are the transfer
of discrete, combinatorial theorems to the measurable context,
the approximation of arbitrary graphs (graphings) by finite
ones, and the application of combinatorial methods to
non-discrete problems. The project concentrates on three problems
in the research frontier:
(1) The dynamical von Neumann problem
Prove that for every probability measure-preserving, almost-free action of a
non-amenable group there is a Borel subrelation induced by an almost-free F2-action!
(2) A measurable Lovász Local Lemma
The goal is to have a measurable version of the Lovász Local Lemma that allows to
have measurable evaluations when the conditions of the lemma are satisfied by
a set of measure-preserving constraints.
(3) The Aldous-Lyons conjecture
Are finite graphs dense in the space of equivalence classes of graphings
(random unimodular networks) w.r.t. the Benjamini-Schramm metric?
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.
(1) The dynamical von Neumann problem
Prove that for every probability measure-preserving, almost-free action of a non-amenable group
there is a Borel subrelation induced by an almost-free F2-action!
The von Neumann problem asked if every non-amenable group has a
non-commutative free subgroup. This was disproved by Olshanskiy in 1980.
A geometric group theoretical solution was found: a fi nitely generated
group is non-amenable iff it has a 4-regular tree as a Lipschitz subgraph. Gaboriau
and Lyons found a weaker dynamical version: they showed that the orbits of a
Bernoulli shift of a non-amenable group decompose into F2-orbits for a properly
chosen probability measure-preserving (pmp) action of the free group F2. The PI
gave an alternative proof to this introducing the following tool:
(2) A measurable Lovász Local Lemma
The goal is to have a measurable version of the Lovász Local Lemma that allows to
have measurable evaluations when the conditions of the lemma are satisfied by
a set of measure-preserving constraints. The PI already gave a weaker version of
this Lemma. A stronger version (with unbounded constraint size) would solve the
dynamical von Neumann problem in positive.
(3) The Aldous-Lyons conjecture
Are finite graphs dense in the space of graphings (random unimodular network)
w.r.t. the Benjamini.Schramm metric?
This is a key problem in many fields: it would imply that every group is sofic and give
a kind of regularity lemma for sparse graphs. It seems too strong to be true.
We address the following easier goal: fi nd a graphing that can not be
approximated in the colored neighborhood metric by fi nite graphs!
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.
The Aldous-Lyons conjecture is clearly the most widely known among the problems of this proposal: it is known at top universities and research institutes over the world. The positive (even the negative) answer to it would be a groundbreaking result. It would give a regularity lemma for sparse graphs and imply that every group is sofic: this would settle quite a few conjectures in group theory at once. The first problem is more classical attracting a wide interest, too, while the second one has the potential to be an important milestone in the theory of graph limits.
Discrete mathematics is a traditionally strong side of Hungarian mathematics. This proposal will strengthen the discrete mathematics school in Hungary and its applications to other fields, especially probability theory, computer science and group theory. These fields seem to move very close
to each other, almost merging in the next decades, like it happened in the successful story via the cross-fertilization of ideas in number theory,
ergodic theory and discrete mathematics related to Szemerédi's theorem on arithmetic progressions. It would be important to take a bigger share of Hungarian mathematics in this story.
The PI will write papers about this research and participate in conferences. All of these three problems have the potential to lead to publications in leading journals in case of success (Annals, Inventiones, Duke...), and significant partial results are definitely welcome to be published in leading combinatorial journals (Combinatorica, J. Comb. Theory A, J. Comb. Theory B). I expect four-five strong papers in the three years of the project,
at least one in leading journals and one in leading conferences in computer science (STOC, FOCS, SODA) and the rest in leading combinatorial journals. This grant would help the PI to settle down and become an independent researcher in Hungary after six years at top universities and research centers, including the University of Cambridge, the Institute for Advanced Study (Princeton), Rutgers University and the Courant Institute: Hungarian mathematics would gain a lot from this, too.
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.
Large networks play an increasing role in everyday life: The internet and the facebook have become our everyday tools. The importance of large networks is not smaller in science either: these appear not in social sciences only, but in biology, physics, computer science and mathematics, too. These very different fields are facing the same basic challenges: How to understand a large graph (network) if we can see only very small parts of it.
And can we model a huge network by a similar, small one that we can put our hands on?!
The proposal will deal with these problems using methods from computer science and discrete mathematics. Our primary goal is to transfer methods
that work for small structures to huge ones. The research has a strong multidisciplinary aspect trying to solve classical mathematical problems using tools in computer science.
|
|
|
|
|
|
|
|
|
|
