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, 2, 4, 6, 8, 10, 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: Counting techniques
23/01/2018 The inclusion-exclusion principle revisited Problem Sheet 1 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: Generating functions
30/01/2018 Manipulating generating functions Problem Sheet 2 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: Codes and designs
Feedback classes (Problem Sheet 1)
06/02/2018 Combinatorial designs Problem Sheet 3 13/02
06/02/2018 Fisher's inequality Solutions
07/02/2018 Error-correcting codes
 
Week 4: Introduction to graph theory
13/02/2018 Perfect codes Assessed Problem Sheet 4 21/02
13/02/2018 Basic properties of graphs Solutions
14/02/2018 The seven bridges of Königsberg
15/02/2018 Problems class (Problem Sheet 2)
 
Week 5: Bipartite graphs
Feedback classes
(Problem Sheet 3 & In-class problems)
In-class problems
Solutions
20/02/2018 Eulerian circuits Problem Sheet 5 27/02
20/02/2018 Hamiltonian cycles Solutions
21/02/2018 Characterisation of bipartite graphs
 
Week 6: Trees and forests
27/02/2018 Hall's marriage theorem Problem Sheet 6 06/03
27/02/2018 Basic properties of trees and forests Solutions
28/02/2018 Spanning trees
01/04/2018 Problems class (Assessed Problem Sheet 4)
 
Week 7: Cliques and independent sets
Feedback classes (Problem Sheet 5)
06/03/2018 Kruskal's algorithm Problem Sheet 7 13/03
06/03/2018 Mantel's theorem Solutions
07/03/2018 Application of Turán's theorem
 
Week 8: Planar graphs
13/03/2018 Proof of Turán's theorem Assessed Problem Sheet 8 21/03
13/03/2018 Introduction to planar graphs Solutions
14/03/2018 Kuratowski's theorem
15/03/2018 Problems class (Problem Sheet 6)
 
Week 9: Graph colouring
Feedback classes
(Problem Sheet 7 & In-class problems)
In-class problems
Solutions
20/03/2018 Euler's formula Problem Sheet 9 17/04
20/03/2018 The chromatic number of a graph Solutions
21/03/2018 The four and five colour theorem
 
Easter Break
 
Week 10: Order from disorder
17/04/2018 A party of six and Ramsey's theorem Problem Sheet 10 24/04
17/04/2018 Bounds on Ramsey numbers Solutions
18/04/2018 Infinite Ramsey and other variants
19/04/2018 Problems class (Assessed Problem Sheet 8)
 
Week 11: Additional problems and revision
Feedback classes (Problem Sheet 9)
24/04/2018 Counting techniques & Generating functions
24/04/2018 Codes and designs
25/04/2018 Introduction to graph theory & Bipartite graphs
26/04/2018 Additional problems class (Problem Sheet 10)
 
Week 12: Additional problems and revision
01/05/2018 Problems Class (Problem Sheet 10)
01/05/2018 Trees and forests & Cliques and independent sets
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 (time and venue tbc), where you can obtain qualified help.

Return to top


Assessment

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.

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

I will be posting corrections and other announcements here. Watch this space!

Return to top

This page was last updated 28th December 2017.