Kombinatorikus problémamegoldó és kutatószeminárium (2020. ősz)



  • IDŐPONT, hely: kedd 16:00-17:30, online ;

    • 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
  • válogatott cikkek feldolgozása


    • 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ő)
  • Jukna - Extremal combonatorics, Springer

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

    9. feladatsor - vegyes extremális (katt)

    8. feladatsor - színezéses feladatok (Csiki) - a blogon

    7. feladatsor - vegyes extremális (katt)

    Kapcsolódó eredmények, cikkek:
  • Gyárfás, Hubenko and Solymosi (2002) cikke feszített C_4-mentességről

  • Szabó Tibor jegyzete cikke Ramsey R(3,k)-ról.

  • Bollobás és Győri cikke háromszögszámról C_5-mentes gráfokban.

    • 6. feladatsor - klikkek száma (Csiki) - a blogon

    5. feladatsor - Schweitzer M. emlékverseny

    4. feladatsor - Napraforgók (katt)

    Kapcsolódó eredmények, cikkek:
  • Polymath 10-ről jegyzet amelyben az Erdős-Szemerédi féle Napraforgó sejtés r=3-ra nyer bizonyítást nem-uniform esetben (Gil Kalai blogja)
  • A Quanta magazin írása Mathematicians-begin-to-tame-wild-sunflower-problem
  • az előző ismeretterjesztő cikk alapja, Improved bounds for the sunflower lemma Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang cikke


    • 3. feladatsor - hipergráfok: konstrukciók és becslések. (katt)

    3. alkalom: Előadást hallgatunk a Rényiből online, erről a cikkről a többszínű Ramsey-problémában elért áttörésről.

    2. feladatsor - kromatikus polinom kapcsán (Csiki). Ez a blogunkon érhető el.

    1. feladatsor - Extremális kombinatorika: körmentesség gráfokban. (katt)

    Kapcsolódó eredmények, cikkek:
  • extremális kérdések hiperkockában, Noga Alon, Anja Krech, Tibor Szabó cikke
  • videó x^2+y^2=m megoldásszáma kapcsán ami a négyzetrácshálóban előforduló rögzített távolságok számában játszik kulcszerepet. Egy meglepő és szórakoztató bijekciós kombinatorikai biz egy számelméleti kérdésre.


    • Lista választható cikkekből.
  • Hadwiger meets Cayley, by J W. Cooper, A. Kabela, D.Král’, T. Pierron (feszítőfák száma a kromatikus szám függvényében, 3 oldal), Kovács Benedeké

  • A note on dense bipartite induced subgraphs by Stefan Glock, (arról, hogy relatív sűrű feszített páros részgráfot keresnénk, 3 oldal)

  • A note on the largest induced matching in graphs without short cycles by D.Reichman, B. Lund (arról hogy feszített párosítások max mérete némileg analóg a ma ftln ponthalmazok méretével, 4.oldal)

  • Some remarks on the Zarankiewicz problem by D. Conlon. (A Zarankiewiczre ad jóféle random algebrai (polinomos) alsó korlátot. Elmondani az egyszerűbb verzióban érdemes 5.o.)

  • TURAN’S THEOREM IMPLIES STANLEY’S BOUND by Nikiforov. ( sajátértékbecslés élszám függvényében).

  • Turan type results for intersection graphs of boxes by I Tomon, D Zakharov. (Téglák metszetgráfjáról kizárt részgráfok mellett, boxicityvel. 4. oldal)



    • Témakörök, feladatsorok, kitekintés - 2020. tavasz:


    1. feladatsor - Vegyes feladatsor. (katt)

    Megjegyzések: Síkgráfoknál példa nem 4-listaszínezhetőségre: M. Voigt. Az 5-listaszínezhetőség bizonyítása: Carsten Thomassen. (keress rá a Scholaron!)

    2. feladatsor - Vegyes feladatsor, gráftranszformációk. (katt) (Csikié)

    Megjegyzések: A 4. feladat kapcsán érdekes kitekintés lehet a probléma kapcsolódási pontjaira ez a tézis

    3. feladatsor - Extremális feladatsor. (katt)

    Innentől a kombinatorikai blogot használjuk paformként, ahol megjegyzésként be lehet írni a feladatokra születő megoldásokat. Csiki küld meghívót mindnenkinek.

    4. feladatsor - Törtkromatikus/törtfedési szám feladatsor. (Csikié)


    5. feladatsor - Intervallumos feladatsor. (katt)


    6. feladatsor - régebbi Schweitzeres feladatsor. (katt)



    Feldolgozandó cikkek listája és a vállalkozók monogramja
  • Mon. növő sétákról: Graham, Kleitman (Régi, vannak újabb eredmények); -> Sz. L.
    • Levi slide-jai
  • Short proofs of extremal results: Conlon, Fox, Sudakov (2. és 3. fejezet) -> N.G.
  • Hosszú számtani sorozatok független halmazon, ha G[n] nem túl sűrű: Conlon, Fox, Sudakov ->

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


    1. feladatsor - Gráfok algebrai leírása: spektrálgráfelmélet, 1. (katt)



    2. feladatsor - Gráfok algebrai leírása: spektrálgráfelmélet, 2. (katt)

     páros gráfok spektrálsugaráról (Liu, Weng)
    séták leszámolása és sajátértékek kapcsolata (Stevanovic)
    J. Fox jegyzete, benne a Petersenekre bontás


    3. feladatsor - Gráfok algebrai leírása: spektrálgráfelmélet, 3. (katt)

    További ajánlott irodalom:
  • J. Matousek: Thirty-three miniatures
  • A. Brouwer, W. Haemers: Spectra of Graphs



    • 4. feladatsor - Kun Gábor EA-ához: Lokál Lemma (katt)



    5. feladatsor - Nagy Dani EA-ához: Extremális halmazrendszerek (katt)



    Feldolgozandó cikkek listája és a vállalkozók monogramja
  • Acute sets of exponentially optimal size -> A.M.
  • Counterexamples to Hedetniemi's conjecture ->
  • On the Erdős-Szekeres convex polygon problem -> I.A.
  • Maximum matchings of regular graphs of high girth -> S.Á.
  • Short proofs of classical theorems -> Z.Á.
  • The trivial lower bound for the girth of S_n -> B.M.
  • On large subsets of F_q^n with no three term arithmetic progression -> M.D.
  • Rational exponents in extremal graph theory - Boris Bukh, David Conlon N.K.
  • r-graphs without 3 edges on r + 2 vertices - Alexander Sidorenko -> Sz.K.
  • Many T copies in H-free graphs -- Noga Alon, Clara Shikhelman
  • More on graphswith just three distinct eigenvalues - Rowlinson -> G.A.

    • 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

    7. feladatsor -Topologikus módszerek (katt), Huszár Kristóf előadása (IST, Austria)


    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