 |
Here you can view and search the projects funded by NKFI since 2004
Back »
|
 |
Details of project |
|
|
| Identifier |
129597 |
| Type |
KH |
| Principal investigator |
Csaba, Béla |
| Title in Hungarian |
Pakolási és extremális problémák |
| Title in English |
Packing and extremal problems |
| Keywords in Hungarian |
pakolás, beágyazás, regularitás, kombinatorikus diszkrepancia, Ramsey-elmélet |
| Keywords in English |
packing, embedding, regularity, combinatorial discrepancy, Ramsey-theory |
| Discipline |
| Mathematics (Council of Physical Sciences) | 100 % | | Ortelius classification: Combinatorial analysis |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Bolyai Institute (University of Szeged) |
| Participants |
Hajnal, Péter
Nagy V., Gábor
Nagy-György, Judit
Pluhár, András Sándor
|
| Starting date |
2018-09-01 |
| Closing date |
2021-08-31 |
| Funding (in million HUF) |
7.746 |
| FTE (full time equivalent) |
5.10 |
| 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 pályázat alapjául szolgáló közlemény:
Csaba, Kühn, Lo, Osthus, Treglown: Proof of the 1-Factorization and Hamilton Decomposition Conjectures. Az egyik fő eredménye, hogy ha egy n pontú G gráf r-reguláris, ahol r legalább n/2, akkor G élhalmaza felbomlik Hamilton-körök és
(r paritásától függően) egy teljes párosítás diszjunkt uniójára. Ez egy extremális gráfelméleti, azon belül is pakolási tétel, és egyben optimális élszínezést is ad a fenti r-reguláris gráfokra.
A projekt egyik fő célja, hogy fenti típusú eredményeket bizonyítsunk ritka G gráfokra. Ha r<n/2, akár r=o(n), akkor nemhogy nem remélhetünk Hamilton-kört, még lineáris hosszú kört sem G-ben. Többek között meg akarjuk határozni, mennyire lehet lecsökkenteni az r fokszámot úgy, hogy még kellően "érdekes" részgráfokat, pl. nagy fákat, tudjunk pakolni, azaz éldiszjunkt példányokkal lefedni G élhalmazát, esetleg kis hibával.
Kicsi, de lineáris minimális fokú gráfok kis véletlen perturbációval (azaz kevés hozzáadott véletlen éllel) már nagy valószínűséggel tartalmaznak Hamilton-kört. Célunk, hogy belássuk, a kicsi lineáris minimális fok helyettesíthető szublineáris minimális fokkal egyes nemtriviális esetekben is.
A vizsgálni kívánt kombinatorikus diszkrepancia kérdésben adva van egy G gráf, ennek élhalmaza egy H hipergráf ponthalmaza. H élhalmazát G-nek valamely természetes módon megadott részgráfcsaládja definiálja, például G feszítőfái.
A kérdés, hogy egy élszínezésre nézve mekkora diszkrepanciát kaphatunk.
A kutatni kívánt problémák megoldása várhatóan igényli a kombinatorika széles eszköztárát, így kiválóan alkalmas doktori képzésben is.
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.
Milyen feltételek mellett lehet beágyazási/pakolási tételeket bizonyítani? Mennyire szükségesek a sűrűségi feltételek? Ki
lehet-e küszöbölni a Regularitási lemma használatát legalább egyes problémákban? Számos eredmény született az utóbbi időben, melyekben sűrű gráfok helyett egy véletlen vagy kvázi-véletlen gráfcsalád relatíve sűrű részgráfjait vizsgálták. A kutatási tervünkben javasolt pakolási és beágyazási problémáknál tetszőleges r-reguláris vagy közel r-reguláris gráfokkal kívánunk foglalkozni, ahol r nagysága miatt a gráf nem sűrű.
Egy másik vizsgálni kívánt kérdéskör a kombinatorikus diszkrepancia. Ezen belül olyan hipergráfokat tekintünk, melyek ponthalmaza egy gráf éleinek halmaza, és az élhalmaza valamely részgráf osztály élhalmaza (pl. feszítő fák, Hamilton-utak, stb.) A mi tervezett vizsgálatainkban többek között a gráfok diszkrepanciájának és a Ramsey-elméletnek a kapcsolatait kívánjuk felderíteni.
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 kutatás több ponton érintkezik alkalmazásokkal. Nem fő célunk az alkalmazásokkal való közvetlen kapcsolat,
de a tapasztalat azt mutatja, hogy az alapkutatások gyakran utat mutatnak a leendő alkalmazásoknak.
Mivel a gyakorlatban előforduló méretű, azaz viszonylag kisebb, illetve ritka gráfok vizsgálata mind elméleti, mind
gyakorlati jelentőséggel bír, és az ilyen problémákra kapott eredményekből egyelőre kevés van, ha sikerrel járunk, azzal sokat előrelépne ez a részterület.
A pályázat korábbi OTKA pályázatok folytatása. Ezek során fiatalokat tudtunk elindítani a kombinatorika kutatásában. Többen már PhD-t szereztek Szegeden és továbbiak szegedi tanulmányaik folytatásában szereztek doktori fokozatot a világ különböző egyetemein. Jelen pályázat segítségével szeretnénk ezt a csoportot együtt tartani és lehetőséget kapni utazásokra, hogy eredményeinket ismertessük, illetve vendégek fogadására a szemináriumunkon (http://www.math.u-szeged.hu/seminars/kombszem.htm). Csoportunk színvonalas kutatást végez és a szegedi diákok közt népszerűsíti a kombinatorikát. Ez a feladat társadalmi érdeket szolgál.
Az eddig gyakran "szétszóródott" csoport ezen projekt keretében az eddigieknél is hatékonyabban tudna dolgozni. Szeged regionális központ, szeretnénk összefogni a régió kombinatorikusait. 2014-ben szerveztük meg először a Szeged-Novi Sad combinatorial workshopot. Ezt a találkozót a jövőben is folytatni kívánjuk. Jelen pályázat költségvetését ez nem terheli, de szakmai munkája kapcsolódik a projekthez.
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 struktúrák nem folytonos változatait vizsgálja. A számítógépek elterjedésével a kombinatorikus gondolkodás fontossá vált, a kombinatorika a matematika oktatás mellett a számítástudomány egy alapkurzusa. Mivel a kombinatorika a matematika egyik legfiatalabb ága, fogalmainak és technikáinak kidolgozása folyamatban van. A friss módszerek alkalmazhatósága, viszonya a korábbi módszerekhez sok problémát rejt. A problémák gyakran új bizonyítási technikák kifejlesztését kívánják. Első pillantásra talán meglepő a valószínűségszámítás (a folytonos matematika egy szintén fiatal ága) és a kombinatorika szoros kapcsolata. Ezen kapcsolat megértése és így elmélyítése a pályázat egyik fő célja. A projekt keretében erősítjük a regionális, határokon áthúzódó kapcsolatokat is.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The project is based upon the following paper:
Csaba, Kühn, Lo, Osthus, Treglown: Proof of the 1-Factorization and Hamilton Decomposition Conjectures. One of its main results is that if a graph G on n vertices is r-regular such that r is at least n/2, then the edges set of G decomposes into the edge-disjoint union of Hamilton cycles and possibly (depending on the parity of r) a perfect matching. This theorem is part of extremal graph theory, in particular packing, and also gives optimal edge coloring of such graphs.
One of the main goals of the project is to prove analogous theorems for sparse graphs. If r<n/2, especially when r=o(n), one cannot hope to have a Hamilton cycle in G, not even a linearly long cycle. Among others we want to determine,
at least approximately, the smallest value of r that still enables to pack "interesting" subgraphs into G, for example large trees.
If a graph has relatively small, but linear minimum degree then adding some random edges to it results in a Hamiltonian graph. We want to prove that linearly small minimum degree can be replaced by sublinear minimum degree in nontrivial cases.
In the proposed problem in combinatorial discrepancy we are given a graph G. Its edge set is the vertex set of a hypergraph H. The edge set of H is determined by some class of subgraphs of G, for example, the spanning trees of G. The question is how large the discrepancy is with respect to edge coloring of G.
We expect that the proposed questions require the application of a large set of combinatorial tools and as such suits well for the education of doctoral students.
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.
What kind of properties guarantee embedding/packing theorems? How important is the density of the host graph?
When can one avoid the use of the Regularity lemma in packing/embedding questions? In several recent results the density requirement of the host graph is relaxed so that the host graph is a dense subgraph of some random or quasi-random graph.
Instead we propose to investigate problems in which that host graph is r-regular (or close to being r-regular) for some r that could be very small so that the host graph is sparse.
Another area we plan to investigate is combinatorial discrepancy theory. Specifically, we want to consider hypergraphs in which the vertex set is the edge set of some underlying graph, and the edges of the hypergraph are the edge sets of
certain classes of subgraphs (e.g., spanning trees, Hamiltonian paths, etc.). Such problems could be related to Ramsey theory, and also to classical discrepancy theory. We want to explore these relations.
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.
Our detailed research plan contains several questions that are closely related to applications, for example, some of the problems are connected to the mathematics of internet. In spite of these our project is a theoretical research. We do not expect immediate usage of it in our every day life, however, discovering packing or embedding results for relativel sparse or small graphs could lead to applications.
Also the present project is the continuation of previous OTKA grants of the same group. Now four of us obtained PhD in Szeged and others at several places in the world. With the help of proposed project we would like to keep together the group, travel to conferences and to workshops and invite researchers to our seminars (http://www.u-szeged.hu/~hajnal/seminars/kombszem.htm).
The project could help us keeping our research at a high level. This way we can attract a lot of students in Szeged for combinatorics. Many of us started this path and got internationally acknowledged results. This a very useful job from the point of society.
We also mention that in 2014 we organized the Szeged-Novi Sad combinatorial workshop. We plan to further develop cooperation between Szeged and Novi Sad (Serbia). This does not require budget allocation from the proposed project budget, but such a cooperation is closely related to our research plans.
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 the study of discrete structures (opposed to continuous structures). It is a very young discipline, computer science has brought it into the center of mathematics. By now combinatorics has become an important part of mathematics and computer science education. Its techniques, notions are being shaped right now. To understand the hidden connections and develope new ideas is an important field of research. First time it is suprising that probability (an also young topic in continuous mathematics) has strong connections to combinatorics. One of our main goals is to establish new connections between the two topics and provide a better understanding of both fields. The project will also help to converge the region's research in combinatorics.
|
|
|
|
|
|
|
|
|
|
