Tantárgy » BMEVIMA9372
Hipergráfok, halmazrendszerek kombinatorikája
Combinatorics of Hypergraphs and Set Systems
A tantárgyleírás hatályossága
Hatályosság kezdete:
—
Hatályosság vége:
—
| Tantárgy neve (magyarul, angolul) |
Hipergráfok, halmazrendszerek kombinatorikája
Combinatorics of Hypergraphs and Set Systems
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tantárgykód | BMEVIMA9372 | ||||||||||||
| Tantárgyjelleg | — | ||||||||||||
| Képzési szint | — | ||||||||||||
| Kurzustípusok és óraszámok (heti/féléves) |
|
||||||||||||
| Tanulmányi teljesítmény/értékelés típusa | vizsga | ||||||||||||
| Tantárgy kreditértéke | 3 | ||||||||||||
| Tantárgyfelelős |
Dr. Simonyi Gábor
elérhetőség:
simonyi@math-inst.hu
|
||||||||||||
| Tantárgyat gondozó oktatási szervezeti egység |
—
|
||||||||||||
| Kar | |||||||||||||
| Tantárgy weboldala | — | ||||||||||||
| Tantárgy elsődleges mintatantervi jellege | — | ||||||||||||
| Közvetlen előkövetelmények – Erős előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Gyenge előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Párhuzamos előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Mérföldkő előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Kizáró feltétel | nincs |
Célkitűzés
Tantárgyprogram
Az alapfogalmak (ezen belül a hipergráfok, halmazrendszerek, 0 – 1 sorozathalmazok fogalmi ekvivalenciájának) tisztázása után tárgyalandó témakörök:
- Sperner rendszerek (Sperner-tétel, LYM-egyenlőtlenség, Ahlswede-Zhang azonosság),
- metsző rendszerek (Erdős-Ko-Rado tétel, Frankl-Wilson tétel, Borsuk-sejtés Kahn-Kalai féle cáfolata),
- halmazrendszerek "árnyéka" (Kruskal-Katona tétel),
- Turán-tétel hipergráfos analogonjai (Erdős-Katona probléma, Shearer-konstrukció, Tolhuizen-tétel),
- perfekt gráf tétel bizonyítása hipergráfok segítségével
- telített és Ä-kritikus rendszerek (Bollobás-egyenlőtlenség és következményei)
- faktorizációs tételek és alkalmazásaik,
- többrendszeres egyenlőtlenségek (Ahlswede-Daykin egyenlőtlenség és speciális esetei),
- extremális halmazelméleti problémák tárgyalása irányított gráfok kapacitáskérdéseiként.
A diszkrét matematikai gondolkodásmód fejlesztése, elmélyítése; hipergráfokkal, illetve véges halmazok részhalmazrendszereivel kapcsolatos tételek megismertetése.
Tanulmányi eredmények
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Tudás
Nincsenek rögzített tanulási eredmények.
Képességek
Nincsenek rögzített tanulási eredmények.
Attitűd
Nincsenek rögzített tanulási eredmények.
Autonómia és felelősség
Nincsenek rögzített tanulási eredmények.
Oktatási módszertan
Heti két óra előadás
Tanulástámogató anyagok
Online források
A vizsgára való felkészülés fő segédanyaga az előadásokon készített jegyzet. Az előadások anyagának jelentős része megtalálható az alábbi, valószínűleg nehezen hozzáférhető könyvben:; B. Bollobás: Combinatorics – Set systems, Hypergraphs, Families of Vectors and Combinatorial Probability, Cambridge University Press, Cambridge, 1986; Háttéranyagként jól használható még: Lovász László: Kombinatorikai problémák és feladatok, Typotex Kiadó, Budapest, 1999,; illetve ugyane könyv eredeti, angol nyelvű változata: L. Lovász: Combinatorial Problems and Exercises, Akadémiai Kiadó, Budapest, 1993
A tantárgy teljesítéséhez ajánlott előzetes ismeretek
Tudás típusú kompetenciák
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
Diszkrét matematikai alapfogalmak, gráfelmélet alapjai.
Képesség típusú kompetenciák
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
Diszkrét matematikai alapfogalmak, gráfelmélet alapjai.
Általános szabályok
Követelmények:
a. A szorgalmi időszakban: -
b. A vizsgaidőszakban: szóbeli vizsga
c. Elővizsga: megállapodás alapján
Pótlási lehetőségek:
-
Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Szorgalmi időszakban végzett teljesítményértékelések részaránya
Nincs megadva részarány.
Vizsgaidőszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Vizsgarészek részaránya
Nincs megadva részarány.
Érdemjegy megállapítása
Nincs megadva érdemjegy határ.
Jelenléti és részvételi követelmények
Nincs megadva jelenléti követelmény.
Javítás, ismétlés és pótlás különös szabályai
Nincs megadva.
Rövid leírás
Nincs megadva.
Részletes leírás
Nincs megadva.
Ajánlott tantárgyak
Ajánlott:
Bevezető gráfelméleti kurzus elvégzése után célszerű felvenni.
Tematikaütközés miatt a tárgyat csak azok vehetik fel, akik korábban nem hallgatták a következő tárgyakat:
Neptun-kód Cím : korábban a tárgy azonos címmel, de bmevima9337 kóddal ment
A tantárgy elvégzéséhez szükséges tanulmányi munka
Nincs megadva munkaidő bontás.
Tantárgykövetelmények hatályossága
Tantárgykövetelmények hatályosságának kezdete:
—
Tantárgykövetelmények hatályosságának vége:
—
Tantervi elhelyezés
Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.