To an outsider attending a graph theory conference, it must appear that we graph theorists have an unnatural reverence for a little symmetrical picture of 10 dots and 15 lines (see figure). No matter what the title of the talk, odds are that sooner or later the speaker will draw it, and heads in the audience will nod in apparent obeisance.
The truth is quite different. In reality, few of us go in search of the Petersen graph. It is more that it stalks us, hiding behind many an innocent lemma, waiting to spring out at us. Sometimes it is in a good mood, and it marches proudly at the head of a new sequence of graphs with some fascinating property. Just as often, alas, it sits across our budding proof as a sullen and stubborn obstacle.
Derek Holton of Otago and John Sheehan of Aberdeen got together on the principle that if you can't avoid it, you might as well write a book about it. Using the pervasiveness of the Petersen graph as their springboard, they explore dozens of active research areas in graph theory. The result is not only of interest as a reference text, but can also serve as a self-contained and entertaining introduction to graph theory for any reader with moderate mathematical maturity.
The important topics in the book can be classified into three themes: matchings and colourings, cycles, and groups.
The Petersen graph P is the smallest graph which is cubic (every vertex has three edges) and bridge-free (no deletion of one edge can disconnect it), but not Tait-colourable. The latter refers to a colouring of the edges using three colours such that every vertex lies on one edge of each colour. Tait-colourings were of fundamental importance to early attacks on the four-colour problem. This theme is explored in some depth, leading to a good summary of Appel and Haken's proof, and a variety of generalisations in contractions, flows and projective geometries. In another direction, the very rare cubic non-Tait-colourable graphs which Martin Gardner called snarks are introduced and studied. Of course, P is the smallest snark.
The second main theme is best introduced via a little problem. A certain club wants to hold a dinner, using a round table, so that everyone has a friend on each side. After exhaustive experimentation, there is found to be no such arrangement, but that if any one person fails to show up (no matter who) a suitable arrangement is available. What is the smallest possible size of this club? As one can infer from the topic of this review, the pattern of friendships in this club must be P. Such a graph is called hypohamiltonian. These are surprisingly difficult to find (try it!), but we now know that they exist for all higher orders except 11, 12, 14 and 17. (The inclusion of 17 on the list is more recent than this book.)
Instead of looking at the longest cycles, we can consider the shortest. Our graph P is the unique smallest cubic graph of girth 5, where the girth is the length of the shortest cycle. More generally, we can ask for the smallest regular graphs of given degree and girth. These are called cages and very little is known about them. In fact even the best known asymptotic bounds on their order are far apart.
The third major theme of the book is that of groups. The automorphism group of P is a primitive rank-3 representation of S5 which acts sharply transitively on directed paths of length~3. These observations lead the book to a wider investigation of graphs with rank-3 groups, and the strongly regular graphs which are a combinatorial generalisation. They also lead to the study of the actions of automorphism groups on directed paths, and more general study of graphs with transitive groups.
The book has the usual number of minor typographical errors or inconsistencies in notation, but these are rarely a distraction. The clarity of style is exceptional. In a few areas, for example hypohamiltonian graphs, the book forms the most complete survey to date. In other areas, a presentation of the main results is followed by selected references to more specialised treatments. I have found it a good starting point for many an inquiry, and it could also be used as a text for a course at honours level or above. I recommend it highly for either purpose.
Australian National University
This text is identical to the favourably reviewed first edition of 1988, save for the addition of two new chapters (11 and 12), an extra 66 pages. Together they cover continuous time and state stochastic processes, the Wiener process, diffusions and stochastic differential equations (SDEs). The presentation of the new chapters is similar to the first edition, viz. a sketch of some theory and illustrative examples.
Chapter 11 begins with a discussion of modelling with differential equations in order to assert the limited value of this approach for ``intrinsically complex systems such as arise in biology and economics''. One could argue against this contention. Anyway, it is used to introduce stochastic differential equations (SDEs), though without saying at this stage what they might be. Next, additive process are defined with the drifting Wiener process appearing as an example. A brief discussion of sample path behaviour follows, and then some covariance properties. White noise enters as the stationary process having a flat spectrum, and the Wiener process reappears as the solution of the simplest SDE - the derivative of white noise. The author indicates problems with these notions. The chapter ends with a discussion of the Chapman-Kolmogorov equation for a continuous state Markov process in the case where a density exists. A selection of rather routine problems is provided, e.g., find the moments and covariance function of the Wiener process.
The real meat of the additions of the second edition is in Chapter 12, Diffusion processes, SDEs and applications. This begins by informally introducing the infinitesimal mean and variance functions, and their role in density versions of the forward (Fokker-Planck) and backward Kolmogorov equations. There follows a brief heuristic treatment of boundary classification and criteria. Next, the stationary density is derived from the stationary forward equation. This is one of the few formal developments in the text. These ideas are illustrated in some detail with the drifting Wiener process moving in R, in (-infinity,a] with the upper barrier absorbing, and in [0,a] with both barriers reflecting. These ideas are further illustrated with a brief treatment of the Ornstein-Uhlenbeck process moving in R.
The remaining sections give an informal account of SDE's. The Ito integral is motivated and defined for non-anticipative integrands, a term familiar in the engineering literature. It is explained to mean a process for which questions up to and including time t can be answered without knowledge of the evolution of the Wiener process (the integrator) for times beyond t. This near-quote gives a flavour of the technical level of the book.
Ito's rule is stated in quite precise terms, and its proof indicated. Its non-classical form is linked to the quadratic variation property of the Wiener process, a connection frequently not made explicit in other texts. The Stratonovich integral is briefly discussed in relation to the Ito integral, with one algebraic illustration. Next, solutions of Ito SDEs as diffusion processes are briefly discussed, and the theory sections then end with a warning against building models by tacking a Wiener driving term onto an ordinary differential equation. In this connection, the author refers readers to work of Wong and Zakai.
The book ends with a ten page section on applications. There is the usual account of the Wiener process as the limit of a sequence of random walk processes, and then from a continuous time walk where the jump epochs are controlled by independent Poisson processes, effectively a biased random telegraph process. This is presented in a neurological context. None of this uses Ito calculus.
Next, Malthusian population growth with a random growth rate is set up as a SDE and solved as a Stratonovich equation. The same equation, but in Ito guise, recurs in a financial context. Bachelier, geometric Brownian motion, and the Black-Scholes option pricing formula are all named, but the overall discussion goes nowhere.
Chapter 12 has a quite extensive reference list for the many items which the author mentions, but does not discuss. A collection of 30 problems is provided, most of which are routine in nature. For example, of the three questions devoted to Ito calculus, one asks for the Ito equations satisfied by three simple functions of the Wiener process, and another asks for the conversion of three Stratonovich equations to Ito form. Although this chapter presents a sound intuitive development of the principles of Ito calculus, in the end it falls down by not working through even one example.
Such abrupt termination of discussion just as things are becoming interesting is an unfortunate characteristic of the entire book. Too often the author gives tantalizing pointers to further reading, where I would have prefered to see some of this included at the expense of the elementary and standard distribution theory which comprises so much of the text. After all, the title emphasises applications, and in the preface the author asserts the book does not contain a lengthy introduction to probability and random variables. That is not my impression of its contents!
University of Western Australia
Do you want to know how Euler died, why Hypatia was killed, that Cantor and Cauchy both wrote poems to their wives and who were Christian Mathematicians?
You may find out the answers in this book. On the other hand you may not. For example, Anglin only surmises that Hypatia may have been killed because she had a well paid job.
Thus far it is clear that this book is tendentious and journalistic in style. To give credit where it is due there is a succinct and commendable account of the discovery and publication of the solution of the cubic by Cardano and others in the sixteenth century. (By the way you have to know that the text reference to ``Ars Magna'' means ``The Great Art'' in the list of references).
As to the book's substance here is a sample. In Chapter 25, p. 147, ``we give the solution to the cubic equation that is essentially that of Ferro, Tartaglia, and Viete.'' This is amazing. Ferro had one partial solution and as the author says on p. 142, Tartaglia could solve more cases, while Viete used a different method entirely. None of them used cube roots of unity as does the author.
So what Anglin does is in fact show is how you (or he) can solve a cubic. Fair enough, but not if you are claiming as Anglin does in the Preface that this is one of the ``many detailed explanations of the important mathematical procedures actually used by famous mathematicians''.
The book is replete with exercises and essay questions. My favourite exercise is no. 1 in Exercises 21: ``Prove the Trivial Theorem.'' However it does not take long to find which theorem is really meant, for the chapter only has two pages of text - not the only chapter of this brevity, nor the shortest.
This book is not a deep study, but someone who did all the exercises and essays - there are lots - would have learnt lots of history of mathematics by the end of those. The text and references would not provide a very good starting point and the student would have to work out which reference was relevant since Anglin rarely cites his sources.
For philosophy one would need even more work; philosophy essentially occupies a mere four pages: 206 and 217-219.
The book is ``accessible to students who have trouble coping with vast amounts of reading.'' Indeed, the main text occupies less than 150 pages.
Finally, the last essay question (p. 225) ends: ``Can you suggest some replacement for The `publish or perish' system that is currently cluttering our libraries with junk?'' - and, one might add, this book?
Monash University