Combinatorics (MATH 20002)


Warning: All content has been removed from this page. Materials will be updated by January 2016.

In a nutshell

Two masters of combinatorics

Starting: Tuesday, 27th January 2015
Times: Tue 2-3pm, Wed 12-1pm, Fri 2-4pm
Venues: Tue Frank (Physics), Wed Peel (Geography), Fri Mott (Physics)
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)
Office hours: Tuesday, 5-6pm (Howard House, Office 2.06)
Maths Cafe: New time: Mon 5-6pm, Portacabin 2
 

Synopsis |  Syllabus |  Notes | Homework | Assessment | Books | Additional office hours


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. The topics taught on any given day may change at short (or with no) notice.

Date ContentHomework
Week 1: Counting techniques
27/01/2015 The inclusion-exclusion principle revisited
28/01/2015 Ordered and unordered selectionProblem Sheet 1 [3,4,5,8,13]
30/01/2015 The binomial theorem and the pigeonhole principle
Problems class
Solutions
In-class problem
 
Week 2: Generating functions
03/02/2015 Manipulating generating functions
04/02/2015 Generating functions for countingProblem Sheet 2 [1,2,4,7]
06/02/2015 Generating functions for recurrence relations
Problems class (Problem Sheet 1)
Solutions
 
Week 3: Codes and designs
10/02/2015 Combinatorial designs
11/02/2015 Fisher's inequalityProblem Sheet 3 [1,2,4,6]
13/02/2015 Error-correcting codes
Problems class (Problem Sheet 2)
 
Solutions
Week 4: Introduction to graph theory
17/02/2015 Perfect codes
18/02/2015 Problems class (Problem Sheet 3)Assessed Problem Sheet 1
20/02/2015 Basic properties of graphs
The seven bridges of Königsberg
[released 18/02, due 24/02]
Solutions
 
Week 5: Bipartite graphs
24/02/2015 Eulerian circuitsShort Problem Sheet 4 [1,2,4,5]
25/02/2015 Hamiltonian cyclesSolutions
27/02/2015 Characterisation of bipartite graphs
Problems class (Assessed Problem Sheet 1
and Short Problem Sheet 4)

Problem Sheet 5 [1,3,4,7]
Solutions
 
Week 6: Trees and forests
03/03/2015 Hall's marriage theorem
04/03/2015 Basic properties of trees and forests
06/03/2015 Spanning trees
Problems class (Problem Sheet 5)
Problem Sheet 6 [1,4,5,6]
Solutions
 
Week 7: Cliques and independent sets
10/03/2015 Kruskal's algorithm
11/03/2015 Mantel's theorem
13/03/2015 Turán's theorem
Problems class (Problem Sheet 6)
Problem Sheet 7
Solutions
 
Week 8: Planar graphs
17/03/2015 Applications of Turán's theorem
18/03/2015 Problems class (Problem Sheet 7)Assessed Problem Sheet 2
20/03/2015 Introduction to planar graphs
Kuratowski's theorem
[released 18/03, due 24/03]
Solutions
 
Week 9: Graph colouring
24/03/2015 Euler's formula
25/03/2015 The chromatic number of a graphShort Problem Sheet 8 [2,3,5]
27/03/2015 The four and five colour theorem
Problems class (Assessed Problem Sheet 2
and Short Problem Sheet 8)
Solutions
 
Easter Break
 
Problem Sheet 9 [3,4,5]
Solutions
Week 10: Order from disorder
21/04/2015 A party of six and Ramsey's theorem
22/04/2015 Bounds on Ramsey numbersProblem Sheet 10 [2,3,5]
24/04/2015 Infinite Ramsey and other variants
Problems class (Problem Sheet 9)
Solutions
 
Week 11: Additional problems and revision
28/04/2015 Counting techniques & Generating functions
29/04/2015 Codes and designs
01/05/2015 Introduction to graph theory & Bipartite graphs
Problems class (Problem Sheet 10)
 
Week 12: Additional problems and revision
05/05/2015 Trees and forests & Cliques and independent sets
06/05/2015 Planar graphs
08/05/2015 Graph colouring & Order from disorder
Additional problems and revision

Return to top


Notes

The lecture notes for the course can be downloaded in pdf format via the following links.

Combinatorics (Notes 2014-2015)
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

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.

Return to top


Homework

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.

Return to top


Assessment

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.
The following would make a suitable question for Section B of the exam, and the solution provided reflects the level of detail we would expect to see for full marks.

Sample exam question
Solution

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

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.

Return to top


Additional office hours

Office hours:
Friday, 1st May: 12-1pm
Tuesday, 5th May: 5-6pm
Friday, 8th May: 12-1pm
Tuesday, 12th May: 5-6pm
Wednesday, 13th May: 2-3pm
Thursday, 14th May: 2-3pm

Maths café:
Thursday, 7th May: 2-3pm in PC1 (instead of Monday, 4th May)

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.

Return to top

This page was last updated 8th September 2015.