Archive for the ‘Combinatorics’ Category

Notes on discrete and polyhedral geometry

Friday, August 28, 2009 10:04
Posted in category Combinatorics, Geometry, Notes

Problems in discrete geometry (i.e. the border between combinatorics and geometry) have made several recent appearances on the IMO (typically, granted as Q6). A nice book by Igor Pak covers much of the important material in this area — the book is aimed at undergaduate and graduate students in maths, but the first few chapters in particular are suitable for Olympiad level students.

As in many cases, the important thing is not the results themselves (though Helly’s theorem is a useful tool in lots of setting) but the “style” of proofs in this area.

Michael

Enumeration

Wednesday, April 8, 2009 12:56
Posted in category Combinatorics, Notes

Here are some scanned notes by Michael on enumeration – the subtle art of counting. They were originally used for a course at Carnegie Mellon, and expand on the ideas in Basic Counting Principles.

The contents pages list a chapter on graph theory; unfortunately this chapter is not available at present.

Induction

Friday, March 27, 2009 15:40
Posted in category Combinatorics, Notes

Induction is a powerful tool for proving that some result or formula is true for all natural numbers n, without resorting to handwaving or saying “and so on.” These notes by Chris Tuffley outline induction in its various forms – and explain just what it has to do with dominoes…

The Principle of Inclusion-Exclusion

Monday, February 2, 2009 17:25
Posted in category Combinatorics, Notes

In Basic Counting Principles you learnt how to find the size of a union of two sets. The powerful
Principle of Inclusion-Exclusion tells us how to generalise this formula to a union of arbitrarily many sets.

Recurrence relations

Tuesday, January 27, 2009 17:06
Posted in category Algebra, Combinatorics

Some notes and problems on finding and solving recurrence relations. Read these if you’ve ever wondered how to find a formula for the Fibonacci sequence!

The Seven Colour Theorem

Wednesday, January 14, 2009 17:29
Posted in category Combinatorics, Notes

Here are the slides from Chris Tuffley’s talk on the seven colour theorem at the 2009 camp. These weren’t really intended as a stand alone document, so you’ll have to fill in some of the gaps yourselves!