Extremal graph theory and extremal set systems  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
83586
Type PD
Principal investigator Patkós, Balázs
Title in Hungarian Extremális gráfelmélet és extremális halmazrendszerek
Title in English Extremal graph theory and extremal set systems
Keywords in Hungarian metszettételek, Sperner-tipusú halamzrendszerek, véletlen gráfok
Keywords in English intersection theorems, Sperner theory, random graphs
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Combinatorial analysis
Panel Natural Sciences Committee Chairs
Department or equivalent Alfréd Rényi Institute of Mathematics
Starting date 2011-03-01
Closing date 2014-02-28
Funding (in million HUF) 14.713
FTE (full time equivalent) 2.39
state closed project
Summary in Hungarian
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.
Summary
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.




 

Final report

  
Results in Hungarian
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.
Results in English
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).
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=83586
Decision
Yes





 

List of publications

  
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



Back »