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.
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. Please notify the lecturer as soon as possible if you are in any doubt regarding the above.
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 (venue tbc), where you can obtain qualified help.
The course will be assessed by a 2.5h written exam in January, 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 will be released before the Easter break.
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 in the Notes section above 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.
I will be posting corrections and other announcements here. Watch this space!
|This page was last updated 28th December 2017.||© 2003-2018 Julia Wolf|