Syllabus |
I- Combinatorics: permutations and combinatorial groups; binomial and multinomial coefficients; principle of the "pigeon cages"; principle of inclusion-exclusion; generating functions and recurrence; combinatorial numbers (Fibonacci, Stirling, Euler and Bell), probabilistic methods in combinatorics.
II- Graphs: fundamental concepts and results on graphs; graph coloring; the theorems of the four and five colors; Turán's theorem; "the museum's theorem"; network optimization problems (shortest path, minimum spanning tree, traveling salesman).
III- Coding Theory: detection and correction of errors; the Hamming distance; the fundamental problem of coding theory; linear codes; perfect codes.
IV- Ramsey Theory: Ramsey's theorem; the principle of compactness; arithmetic progressions and the theorem of van der Waerden: van der Waerden numbers; Euclidean Ramsey theory.
|
Main Bibliography |
1) Aigner, M., Ziegler, G. M., Proofs from the book, Springer, 2000. 2) Cardoso, D. M., Szyman´ski, J., Rostami, M. Matemática discreta, Escolar Editora, 2009. 3) Chuan-Chong, C., Khee-Meng, K., Principles and Technics in Combinatorics, World Scientific Publishing Company, 1992. 4) Hill, Raymond, A first course in coding theory, Oxford University Press, 1986. 5) Landman, B. M. & Robertson, A., Ramsey Theory on the Integers, Student Mathematical Library, 24, Providence, AMS, 2004.
|