Course of combinatorics for computer scientists.

Course offering missing for current semester as well as for previous and coming semesters

## Content and learning outcomes

### Course contents

Combinatorial objects, combinatorial proofs, formal power series, recursions, generating functions, the RSK algorithm, enumeration under group actions, elementary theory of graphs and networks, graph colouring theory, topological graph theory, error-correcting codes.

### Intended learning outcomes

After the course, the student should be acquainted with basic combinatorial methods and theories that provide a foundation for further studies in the field as well as for applications in related areas, in particular computer science. In practice, this means that the student should

• Be familiar with various standard combinatorial objects and sequences, for example permutations, partitions, Bell numbers, Catalan numbers, ...
• Perform computations with, and deduce properties of, formal power series
• Deduce recursions, generating functions and explicit expressions for combinatorially defined number sequences
• Construct combinatorial proofs of identities and inequalities
• Know the RSK algorithm and be able to use it in order to deduce properties of permutations and tableaux
• Interpret certain counting problems in terms of enumeration under group actions and use Burnside's lemma and Pólya theory to solve them
• Use some classical graph algorithms in order to find subgraphs with desirable properties
• Find maximal flows in networks and give an account of how this method is connected with results of Menger, König and Hall as well as solving certain problems by formulating them in terms of network flows
• Compute, and deduce properties of, chromatic numbers and polynomials and identify certain problems as graph colouring problems
• Apply results of Euler, Kuratowski-Wagner and Appel-Haken to deduce properties of (non-)planar graphs
• Construct, perform calculations with and deduce properties of certain codes
• Determine, interpret and compare various bounds for code performance

### Course Disposition

No information inserted

## Literature and preparations

### Specific prerequisites

No information inserted

### Recommended prerequisites

SF1631 Diskret matematik or equivalent material.

### Equipment

No information inserted

### Literature

Peter J. Cameron, "Combinatorics: Topics, Techniques, Algorithms", Cambridge University Press, 1994.

## Examination and completion

If the course is discontinued, students may request to be examined during the following two academic years.

A, B, C, D, E, FX, F

### Examination

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

### Other requirements for final grade

Written/oral exam, possibly with the possibility of continuous examination.

### Opportunity to complete the requirements via supplementary examination

No information inserted

### Opportunity to raise an approved grade via renewed examination

No information inserted

### Examiner

No information inserted

### Ethical approach

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

## Further information

### Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web SF2715

### Offered by

SCI/Mathematics

Mathematics

Second cycle