SF2715 Applied Combinatorics 6.0 credits

Tillämpad kombinatorik

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

Grading scale *

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

    Main field of study *

    Mathematics

    Education cycle *

    Second cycle

    Add-on studies

    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.