Combinatorics (MATH 20002)


In a nutshell

The Petersen graph

Starting: Tuesday, 23th January 2018
Level: 2nd year undergraduate (20 credit points)
Prerequisites: Analysis I, Number Theory and Group Theory, Linear Algebra and Geometry, Probability I
Department information: Combinatorics (MATH 20002)
Lectures: Tu 10-11am  |  Tu 4-5pm  |  We 12-1pm
Venues: Physics Frank  |  Physics Mott  |  Physics Mott
Problems Classes: Weeks 1, 4, 6, 8, 10, 11, 12: Th 5-6pm, Physics Frank
Feedback Classes: Weeks 3, 5, 7, 9, 11: in smaller groups
Maths Cafe: Mo 4pm
Office hours: Tu 2:30-3:30pm, Howard House 2.06
 

Synopsis | Syllabus | Notes | Homework | Assessment | Books | Updates


Synopsis

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.

Return to top


Syllabus

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.

Date Content Homework [to be marked] Due
 
Week 1
23/01/2018 The inclusion-exclusion principle revisited Problem Sheet 1 [4,8,11] 30/01
23/01/2018 Ordered and unordered selection Solutions
24/01/2018 The binomial theorem and the pigeonhole principle
25/01/2018 Problems class (In-class problem) In-class problem
Solutions
 
Week 2
30/01/2018 Manipulating generating functions Problem Sheet 2 [2,5,6] 06/02
30/01/2018 Generating functions for counting Solutions
31/01/2018 Generating functions for recurrence relations
01/02/2018 No problems class (Postponed to Week 11!)
 
Week 3
Feedback classes (Problem Sheet 1)
06/02/2018 Combinatorial designs Problem Sheet 3 [3a,3b,4] 13/02
06/02/2018 Fisher's inequality Solutions
07/02/2018 Error-correcting codes
 
Week 4
13/02/2018 Perfect codes Assessed Problem Sheet 4 21/02
13/02/2018 Introduction to graph theory Solutions
14/02/2018 Basic properties of graphs
15/02/2018 Problems class (Problem Sheet 2)
 
Week 5
Feedback classes
(Problem Sheet 3 & In-class problems)
In-class problems
Solutions
20/02/2018 The seven bridges of Königsberg Problem Sheet 5 [1,2,4] 27/02
20/02/2018 Eulerian circuits Solutions
21/02/2018 Hamiltonian cycles
 
Week 6
27/02/2018 [Industrial action]
27/02/2018 [Industrial action]
28/02/2018 [Industrial action]
01/03/2018 Snow Day--University closed!
 
Week 7
Feedback classes (Problem Sheet 5 and
Assessed Problem Sheet 4)
06/03/2018 [Industrial action] Problem Sheet 6 [1,5,8] 16/03
06/03/2018 [Industrial action] Solutions
07/03/2018 [Industrial action]
 
Week 8
13/03/2018 Characterisation of bipartite graphs Assessed Problem Sheet 7 21/03
13/03/2018 Hall's marriage theorem Solutions
14/03/2018 Basic properties of trees and forests
15/03/2018 Spanning trees
 
Week 9
Feedback classes
(Problem Sheet 6)
20/03/2018 Introduction to planar graphs Problem Sheet 8 [3,5,12b] 17/04
20/03/2018 Euler's formula Solutions
21/03/2018 The chromatic number of a graph
 
Easter Break
 
Week 10
17/04/2018 The four and five colour theorems Problem Sheet 9 [2,5,6] 24/04
17/04/2018 A party of six and Ramsey's theorem Solutions
18/04/2018 Bounds on Ramsey numbers
19/04/2018 Problems class (Assessed Problem Sheet 7)
 
Week 11 [Revision]
Feedback classes (Problem Sheet 8)
24/04/2018 Counting techniques
24/04/2018 Generating functions
25/04/2018 Codes and designs
 
Week 12 [Revision]
01/05/2018 Introduction to graph theory
01/05/2018 Bipartite graphs, trees and forests
01/05/2018 Additional problems class (Problem Sheet 9)
02/05/2018 Planar graphs
03/05/2018 Graph colouring & Order from disorder

Return to top


Notes

The lecture notes for the course will be available for download in pdf format via the following links.

Notes 2017-2018:
Frontmatter
Chapter 1: Counting techniques
Chapter 2: Generating functions
Chapter 3: Codes and designs
Chapter 4: Introduction to graph theory
Chapter 5: Bipartite graphs
Chapter 6: Trees and forests
Chapter 7: Cliques and independent sets
Chapter 8: Planar graphs
Chapter 9: Graph colouring
Chapter 10: Order from disorder
Complete set

Please notify the lecturer of any misprints, errors or omissions by email or in person.

Return to top


Homework

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.

Return to top


Assessment

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.

Return to top


Books

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.
•   J.H. van Lint and R.M. Wilson. A course in combinatorics, Cambridge University Press, 1992.
•   J. Nesetril and J. Matousek. An invitation to discrete mathematics, Oxford University Press, 2008.
•   I. Anderson. A first course in combinatorial mathematics, Oxford University Press, 1989.
•   R. Wilson. Combinatorics: A very short introduction, Cambridge University Press, 2016.
•   M. Bona. A walk through combinatorics, World Scientific, 2011.

Return to top


Updates

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:
•   Chapter 6: everything after the end of the proof of Theorem 6.8
•   Chapter 7: everything
•   Chapter 8: everything in Section 8.1 (!) after the end of Observation 1
•   Chapter 9: everything that appears after Theorem 9.4 and before Theorem 9.6
•   Chapter 10: everything after the end of the proof of Corollary 10.7. You may also disregard Examples 3 and 4.

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
Wednesday, 30th May 2018, from 14:15 to 16:45 (Room F101 a/b/c, Queens Building).

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:
•   Wednesday, 9th May, 2-3pm: my office, 2.06 Howard House
•   Wednesday, 16th May, 2-3pm: 2nd floor seminar room, Howard House
•   Friday, 25th May, 2-3pm: 2nd floor seminar room, Howard House

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).

Return to top

This page was last updated 24th April 2018.