 |
Turán numbers and extremal problems for paths
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
129364 |
| Type |
SNN |
| Principal investigator |
Tuza, Zsolt |
| Title in Hungarian |
Turán-számok és extremális problémák utakra |
| Title in English |
Turán numbers and extremal problems for paths |
| Keywords in Hungarian |
gráf, extremális probléma, Turán-szám, útrendszer, optimális fedés, hipergráf |
| Keywords in English |
graph, extremal problem, Turán number, path system, optimal cover, hypergraph |
| Discipline |
| Mathematics (Council of Physical Sciences) | 100 % | | Ortelius classification: Discrete mathematics |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Alfréd Rényi Institute of Mathematics |
| Participants |
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.
|
|
|
|
|
|
|
|
| |
List of publications |
|
|
| Gy. Ábrahám, P. Auer, Gy. Dósa, T. Dulai, Á. Werner-Stark: A reinforcement learning motivated algorithm for process optimization, Periodica Polytechnica Civil Engineering, 63:4, 961-970, 2019 | | G. Bacsó, Zs. Tuza: The equal-sum-free subset problem, Acta Scientiarum Mathematicarum (Szeged) - accepted, 2020 | | M. Balko, D. Gerbner, D. Y. Kang, Y. Kim, C. Palmer: Hypergraph based Berge hypergraphs, submitted manuscript, 2019 | | 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 | | J. Balogh, G. O. H. Katona, W. Linz, Zs. Tuza: The domination number of the graph defined by two levels of the n-cube, II, submitted manuscript, 2019 | | 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 | | Cs. Bujtás, Zs. Tuza: Fractional Domination Game, Electronic Journal of Combinatorics, 26, #P4.3, 2019 | | Y. Caro, Zs. Tuza: Singular Ramsey and Turán numbers, Theory and Applications of Graphs, 6:1, Article 1, 2019 | | Y. Caro, Zs. Tuza: Regular Turán numbers, submitted manuscript, 2019 | | S. Cichacz, Zs. Tuza: Realization of digraphs in Abelian groups and its consequences, submitted manuscript, 2019 | | G. Damásdi, D. Gerbner, G. O. H. Katona, B. Keszegh, D. Lenger, A. Methuku, D. T. Nagy, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: Adaptive majority problems for restricted query graphs and for weighted sets, Acta Mathematica Universitatis Comenianae, 88:3, 601-609, 2019 | | S. Dara, S. Mishra, N. Narayanan, Zs. Tuza: Strong edge colouring of Cayley graphs and some product graphs, submitted manuscript, 2019 | | A. Davoodi, D. Gerbner, A. Methuku, M. Vizer: Sigma clique covering, Discrete Applied Mathematics - accepted, 2020 | | Gy. Dósa, L. Epstein: A new lower bound on the price of anarchy of selfish bin packing, Information Processing Letters, 150, 6-12, 2019 | | S. English, D. Gerbner, A. Methuku, C. Palmer: On the weight of Berge-F-free hypergraphs, submitted manuscript, 2019 | | Z. Füredi, D. Gerbner: Hypergraphs without exponents, submitted manuscript, 2019 | | D. Gerbner: A note on the Turán number of a Berge odd cycle, submitted manuscript, 2019 | | D. Gerbner: Between the deterministic and non-deterministic query complexity, submitted manuscript, 2019 | | D. Gerbner: On Berge-Ramsey problems, submitted manuscript, 2019 | | D. Gerbner: The covering lemma and q-analogues of extremal set theory problems, submitted manuscript, 2019 | | D. Gerbner, E. Győri, A. Methuku, M. Vizer: Generalized Turán numbers for even cycles, Acta Mathematica Universitatis Comenianae, 88:3, 723-728, 2019 | | D. Gerbner, B. Keszegh, A. Methuku, D. T. Nagy, B. Patkós, C. Tompkins, C. Xiao: Set systems related to a house allocation problem, submitted manuscript, 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, T. Mészáros, A. Methuku, C. Palmer: Generalized rainbow Turán problems, submitted manuscript, 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 | | D. Gerbner, A. Methuku, D.T. Nagy, B. Patkós, M. Vizer: Stability results on vertex Turán problems in Kneser graphs, Electronic Journal of Combinatorics, 26:2, #P2.13, 2019 | | D. Gerbner, A. Methuku, G. Omidi, M. Vizer: Ramsey problems for Berge hypergraphs, SIAM Journal on Discrete Mathematics - accepted, 2020 | | D. Gerbner, A. Methuku, C. Palmer: General lemmas for Berge-Turán problems, European Journal of Combinatorics - accepted, 2020 | | D. Gerbner, A. Methuku, M. Vizer: Asymptotics for the Turán number of Berge-K_{2,t}, Journal of Combinatorial Theory Ser. B, 137, 264-290, 2019 | | D. Gerbner, D. T. Nagy, B. Patkós, M. Vizer: t-wise Berge and t-heavy hypergraphs, submitted manuscript, 2019 | | D. Gerbner, C. Palmer: Counting copies of a fixed subgraph of F-free graphs, European Journal of Combinatorics, 82, 103001, 2019 | | D. Gerbner, B. Patkós, Zs. tuza, M. Vizer: Singular Turán numbers and WORM-colorings, submitted manuscript, 2019 | | D. Gerbner, B. Patkós, Zs. Tuza, M. Vizer: Some exact results for regular Turán problems, submitted manuscript, 2019 | | D. Gerbner, M. Vizer: Rounds in a combinatorial search problem, Discrete Applied Mathematics - accepted, 2020 | | A. Gyárfás, D. Pálvölgyi, B. Patkós, M. Wales: Distribution of colors in Gallai colorings, submitted manuscript, 2019 | | S. Klavžar, B. Patkós, G. Rus, I. G. Yero: On general position sets in Cartesian grids, submitted manuscript, 2019 | | B. Patkós: On L-close Sperner systems, submitted manuscript, 2019 | | B. Patkós: On the general position problem on Kneser graphs, submitted manuscript, 2019 | | G. Bacsó, Zs. Tuza: The equal-sum-free subset problem, Acta Scientiarum Mathematicarum (Szeged), 86,73-79, 2020 | | M. Balko, M. Vizer: Edge-ordered Ramsey numbers, European Journal of Combinatorics, 87, 103100, 2020 | | J. Balogh, G. O. H. Katona, W. Linz, Zs. Tuza: The domination number of the graph defined by two levels of the n-cube, II, European Journal of Combinatorics, 91, 103201, 2021 | | M. Borowiecki, A. Fiedorowicz, E. Sidorowicz, Zs. Tuza: Independent (k+1)-domination in k-trees, Discrete Applied Mathematics, 284, 99-110, 2020 | | Cs. Bujtás, S. Jendrol’, Zs. Tuza: On specific factors in graphs, Graphs and Combinatorics, 36:5, 1391-1399, 2020 | | Y. Caro, Zs. Tuza: Regular Turán numbers, Australasian Journal of Combinatorics, 78:1, 133-144, 2020 | | G. Damásdi, D. Gerbner, G. O. H. Katona, B. Keszegh, D. Lenger, A. Methuku, D. T. Nagy, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: Adaptive majority problems for restricted query graphs and for weighted sets, Discrete Applied Mathematics, 288, 235-245, 2020 | | A. Davoodi, D. Gerbner, A. Methuku, M. Vizer: On sigma clique coverings of multipartite graphs, Discrete Applied Mathematics, 276, 19-23, 2020 | | D. Gerbner: A note on the Turán number of a Berge odd cycle, Australasian Journal of Combinatorics, accepted, 2021 | | D. Gerbner: On Berge-Ramsey problems, Electronic Journal of Combinatorics, 27:2, #2.39, 2020 | | D. Gerbner, E. Győri, A. Methuku, M. Vizer: Generalized Turán numbers for even cycles, Journal of Combinatorial Theory, Series B, 145, 165-213, 2020 | | D. Gerbner, B. Keszegh, A. Methuku, D. T. Nagy, B. Patkós, C. Tompkins, C. Xiao: Set systems related to a house allocation problem, Discrete Mathematics, 343:7, 111886, 2020 | | D. Gerbner, A. Methuku, G. Omidi, M. Vizer: Ramsey problems for Berge hypergraphs, SIAM Journal on Discrete Mathematics, 34:1, 351-369, 2020 | | D. Gerbner, D. T. Nagy, B. Patkós, M. Vizer: t-wise Berge and t-heavy hypergraphs, SIAM Journal on Discrete Mathematics, 34:3, 1813-1829, 2020 | | D. Gerbner, B. Patkós, Zs. tuza, M. Vizer: Singular Turán numbers and WORM-colorings, Discussiones Mathematicae Graph Theory, Published online: 09 Jul 2020, 2020 | | D. Gerbner, M. Vizer: Rounds in a combinatorial search problem, Discrete Applied Mathematics, 276, 60-68, 2020 | | A. Gyárfás, D. Pálvölgyi, B. Patkós, M. Wales: Distribution of colors in Gallai colorings, European Journal of Combinatorics, 86, 103087, 2020 | | B. Patkós, D. T. Nagy: On L-close Sperner systems, Graphs and Combinatorics, accepted, 2021 | | B. Patkós: On the general position problem on Kneser graphs, Ars Mathematica Contemporanea, 18:2, 273-280, 2020 | | M. Balko, M. Vizer: On ordered Ramsey numbers of tripartite 3-uniform hypergraphs, submitted manuscript, 2020 | | D. Gerbner, Z. L. Nagy, M. Vizer: Unified approach to the generalized Turán problem and supersaturation, submitted manuscript, 2020 | | G. Kiss, R. D. Malikiosis, G. Somlai, M. Vizer: Fuglede's conjecture holds for cyclic groups of order pqrs, submitted manuscript, 2020 | | D. Gerbner, M. Vizer: On non-adaptive majority problems of large query size, submitted manuscript, 2020 | | P. Auer, Gy. Dósa, T. Dulai, A. Fügenschuh, P. Näser, R. Ortner, Á. Werner-Stark: A new heuristic and an exact approach for a production planning problem, Central European Journal of Operations Research, 2020 | | 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 | | G. Dosa, L. M. Hvattum, T. Olaj, Zs. Tuza: The board packing problem: Packing rectangles into a board to maximize profit, Pannonian Conference on Advances in Information Technology, (PCIT 2020), 5 June 2020, pp. 10-16, University of Pannonia, Veszprém, Hungary, 2020 | | Gy. Ábrahám, Gy. Dósa, T. Dulai, Á. Werner-Stark: Parameter optimization of Q-learning motivated algorithm in process scheduling, Pannonian Conference on Advances in Information Technology, (PCIT 2020), pp 17- 24, 5 June 2020, University of Pannonia, Veszprém, Hungary, 2020 | | D. Gerbner, B. Patkós, Zs. Tuza, M. Vizer: Saturation problems with regularity constraints, submitted manuscript, 2020 | | D. Gerbner, D. Nagy, B. Patkós, N. Salia, M. Vizer: Stability of extremal connected hypergraphs avoiding Berge-paths, submitted manuscript, 2020 | | D. Gerbner, D. Nagy, B. Patkós, M. Vizer: Supersaturation, counting, and randomness in forbidden subposet problems, submitted manuscript, 2020 | | N. Frankl, S. Kiselev, A. Kupavskii, B. Patkós: VC-saturated set systems, submitted manuscript, 2020 | | B. Keszegh, N. Lemons, R. R. Martin, D. Pálvölgyi, B. Patkós: Induced and non-induced poset saturation problems, submitted manuscript, 2020 | | 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 | | S. Cichacz, Zs. Tuza: Realization of digraphs in Abelian groups and its consequences, Journal of Graph Theory, in print, 2022 | | S. Dara, S. Mishra, N. Narayanan, Zs. Tuza: Strong edge colouring of Cayley graphs and some product graphs, Graphs and Combinatorics, in print, 2022 | | D. Gerbner, A. Methuku, M. Vizer: Asymptotics for the Turán number of Berge-K_{2,t}, Journal of Combinatorial Theory, Series B, 137, 264-290, 2019 | | S. Klavžar, B. Patkós, G. Rus, I. G. Yero: On general position sets in Cartesian grids, Results in Mathematics 76:13, 123, 1-21, 2021 | | B. Patkós, D. T. Nagy: On L-close Sperner systems, Graphs and Combinatorics, 37, 789-796, 2021 | | D. Gerbner, M. Vizer: On non-adaptive majority problems of large query size, Discrete Mathematics & Theoretical Computer Science, 2021, 23:3, #15, 2021 | | P. Auer, Gy. Dósa, T. Dulai, A. Fügenschuh, P. Näser, R. Ortner, Á. Werner-Stark: A new heuristic and an exact approach for a production planning problem, Central European Journal of Operations Research, 29, 1079-1113, 2021 | | 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 | | D. Gerbner, D. Nagy, B. Patkós, M. Vizer: Supersaturation, counting, and randomness in forbidden subposet problems, Electronic Journal of combinatorics 28:1, #Pl.40, 2021 | | B. Keszegh, N. Lemons, R. R. Martin, D. Pálvölgyi, B. Patkós: Induced and non-induced poset saturation problems, Journal of Combinatorial Theory, Series A, 184, 105497, 2021 | | D. Gerbner: Generalized Turán problems for small graphs, Discussiones Mathematicae Graph Theory, in print, 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 | | A. Keszler, Zs. Tuza: Hypercycle systems of 5-cycles in complete 3-uniform hypergraphs, Mathematics, 9:5, 2021, 484, 1-60, 2021 | | F.-H. Chang, D. Gerbner, W.-T. Li, A. Methuku, D. Nagy, B. Patkós, M. Vizer: Rainbow Ramsey problems for the Boolean lattice, submitted manuscript, 2020 | | B. Patkós, Zs. Tuza, M. Vizer: Vector sum-intersection theorems, submitted manuscript, 2021 | | D. Gerbner: A note on stability for maximal F-free graphs, Graphs and Combinatorics, 37, 2571-2580, 2021 | | D. Gerbner: Generalized Turán problems for K_{2,t}, submitted manuscript, 2021 | | D. Gerbner: A non-aligning variant of generalized Turán problems, submitted manuscript, 2021 | | D. Gerbner: The profile polytope of non-trivial intersecting families, submitted manuscript, 2021 | | D. Gerbner: A note on the uniformity threshold for Berge hypergraphs, submitted manuscript, 2021 | | D. Gerbner: The Turán number of Berge book hypergraphs, submitted manuscript, 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 | | J. Balogh, R. R. Martin, D. T. Nagy, B. Patkós: On generalized Turán results in height two posets, submitted manuscript, 2021 | | M. Balko, M. Vizer: On ordered Ramsey numbers of tripartite 3-uniform hypergraphs, Extended Abstracts EuroComb 2021, pp. 142-147. Birkhauser, Cham., 2021 | | P. P. Pach, M. Vizer: Improved lower bounds for multiplicative square-free sequences, submitted manuscript, 2021 | | D. Gerbner, B. Patkós, Zs. Tuza, M. Vizer: On saturation of Berge hypergraphs, European Journal of Combinatorics, 102: 103477, 2022 | | D. Gerbner, D. Nagy, B. Patkós, M. Vizer: Forbidden subposet problems in the grid, Discrete Mathematics, 345:3, 112720, 2022 | | Gy. Ábrahám, Gy. Dósa, T. Dulai, Zs. Tuza, Á. Werner-Stark: Efficient pre-solve algorithms for the Schwerin and Falkenauer U bin packing benchmark problems for getting optimal solutions with high probability, Mathematics, 9:13, 1540, 1-21, 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 | | Gy. Dosa, N. Newman, Zs. Tuza, V. I. Voloshin: Coloring properties of mixed cycloids, Symmetry, 13:8, 1539, 1-12, 2021 | | A. Kemnitz, M. Marangio, Zs. Tuza, M. Voigt: Comparison of sum choice number with chromatic sum, Discrete Mathematics, 344:7, 112391, 2021 | | Cs. Bujtás, M. Gionfriddo, E. Guardo, L. Milazzo, S. Milici, Zs. Tuza: Complex uniformly resolvable decompositions of K_v, Ars Mathematica Contemporanea, 21:1, #P1.02, 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 | | Cs. Bujtás, M. Jakovac, Zs. Tuza: The k-path vertex cover: General bounds and chordal graphs, Networks, published online first, 2021 | | M. Balko, D. Gerbner, D. Y. Kang, Y. Kim, C. Palmer: Hypergraph based Berge hypergraphs, Graphs and Combinatorics, 38, #11, 2022 | | S. Cichacz, Zs. Tuza: Realization of digraphs in Abelian groups and its consequences, Journal of Graph Theory, 100:2, 331-345, 2022 | | S. Dara, S. Mishra, N. Narayanan, Zs. Tuza: Strong edge colouring of Cayley graphs and some product graphs, Graphs and Combinatorics, 38:2, #51, 2022 | | S. English, D. Gerbner, A. Methuku, C. Palmer: On the weight of Berge-F-free hypergraphs, Electronic Journal of Combinatorics, 26:4, #P4.7, 2019 | | Z. Füredi, D. Gerbner: Hypergraphs without exponents, Journal of Combinatorial Theory, Series A, 184, 105517, 2021 | | D. Gerbner, D. Lenger, M. Vizer: A plurality problem with three colors and query size three, Discrete Mathematics, 346, 113151, 2023 | | D. Gerbner, T. Mészáros, A. Methuku, C. Palmer: Generalized rainbow Turán problems, Electronic Journal of Combinatorics, 29:2, #P2.44, 2022 | | D. Gerbner, A. Methuku, C. Palmer: General lemmas for Berge-Turán problems, European Journal of Combinatorics, 86, 103082, 2020 | | D. Gerbner, B. Patkós, Zs. tuza, M. Vizer: Singular Turán numbers and WORM-colorings, Discussiones Mathematicae Graph Theory, 42:4, 1061-1074, 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 | | D. Gerbner, B. Patkós, Zs. Tuza, M. Vizer: Saturation problems with regularity constraints, Discrete Mathematics, 345:8, 112921, 2022 | | N. Frankl, S. Kiselev, A. Kupavskii, B. Patkós: VC-saturated set systems, European Journal of Combinatorics, 104, 103528, 2022 | | D. Gerbner, C. Palmer: Some exact results for generalized Turán problems, European Journal of Combinatorics, 103, 103519, 2022 | | D. Gerbner: On Turán-good graphs, Discrete Mathematics, 344:8, 112445, 2021 | | F.-H. Chang, D. Gerbner, W.-T. Li, A. Methuku, D. Nagy, B. Patkós, M. Vizer: Rainbow Ramsey problems for the Boolean lattice, Order, 39, 453–463, 2022 | | D. Gerbner: Generalized Turán problems for K_{2,t}, Electronic Journal of Combinatorics, accepted for publication, 2023 | | D. Gerbner: A non-aligning variant of generalized Turán problems, Annals of Combinatorics, accepted for publication, 2023 | | D. Gerbner: A note on the uniformity threshold for Berge hypergraphs, European Journal of Combinatorics, 105, 103561, 2022 | | D. Gerbner, B. Patkós: Generalized Turán problems for complete bipartite graphs, Graphs and Combinatorics, 38, #164,, 2022 | | J. Balogh, R. R. Martin, D. T. Nagy, B. Patkós: On generalized Turán results in height two posets, SIAM Journal on Discrete Mathematics, 36:2, 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 | | Cs. Bujtás, M. Jakovac, Zs. Tuza: The k-path vertex cover: General bounds and chordal graphs, Networks, 80:1, 63-76, 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, P. Auer, Gy. Dosa, T. Dulai, Zs. Tuza, A. Werner-Stark: The bin covering with delivery problem, extended investigations for the online case, Central European Journal of Operations Research, 31:1, 21-47, 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 | | D. Gerbner, Balázs Keszegh, D. Lenger, D. T. Nagy, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: On graphs that contain exactly k copies of a subgraph, and a related problem in search theory, submitted manuscript, 2023 | | D, T. Nagy, B. Patkós: Triangles in intersecting families, Mathematika, 68:4, 1073-1079, 2022 | | J. Balogh, W. B. Linz, B. Patkós: On the sizes of t-intersecting k-chain-free families, submitted manuscript, 2023 | | Y. Caro, B. Patkós, Zs. Tuza: Connected Turán number of trees, submitted manuscript, 2022 | | Y. Caro, B. Patkós, Zs. Tuza, M. Vizer: Counting connected partitions of graphs, submitted manuscript, 2022 | | B. Patkós, M. Stojaković, M. Vizer: The Constructor-Blocker Game, submitted manuscript, 2022 | | C. Palmer, B. Patkós: On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza, submitted manuscript, 2022 | | 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 | | G. Bacsó, J. Túri, Zs. Tuza: Connected domination in random graphs, Indian Journal of Pure and Applied Mathematics, published online first, 2023 | | A. Keszler, Zs. Tuza: Spectrum of 3-uniform 6- and 9-cycle systems over K(3)v−I, submitted manuscript, 2022 | | Cs. Bujtás, G. Rote, Zs. Tuza: Optimal strategies in fractional games: Vertex cover and domination, submitted manuscript, 2023 | | D. Gerbner: A note on the Turán number of a Berge odd cycle, Australasian Journal of Combinatorics, 79:2, 205–214, 2021 | | D. Gerbner: The covering lemma and q-analogues of extremal set theory problems, Ars Mathematica Contemporanea, accepted for publication, 2023 | | D. Gerbner: Generalized Turán problems for small graphs, Discussiones Mathematicae Graph Theory, 43:2, 549-572, 2023 | | B. Patkós, Zs. Tuza, M. Vizer: Vector sum-intersection theorems, Discrete Mathematics, 346:10, 113506, 2023 | | D. Gerbner: Generalized Turán problems for K_{2,t}, Electronic Journal of Combinatorics, 30:1, P1.34, 2023 | | D. Gerbner: The profile polytope of non-trivial intersecting families, Siam Journal on Discrete Mathematics, accepted for publication, 2023 | | P. P. Pach, M. Vizer: Improved lower bounds for multiplicative square-free sequences, Electronic Journal of Combinatorics, accepted for publication, 2023 | | 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 | | 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 | | D. Gerbner, Balázs Keszegh, D. Lenger, D. T. Nagy, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: On graphs that contain exactly k copies of a subgraph, and a related problem in search theory, Discrete Applied Mathematics, accepted for publication, 2023 | | J. Balogh, W. B. Linz, B. Patkós: On the sizes of t-intersecting k-chain-free families, Combinatorial Theory, accepted for publication, 2023 | | C. Palmer, B. Patkós: On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza, Journal of Graph Theory, https://doi.org/10.1002/jgt.22971, 2023 | | D. Gerbner: Paths are Turán-good,, Graphs and Combinatorics, 39, 56, 2023 | | D. Gerbner: Some stability and exact results in generalized Turán problems, Studia Scientiarum Mathematicarum Hungarica, 60:1, 16-26, 2023 | | G. Bacsó, J. Túri, Zs. Tuza: Connected domination in random graphs, Indian Journal of Pure and Applied Mathematics, 54:2, 439-446, 2023 | | P. B. Czaun, P. Pusztai, L. Sebők, Zs. Tuza: Minimal non-C-perfect hypergraphs with circular symmetry, Symmmetry, 15:5, 1114, 1-30, 2023 | | G. Bacsó, J. Túri: An enumeration approach to network evolution, Miskolc Mathematical Notes, 24:2, 625-634, 2023 | | G. Bacsó, B. Brešar, K. Kuenzel, D. F. Rall: Graphs with equal Grundy domination and independence number, Discrete Optimization 48:2, 100777, 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 | | D. Gerbner, B. Keszegh, K. Nagy, B. Patkós, G. Wiener: Cooperation in combinatorial search, submitted manuscript, 2023 | | G. Bacsó, B. Patkós, Zs. Tuza, M. Vizer: The robust chromatic number of graphs, submitted manuscript, 2023 | | G. Bacsó, Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: The robust chromatic number of certain graph classes, submitted manuscript, 2023 | | D. Pálvölgyi, B. Patkós: Projective and external saturation problem for posets, submitted manuscript, 2023 |
|
|
|
|
|
|
|
|
|
