Kutatásaink témája elsősorban extremális gráfelmélet, Ramsey elmélet gráfokra
és hipergráfokra, ezek alkalmazására például számelméletben, illetve az
ezekhez kapcsolódó módszerek, elsősorban a regularitási lemmák elmélete és
alkalmazása, a pszeudovéletlen gráfok elmélete, és a gráf-limeszek elméletének
és alkalmazásainak kiépítésére, illetve vizsgálatára/alkalmazására irányult.
Kiemelendő a pontos tételek bizonyítása hipergráfok extremális, illetve Ramsey
gráfproblémákra (Füredi-Simonovits-Pikhurko, Haxell at al), A gráf-limeszek
elméletének kidolgozása/alkalmazása, (Borgs, Chayes, Lovász, T. Sós,
Vesztergombi cikksorozat, Lovász-T. Sós, Lovász-Szegedy cikkek, illetve
Elek-Szegedy cikkek, az utóbbiak nem tartoznak pályázatunkhoz.)
A számelméleti alkalmazások között említjük Győri extrém gráfelméleti és
hipergráfelméleti eredményeit.
További eredményeink közül kiemelendő a T. Sós és Saks által indított
Bollobás-Balogh-Sós eredmények a gráfok az öröklődő gráf-tulajdonságokkal
definiált gráf-izomorfiaoszályok számainak és a tipikus szerkezeteiknek
kapcsolatáról, illetve a Balogh-Bollobás-Simonovits eredmények, melyek
Erdós-Frankl-Rődl tételt messze megjavítva struktúrális leírást adnak a
tipikus gráf-szerkezetről.
Results in English
Extremal structures
OTKA closing report T-032810}
Miklós Simonovits
Our research was primarily concentrated on extremal graph theory, Ramsey
Theory, Extremal hypergraph theory their applications, e.g., in Number Theory,
and the methods connected to these areas.
Large part of our research is connected to quasirandom structures, Szemeredi
Regularity Lemma, their connection. Recently much of the research was extended
to a wider area around the Regularity Lemma, and also to the theory of graph
homomorphisms, and graph limits, strongly connected to the above areas. See
the results of Borgs, Chayes, Lovász, T. Sós, Vesztergombi of Lovász-T. Sós,
etc.
We have proved several sharp hypergraph extremal and Ramsey theorems.
Füredi-Simonovits-Pikhurko, Haxell at al.
We also mention our applications to number theory e.g. Győri's $C_6$ theorem,
and related hypergraph results, and some coloring results.
Some number theoretical analogies led to some results of T. Sós és Saks,
connected also to the results of Bollobás-Balogh-Sós-Saks on hereditary
properties of unlabelled graphs.
Finally, we mention the improvements of the Erdős-Frankl-Rődl results, given by
Balogh-Bollobás-Simonovits, on the typical structure of $L$-free graphs.
E. Győri; M. Hornak; C. Parmer; M. Wozniak: General neighbour-distinguishing index of a graph, to appear Discrete Math., 0
E. Győri; Y. Rho: An extremal problem concerning graphs not containing K_t and K_(t,t,t), Discrete Mathematics, 303(2005), 56-64., 2005
Z. Füredi; O. Pikhurko; M. Simonovits: On triple systems with independent neighborhoods, Combin. Probab. Comput. 14(2005), no. 5-6., 795-813., 2005
P. Haxel; T. Luczak; M. Peng; V. Rödl; A. Rucinski; M. Simonovits; J. Skokan: The Ramsey number for hypergraph cycles I., J. Combin. Theory Ser.A 113(1), 67-83., 2006
Z. Kohayakawa; M. Simonovits; J. Skokan: The 3-colored Ramsey number of odd cycles, Proc. of GRACO2005, 397-402 (electronic), Electron. Notes Discrete Math., 19, Elsevier, Amsterdam, 2005
Sós, V. T.: Turbulent years: Erdös in his correspondence with Turán from 1934 to 1940., Paul Erdös and his mathematics, I (Budapest, 1999), 85--146, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002., 2002
R. Dietmann; C. Elsholtz; K. Gyarmati; M. Simonovits: Shifted products that are coprime pure powers, J. Combin. Theory Ser.A 111(2005), no.1, 24-36., 2005
S. Artstein; A. Fraenkel; V.T. Sós: A two-parameter family of an extension of Strumian sequences, to appear in Discrete Mathematics, 0
Y-G. Chen; A. Sárközy; V.T. Sós; M. Tang: On the monotonicity properties of additive representation functions, Bull. Austral. Math. Soc. 72(2005), no.1, 129-138., 2005
P.N. Balister; E. Győri; J. Lehel; R.H. Schelp: Longest paths in circular arc graphs, Combin. Probab. Comput. 13(2004), 311-317., 2005
Mubayi, Dhruv; Sós, Vera T: Explicit constructions of triple systems for Ramsey-Turán problems, J. Graph Theory 52 (2006), no. 3, 211--216., 2006
Ch. Borgs, J. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi: Graph limits and parameter testing, STOC 2006, p.261-270, 2006
Simonovits, Miklós; Sós, Vera T: A hierarchy of randomness for graphs., Discrete Math. 303 (2005), no. 1-3, 209--233., 2005
Chen, Yong-Gao; Sárközy, András; Sós, Vera T.; Tang, Min: On the monotonicity properties of additive representation functions, Bull. Austral Math. Soc. 72 (2005), no. 1, 129--138., 2005
Elek, Gábor; Sós, Vera T.: Paradoxical decompositions and growth conditions, Combin. Probab. Comput. 14 (2005), no. 1-2, 81--105., 2005
Simonovits, Miklós; Sós, Vera T: Different levels of randomness in random Ramsey theorems, Electronic notes in discrete mathematics. Vol. 15, 191--194 (electronic), Electron. Notes Discrete Math., 15, Elsevier, Amsterdam, 2003., 2003
Simonovits, Miklós; Sós, Vera T: Hereditary extended properties, quasi-random graphs and induced subgraphs, Combinatorics, probability and computing (Oberwolfach, 2001). Combin. Probab. Comput. 12 (2003), no. 3, 319-344, 2003
Györi, Ervin; Schelp: Two-edge colorings of graphs with bounded degree in both colors, Combinatorics, graph theory and computing (Louisville,KY, 1999). Discrete Math. 249 (2002), no. 1-3, 105--110., 2002
Füredi, Zoltán; Pikhurko, Oleg; Simonovits, Miklós: 4-books of three pages, J. Combin. Theory Ser. A 113 (2006), no. 5, 882--891, 2006
Haxell, P. E.; Luczak, T.; Peng, Y.; Rödl, V.; Rucinski, A., Simonovits, M.; Skokan, J.: The Ramsey number of hypergraph cycles. I, J. Combin. Theory Ser. A 113 (2006), no. 1, 67--83., 2006
Kohayakawa, Yoshiharu; Simonovits, Miklós; Skokan, Jozef: The 3-colored Ramsey number of odd cycles, Proceedings of GRACO2005, 397--402 (electronic), Electron. Notes Discrete Math., 19, Elsevier, Amsterdam, 2005., 2005
Balogh, József; Bollobás, Béla; Simonovits, Miklós: The number of graphs without forbidden subgraphs, J. Combin. Theory Ser. B 91 (2004), no. 1, 1--24., 2004
Simonovits, Miklós: How to compute the volume in high dimension?, ISMP, 2003 (Copenhagen). Math. Program. 97 (2003), no. 1-2, Ser. B, 337--374., 2003
Füredi, Zoltán; Pikhurko, Oleg; Simonovits, Miklós: The Turán density of the hypergraph {abc,ade,bde,cde}, Electron. J. Combin. 10 (2003), Research Paper 18, 7 pp. (electronic)., 2003