Introduction to the course

Sets Relations Functions

Sets relations and functions

Exercises for introduction lesson

Sets Relations Functions

Partial orderings: basic notions

Mirsky's and Dilworth's Theorem

Partial orders maximal and minimal elements chains antichains

Partial orders maximal and minimal elements chains antichains

How to Count Functions Injections Permutations and Subsets

Evaluating Simple Sums

Pascal's Triangle

Counting Basic Objects

Counting Basic Objects

Combinatorial Identities

Estimating the Binomial Coefficient

Excursion to Discrete Probability: Computing the Expected Minimum of k Random Elements from {1...n}

An Eagle's View of Pascal's Triangle

Combinatorial Identities

Digging Into Pascal's Triangle

Asymptotics and the O( )-Notation

The Big-O-Notation

Basic Facts

Classes that often occur in complexity theory

Basic Notions and Examples

Graph Isomorphism Degree Graph Score

Graph Score Theorem

Graphs isomorphisms and the sliding tile puzzle

Graphs and Isomorphisms

The Graph Score Theorem

Graphs and Connectivity

Cycles and Trees

An Efficient Algorithm for Isomorphism of Trees

Cycles and Trees

Cycles and Trees

Spanning Tree Exchange Graph

Eulerian Cycles

Hamilton Cycles - Ore's and Dirac's Theorem

Hamiltonian Cycles and Paths

Hamiltonian Cycles and Paths

Minimum Spanning Trees

The Number of Trees on n Vertices

Spanning Trees

Minimum Spanning Trees

Counting Trees on n Vertices

Flow Networks Flows Cuts: Basic Notions and Examples

Flow Networks: The Maxflow - Mincut Theorem

Network flow

Network Flows

Matchings in Bipartite Graphs - Basic Notions and an Algorithm

Matchings in Bipartite Graphs: Hall's and König's Theorem

Partial Orders: Dilworth's Theorem on Chains and Antichains

Matchings in Bipartite Graphs