HUN-REN Institute for Computer Science and Control
Participants
Ruszinkó, Miklós Sarkozy, Gabor
Starting date
2007-07-01
Closing date
2011-07-31
Funding (in million HUF)
9.073
FTE (full time equivalent)
4.46
state
closed project
Summary in Hungarian
E kutatási pályázattal szeretnénk folytatni az extremális diszkrét matematika területén végzett kutatásainkat. E terület központi kérdése a következő: határozzuk meg egy adott feltételt kielégítő diszkrét matematikai objektum maximális (vagy minimális) méretét. Ez az általános téma szorosan kapcsolódik a matematika számos más ágához (pl. geometria, design elmélet, számelmélet, algebra, topológia, stb.) illetve olyan területekhez amelyek fontos alkalmazásokkal rendelkeznek a mindennapi életben (pl. számítógéptudomány, kódelmélet, kriptográfia, optimalizálás, kommunikációs és hálózati problémák, stb.). Ezért a javasolt problémákon elért eredményeknek komoly következményei lehetnek ezekben az alkalmazásokban is.
Summary
We plan to continue our research in the area of extremal discrete mathematics. The central question of this field has the following form: determine the maximum (or minimum) size of a discrete mathematical object that satisfies a certain condition. It turns out that this general topic has connections to very diverse fields (geometry, design theory, number theory, algebra, topology, etc.) and to areas with important concrete applications in everyday life (computer science, coding theory, cryptography, optimization and scheduling problems, communication and networking problems, etc.). Therefore the broader impact of this proposal is that achieving results on the proposed research problems will have serious implications in these applications as well.
Final report
Results in Hungarian
A négy éves projekt során 17 cikkünk jelent meg, 2 nyomdában van, 2 elfogadott és 2 benyújtott. Örvendetes, hogy a pályázókon kivül sikerült 17 további kutatót (fiatalokat és szeniorokat egyaránt) megnyerni témáinknak, melyeket - némi önkénnyel - igy csoportositok (a számok a közlemények sorszámai a zárójelentésből):
1. Ramsey elmélet. Kiemelem a regularitás lemma új alkalmazásait, melyek a terület előtérben lévő kutatásaihoz tartoznak, pl. 3,4,8,9,10,16,17 - legtöbbjükben társszerző Szemerédi Endre is. Jelentős cikknek tartom a 6. könyvfejezetet is, mely egy utóbbi időben egyre aktivabb területet foglal össze.
2. Gallai szinezések. Ez valójában a Ramsey elmélet ás extremális kombinatorika határán van, izgalmas, de nehéz kérdéseket vet fel Gallai egy alapvető technikájának általánositási lehetőségeiről, 1,11,18.
3. Kódok és extremális problémák. Kiemelendő Füredi és Ruszinkó 23-as igen tartalmas és gondosan megirt cikke, melyet az Advances in Mathematicshoz nyujtottak be és 7. cikk, mely gráfok perfektségének alapvető mértékszámát kapcsolja össze a Ramsey gráfok elméletével. Néhány további eredményünk (14, 19,20,21) nem kapcsolódik alapvető témákhoz, de azokban is új eredményeket fejlesztünk tovább az extremális gráf és hipergráfelmélet területéről.
Results in English
During the four year project 17 papers are published, 2 in press, 2 are accepted and 2 are submitted. We are glad that apart from the three persons participating in the project, we could attract 17 further researchers (both young and seniors) to our subjects. Somewhat arbitrarily, these subjects can be grouped as follows (the numbers refer to the numbering of the list of publications).
1.Ramsey theory. I pinpoint some new applications of the Regularity Lemma related to recent research areas, namely 3,4,8,9,10,16,17 - most with coauthor Endre Szemerédi. I think that 6., a book chapter is also significant, reviewing an area with increasing of present activity.
2. Gallai colorings. This area is on the border of Ramsey theory and extremal combinatorics, posing exciting but difficult questions on possible extensions of a basic technique of Gallai, 1,11,18.
3. Codes and extremal problems. Here I emphasize 23, a deep and carefully written paper of Füredi and Ruszinkó submitted to Advances in Mathematics and 7, which relates a basic measure of perfectness of graphs to the theory of Ramsey graphs. Some of our further results (14,19,20,21) does not relate to basic results but still extends recent results of extremal graph and hypergraph theory.
Gyárfás A. - Sárközy G. - Szemerédi E.: Long monochromatic Berge cycles in colored 4-uniform hypergraphs, Graphs and Combinatorics, 26. (2o1o) 71-76., 2010
Gyárfás A. - Sárközy G. - Sebő A. - Selkow S: Ramsey-type results for Gallai colorings, Journal of Graph Theory, 64 (3) (2oo9) 233-243., 2009
Gyárfás A.- Mhalla M.: Ramsey-type results for Gallai colorings, Journal of Combinatorial Designs, 18. (3), 2010
Gyárfás A.- Sárközy G. Szemerédi E.: The stability of the path - path Ramsey number, Discrete Mathematics, 3o9 (2oo9) 459o-4595., 2009
Gyárfás A.- Sárközy G. -Szemerédi E.: Monochromatic matchings in the shadow graph of almost complete hypergraphs, Annals of Combinatorics, 14, (2) (2o1o) 245-249., 2009
Gyárfás A.- Haxell P.: Large monochromatic components in colorings of complete 3-uniform hypergraphs, Discrete Mathematics, 3o9, (2oo9) 3156-316o, 2009
Gyárfás A. - Sárközy G.,: Gallai colorings of non-complete graphs, Discrete Mathematics, 31o, (2o1o)977-98o., 2010
1. I. Levitt, G.N. Sárközy, E. Szemerédi: How to avoid using the Regularity Lemma; Pósa's Conjecture revisited, Discrete Mathematics 310, 2010, pp. 630-641., 2010
A.Gyárfás- J.Lehel: Trees in Greedy colorings of hypergraphs, Discrete Mathematics, 2011
A.Gyárfás - M. Ruszinkó - G. Sárközy - R.H. Schelp: Long rainbow cycles in proper edge-colorings of complete graphs, Australasian J. of Combinatorics, 50, 2011
A. Gyárfás: Large monochromatic components in edge coloring of graphs, Springer - Brickhauser, Advances in Mathematics, volume 285, 2010
A. Gyárfás: Ramsey and Turán type problems for non-crossing subgraphs of bipartite geometric graphs, Annales Eötvös L. Sect. Mathematica, 2011
A. Gyárfás, G. Sárközy: The 3-colour Ramsey number of a 3-uniform Berge cycle, Combinatorics, Probability and Computing, 20, 2011
A. Gyárfás, M. Ruszinkó - G. Sárközy, E.Szemerédi: Partitioning 3-colored complete graphs into three monochromatic cycles, Electronic J. of Combinatorics, 18, P53, 2011
M.Ruszinkó: Large monochromatic components in r-edge colorings of K have diameter at most five, Journal of Graph Theory, in press, 2010
G.N.Sárközy: Monochromatic cycle partitions of edge colored graphs, Journal of Graph Theory, 2010
G.N.Sárközy, S.Selkow, F. Song: Vertex partitions of non-complete graphs by connected monochromatic k-regular graphs, Journal of Graph Theory IN PRESS, 2011
A. Gyárfás, G.Simonyi, Á. Tóth, Accepted to: Gallai colorings and domination in multipartite digraphs, Journal of Graph theory, ACCEPTED, 2011
A.Gyárfás - G.Raeisi: Ramsey number of loose triangles and quadrangles in hypergraphs, Electronic J. of Combinatorics, SUBMITTED, 2011
A. Gyárfás, - A. Sebő - N. Trotignon, ,: The chromatic gap and its extremes, Journal of Combinatorial Thoery B SUBMITTED, 2010
V.Campos, A. Gyárfás, F. Havet, C.L. Sales, F. Maffray: New bounds on the Grundy number of product graphs, Journal of graph Theory, ACCEPTED, 2010
Z. Füredi - M. Ruszinkó, , Advances in Mathematics, submitted to: Uniform hypergraphs Containing no grids, Advances in Mathematics, SUBMITTED, 2011
Gyárfás A. - Sárközy G. - Szemerédi E.: Monochromatic Hamiltonian 3-tight Berge cycles in 2-colored 4-uniform hypergraphs, Journal of Graph Theory, 63. (2o1o) 34-44, 2010
