Hipergráfok, halmazrendszerek kombinatorikája

A tantárgy angol neve: Combinatorics of Hypergraphs and Set Systems

Adatlap utolsó módosítása: 2006. július 1.

Tantárgy lejárati dátuma: 2009. november 24.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Villamosmérnöki Szak

Műszaki Informatika Szak

Választható tárgy
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VIMA9372 tavasz 2/0/0/v 3 1/1
4. A tantárgy előadója

Név:

Beosztás:

Tanszék, Int.:

Dr. Simonyi Gábor

egyetemi docens

Számítástudományi és Információelméleti Tanszék
5. A tantárgy az alábbi témakörök ismeretére épít

Diszkrét matematikai alapfogalmak, gráfelmélet alapjai.

6. Előtanulmányi rend
Ajánlott:

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

7. A tantárgy célkitűzése

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.

8. A tantárgy részletes tematikája

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.
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

Heti két óra előadás

10. Követelmények

a. A szorgalmi időszakban: -

b. A vizsgaidőszakban: szóbeli vizsga

c. Elővizsga: megállapodás alapján

11. Pótlási lehetőségek

-

12. Konzultációs lehetőségek

vizsgák előtt, megbeszélés szerint

13. Jegyzet, tankönyv, felhasználható irodalom

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

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

(a tantárgyhoz tartozó tanulmányi idő körülbelüli felosztása a tanórák, továbbá a házi feladatok és a zárthelyik között (a felkészülésre, ill. a kidolgozásra átlagosan fordítandó/elvárható idők félévi munkaórában, kredit x 30 óra, pl. 5 kredit esetén 150 óra)):

Kontakt óra

30

Félévközi készülés órákra

10

Felkészülés zárthelyire

Házi feladat elkészítése

Kijelölt írásos tananyag elsajátítása

..

Vizsgafelkészülés

50

Összesen

90

15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Simonyi Gábor

egyetemi docens

Számítástudományi és Információelméleti Tanszék

vima9372.rtf