# SF2715 Applied Combinatorics 6.0 credits

Course of combinatorics for computer scientists.

### Offering and execution

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

## Course information

### 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

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

### 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