| Course objectives: |
| Introduction to combinatorics and graph theory and to some aspects of algebra |
| Course content and structure: |
| Exclusion-inclusion (sieve) formula and its applications: number of fixed point free permutations, number of surjective functions, Euler’s phi function. Catalan numbers: different equivalent definitions. Some combinatorial identities. Graph theory: chromatic number, Brooks theorem, perfect graphs, Turan’s problem, complete matchings, theorems of Tutte, linear algebraic methods in graph theory, further topics in recent graph theory. Introduction to Ramsey theory. Semigroups, groups and rings. Permutation groups. |
| Evaluation method: |
| short presentation of a given subject |
| Required reading: 1. Stephan Foldes: Fundamental Structures of Discrete Mathematics, Wiley, 2. R. Distel: Graph Theory, Springer, 3. R. P. Stanley: Enumerative Combinatorics, http://www-math.mit.edu/~rstan/ec/ec1.pdf |
| |
| Suggested reading: |
| J. Riordan: Combinatorial identities, R.E. Krieger Pub. Co. |
