Combinatorics (MATH 20002)
Warning: All content has been removed from this page. Materials will be updated by January 2016.
Synopsis | Syllabus | Notes | Homework | Assessment | Books | Additional office hours
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. The topics taught on any given day may change at short (or with no) notice.
The lecture notes for the course can be downloaded in pdf format via the following links.
As this is the first year the course is being taught, new chapters will be added on a weekly basis. Moreover, the notes are likely to contain an above-average number of typos and other inaccuracies. Please notify the lecturer of any misprints, errors or omissions by email or in person.
Homework is compulsory 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 normally be discussed during the examples class in Week k+1. Solutions will be posted one week after the initial release of the problem sheet, by default after the lecture on Wednesday.
Attendance at all lectures and problems 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, my office hours are on Tuesdays 5-6pm, and you are always welcome to stop by and ask questions on the homework or the content of the lectures. Third, there is a maths cafe for this course on Mondays 5-6pm in Portacabin 2, where you can also obtain highly qualified help.
We operate a peer marking scheme in this course. The idea is for you and your homework partner to swap the previous week's homework during the lecture on Wednesday. Solutions will be online from that afternoon, and you have until the lecture on Friday to go over your homework partner's work with the help of the model solutions if necessary. We will go over any remaining queries during the problems class on Friday. If you have trouble finding a homework partner, please get in touch either in person or by email.
As discussed in class, I would suggest that you use the three categories "Mathematical argument", "Clarity of presentation" and "Basic concepts" as marking criteria, but you may agree on a different system with your homework partner. Please be sure you both know (and agree on) what exactly these terms mean to you.
In addition to assigning a letter grade in each of the three categories, you should indicate with a tick if a solution or an argument is correct, or mark with a cross the point where the answer started to go wrong. If you have further insights that you think may help your homework partner approach similar problems in the future, you may also note these down or communicate them verbally. If you and your homework partner disagree on or are not sure whether a particular solution is correct, please come and talk to me or raise it during the problems class. First and foremost, however, discuss the problems with each other! You'll often find that you can come to a conclusion after all.
The benefits of peer marking are well documented. Yes, it is going to take up an extra 30 minutes of your week, but this time is well spent. Learning to approach problems from different angles is a vital skill in combinatorics, and looking at somebody else's solution (or attempt) will help you acquire this skill. It will also provide you with a valuable opportunity to look at the model solutions for the compulsory homework problems.
I am very interested in obtaining feedback on this process at any point during the course.
The course will be assessed by a 2.5h written exam in May/June, contributing 80% of the final mark, and 2 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 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. Discussion with your peers is allowed but answers must be written up independently. Late or illegible submissions will not receive any credit.
The final exam consists of two sections. Section A contains 3 short questions carrying 25% of the marks, and Section B contains 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.) You will be expected to attempt all questions.
Past examination papers are not available for download on Blackboard as this is a brand new course. In order to prepare for the exam, your best strategy will be to go over all the problems covered in lectures, as well as on past homework sheets.
Detailed rules and regulations pertaining to exams may be found here.
Time and venue for the combinatorics summer examination have now been confirmed. The exam will take place on Monday, 18th May 2015 from 2:15 to 4:45pm, in the Sports Hall, Tyndall Avenue (AP-GYM).
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.
Please note that I shall not be answering questions by email the weekend before the exam, specifically between 6pm on Friday, 15th May and 9am on Monday, 18th May.
|This page was last updated 8th September 2015.||© 2003-2017 Julia Wolf|