Bacsó, Gábor Bujtás, Csilla Dósa, György Gerbner, Dániel Patkós, Balázs Vizer, Máté
Starting date
2019-01-01
Closing date
2023-07-31
Funding (in million HUF)
35.663
FTE (full time equivalent)
13.51
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. Az extremális kombinatorika a legnagyobb, legkisebb vagy egyéb módon extremális struktúrákat keresi egy adott tulajdonsággal rendelkezők közül. A legtöbb kombinatorikai probléma leírható gráfok, hipergráfok vagy halmazrendszerek segítségével.Tervezett kutatásunk során a következő problémákra kívánunk koncentrálni:
* A Turán típusú problémakör az extremális (hiper)gráfelmélet egy jelentős területe. Bár sok régi és alapvető kérdés továbbra is megoldatlan, az utóbbi időben az alapprobléma jó néhány általánosítása került bevezetésre: az élszám maximalizálása helyett vizsgálták egyes fix részgráfok számának maximalizálását (általánosított Turán-számok), az élszám maximalizásával próbálkoztak az eredeti feltételek rendezett változatában, illetve extra fokszámfeltételek mellett. A csúcsokra vonatkozó variáns is kapott némi figyelmet: mekkora U részhalmazát lehet venni egy adott G gráfnak úgy, hogy az U-n feszített részgráf rendelkezzen egy adott tulajdonsággal. Hipergráfos Turán problémákra csak elszórt, egyedi eredmények voltak eddig ismertek, az utóbbi időben előtérbe kerültek olyan kizárt hipergráfcsaládok, melyek gráfokból bizonyos operációk segítségével eredeztethetőek (extensions, expansions, inflations, suspension, Berge típusú kizárt hipergráfok).
* Sok geometriai probléma egyszerűbb változatait lehet gráfokkal modellezni, mely modellekben csúcsok közötti legrövidebb vagy más módon extremális utak kitüntetett szerepet kapnak. Tervezünk olyan extremális problémákkal foglalkozni, melyekben bizonyos tulajdonsággal rendelkező utakat kell minimális számú csúccsal lefogni, illetve bizonyos utakra nézve általános helyzetű pontok maximális számát kell meghatározni.
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. Matematikai alapkutatások esetén nehéz előre meghatározni a várható eredményeket. Ennek ellenére alább megpróbáljuk felsorolni tervezett kutatásunk azon irányait, ahol vizsgálódásaink nyomán mindenképpen előrelépésre számítunk.
* Körök számával kapcsolatos vagy más módon körökre vonatkozó Turán típusú problémák kapcsán próbálunk új korlátokat adni. Tervezzük a problémák vizsgálatát az élek cimkézése mellett is.
* A csúcsokra vonatkozó Turán típusú kérdéskört szeretnénk összekapcsolni a kizárt részposzetes problémák témájával, és az ott alkalmazott technikák alkalmazásával adni korlátokat a hiperkockában felmerülő csúcshalmazos Turán kérdésekre.
* A fokszámfeltételekkel megtoldott Turán típusú problémák kérdésköre még nagyon friss. Itt az alapkérdések aszimptotikus megválaszolása is jelentős előrelépés lehet. Tervezzük fokszámfeltételes Ramsey-típusú kérdések vizsgálatát is.
* Szintén tervezzük, hogy az útrendszerekkel kapcsolatos optimalizálás általánosított modelljében haladást érjünk el.
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! Tervezett együttműködésünk a matematikai alapkutatások közé tartozik. Turán típusú és más extremális problémák nemcsak a kombinatorikán belül bizonyultak alapvetőnek, hanem más tudományterületeken is számos alkalmazásuk lett ismert. Így például gráfok éleinek vagy részgráfjainak leszámlálása fontos szerepet játszik hálózatelméleti kutatásokban is. Más extremális kérdések különböző diszkrét optimalizálási feladatokban voltak alkalmazhatók.
Általános helyzetű csúcsok keresésének gráfokban a matemaika különböző területein vannak alkalmazásai: diszkrét geometriában és az alkalmazott matematika némely ágában például robotikában.
Ládapakolási és ütemezési problémák, illetve hálózati folyamok alkalmazásai lépten-nyomon előkerülnek a közgazdaságtantól kezdve a közlekedésen át az iparig. Ezen problémák egy közös általánosítása segíthetne abban, hogy a felmerülő problémák egy jelentős részét egy közös keretben egy közös nyelven lehessen vizsgálni.
A k-hosszú utak csúcslefogásának fogalma szorosan kapcsolódik ahhoz a gyakorlati problémához, amikor vezeték nélküli hálózatokban szeretnénk biztosítani a kommunikáció adatintegritását.
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 kombinatorikus problémák mindenhol jelen vannak életünkben. Ez az oka annak, hogy e terület tanulmányozásának történelmi gyökerei oly messzire nyúlnak vissza. A számítógépek gyors fejlődése által a kombinatorikus matematika szerepe tovább növekedett és az egyik legintenzívebben kutatott matematikai területté vált. A tendencia alapján a XXI. században az optimalizálási problémák – köztük a kombinatorikaiak – és megoldásuk fontosabb, mint valaha: egy jobb megoldás segítségével pénz, energia, idő takarítható meg, és a természeti környezet védelmét is szolgálhatja.
Amikor hálózatokat és halmazrendszereket, azon belül extremális és optimalizálási problémákat tanulmányozunk, olyan absztrakt entitásokkal foglalkozunk, amelyek sok gyakorlati probléma modelljéül szolgálhatnak. A hálózatokon belül az utak olyan egyszerű és fontos részek, amelyek biztosítják az összefüggőséget és amelyekből felépíthetők az összetettebb struktúrák. Ezáltal az utakra vonatkozó ismeretek fontos információt nyújtanak egy bonyolult hálózat egészének viselkedéséről is.
Eredményeinket vezető diszkrét matematikai szakfolyóiratokban tervezzük publikálni, és beszámolunk róluk nemzetközi tudományos konferenciákon is. Úgy reméljük, plenáris előadások tartására is meghívást fogunk kapni, ami szintén hangsúlyozza a projekt során elért eredmények fontosságát. Mindezek által tovább növekedhet mind a magyar, mind a szlovén diszkrét matematikai iskola tudományos elismertsége.
Summary
Summary of the research and its aims for experts Describe the major aims of the research for experts. Extremal combinatorics is concerned with finding the largest, smallest, or otherwise optimal combinatorial structures with a given property. Most combinatorial problems can be described by graphs, hypergraphs, set systems. Our proposed research considers extremal problems on (hyper)graphs focusing on the following topics:
* Turán-type problems form a huge area within extremal (hyper)graph theory. Although, even many of the original questions are still unsettled, there has been a recent trend of introducing these types of problems in several generalized settings: maximizing the number of subgraphs instead of the number of edges (generalized Turán numbers), maximizing the number of edges in ordered versions of the original problem, maximizing the number of edges if some additional degree condition should also be satisfied. One can also consider vertex versions and ask for the maximum number of vertices such that the (hyper)graph induced on them satisfies a given property. In the case of hypergraph Turán problems, only sporadic results are known and much attention is paid to problems when the forbidden hypergraph arises from ordinary graphs via some specified operations (extensions, expansions, inflations, suspension, Berge-type generalizations).
* Graphs can model geometric settings in a simple way. Paths possessing some extra properties can be considered as discrete analogues of some natural geometric objects. We plan to address problems of finding the minimum number of vertices hitting all paths with an extra property (e.g. shortest paths) or the maximum number of vertices that avoid certain configurations (points in general positions).
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. In mathematical research it is difficult to predict the exact type of results and whether a certain question can be answered at the end of the study. Nevertheless, we list some important directions which we will investigate.
* Concerning Turán-type questions about edges we plan to focus on cycles in different settings. We also plan to achieve results about edge-labeled graphs.
* Concerning vertex Turán questions we plan to connect this area with the forbidden subposet problem and so use techniques that were developed there.
* Concerning the Turán problems with degree restrictions we plan to investigate the very basic questions (e.g. asymptotics) of this topic. We also plan to study analogous Ramsey-type questions in detail.
* We also plan to make steps in the general model of path-system-related optimization.
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 project belongs to basic research in the area of mathematics. Turán-type and other extremal problems turned out to be fundamental not only in combinatorics, but at the same time they have applications in other scientific fields. For instance, counting edges and subgraphs plays a central role in the theory of large networks. Other extremal questions can be applied in different discrete optimization scenarios.
Finding vertices in graphs in general position has applications in other branches of combinatorics, e.g. in discrete geometry and also in applied mathematics, e.g. in robotics.
Bin packing and scheduling problems, as well as network flows have many different applications for example in economics, transportation, industry, and many other areas. To find a common generalization for them could help us to handle a wide range of problems with a common language.
The concept of k-path vertex cover is strongly motivated by the practical problem of ensuring data integrity communication in wireless sensor networks.
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. Combinatorial problems are intrinsic in our lives. This is the reason that the historical roots of this research area go back so far. The fast development of computers led the investigations in combinatorial mathematics to be one of the central subjects and one of the most explored mathematical topics. Trends indicate that, in the 21st century, optimization problems -- including the discrete ones -- and their solutions are more important than ever: a better solution may mean saving money, energy, time, and also saving the natural environment.
When studying networks and set systems and, in particular, extremal and optimization problems in combinatorial structures, we are working with highly abstract entities which can serve as models for many practical problems. Paths are simple but basic parts in networks. They ensure the connectivity and also serve as basic building parts in more complex structures. The study of different optimization problems related to paths provides us information about the behaviour of more complex networks.
We expect that the newly obtained results will be published in leading journals in the area of discrete mathematics, and we will present them at international scientific conferences. We also expect that we will be invited to deliver plenary talks which will further emphasize the importance of our research achievements. In this way we would further increase the international role of the Hungarian and the Slovenian school in discrete mathematics.
Final report
Results in Hungarian
Az SNN 129364 projekt keretében sok új tudományos eredményt értünk el. A támogatást feltüntető 124 cikkből 87 impakt faktoros SCI folyóiratban már megjelent vagy elfogadásra került, és további 25 lett benyújtva rangos nemzetközi szakfolyóiratokba. A többi 12 cikk is lektorált újságokban, illetve szerkesztett konferenciakötetekben jelent meg.
A szlovén kutatócsoport tagjaival közösen készült munkák többsége a gráfdominálás elméletével, valamint gráfszorzat útján előállított struktúrák vizsgálatával foglalkozik. Az eddigi tendencia azt jelzi, hogy ezen publikációk közül néhány a szerzők sokat hivatkozott művei között lesz. A két kutatócsoport együttműködését konferenciákon és workshopokon való közös részvétel is erősítette.
A Turán-típusú problémáknak és kapcsolódó területeknek sok aspektusát vizsgáltuk: szinguláris, reguláris, valamint összefüggő Turán-szám, Berge-Turán probléma, Turán probléma gráfok párjaira illetve q-gráfokra és ehhez kötődő gráfszínezések, stabilitás, telítettség, tiltott részek a részben rendezett halmazokban, rendezett Ramsey-számok, többségi kiválasztási feladat, metsző halmazcsaládok extremális tulajdonságai, általános helyzetű csúcshalmazok, dominálási játékok, valamint a kombinatorikus optimalizálás néhány további aspektusa. Mindezeket egy hosszabb összefoglaló dokumentumban tárgyaljuk.
Results in English
In the framework of the project SNN 129364, we achieved many new scientific results. The list of papers acknowledging support from this project includes 124 items. 87 of those works appear(ed) in SCI journals with impact factors, and 25 others are under review, also at high-level international journals. The other 12 works appeared in conference proceedings and non-SCI journals.
The joint papers published with the Slovenian research group are mostly in the area of graph domination theory and in the study of structures obtained via graph product operations. Tendency indicates that some of these papers will be among the highly cited works of the authors. Collaboration between the two research groups has been strengthened with joint participation in conferences and workshops.
During the duration of the project, many aspects of Turán-type problems and related areas have been investigated: singular and regular Turán number, generalized Turán problem, Berge-Turán problem, connected Turán number, Turán problem for q-graphs and related graph colorings, stability problems, saturation problems, forbidden subposets, ordered Ramsey numbers, majority problem, extremal properties of intersecting set families, vertex sets in general position, domination games, and further aspects of combinatorial optimization. A summary with more details is given in a longer separate description.
M. Balko, M. Vizer: Edge-ordered Ramsey numbers, Acta Mathematica Universitatis Comenianae, 88:3, 409-414, 2019
J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: A new lower bound for classic online bin packing, Approximation and Online Algorithms, E. Bampis and N. Megow (Eds.), WAOA 2019, Lecture Notes in Computer Science, 11926, pp. 1–11, 2020
M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Zs. Tuza: Independent (k+1)-domination in k-trees, submitted manuscript, 2019
B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza, M. Vizer: The variety of domination games, Aequationes Mathematicae, 93, 1085-1109, 2019
Cs. Bujtás, S. Jendrol’, Zs. Tuza: On specific factors in graphs, submitted manuscript, 2019
Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: Domination game on uniform hypergraphs, Discrete Applied Mathematics, 258, 65-75, 2019
D. Gerbner, B. Keszegh, A. Methuku, B. Patkós, M. Vizer: An improvement on the maximum number of k-dominating independent sets, Journal of Graph Theory, 91:1, 88-97, 2019
D. Gerbner, D. Lenger, M. Vizer: Plurality problems with three colors and query size three, Proceedings of 11th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 466-474, 2019
D. Gerbner, A. Methuku, D. T. Nagy, D. Pálvölgyi, G. Tardos, M. Vizer: Edge ordered Turán problems, Acta Mathematica Universitatis Comenianae, 88:3, 717-722, 2019
D. Gerbner, A. Methuku, D.T. Nagy, B. Patkós, M. Vizer: On the number of containments in P-free families, Graphs and Combinatorics, 35, 1519-1540, 2019
J. Bekesi, Gy. Dosa, G. Galambos: Analysis of the FFD algorithm for UET coupled of tasks scheduling on single machine for two job-types, submitted manuscript, 2021
D. Gerbner, C. Palmer: Some exact results for generalized Turán problems, submitted manuscript, 2020
D. Gerbner: Generalized Turán problems for small graphs, submitted manuscript, 2020
D. Gerbner: On Turán-good graphs, submitted manuscript, 2020
Gy. Dósa, H. Kellerer, Zs. Tuza: A nearly best possible parametric algorithm for two-machine scheduling with given lower and upper bounds for the total processing time, submitted manuscript, 2020
A. Keszler, Zs. Tuza: Hypercycle systems of 5-cycles in complete 3-uniform hypergraphs, submitted manuscript, 2020
B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza, M. Vizer: On Grundy total domination number in product graphs, Discussiones Mathematicae Graph Theory, 41:1, 225-247, 2021
Cs. Bujtás, S. Jendrol’, Zs. Tuza: On caterpillar factors in graphs, Theoretical Computer Science 846, 82-90, 2020
J. Bekesi, Gy. Dosa, G. Galambos: A first Fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays, European Journal of Operational Research, 297:3, 844-852, 2021
Gy. Dósa, H. Kellerer, T. Olaj, Zs. Tuza: An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time, Theoretical Computer Science, 880, 69-81, 2021
D. Gerbner, B. Patkós: Generalized Turán problems for complete bipartite graphs, submitted manuscript, 2021
D. Gerbner, D. T. Nagy, B. Patk6s, M. Vizer: On the maximum number of copies of H in graphs with given size and order, Journal of Graph Theory, 96:1, 34-43, 2021
M. Balko, M. Vizer: On ordered Ramsey numbers of tripartite 3-uniform hypergraphs, Extended Abstracts EuroComb 2021, pp. 142-147. Birkhauser, Cham., 2021
J. Balogh, J. Békési, Gy. Dósa, L. Epstein, A. Levin: A new lower bound for classic online bin packing, Algorithmica, 83:7, 2047-2062, 2021
J. Balogh, J. Békési, Gy. Dósa, L. Epstein, A. Levin: Lower bounds for batched bin packing, Journal of Combinatorial Optimization, published online first, 2021
A. Frendrup, Zs. Tuza, P. D. Vestergaard: Distance domination in vertex-partitioned graphs, Mathematica Pannonica, accepted for publication, 2022
J. Balogh, Gy. Dosa, L. M. Hvattum, T. Olaj, Zs. Tuza: Guillotine cutting is asymptotically optimal for packing consecutive squares, Optimization Letters, accepted for publiation, 2022
M. Balko, M. Vizer: On ordered Ramsey numbers of tripartite 3-uniform hypergraphs, SIAM Journal on Discrete Mathematics, 36:1, 214-228, 2022
D. Gerbner, Z. L. Nagy, M. Vizer: Unified approach to the generalized Turán problem and supersaturation, Discrete Mathematics, 345:3, 112743, 2022
G. Kiss, R. D. Malikiosis, G. Somlai, M. Vizer: Fuglede's conjecture holds for cyclic groups of order pqrs, Journal of Fourier Analysis and Applications 28, #79, 2022
J. Balogh, J. Békési, Gy. Dósa, L. Epstein, A. Levin: Lower bounds for batched bin packing, Journal of Combinatorial Optimization, 3:3, 613-629, 2022
A. Frendrup, Zs. Tuza, P. D. Vestergaard: Distance domination in vertex-partitioned graphs, Mathematica Pannonica, 28:1, 44-57, 2022
J. Balogh, Gy. Dosa, L. M. Hvattum, T. Olaj, Zs. Tuza: Guillotine cutting is asymptotically optimal for packing consecutive squares, Optimization Letters, 16:9, 2775-2785, 2022
D. Gerbner, A. Methuku, D. T. Nagy, D. Pálvölgyi, G. Tardos, M. Vizer: Turán problems for edge-ordered graphs, Journal of Combinatorial Theory, Series B, 160, 66-113, 2023
Gy. Abraham, Gy. Dosa, L. M. Hvattum, T. A. Olaj, Zs. Tuza: The board packing problem, European Journal of Operational Research, published online, 2023
J. Balogh, Gy. Dosa, L. M. Hvattum, T. A. Olaj, I. Szalkai, Zs. Tuza: Covering a square with consecutive squares, submitted manuscript, 2023
J. Barát, D. Gerbner, A. Halfpap:: On the number of A-transversals in hypergraphs, submitted manuscript, 2022
D. Gerbner: On Turán problems with bounded matching number, submitted manuscript, 2022
D. Gerbner: Rainbow copies of F in families of H, submitted manuscript, 2022
D. Gerbner: On the extremal graphs in generalized Turán problems, submitted manuscript, 2022
D. Gerbner: Some exact results for non-degenerate generalized Turán problems, submitted manuscript, 2022
D. Gerbner: On weakly Turán-good graphs, submitted manuscript, 2022
X. Zhu, Y. Chen, D. Gerbner, E. Győri, H. Hama Karim: The maximum number of triangles in F_k-free graphs, submitted manuscript, 2022
D. Gerbner: Paths are Turán-good,, submitted manuscript, 2022
D. Gerbner: Some stability and exact results in generalized Turán problems, Studia Scientiarum Mathematicarum Hungarica, accepted for publication, 2023
D. Gerbner: A note on the number of triangles in graphs without the suspension of a path on four vertices, Discrete Mathematics Letters, 10, 32-34, 2022
Gy. Abraham, Gy. Dosa, L. M. Hvattum, T. A. Olaj, Zs. Tuza: The board packing problem, European Journal of Operational Research, 308:3, 1056-1073, 2023
X. Zhu, Y. Chen, D. Gerbner, E. Győri, H. Hama Karim: The maximum number of triangles in F_k-free graphs, European Journal of Combinatorics, accepted for publication, 2023
D. Gerbner: On non-degenerate Berge-Turán problems, submitted manuscript, 2023
D. Gerbner: A note on strongly and totally chain intersecting families, submitted manuscript, 2023
D. Gerbner: Generalized Turán results for disjoint cliques, submitted manuscript, 2023
D. Gerbner, H. Hama Karim: Stability from graph symmetrization arguments in generalized Turán problems, submitted manuscript, 2023
