Extremális gráfelmélet és extremális halmazrendszerek  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
83586
típus PD
Vezető kutató Patkós Balázs
magyar cím Extremális gráfelmélet és extremális halmazrendszerek
Angol cím Extremal graph theory and extremal set systems
magyar kulcsszavak metszettételek, Sperner-tipusú halamzrendszerek, véletlen gráfok
angol kulcsszavak intersection theorems, Sperner theory, random graphs
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Kombinatorika
zsűri Műszaki és Természettudományi zsűrielnökök
Kutatóhely HUN-REN Rényi Alfréd Matematikai Kutatóintézet
projekt kezdete 2011-03-01
projekt vége 2014-02-28
aktuális összeg (MFt) 14.713
FTE (kutatóév egyenérték) 2.39
állapot lezárult projekt
magyar összefoglaló
Az extremális kombinatorika a matematika egy olyan területe, melyben a magyar kutatók mindig is
meghatározó szerepet játszottak. Az általam kutatni kivánt két részterület egyike az extremális halmazrendszerek témaköre, mely nagy általánosságban azzal foglalkozik, hogy hány részhalmazát tudjuk egy adott alaphalmaznak úgy kiválasztani, hogy a kiválasztottaknakki kell elégiteniük valamilyen elõre meghatározott tulajdonságot. A másik részterület az extremális gráfelmélet, amely (szintén egyszerûsitve) adott gráftulajdonsággal biró gráfok valamely paraméterének minimális/maximális értékét keresi. Mindkét területtel jelenleg is sok kutató foglalkozik, jelentõs eredmények születtek az utóbbi idõszakban. Az extremális halmazrendszerek témakörét jól ismerem, több publikációm, PhD-értekezésem is ebbõl született, a tervezett kutatás eredményeinek zöme is ebbõl a témából várható. Az extremális gráfelmélet témakörében a projekt részeként szeretném tudásom elmélyíteni a Rényi Intézet kutatói segitségével.

A tervezett kutatas az extremalis halmazrendszerek teruleten belul (1) a metszo illetve Sperner-tulajdonsagu rendszerek altalanositasaival, (2) halmazrendszerek nyomaival (3) a hipergraf Turan temakorrel kapcsolatos problemakkal foglalkozik. Az extremalis grafelmelet teruleterol a graf Turan tipusu kerdesek illetve a Ramsey-Turan tipusu problemak lesznek a kutatas kozeppontjaban.
angol összefoglaló
Hungarian mathematicians have always had an enormous impact on extremal combinatorics. One of the two
topics I would like to research is the area of extremal set systems. Most of its problems can be formulated in the
following (simplified) way: at most how many sets may belong to a system of subsets of a fixed ground set if these sets must satisfy some prescribed property. The other topic is extremal graph theory which mainly considers
problems of determining the minimal or maximal value of some parameter of all graphs satisfying some fixed
property. Both areas attract the attention of many researchers, new and important results have been proved in
recent years. I am familiar with the trends and results about extremal sets systems, most of my
publications and my PhD thesis consider problems from this area of mathematics and the majority of the new results of the project will expectedly come from this topic. As part of the project, I would like to expand my knowledge in extremal graph theory with the help of senior researchers of the Rényi Institute.

The results of the project will be published in international refereed scientific journals. I plan to
submit 3-4 papers per year. The most part of the funding would be spent on costs of international conferences
(travel, accommodation, registration fee). This would help me to popularize the results of my research and also
to keep track of the latest results, trends and open problems in my research areas.




 

Zárójelentés

  
kutatási eredmények (magyarul)
A kutatásom eredményei három kategóriába sorolhatók. Egyrészt az extremális gráfelmélet illetve halmazelmélet témájával foglalkozó cikkeim. Ide főleg a halmazrendszerek nyomaival kapcsolatos eredmények, illetve az irodalomban bevett metszet- vagy tartalmazási feltételek általánosításaihoz kapcsolódó eredmények tartoznak. Másrészt az extremális technikákat alkalmazó, de más kutatási terültek problémáit megoldó eredmények. Itt szerepel például kereséselméleti kérdés, ahol az optimális kérdezési struktúrát az extremális gráfelméletben jól ismert Turán-gráf írja le, vagy a diszkrét geometriai Chen-Chvatal sejtés egy speciális esete, ahol a bizonyítás során egy részben rendezést vezettünk be, majd az extremális halmazrendszerek vizsgálatánál gyakran alkalmazott Dilworth-felbontását tekintettük a részben rendezett halmaznak. Végül a harmadik csoportot azok az eredményeim alkotják, melyek az általam szervezett Emléktábla Műhelyek valamelyikén születtek.
kutatási eredmények (angolul)
The results of my research can be partitioned into three groups. First and foremost, papers in extremal graph theory and extremal set system theory. Mostly, my results on traces of set systems and results concerning generalizations of well-known intersecting and Sperner-type properties belong to this group. Secondly, papers with applications of techniques from extremal combinatorics. A combinatorial search problem can be mentioned herefor which optimal strategies can be described by the Turán graph, a graph well-known and widely used in extremal graph theory. Also we solved a special case of conjecture of Chen and Chvatal in discrete geometry. In our proof we introduced a partial ordering and coonsidered its Dilworth decomposition, a tool appiled very often in extremal set system theory. Finally, the third group consists of those results of mine that were obtained (at least partly) during some of the evets of the Emléktábla Workshop series (founded and organized by myself).
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=83586
döntés eredménye
igen





 

Közleményjegyzék

  
J Barát, Z Füredi, I Kantor, Y Kim, B Patkós: Large B_d-free and union-free subfamilies., SIAM JOURNAL ON DISCRETE MATHEMATICS 26:(1) pp. 71-76. (2012), 2012
D Gerbner, B Keszegh, N Lemons, C Palmer, D Palvolgyi, B Patkos: Saturating Sperner families, In: S Iwata (szerk.) Proceedings of 7th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications. Kyoto, Japán, 2011.05.31-2011.06.03. Kyoto: pp. 341-350, 2011
Dániel Gerbner, Nathan Lemons, Cory Palmer, Dömötör Pálvölgyi, Balázs Patkós and Vajk Szécsi: Almost Cross-Intersecting and Almost Cross-Sperner Pairs of Families of Sets, Graphs and Combinatorics, megjelenes alatt (online first), 2012
Dániel Gerbner, Nathan Lemons, Cory Palmer, Balázs Patkós , Vajk Szécsi: Cross-Sperner families, Studia Scientiarum Mathematicarum Hungarica 49(1) 44-51., 2012
P.L. Erdos, D. Gerbner, N. Lemons, D. Mubayi, C. Palmer, B. Patkos: Two-part set systems, Electronic Journal of Combinatorics, 19 (2012), P52, 2012
B. Patkos: Families that remain k-Sperner even after omitting an element of their ground set, Electronic Journal of Combinatorics, 20, P32,, 2013
B. Patkos: A note on traces of set families, Moscow Journal of Combinatorics and Number Theory, 2, 47-55., 2012
D. Gerbner, N. Lemons, C. Palmer, B. Patkos, V. Szecsi: Almost intersecting families, SIAM J. on Discrete Mathematics, 26, 1657-1669., 2012
Z.L. Nagy, L. Ozkahya, B. Patkos, M. Vizer: On the ratio of maximum and minimum degree in maximal intersecting families, Discrete Mathematics, 313, 207-211., 2013
D. Gerbner, G.O.H. Katona, D. Palvolgyi, B. Patkos: On majority and plurality problems, Discrete Applied Mathematics, megjelenés alatt, 2012
D Gerbner, B Keszegh, N Lemons, C Palmer, D Palvolgyi, B Patkos: Saturating Sperner families, GRAPHS AND COMBINATORICS 29:(5) pp. 1355-1364. (2013), 2013
D. Gerbner, G.O.H. Katona, D. Pálvölgyi, B. Patkós: Majority and plurality problems, DISCRETE APPLIED MATHEMATICS (ISSN: 0166-218X) 161: (6) pp. 813-818. (2013), 2013
D. Gerbner, N. Lemons, C. Palmer, D. Pálvölgyi, B. Patkós, V. Szécsi: Almost Cross-Intersecting and Almost Cross-Sperner Pairs of Families of Sets, GRAPHS AND COMBINATORICS (ISSN: 0911-0119) 29: (3) pp. 489-498. (2013), 2013
Ida Kantor, Balazs Patkos: Towards a de Bruijn–Erdős Theorem in the L1 -Metric, DISCRETE AND COMPUTATIONAL GEOMETRY (ISSN: 0179-5376) 49: pp. 659-670. (2013), 2013
Andrzej Grzesik, Mirjana Mikalački, Zoltán Lóránt Nagy, Alon Naor, Balázs Patkós, Fiona Skerman: Avoider-Enforcer star games, publikálásra beküldve, 2014
Balázs Keszegh, Balázs Patkós, Xuding Zhu: Nonrepetitive colorings of lexicographic product of graphs, publikálásra beküldve, 2014
Balazs Patkos, Mate Vizer: Game saturation of intersecting families, Central European Journal of Mathematics, megjelenés alatt, 2014
Tamás Héger, Balázs Patkós, Marcella Takáts: Search Problems in Vector Spaces, Codes, Designs, and Criptography, megjelenés alatt, DOI 10.1007/s10623-014-9941-9, 2014



vissza »