Extremal structures  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
38210
Type K
Principal investigator Simonovits, Miklós
Title in Hungarian Extremális struktúrák
Title in English Extremal structures
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Gyori, Ervin
T. Sós, Vera
Starting date 2002-01-01
Closing date 2006-12-31
Funding (in million HUF) 9.419
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
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.
Full text http://real.mtak.hu/507/
Decision
Yes





 

List of publications

  
P.N. Balister; E. Győri; J. Lehel; R.H. Schelp: Adjacent vertex distinguishing edge-colorings, to appear SIAM J on Discrete Math., 0
Györi, E.; Nikiforov, V.; Schelp, R. H.: Nearly bipartite graphs, Discrete Math. 272 (2003), no. 2-3, 187--196., 2003
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
Györi, Ervin: Triangle-free hypergraphs, Combin. Probab. Comput. 15 (2006), no. 1-2, 185--191., 2006
A. Bíró; V.T. Sós: Strong characterizing sequences in simultaneous Diophantine approximation, J. Number Theory, 99(2003), no.2, 405-414., 2003
M. Simonovits; V.T. Sós: A hierearchy of randomness for graphs, Discrete Math., 303(1-3), 209-233., 2005
P.N. Balister; E. Győri; J. Lehel; R.H. Schelp: On the edge number of connected graphs not containing paths of length k, to appear Discrete Math., 0
E. Győri: On the edge number of unbalanced C_6-free bipartite graphs, to appear in Comb. Prob. Comp., 0
B. Bollobás; E. Győri: Pentagonfree graphs and hypergraphs, to appear in Discrete Mathematics, 0
Füredi, Zoltán; Simonovits, Miklós: Triple systems not containing a Fano configuration, Combin. Probab. Comput. 14 (2005), no. 4, 467--484., 2005
Borgs, Christian; Chayes, Jennifer; Lovász, László; Sós, Vera T; Vesztergombi, Katalin: Counting graph homomorphisms., Topics in discrete mathematics 315--371, Algorithms Combin., 26, Springer, Berlin, 2006., 2006
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



Back »