There is little in the way of assumed knowledge, with both the combinatorics and graph theory developed from foundations, but the material gets progressively more difficult. Much of the graph theory would be within reach of an engaged secondary school student, though it does assume familiarity with mathematical notation. The combinatorics assumes comfort with matrices and infinite series, and for one section with group theory (an introduction there will work best as a refresher). And the extension to the infinite delves into set theory and mathematical logic, touching (without proofs) on striking results such as the construction of a finite combinatorial statement that can only be proven with assumptions about large (k-subtle) infinite cardinals.
The material in the first two parts provides a solid introduction to the basics and a glimpse of further topics. The graph theory covers planarity (Kuratowski's Theorem), colourings (chromatic polynomials), matchings, and Ramsey theory. The combinatorics centres generating functions, with introductions to Stirling numbers, Bell numbers, and so forth used to develop that, but also includes introductions to Polya theory, stable "marriage" problems, and combinatorial geometry. The third part stays connected to this, beginning with some simple results about infinite pigeonholes and trees and graphs, and an example of their use to prove finite results, before rapidly surveying axiomatic set theory, incompleteness, the hierarchy of cardinals, and infinite marriage problems.
The presentation is rigorous, with proofs included for almost everything until near the end, including a few longer multi-page proofs: Tutte's Theorem, Brook's Theorem, and so forth. And there is some discussion of open problems. The exercises are well motivated and range from the simple to the moderately challenging.
- External links:
- buy from Bookshop.org (UK)
- buy from Amazon.com or Amazon.co.uk
- share this review on Facebook or Twitter