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 egyik terület, amit vizsgálni szeretnék az extremális halmazrendszerek elmélete. Több új, érdekes probléma származik néhány cikkből, amit szerzőtársaimmal a közelmúltban publikáltunk. Ha halmazrendszerek egy tulajdonsága azon alapul, hogy kizárunk valamilyen relációt két halmaz között, akkor a tulajdonság neve elé odatehetjük, hogy l-majdnem, azt értve ezen, hogy minden halmaz legfeljebb l másikkal állhat ebben a relációban. Azt tervezem, hogy tovább vizsgálom az ilyen tulajdonságokat. Szintén folytatni kívánom a profil-politópok vizsgálatát. Egy harmadik téma a halmazrendszereknél megszokott kérdések vizsgálata multihalmaz-rendszerek esetén.
A másik terület a gráfok dekompozíciói, fedései és partíciói. Egyik fő célom egy olyan állítás bebizonyítása, ami Erdős, Pyber és Gyárfás egy sejtéséhez kapcsolódik, amely 2-élszínezett teljes gráf pontjainak monokromatikus körökkel való fedéséről szól. Egy másik célom Gyárfás fapakolási sejtésének vizsgálata. Szerzőtársaimmal több (egymáshoz kapcsolódó) általánosítását vizsgáltuk a sejtésnek, és a legtöbb olyan részeredményt, ami ismert volt az eredeti esetben, bebizonyítottuk az általánosabb kérdéseknél is. Emellett (szintén korábbi kutatásaimból kiindulva) szeretném megmutatni, hogy ha egy gráf elég sokszorosan összefüggő, akkor fel lehet bontani egy adott fa példányaira, feltéve hogy az élszámokra teljesül egy oszthatósági feltétel.
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. Két nagy területen belül több, egymáshoz lazán kapcsolódó kérdést szeretnék vizsgálni.
Az extremális halmazrendszerek területén a legalapvetőbb kérdés egy - bizonyos feltételeket kielégítő - halmazrendszer maximális méretének meghatározása. Szeretném ezt a kérdést megválaszolni majdnem metsző halmazrendszerek esetén. Szintén tervezem profilpolitópok vizsgálatát (ezen belül a nemtriviálisan metsző halmazrendszerek profilpolitópjának meghatározását), valamint a halmazrendszereknél megszokott kérdések vizsgálatát multihalmaz-rendszerek esetén.
A gárf-dekompozíciók, -partíciók és -fedések területén egy fontos kérdés a következő. Hány diszjunkt monokromatikus kör (vagy út) kell ahhoz hogy lefedjük egy olyan teljes gráf csúcsait, aminek az élei színezve vannak? Rengeteg még általánosabb kérdést is tanulmányoztak. Én szeretném azt az esetet vizsgálni, amikor a teljes gráf helyén más gráf áll. Érdekes kérdések egy másik csoportja amikor adott egy gráf és úgy akarjuk az éleit partícionálni, hogy a kapott osztályok izomorfak néhány előre megadott gráffal.
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 fő célja matematikai ismeretek fejlesztése. A kérdések jobb megértése más matematikai tételekhez vezethet. Ezen kutatásnak nem célja a lehetséges gyakorlati alkalmazások vizsgálata.
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. Két különböző területen több, egymáshoz lazán kapcsolódó kérdést szeretnék vizsgálni
Az egyik téma az extremális halmazrendszerek elmélete. Itt a legalapvetőbb problémánál adott egy véges alaphalmaz részhalmazainak egy rendszere. Ismerjük a halmazrendszer néhány tulajdonságát, és a méretére vagyunk kíváncsiak. Vizsgálni tervezem azt az esetet, amikor azt tudjuk a halmazrendszerről, hogy majdnem metsző. Emellett egy jól ismert általánosítása az alapvető kérdésnek az, ha nem csak arra figyelünk, hogy hány halmaz tartozik a halmazrendszerhez, de arra is, hogy mekkorák azok a halmazok. És egy másik általánosítás, amit szintén vizsgálni szeretnék, a multihalmaz-rendszerek. Egy multihalmaz, szemben egy halmazzal, egy elemet többször is tartalmazhat. Ugyanazok az extremális jellegű kérdések, amiket halmazrendszereknél felteszünk, többnyire multihalmaz-rendszereknél is feltehetők, de ezt a területet eddig keveset vizsgálták.
A másik téma gráfok dekompozíciói, fedései és partíciói. Egy gráf pontok egy halmaza úgy, hogy némely pontpár össze van kötve egy éllel.
A következő problémát vizsgáljuk: adott egy gráf és úgy akarjuk az éleit partícionálni (azaz szétosztani több osztályba), hogy a kapott osztályok megegyeznek néhány előre megadott gráffal. Én arra az esetre koncentrálnék, amikor a megadott gráfok fák. Egy másik probléma amikor adott egy gráf aminek az élei két színnel vannak színezve, és a ponthalmazát akarjuk egyszínű utakra szétosztani.
Mindkét területet sok kutató vizsgálta a közelmúltban és korábban is. Mindkettő kapcsolódik a kombinatorika sok más területéhez is.
Summary
Summary of the research and its aims for experts Describe the major aims of the research for experts. One of the areas I would like to study is the theory of extremal families. A new branch of problems came from a recent series of papers by me and a number of co-authors. If we are given a property of families which relies on a forbidden configuration of two members, we can add l-almost in front of the name of the property, meaning that any member can be in that configuration with at most l other members. I am planning to continue this research, and also the study of the so-called profile polytopes. Another topic is examining the usual questions from extremal set theory, but for multisets.
The other area consists of decompositions, coverings and packings of graphs. One of my main goals is to prove a statement related to a conjecture of Erdõs, Gyárfás and Pyber on the number of monochromatic cycles needed to cover the vertices of a two-edge-colored complete graph. Another goal is to show that high edge-connectivity implies that the graph can be decomposed to copies of a given tree, assuming a divisibility condition on the edges.
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. I would like to study several loosely connected questions in two areas.
In the area of extremal families the most basic question is to determine the maximum cardinality of a family satisfying some properties. I would like to answer this question for almost intersecting families. Also I am planning to study profile polytopes (more specifically to determine the profile polytope of the non-trivial intersecting families) and the usual questions of set theory with respect to multisets.
In the area of graph decompositions, coverings and partitions an important question is the following. How many disjoint monochromatic cycles (or paths) are needed to cover the vertices of a complete graph that has colored edges? Several more general questions have also been studied. I would like to consider the case when the complete graph is replaced by another graph. Another group of interesting problems is when we are given a graph and we want to partition its edges such a way that each partition class is isomorphic to one of some prescribed graphs.
What is the significance of the research? Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field. The main goal of this research is to develop mathematical knowledge. A better understanding of these questions could lead to other mathematical theorems. It is not my goal in this research to investigate the possible practical applications.
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. I would like to study several loosely connected questions in two areas.
One of the topics is the theory of extremal families of sets. Here the most basic problem is that we are given a family of subsets of a finite underlying set. The family is known to satisfy certain properties and we are interested in its cardinality. I am planning to examine the case when we know that the family is almost intersecting. A well-known generalization of the basic question is when we are not only interested in the number of sets belonging to the family, but also the sizes of those sets. Another generalization is to consider families of multisets. A multiset, unlike a set, can contain an element multiple times. The extremal questions asked about families of sets can usually asked about families of multisets as well, but this area has not been studied much.
The other topic is decompositions, coverings and partitions of graphs. A graph is a set of points, such that some pairs of points are connected by edges.
In general the following problem is considered: we are given a graph and we want to partition its edges such a way that each partition class is equal to one of some prescribed graphs. I would focus on the case when the prescribed graphs are trees. Another problem is when we are given a graph and its edges are colored with two colors, and we want to partition its vertex set into monochromatic paths.
Both areas have attracted the attention of many researchers in recent years and earlier as well. Both are connected to several other areas in Combinatorics.
Final report
Results in Hungarian
A kutatás során több lazán kapcsolódó problémát vizsgáltam. Különböző szerzőtársakkal több problémát vizsgáltam az extremális halmazelmélet és gráfelmélet területén. Berge definiálta a köröket hipergráfokban. Cory Palmerrel ezt a definíciót kiterjesztettük egyéb gráfokra és Turán-típusú problémákat vizsgáltunk. Ez vezetett ahhoz hogy egy gáf teljes részgráfjainak számát vizsgáljuk, és az általánosabb kérdéshez hogy egy tetszőleges részgráf példányait számoljuk egy gráfban, ami egy másik részgráfot nem tartalmaz. Más társszerzőkkel módosítottuk a kérdést egy kicsit és egy tiltott részgráf helyett majdnem az összes kört megtiltottuk és a megmaradó lehetséges köröket számoltuk. Egy másik kapcsolódó probléma volt a hasonló kérdés vizsgálata a Boole-poszet részposzetjei kapcsán. Ha egy részposzetet tiltunk, egy másik érdekes problémához vezetett ha azt tettük fel még hogy a halmazrendszer metsző is. Más extremális eredményeim közé tartozik az úgynevezett tilted Sperner-rendszerek és a kis halmazokból álló szeparáló remdszerek vizsgálata. Szintén kiterjesztettük a perkolációk vizsgálatát hipergráfokra.
Results in English
During this project I have studied several loosely connected problems. With various co-authors we examined different problems in the areas of extremal set theory and graph theory. Berge defined cycles in hypergraphs. With Cory Palmer we extended this to other graphs and studied Turán-type questions. This led us to consider the number of complete subgraphs of a graph, and the more general question of counting copies of a subgraph when forbidding another subgraph. With other co-authors we modified the question a bit and instead of forbidding one specific graph, we forbid almost all the cycles and counted the cycles of the remaining possible lengths. Another related problem was to ask the same questions about subposets of the Boolean poset. If we forbid a subposet, another new question was to assume in addition that the family is intersecting. Other extremal set theoretical results came by studying tilted Sperner families with patterns and separating families consisting of small sets. We also generalized bootstrap percolation to hypergraphs.
J. Barát, D. Gerbner: Edge-Decomposition of Graphs into Copies of a Tree with Four Edges, Electronic Journal of Combinatorics, 2014
Z. Füredi, D. Gerbner, M. Vizer: A discrete isodiametric result: the Erdős-Ko-Rado theorem for multisets, European J. Combin. 48 224-233, 2015
D. Gerbner, V. Mészáros, D. Pálvölgyi, A. Pokrovskiy, G. Rote: Advantage in the discrete Voronoi game, J. Graphs Algorithms Appl. 18 439-457, 2014
A. Dumitrescu, D. Gerbner, B. Keszegh, Cs. Tóth: Covering paths for planar point sets, Discrete & Computational Geometry 51 462-484, 2014
D Gerbner, M Vizer: A note on tilted Sperner families with patterns, DISCRETE MATH 339: (11) 2737-2741, 2016
Vizer Máté , Gerbner Dániel, Keszegh Balázs, Pálvölgyi Dömötör, Patkós Balázs , Wiener Gábor : Finding a majority ball with majority answers, ELECTRON NOTES DISCRETE MATH 49: 345-351, 2015
