Objectives and competences
To deepen the knowledge of more demanding areas of temporary discrete mathematics and its applications: algebraic combinatorics, error-correcting codes, additional topics from graph theory, combinatorics of partially ordered sets, tools from linear algebra in discrete mathematics, and Ramsey theory.
Content (Syllabus outline)
Algebraic combinatorics; generating functions; applications of generating functions (Catalan numbers, partitions of a positive integer); cyclic index; Polya theory; linear algebra in discrete mathematics (designs and Fisher's inequality; coverings with complete bipartite graphs; cycle space, circulations and cuts; applications of eigenvalues).
Error-correcting codes: basic concepts; linear codes; constructions of linear codes; correcting errors; cyclic codes; classification of cyclic codes.
Graph theory: additional graph coloring topics (proof of Brooks theorem, critical graphs, circular colorings); k-connected graphs (proof of Menger's theorem); networks and flows in networks; proof of Kuratowski theorem; independent and dominating sets.
Combinatorics of partially ordered sets: linear extensions; dimension of a partial order; Dilworth's theorem; Sperner's theorem. Schnyder's theorem.
Ramsey theory: number of monochromatic triangles; Ramsey theorem; Ramsey numbers; applications of the theorem, graph Ramsey numbers.
Learning and teaching methods
Lectures
Tutorial
Intended learning outcomes - knowledge and understanding
• Be able to understand more demanding principals of discrete mathematics.
• To deepen the knowledge of nontrivial applications of discrete mathematics.
• To connect discrete mathematics with other fields of mathematics.
Intended learning outcomes - transferable/key skills and other attributes
• Knowledge transfer of more demanding methods of discrete mathematics into other fields (computer science, chemistry, biology, optimization, …)
• Communication skills: public performance at seminar presentation, manner of expression at exams.
• Problem solving: solving of demanding problems in discrete mathematics.
Readings
N. L. Biggs, Discrete Mathematics. Second Edition. The Clarendon Press, Oxford University Press, New York, 1989.
M. Aigner, Discrete Mathematics, American Mathematical Society, Providence RI, 2007.
R. Diestel, Graph Theory, Springer-Verlag, Berlin Heidelberg, 2005.
M. Juvan, P. Potočnik, Teorija grafov in kombinatorika, DMFA, Ljubljana, 2000.
J. H. van Lint, R. M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 2001.
D. B. West, Introduction to Graph Theory, Second Edition. Prentice Hall, Inc., Upper Saddle River, NJ, 2001.
Prerequisits
Knowledge of graph theory.
Additional information on implementation and assessment - Seminar exercise
- Written exam
- Oral exam
Each of the mentioned commitments must be assessed with a passing grade.
Written exam can be replaced by two partial tests (mid-term testing).
Passing grade of the seminar and of written tests are required for taking the oral exam.
