SF2715 Applied Combinatorics 6.0 credits

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.

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

SF1631 Diskret matematik or equivalent material.

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

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

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.

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

• 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.