Responsible: Csilla Bujtás
Prerequisites:
- Linear Algebra
- Discrete Mathematics
- Theory of digital computation
- Combinatorial methods and algorithms
Areas covered:
- Interval systems and hypertrees. Helly-property for intervals and subtrees of a tree, optimization algorithms (covering and packing).
- Classical vertex coloring of hypergraphs. Necessary and sufficient conditions for 2-colorability, application of the Lovász Local Lemma. Algorithmic aspects of the corresponding decision problem.
- Mixed hypergraph coloring, estimations on the lower and upper chromatic numbers, chromatic spectrum. Coloring of mixed hypertrees. Color-bounded hypergraphs.
- Transversals and independent vertex sets in uniform hypergraphs, bounds on the transversal number, approximability, Ryser’s conjecture.
- Dominating sets in graphs as transversals in hypergraphs. Dominating vertex sets in hypergraphs.
- Decompositions, Steiner systems. 1-factorization of hypergraphs, Baranyai’s theorem.
- Intersecting set systems, Erdős-Ko-Rado theorem, maximum size of a Sperner system.
Literature:
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. www.cs.elte.hu/~karolyi/tempus.pdf
Voloshin V. Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. Fields Institute Monographs 17, American Mathematical Society, 2002.