Pakolási és extremális problémák  részletek

súgó  nyomtatás 
vissza »

 

Projekt adatai

 
azonosító
129597
típus KH
Vezető kutató Csaba Béla
magyar cím Pakolási és extremális problémák
Angol cím Packing and extremal problems
magyar kulcsszavak pakolás, beágyazás, regularitás, kombinatorikus diszkrepancia, Ramsey-elmélet
angol kulcsszavak packing, embedding, regularity, combinatorial discrepancy, Ramsey-theory
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Kombinatorika
zsűri Matematika–Számítástudomány
Kutatóhely Bolyai Intézet (Szegedi Tudományegyetem)
résztvevők Hajnal Péter
Nagy V. Gábor
Nagy-György Judit
Pluhár András Sándor
projekt kezdete 2018-09-01
projekt vége 2021-08-31
aktuális összeg (MFt) 7.746
FTE (kutatóév egyenérték) 5.10
á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 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.
angol összefoglaló
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.





 

Zárójelentés

 
kutatási eredmények (magyarul)
A projekt fő témakörei a következők voltak: (1) Fapakolási problémák vizsgálata Regularitási lemma nélkül, nemcsak korlátos fokú fákra. (2) Véletlen perturbációk és gráfbeágyazások Regularitási lemma nélkül. (3) Beágyazási és pakolási kérdések n pontú r-reguláris gráfokra, ahol r=o(n). (4) Gráfdiszkrepanciák vizsgálata. Az (1)-es kérdésben sikerült előrelépni: tetszőleges n pontú G gráf élhalmazának túlnyomó részét, ha annak a sűrűsége legalább c loglog n/(log n)^(1/2) egy c>0 konstansra, fel lehet bontani éldiszjunkt, akár lineáris fokú és akár lineáris méretű fákra. Ez egy véletlen polinom időben lefutó algoritmussal is megtehető, ha a sűrűség az előzőnél nagyobb, de még mindig c loglog n/(log n)^k egy pozitív k egészre. A (2)-es kérdésben előkészületben van dolgozat. Az (1)-es kérdéshez kapcsolódó módszerek itt is működnek, időhiányban a dolgozatot még nem sikerült befejezni. A (3)-as problémakörben sikerült NP-nehéz gráfelméleti optimalizálási feladatokra véletlen polinomiális idejű approximációs algoritmusokat találni, ha r>= cn loglog n/(log n)^(1/k). A (4)-es gráfdiszkrepancia problémáiról két dolgozat is született. Az egyikben többek között feszítőfákhoz és Hamilton-körökhöz tartozó halmazrendszerek diszkrepanciáját határoztuk meg sűrű gráfokban és síkgráfokban. A másikban klikk-faktorokat vizsgáltunk. A fenti fő kutatási irányokon szigorúan véve kívül eső, de azért azokhoz kapcsolódó eredmények is születtek kombinatorikai, számítástudományi kérdésekben.
kutatási eredmények (angolul)
The main research questions of the project were as follows: (1) Packing of trees without the Regularity lemma. (2) Random perturbation of graphs and embedding problems. (3) Embedding and packing problems for r-regular graphs with vanishing density. (4) Investigations in the discrepancy of graphs. Concerning question (1) we proved that if G is a graph on n vertices with density at least c loglog n/(log n)^(1/2) for some c>0 constant, then its edge set can be almost decomposed into the edge-disjoint union of trees which may have linear size and linear maximum degree. One can find such an almost decomposition by a randomized polynomial time algorithm, but then the density have to be somewhat larger. There is a paper in preparation for question (2), the methods of (1) work in this case as well. We managed to find randomized polinomial time algorithms for some NP-hard problems regarding the r-regular graphs of question (3), where r>= cn loglog n/(log n)^(1/k). We published two papers in graph discrepancy for question (4). In one we considered the discrepancy of set systems determined by spanning trees or Hamilton cycles in dense graphs and planar graphs, in the other one we considered clique factors. Apart from the main research questions of the project we worked on other problems in combinatorics and computer science.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=129597
döntés eredménye
igen





 

Közleményjegyzék

 
Béla Csaba: A new graph decomposition method for bipartite graphs, MATCOS 19, 2019
Péter Hajnal, Simao Herdade, Endre Szemerédi: Proof of the Pósa-Seymour Conjecture, in preparation, 2021
József Balogh, Béla Csaba, Yifan Jing, András Pluhár: ON THE DISCREPANCIES OF GRAPHS, Electronic Journal of Combinatorics, 27 (2020) P2.12., 2020
Péter Hajnal, György Turán, Zhihao Liu: Nearest neighbor representations of Boolean functions, Information and Computation, to appear, 2021
Gábor V. Nagy, Beáta Bényi: Lonesum and Γ-free 0-1 fillings of Ferrers shapes, EUROPEAN J. OF COMBINATORICS 89 (2020) DOI: https://doi.org/10.1016/j.ejc.2020.103180, 2020
Gábor V. Nagy, Horst Alzer: SOME IDENTITIES INVOLVING CENTRAL BINOMIAL COEFFICIENTS AND CATALAN NUMBERS, INTEGERS 20, Paper #A59. (2020), 2020
Béla Csaba, András Pluhár, József Balogh, Andrew Treglown: A DISCREPANCY VERSION OF THE HAJNAL–SZEMEREDI THEOREM, COMBINATORICS, PROBABILITY & COMPUTING, 30 (2021) 444-459, 2021
Béla Csaba: Bundle decomposition of graphs with applications, submitted for publication, 2021
Béla Csaba: Regular decomposition of the edge set of graphs with applications, submitted for publication, 2021
Debarun Ghosh, Ervin Győri, Addisu Paulos, Chuanqi Xiao, Oscar Zamora, Judit Nagy-György: Book free 3-Uniform Hypergraphs, arxiv.org, 2021
Péter Hajnal, György Turán, Zhihao Liu: Nearest neighbor representations of Boolean functions, https://arxiv.org/abs/2004.01741, 2020
Gábor V. Nagy, Beáta Bényi: Lonesum and Γ-free 0-1 fillings of Ferrers shapes, https://doi.org/10.1016/j.ejc.2020.103180, 2020
Gábor V. Nagy, Horst Alzer: SOME IDENTITIES INVOLVING CENTRAL BINOMIAL COEFFICIENTS AND CATALAN NUMBERS, http://math.colgate.edu/~integers/u59/u59.pdf, 2020
Béla Csaba, András Pluhár, József Balogh, Andrew Treglown: A DISCREPANCY VERSION OF THE HAJNAL–SZEMEREDI THEOREM, https://arxiv.org/abs/2002.12594, 2020
Béla Csaba: Bundle decomposition of graphs with applications, --, 2020
Béla Csaba, Judit Nagy-György: Embedding graphs having Ore-degree at most five, SIAM JOURNAL ON DISCRETE MATHEMATICS 33: (1) pp. 474-508., 2019
Béla Csaba, Bálint Vásárhelyi: On embedding degree sequences, Informatica (43) pp. 23-31., 2019
Béla Csaba, Bálint Vásárhelyi: On the relation of separability, bandwidth and embedding, Graphs and Combinatorics, 2019
Béla Csaba: A new graph decomposition method for bipartite graphs, MATCOS 19, 2019
Péter Hajnal, Endre Szemerédi: Two geometrical applications of the semi-random method, New trends in intuitive geometry, 189–199, Bolyai Soc. Math. Stud., 2018
Péter Hajnal, Zhihao Liu and György Turán: Nearest neighbor representations of Boolean functions, ITCS20 (submitted for publication), 2020
Péter Hajnal, Simao Herdade, Endre Szemerédi: Proof of the Pósa-Seymour Conjecture, (submitted for publication), 2019
József Balogh, Béla Csaba, Yifan Jing, András Pluhár: ON THE DISCREPANCIES OF GRAPHS, Electronic Journal of Combinatorics (accepted for publication), 2019




vissza »