Combinatorics (MATH 20002)
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.
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.
The syllabus below is for indicative purposes only. Please note that the topics taught on any given day may change with little (or no) prior notice. The links will activate once the material is released.
The lecture notes for the course will be available for download in pdf format via the following links.
Please notify the lecturer of any misprints, errors or omissions by email or in person.
Homework is compulsory and will be marked, but not assessed except in Weeks 4 and 8 (see the section on Assessment below). Problem sheet k covers the material in Week k and will usually be released on the Tuesday of that week. It is to be handed in for marking to the box labelled "Combinatorics homework" in the main building by Tuesday, 4pm in Week k+1, and will be discussed during the problems/feedback class in Week k+2. Late or illegible homework will not be marked. Solutions will be posted approximately ten days after the initial release of the problem sheet.
Attendance at all lectures, problems and feedback classes is absolutely vital!
If you have trouble with the homework there are various options open to you: first, try talking your problem over with other students taking the course. Enormous benefit can often be drawn by simply formulating one's difficulty and seeing the problem in a different light. Second, you are most welcome to stop by during my office hours and ask questions on the homework or the content of the lectures. Third, there is a maths cafe for this course on Mondays at 4pm, where you can obtain qualified help.
The course will be assessed by a 2.5h written exam in May, contributing 80% of the final mark, and two assessed take-home problem sheets in Weeks 4 and 8, contributing 20% of the final mark.
The questions on the assessed problem sheets will be similar in style to the ones you have seen on the problem sheets in Weeks 1-3 and Weeks 5-7, respectively. Each assessment sheet will be released approximately one week before it is due (see dates in the Syllabus section). Discussion with your peers is allowed but answers must be written up independently. Late or illegible submissions will not receive any credit.
Unlike previous years, the final exam consists of four questions carrying equal weight. You will be expected to attempt all questions.
Three past examination papers are available in the "Examinations" section of the student intranet. Please note that for pedagogical reasons I will not publish solutions to these. An additional mock exam question with a model solution is available at the bottom of this page.
Also note that in previous years the final exam consisted of two sections, with the 3 short questions in Section A carrying 25% of the marks, and Section B containing 3 longer questions accounting for the remaining 75% of marks. (If you like, you can think of the three shorter questions in Section A taken together as equivalent to one long question.)
Links to detailed rules and regulations pertaining to exams may also be found on the student intranet.
Please also see the additional comments under Updates below concerning what material is examinable this year.
All examinable material is contained in the lecture notes and problem sheets published above, but the following texts are available in the library and may be useful to students seeking a broader understanding of the subject or more details on certain aspects of the course.
• P. Cameron. Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.
The unit questionnaire is available via this google form. Please take the time to fill it in before the end of term, even if you have no strong opinions on the unit.
The following content is non-examinable this year:
Needless to say, problems on the problem sheets that refer to material in these sections are similarly non-examinable. This applies to Problems 9 and 10 on Sheet 6, and Problem 7 on Sheet 9. Note that despite skipping Chapter 7, I expect you to know what a clique and an independent set are (as these terms have occurred in other contexts).
Everything else in the lecture notes is examinable in the sense that you are expected to be able to state the definitions, lemmas, propositions and theorems precisely (and correctly), and be able to prove these from memory. The content of the problem sheets (including the assessed ones) is examinable in the sense that you are expected to be able to solve similar problems in the exam.
Please notify the lecturer as soon as possible if you are in any doubt regarding the above.
The time and venue for the combinatorics exam have been confirmed. It will take place on
Please read the section on assessment which outlines the structure of the exam before attempting this mock exam question, and looking at the model solution.
You do NOT need to bring coloured pens to the exam.
Revision office hours will be held at the following times:
If you have any questions about the mark(s) you received on the assessed homework, please bring your homework to my office during my office hour (or email me to arrange a separate appointment).
|This page was last updated 24th April 2018.||© 2003-2019 Julia Wolf|