SUBJECT

Title

Discrete mathematics

Type of instruction

lecture + practical

Level

master

Faculty

Faculty of Science

Part of degree program

Mathematics MSc

Credits

2+3

Recommended in

Semesters 1-4

Typically offered in

Autumn/Spring semester

Course description

Graph Theory: Colorings of graphs and.hypergraphs, perfect graphs.Matching Theory. Multiple connectivity. Strongly regular graphs, integrality condition and its application. Extremal graphs. Regularity Lemma. Planarity, Kuratowski’s Theorem, drawing graphs on surfaces, minors, Robertson-Seymour Theory.

Fundamental questions of enumerative combinatorics. Generating functions, inversion formulas for partially ordered sets, recurrences. Mechanical summation.Classical counting problems in graph theory, tress, spanning trees, number of 1-factors.

Randomized methods: Expectation and second moment method. Random graphs, threshold functions.

Applications of fields: the linear algebra method, extremal set systems. Finite fields, error correcting codes, perfect codes.

Readings

J. H. van Lint, R.J. Wilson, A course in combinatorics, Cambridge Univ. Press, 1992; 2001.
L. Lovász: Combinatorial Problems and Exercises, AMS, Providence, RI, 2007
R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics,