Lehrinhalte
This class aims to give a basic introduction into Combinatorics and Graph Theory.
Combinatorics briefly is about how we can combine (mathematical) objects according to certain given rules. We can ask, how many such combinations exist, whether one such combination exists at all, or which further properties our combinations may share. If we are given some valuation for our combinations we can also ask which one is the best according to this valuation. A basic, but typical question is this area is the following. Given a natural number, in how meny different ways can we write this number as the sum of finite numbers.
Combinatorial problems often arise as a subproblem in research questions of quite a number of different areas of mathematics, e.g. algebra, probability theory, topology, geometry, or optimization. For a long time these combinatorial problems have been studied independently in these areas and have often been solved with some ad hoc method. It was only in the second half of the last century that the similarity of these questions has been studied systematically. With the development of new powerful methods the field of combinatorics turned into a quite large and active research area of its own.
Graph theory is one of the oldest and largest parts of combinatorics. It deals with finite structures and relations between its objects. Graphs are often visualised using a finite set of nodes, and two such nodes are connected by a line if the nodes are in relation in our structure. Basic questions in this field start with asking how many graphs there are sharing certein properties. Another typical question is the coloring problem. Here we want to assign (as few as possible) colors to the nodes in such a way that connected nodes get different colors.
We aim to discuss the following topics in class:
- combinations and counting
- generating functions and recursions
- partially ordered sets
- graph theory, planar graphs and colorings
- polyhedra
- triangulations
- counting with symmetry
- probabilistic methods
- designs
- codes
Literature
M. Aigner, Diskrete Mathematik, 5. Auflage, Vieweg, 2003.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Second edition, Addison-Wesley, Reading, MA, 1994.
W. Koepf, Hypergeometric Summation. An Algorithmic Approach to Summation and Special Function Identities, AMS, 1998.
J. Matouek, J. Neetril, Diskrete Mathematik. Eine Entdeckungsreise, Springer, 2002.
R.P. Stanley, Enumerative Combinatorics, Volume I, Cambridge 1997.
J.H. van Lint, R.M. Wilson: A Course in Combinatorics, Cambridge University Press, 2009.
Voraussetzungen
recommended: Algorithmic Discrete Mathematics
Online-Angebote
moodle
This class aims to give a basic introduction into Combinatorics and Graph Theory.
Combinatorics briefly is about how we can combine (mathematical) objects according to certain given rules. We can ask, how many such combinations exist, whether one such combination exists at all, or which further properties our combinations may share. If we are given some valuation for our combinations we can also ask which one is the best according to this valuation. A basic, but typical question is this area is the following. Given a natural number, in how meny different ways can we write this number as the sum of finite numbers.
Combinatorial problems often arise as a subproblem in research questions of quite a number of different areas of mathematics, e.g. algebra, probability theory, topology, geometry, or optimization. For a long time these combinatorial problems have been studied independently in these areas and have often been solved with some ad hoc method. It was only in the second half of the last century that the similarity of these questions has been studied systematically. With the development of new powerful methods the field of combinatorics turned into a quite large and active research area of its own.
Graph theory is one of the oldest and largest parts of combinatorics. It deals with finite structures and relations between its objects. Graphs are often visualised using a finite set of nodes, and two such nodes are connected by a line if the nodes are in relation in our structure. Basic questions in this field start with asking how many graphs there are sharing certein properties. Another typical question is the coloring problem. Here we want to assign (as few as possible) colors to the nodes in such a way that connected nodes get different colors.
We aim to discuss the following topics in class:
- combinations and counting
- generating functions and recursions
- partially ordered sets
- graph theory, planar graphs and colorings
- polyhedra
- triangulations
- counting with symmetry
- probabilistic methods
- designs
- codes
Literature
M. Aigner, Diskrete Mathematik, 5. Auflage, Vieweg, 2003.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Second edition, Addison-Wesley, Reading, MA, 1994.
W. Koepf, Hypergeometric Summation. An Algorithmic Approach to Summation and Special Function Identities, AMS, 1998.
J. Matouek, J. Neetril, Diskrete Mathematik. Eine Entdeckungsreise, Springer, 2002.
R.P. Stanley, Enumerative Combinatorics, Volume I, Cambridge 1997.
J.H. van Lint, R.M. Wilson: A Course in Combinatorics, Cambridge University Press, 2009.
Voraussetzungen
recommended: Algorithmic Discrete Mathematics
Online-Angebote
moodle
- Lehrende: Andreas Paffenholz
Semester: WT 2022/23