Core Courses
The two BMS Core Course sequences in RTA 4 cover the fundamental concepts, results, methods, and algorithms in Combinatorics and Graph Theory, as well as in Combinatorial Optimization, Linear and Integer Programming. The two sequences are intrinsically connected, yet disjoint in terms of their material.
- Enumeration and generating functions (twelvefold way, recurrences, formal power series)
- Graph theory (connectivity, matchings, colorings, planarity, extremal problems)
- Finite discrete structures (hypergraphs, posets, designs)
- Methods (algebra, discrete probability, topology)
The BMS Core sequences in Combinatorics and Graph Theory start in the Summer Semester and continue in the Winter Semester. At the FU the courses are called Discrete Mathematics I (offered every year) and Discrete Mathematics II-Extremal Combinatorics (offered every odd year). At the TU the courses are called Discrete Structures I (offered every odd year) and Discrete Strutures II (offered every odd year). Both of these sequences provide a thorough introduction into Combinatorics and Graph Theory, but their eventual foci are different: the sequence at FU delves more into the methods of Extremal Combinatorics, while the sequence at TU expands more towards Algebraic Combinatorics.
Discrete Optimization I + II
- Graph algorithms (paths, spanning trees, matchings, Hamilton cycles, flows)
- Linear Programming (simplex algorithm, duality) and its applications
- Approximation algorithms, randomized algorithms
- Basics of complexity
- Integer Linear Programming (branch-and-bound, relaxations, approximation)
- Cutting planes (elementary closure, Gomory cuts, mixed-integer programs)
- Polyhedral Combinatorics (Matroid, Matching, TSP polytope)
- Implementations
The BMS Core sequences in Discrete Optimization start in the Winter Semester and continue in the Summer Semester. At the TU the courses are called Algorithmic Discrete Mathematics I and II, and are offered every year. At the FU, in even years the Discrete Opimization I BMS course runs under the name Discrete Mathematics II-Algorithmic Combinatorics, and in the odd years it is called Discrete Mathematics II-Optimierung. All these courses cover the same basics, yet they differ in their approach. The ADM-sequence and Optimierung are tailored towards Optimization, while Algorithmic Combinatorics is emphasizing more the combinatorial connections.
Spectrum of Advanced Courses
Topics for typical advanced courses include:
Extremal Combinatorics, The Probabilistic Method, Constructive Combinatorics, Positional Games, Order Theory, Algebraic Combinatorics, Topological Methods; Combinatorial Algorithms, Approximation Algorithms, Online-Algorithms, Mechanism Design, Online Optimization, Scheduling, Periodic Timetabling and Passenger Routing, Integer and Mixed-Integer Programming, Convex Optimization and Applications.
