Hipergá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
VIMA9337 tavasz 2/0/0/v 2.5 1/1
3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,
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:

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

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,
  • Helly-típusú rendszerek,
  • 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

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

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

vima9337.rtf