## Combinatorics (MATH 20002)## In a nutshell
## Synopsis | Syllabus | Notes | Homework | Assessment | Books | Updates## SynopsisCombinatorics 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. ## SyllabusThe 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.
## NotesThe 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. ## HomeworkHomework is
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. ## AssessmentThe 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 Three past examination papers are available in the "Examinations" section of the student intranet. Please note that for pedagogical reasons I will 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 ## BooksAll 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. ## UpdatesThe
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).
Please notify the lecturer as soon as possible if you are in any doubt regarding the above.
The time and venue for the combinatorics Please read the section on assessment which outlines the structure of the exam before attempting this You do NOT need to bring coloured pens to the exam.
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 |