Válogatott fejezetek az Extremális Kombinatorikából

Győri Ervin és Simonovits Miklós

Időpont: Kedd 14-15.30

Hely: ELTE TTK D 3716

Elérhetőségem a főlapon: miki@renyi.hu, tel: otthon: 3-320-318.

Győri Ervin: ervin@renyi.hu, 4838-319 (Mat. Kutató)

Az előadások időpontjai és cimei

Az alábbiakban megadott vázlatokat az előadás csak lazán követi!

Február 14: Ismerkedés, rövid bevezető,

• Kezdetek: Erdős egy problémája a különböző szorzatokról
• A 4-kör problémája
• Turán tétele
• Kővári-T. Sós-Turán
• Véges Geometriai konstrukciók

  Február 21: Néhány alaptétel

• Erdős-Stone-Simonovits
• Strukturális stabilitás
• A Dekompozició osztály definiciói, felhasználása
• Turán hipergráf sejtés
  
• A Fano hipergráf probléma
  

• Gráfok körei

• Bondy-Simonovits tétel
• Erdős-Pósa tétel
• Számelméleti alkalmazások

  ---

  Geometriai Alkalmazások

  Összefüggőség és extremalitás

  Vizsgakövetelmények

  (1) Aktiv részvétel az órákon
  (2) Egy cikk előadása
  (3) Mini-vizsga: a főbb tételek, definiciók ismerete, pontos kimondása

  ---

  Tematika

• Bevezetés
• Aszimptotikus extrémek strukturája
• Elfajult extremalis gráf problémák
• Túltelített gráfok

  ---

  Ajánlott irodalom:

• B. Bollobás: Extremal Graph Theory
• Art of Counting, Erdős összgyüjtött, válogatott kombinatorika cikkei, megtalálható pl. A Mat. Kutató kézi k0nyvtárában.

  Fejezetek a Handbook of Combinatorics-bol

• Bollobás
• Bondy
• Alon

  Ajánlott irodalom: CIKKEK

• Bondy, J. A., and M. Simonovits: Cycles of even length in graphs, JCT 16B(2) April (1974) 97-105.
• Füredi, Zoltán: The maximum number of edges in a minimal graph of diameter $2$. J. Graph Theory 16 (1992), no. 1, 81--98.
• Füredi, Zoltán: On a Turán type problem of Erdős. Combinatorica 11 (1991), no. 1, 75--79.
• Erdös, P.; Pósa, L. On independent circuits contained in a graph. Canad. J. Math. 17 1965 347--352
• Bollobás, Béla; Thomason, Andrew Highly linked graphs. Combinatorica 16 (1996), no. 3, 313--320.
• Györi, Ervin, $C\sb 6$-free bipartite graphs and product representation of squares. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 371--375.
• Györi, E. On the number of $C\sb 5$'s in a triangle-free graph. Combinatorica 9 (1989), no. 1, 101--102.
• Häggkvist, Roland; Thomassen, Carsten Circuits through specified edges. Discrete Math. 41 (1982), no. 1, 29--34.
• L. Lov\'asz: Independent sets in critical chromatic graphs, Studia Sci. Math. Hungar. {\bf 8} (1973) 165-168; MR{\bf 48}\#8289.
• G. A. Margulis: Explicit constructions of graphs without short cycles and low density codes, Combinatorica, 2(1) (1982) 71-78.
• L. Pyber: Regular subgraphs of dense graphs, Combinatorica {\bf 5} (4) (1985) 347-349.

  Szakfolyóiratok

• Combinatorica
• JCTB (Journal of Combinatorial Theory, (B))
• Journal of Graph Theory
• Random Structures and Algorithms
• Combinatorics, Probability and Computation

  Innen letölthető survey cikkek

• M. Simonovits and Vera T. Sós, Ramsey-Turán theory. Combinatorics, graph theory, algorithms and applications. Discrete Math. 229 (2001), no. 1-3, 293--340. [PS] [PDF]
• W. G. Brown and M. Simonovits, Extremal multigraph and digraph problems, in Paul Erdős and his mathematics, II. Springer 2002 [PS] [PDF]
• Some of my Favorite Erdős Theorems and related results, theories in Paul Erdős and his mathematics, II. Springer 2002 [PS] [PDF]
• J. Komlós and M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory. Combinatorics, Paul Erdös is eighty, Vol. 2 (Keszthely, 1993), 295--352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996. [PS] [PDF]