This new unit serves as an introduction to combinatorics, developing fundamental aspects of a diverse range of topics in discrete mathematics such as counting, generating functions, extremal graph theory, Ramsey theory and random walks. The unit aims to develop and improve students’ problem-solving and theorem-proving skills, building on those acquired in first-year courses. Moreover, it seeks to enhance students’ appreciation of the interconnectedness of different areas of mathematics by introducing probabilistic, analytic and algebraic techniques.
Combinatorics is the study of discrete structures, which are ubiquitous in our everyday lives. While combinatorics has important practical applications (for example to networking, optimisation, and statistical physics), problems of a combinatorial nature also arise in many areas of pure mathematics such as algebra, probability, topology and geometry.
The course will start with a revision of various counting techniques, and take a close look at generating functions. The unit will then proceed to introduce the basic notions and fundamental results of graph theory, including Turán’s theorem on independent sets, Hall’s marriage theorem, Euler’s formula for planar graphs and Kuratowski’s theorem. In the last part of the unit probabilistic and algebraic methods will be used to study more advanced topics in graph theory, including Ramsey’s theorem and random walks.
Relation to other units
This unit prepares students for the more advanced third/fourth year unit Topics in Discrete Mathematics.
Students who successfully complete the unit should
- be proficient at counting rearrangements of finite sets;
- have acquired facility with the computation and application of generating functions;
- be familiar with the basic definitions and concepts in graph theory, including trees, cycles, connectivity, matchings, planarity;
- understand, be able to prove and apply the fundamental results derived in the course, and solve unseen problems of a similar kind;understand and be able to apply methods from elementary probability, analysis and linear algebra to a range of problems in discrete mathematics, including Ramsey theory and random walks.
In addition, students should have
- learnt how to give a mathematical formulation to word problems of a discrete nature;
- improved their problem-solving and theorem-proving skills;
- gained an appreciation of how methods from probability, analysis and algebra can be used to solve problems in discrete mathematics.
- Ability to write coherent and logically sound arguments.
- Assimilation and use of novel and abstract ideas.
Topics covered will include:
- elementary counting techniques;
- generating functions;
- codes and designs;
- introduction to graphs: trees, paths, cycles and cliques;
- Turan's theorem;
- matchings: Hall's marriage theorem;
- planar graphs: Euler's formula and Kuratowski's theorem;
- graph colouring: Ramsey's theorem;
Reading and References
Lecture notes will be provided covering all the material presented in lectures. The following supplementary texts provide additional background reading:
- Peter Cameron, Combinatorics: Topics, techniques, algorithms
- J.H. van Lint and R.M. Wilson, A course in combinatorics
- George Pólya, Robert Tarjan and Donald Woods, Notes on introductory combinatorics
- Jaroslav Nesetril and Jiri Matousek, An invitation to discrete mathematics
Linear Algebra and Geometry, Probability 1, Analysis 1A, Foundations and Proof and Introduction to Group Theory
Methods of teaching
This course will consist of three lectures a week, supported by a weekly examples class.
Methods of Assessment
The pass mark for this unit is 40.
The final mark is calculated as follows:
- 80% from a 2 hour 30 minute exam in May/June
- 20% from 2 assessed take home problem sheets in weeks 4 & 8.
NOTE: Calculators are NOT allowed in the examination.
For information resit arrangements, please see the re-sit page on the intranet.
Further exam information can be found on the Maths Intranet.