Tárgyfelelős: Dr. Bujtás Csilla egyetemi docens
Feltételezett előismeretek:
- Lineáris algebra
- Diszkrét matematika
- Digitális számítások elmélete
- Kombinatorikus módszerek és algoritmusok
Tematika:
- Intervallumrendszerek és fahipergráfok. Helly-tulajdonság intervallumokra és fák részfáira, optimalizálási algoritmusok (lefogás, pakolás).
- Hipergráfok klaszikus csúcsszínezése. A 2-színezhetőség szükséges illetve elegendő feltételei, a Lovász Lokális Lemma alkalmazása. Az eldöntési probléma algoritmikus vonatkozásai.
- Vegyes hipergráf színezés, alsó és felső kromatikus szám korlátai, kromatikus spektrum. Vegyes fahipergráfok színezése. Színkorlátos hipergráfok.
- Uniform hipergráfok transzverzálisai és független csúcshalmazai, az optimális lefogásra vonatkozó korlátok, approximálhatóság. Ryser-sejtés.
- Kapcsolat a gráfok dominálási problémáival. Hipergráfok domináló csúcshalmazai.
- Dekompozíciók. Steiner-rendszerek. Hipergráfok 1-faktorizációja, Baranyai tétele.
- Metsző halmazrendszerek, Erdős-Ko-Rado tétel. Sperner-rendszerek maximális mérete.
Irodalom:
Bujtás Cs., Henning M. A., Tuza Zs. Transversals and domination in uniform hypergraphs. Europ. J. Combin. 33 (2012), 62–72.
Bujtás Cs., Tuza Zs. Color-bounded hypergraphs, I. – VI. (article series, 2007–2013)
Bujtás Cs., Tuza Zs., Voloshin V. Hypergraph colouring. in: Beineke L. W. and Wilson R. J. (eds.), Topics in Chromatic Graph Theory, Cambridge University Press, 2015.
van Lint J. H., Wilson R. M.. A Course in Combinatorics (Chapters 6, 19, 38), Cambridge University Press, 2001.
Katona Gy. A simple proof of the Erdös-Chao Ko-Rado theorem. Journal of Combinatorial Theory, Series B 13 (1972), 183–184.
Károlyi Gy. Lectures on extremal set systems and two-colorings of hypergraphs. Online jegyzet:
www.cs.elte.hu/~karolyi/tempus.pdf
Voloshin V. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. Fields Institute Monographs 17, American Mathematical Society, 2002.