Kombinatorikus problémamegoldó és kutatószeminárium (2019. tavasz)



  • IDŐPONT, hely: csütörtök 16:15-17:45, 1-105 (Cholnoky);

  • Célok:
  • problémammegoldási eszköztár bővítése,
  • kutatáscentrikus gondolkodás: a megismerttel analóg helyzetben, vagy általánosan mit mondhatunk? melyik feltételt mennyivel gyengíthetjük? Hogyan lehet általánosítani?
  • kutatatást segítő háttér megismerése
  • meghívott előadókon keresztül egyéni tapasztalatok megismerése


  • Néhány ajánlott irodalom :
  • Aigner - Ziegler: Bizonyítások a könyvből (Typotex, neten angolul is fellelhető) - központi problémák és elegáns bizonyítási technikák, látókörszélesítés
  • Lovász László: Kombinatorikai problémák és feladatok - kombinatorikus gondolkozás feladatmegoldásokon keresztül.
  • Bondy - Murty: Graph Theory (könyv, fejezetenként gyakorlófeladatokkal - neten angolul fellelhető)
  • Témakörök, feladatsorok, kitekintés - 2019. tavasz:


    1. feladatsor - Gráfok és szimmetriák (katt)

    Egy rövidebb topologikus biz a Kneser-gráfok kromatikus számáról - Greene biz. feldolgozása

    2. feladatsor - 2 átmérőjű Moore-gráfok (katt)

    Hoffman és Singleton cikke (1960)


    3. feladatsor - Vegyes feladatok-gráfparaméterek (katt)


    4. feladatsor - Erdős-Rogers függvény: K_t mentes gráfok nagy K_s mentes részgráfjai (katt)

    Janzer Olivér előadása kapcsán. Olivér Tim Gowers-szel közös vonatkozó cikke


    5. feladatsor - Reguláris gráfok, 1-faktorok, d-faktorok, Latin négyzetek (katt)

    M. D. Plummer survey cikke faktorizációkról

    Ian Wanless survey cikke Latin négyzetek kapcsán


    6. feladatsor - Minorok, síkgráfok, dependent random choice (katt)

    kis írás a Robertson-Seymour tétel környékéről: jellemzés kizárt minorokkal

    Jacob Fox és Benny Sudakov cikke a Dependent Random choice technikáról


    Témakörök, feladatsorok, kitekintés - 2018. ősz:


    1. feladatsor - Sylvester-Gallai probléma, körök extremális problémái (katt)

    Ajánlott további böngésznivaló: Terry Tao blogbejegyzése a Sylvester-Gallai probléma általánosításáról
                    egy további összefoglaló cikk a témáról, néhány bizonyítással és biz. ötlettel (Brönnimann, Lechner)

    rövid bejegyzés irodalommal a kapcsolatról az élsűrűség a és a gráfban megjelenő adott méretű páros körök között

    2. feladatsor - Irányított gráfok (katt)

    Erősen összefüggő komponensek keresése; Irányított Hamilton út ill kör keresése: ez irányított esetben egyszerűbb mint irányítatlan esetben.
    Pár kapcsolódó cikk:
        Bondy és Thomassen egyszerű bizonyítása a Hamilton-körre (Meyniel-t.)
        néhány további elégséges feltétel és nyitott kérdés (Kühn, Osthus)

    3. feladatsor - Hipergráfok: élszám a színezések, metszési számok és halmazméretek függvényében (katt)

    Módszerek: Valószínűségi; indukció, aritmetikai konstrukciók.

    További olvasnivalók: Lovász László ajánlott problémakönyve, 13. fejezet;
        Ryser sejtésről
        Erdős-Faber Lovász sejtésről

    4. feladatsor -Élszínezések és extrémitás: Ramsey és Antiramsey probléma különböző gráfokra (katt)

    Ramsey: éleket színezünk adott számú színnel, monokromatikus adott méretű klikkre ill általánosan F részgráfra szeretnénk garanciát: ehhez szükséges csúcsszám. R(F,F,F...F) (színek száma a paraméterek száma)
    Anti-Ramsey: éleket színezünk K_n-ben, szivárvány= rainbow=csupa-különböző-színű-élű F részgráfra szeretnénk garanciát: ehhez szükséges színszám. AR(n,F).

    Vizsgált kérdéseink a klasszikus klikk után: F=tK_2, F=P_k, F=C_k.
    Tipikus módszerek és eredményekről itt (Ramsey, utak és körök, 2017) és itt (Ramsey-típusú, 3 útra éles, Pokrovskiy) és itt (Anti-Ramsey, párosítások, utak, körök)

    5. feladatsor - Felbontások: Teljes gráfok és hipergráfok feélbontásai fix részgráfokra, részhipergráfokra (katt)

    Főtéma: K_n élfelbontása F részgráffal izomorf példányokra; és ennek általánosítása.
    F = K_k eset: Steiner rendszerek. Állítás: ha a nyilvánvaló feltételek teljesülnek (ami a fokszámokra és az élszámra vonatkozik), akkor elegendően nagy n esetén a felbontás megvalósítható. (Wilson, '73)
        Ennek általánosítása Peter Keevash eredménye (2014): amikor K_n helyett az n-csúcsú r-uniform teljes gráf élhalmazát bontjuk fel hasonlóan. Rövid áttekintés, ill. Keevash (mély) cikke
    F=C_k eset. Itt is a nyilvánvaló szükséges feltétel elégséges is, minden n-re, ha k páros.
        Kapcsolódó kérdés az Oberwolfach-probléma.
    F= tK_2 általánosítása hipergráfokra: Baranyai tétele

    További olvasnivaló a Graham-Pollak tétel általánosításáról amikor teljes r-uniform hipergráfot bontunk r-uniform, r-osztályú családokra..

    A félév során még vizsgált témakörök - Csikvári Péter feladatsorai:
  • Várható érték módszerről (első) (második)
  • Függetlenségi és kromatikus polinomok (katt)
  • Reguláris gráfok paraméterei (katt)
  • Vegyes katt
  • Csikvári Péter honlapja

    Visszatérhetsz a főoldalra