1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2019/2020
4. Mathematics - Second-cycle studies leading to MS degree
5. Combinatorial Analysis

Generate PDF for this page

Combinatorial Analysis - course description

Aim of the course

Introducing students to basic definitions, theorems and methods of combinatorial analysis and examples of applications of them.

Prerequisites

Save changes

Completed courses of mathematical analysis, linear algebra and discrete mathematics.

Scope

Lecture
1. The binomial coefficients (2 h)
2. Rook polynomials (2 h)
3. Latin squares (2 h)
4. Van der Waerden’s Theorem, Schur’s Theorem (2 h)
5. Map-colourings, Four – Colour Theorem (3 h)
6. Minimax theorems (4 h)
7. Combinatorial designs (2 h)
8. Perfect codes, Hadamard’s matrices (5 h)
9. Sperner’s Lemma (3 h)
10. Minkowski’s Theorem, Radon’s Theorem, Helly’s Theorem, Tverberg’s Theorem (5 h)
 

Class
1. Proving combinatorial identities (2 h)
2. Applications of rook polynomials (3 h)
3. Making latin squares; proving properties of latin squares (3 h)
4. Applications of van der Waerden’s and Schur’s Theorems (2 h)
Test (2 h)
5. Applications of Four - Colour Theorem and minimax theorems (4 h)

6. Proving properties of combinatorial designs; applications of combinatorial designs (3 h)
7. Constructing of perfect codes (3 h)
8. Applications of Sperner’s Lemma and basic theorems of combinatorial geometry (6 h)
Test (2 h)

Teaching methods

Traditional lecture, discussion exercises, work in groups.

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

1. Checking of preparedness of students and their activity during exercise
2. Colloquiums with tasks of different difficulty, allowing to evaluate whether the students have achieved specified learning outcomes in minimal level
3. Written exam
The grade of the module is the arithmetic mean of the exercise grade and the exam grade. The prerequisite of the exam is to get a positive assessment of the exercise. The condition to obtain a positive evaluation of the module is the positive evaluation of the exam.

Recommended reading

1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa,1986.
2. K. A. Rybnikow (red.), Analiza kombinatoryczna w zadaniach, PWN, Warszawa, 1988.
3. J. Matoušek, Lectures on Discrete Geometry, Springer, New York, 2002.

Further reading

1. Z. Palka, A. Ruciński, Wykłady z kombinatoryki, WNT, Warszawa, 1998.
2. R. L. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna, PWN, Warszawa, 2011.
3. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.

Notes

Modified by dr Robert Dylewski, prof. UZ (last modification: 20-09-2019 11:46)