Earlier today I spotted this video, featuring the stand-up mathematician Matt Parker and all-round interesting person Tom Scott exploring some oddities of the tube:
Matt’s ability to beat Tom around the network depended on local knowledge of hidden shortcuts. You might wonder why these quicker options aren’t indicated by signs, but as they explain in the video, for some the problem is that they’re only quicker because they’re secret. Were the full force of the travelling public to try and use them, the resulting congestion would lead to travel times even worse than the officially sanctioned route.
This is a real-world manifestation of the price of anarchy, an area of maths I find fascinating, as it collides game theory with networks. An obvious starting point is `Pigou’s Example’, which I’ll simplify here slightly.
Suppose there are two choices for a journey across a valley: a long but reliable bypass that loops around it, taking ten minutes to complete the journey; and a direct bridge that suffers badly from congestion, so that journey times grow with the number of users. To be precise, let’s imagine that if x people cross the bridge, they each take x minutes to do so. Now imagine that ten people want to travel across the valley. Which route should they take?
With a bit of thought, we can see that they should all try for the bridge: at worst it only takes ten minutes anyway, but for each person that opts for the bypass you’ll save a minute by sticking with the bridge. Put another way, if you’ve opted for the bridge, you gain nothing by switching to the bypass, regardless of the choices of the other travellers. In game theory terms, everyone using the bridge is a Nash equilibrium – a stable situation in the sense that no-one can improve their journey by changing strategy (from bridge to bypass).
However, it’s not a social optimum: with ten people on the bridge, they each have a journey time of ten minutes each; but if we could force five to take the bypass instead (requiring the same ten minutes) then those on the bridge now have a journey time of five minutes. This means that the population as a whole spends 75 minutes travelling, rather than a hundred. This is a genuine improvement for all concerned, with no-one being asked to take a longer journey than before, and some experiencing a shorter one. (One can devise scenarios where forcing a longer journey on a few makes things better on average, but that seems less fair.)
Unfortunately, allowing selfish travellers to self-organise, this arrangement is not stable: those on the bypass will look enviously at the speedsters on the bridge, and opt for it next time. The problem is choice, or rather that we can’t trust others not to make a choice that gives them an advantage. If our valley crossers could enter into a gentleman’s agreement that half of them would use the bridge on the opposite day to the rest, all would be well. But the non-cooperative approach to game theory takes the pessimistic view that people will agree to anything – particularly if that puts you on the bypass! – then proceed to selfishly use the bridge every day anyway. Under such assumptions, we then need an external authority – be it a government, the mafia code of honor, or Transport for London’s crafty signwriters – to force us to take action that’s for the greater good: even if it’s good for us too.
This sheds some light on a related problem that seems at first counter-intuitive, and has thus become known as Braess’ Paradox: adding more capacity can make everyone’s journey slower! This will occur if the network is already experiencing congestion, and once again is due to the perils of choice. If the new route becomes the obvious way to go, it can create an even greater bottleneck than before as everyone tries to save some time by using it.
As an example, consider our same ten travellers, now trying to get from A to B via two alternatives C and D as follows:
As before, we have a social optimum by sending half of the traffic via C, and the rest via D. In this way, everyone has a journey time of 17 minutes. But as both routes involve a road that is subject to congestion, this is also a Nash equilibrium: if C and D are equally used, then you make your journey worse by swapping to the other. However, a well-meaning city planner can ruin everything by adding a new, fast road between those two:
Now a Nash Equilibrium arises in which everyone takes the route A-C-D-B: for a total travel time of 21 minutes, four worse than before! We see that this is an equilibrium because if you switch to A-D-B your journey time becomes 22 minutes (because everyone is still on D-B); A-C-B also takes 22 minutes since then everyone uses A-C. Of course, with a benign dictator we can ignore the C-D road entirely and have 17-minute journeys for all. But that can’t arise from selfish decisions, as anyone on the A-C-B route will try to trade the 12 minutes of C-B for the 1+x of C-D-B, and similarly A-D-B travellers will spot that A-C-D is more appealing than A-D. So everyone defects to A-C-D-B in the hopes of a 12 minute journey- and they all end up worse off than before…
Such phenomena are not just mathematical curiosities, as they’ve been encountered in real travel networks too. A New York Times article, What if They Closed 42d Street and Nobody Noticed?, discusses Braess’ paradox in reverse- closing a road in a notoriously busy city sounds like a recipe for travel disaster, but by removing an option the flow of traffic actually improved. Similarly travel times in Seoul were reduced after a 6-lane highway was demolished in favour of a park: a double-win for the environment!
Still, as a fairly-frequent user of the Underground, I can’t help but fear I’ll be selfishly adopting some of Matt and Tom’s hacks- at least until everyone else catches on…
My third paper on the Mahler measure problem has been accepted by the Electronic Journal of Combinatorics, and is available here freely under the E-JC’s open access policy.
This is joint work with Gary Greaves, and completes the proof of Lehmer’s conjecture for matrices with entries from rings of integers of quadratic extensions: a project that has spanned five papers and two PhDs between us!
I have now completed a series of introductory lectures on Graph Theory, for 3rd/4th year students at the University of Bristol. A set of written notes plus (less usefully) my slides are mirrored here. One student declared this to be “[the] most interesting course I have taken at Bristol Uni”, so take a look to see how graphs can be applied to everything from organic chemistry to cold war politics!
The San Diego Convention Center, home to the 2013 Joint Mathematics Meetings.
Earlier this month I attended the 2013 Joint Mathematics Meetings, trading freezing Britain for sunny San Diego! This was the 119th annual meeting of the American Mathematical Society, the 96th of the Mathematical Association of America, my third trip to the US for a JMM, and the first at which I’ve given a talk. There are also sessions organised by the Association of Women in Mathematics, the National Association of Mathematicians, the Association of Symbolic Logic, and the Society for Industrial and Applied Mathematics, and with over 6500 people in attendance, no shortage of topics to hear about! One of the things I love about these meetings is that in addition to the sessions that you’re involved in, you have an opportunity to attend events that catch your interest, but you couldn’t normally justify travelling to on their own. Two years ago, I gave a complete rundown of my schedule for my first JMM; this year I thought I’d pull out some highlights.
As a photographer I have a particular love of architectural subjects. But even without a camera in hand, I can spend many a happy hour wandering an unfamiliar city absorbing its particular style (conversely, few things will put me off a place faster than ugly buildings – 60′s brutalists, I’m looking at you!) However, I don’t generally know much about what I’m looking at! So I was pleased to find a trio of consecutive talks in the MAA Session on Mathematics and the Arts of an architectural bent. One of the speakers turned out to be the author of a book – Mathematical Excursions to the World’s Greatest Buildings – which I received for christmas and am very much looking forward to diving into; and another also presented a series of locations used an examples in a course on multicultural mathematics. Perhaps it’s time for me to revive my mathematical tourism efforts! Most intriguing, though, was Frode Rønning’s talk on the Dutch Benedictine monk Dom Hans van der Laan, who sought to find theoretical underpinnings to architecture. His study of the limits in our ability to perceive differences in proportion in the context of 3-dimensional space led him to the plastic number: the real solution to P+1=P3. Much has been made of the alleged aesthetic qualities of its more famous cousin, the golden ratio; that is a solution to &Phi+1=Φ2. Another characterisation of the golden ratio is that it satisfies Φ-1=1/Φ the plastic number is similar in that P-1=1/P4. A number is called morphic if there are positive integers m and n such that x+1 = xm and x-1=x-n; the golden ratio and plastic number are both morphic, and in fact, they are the only morphic numbers! But my own connection to this number is through Mahler measure; in my work, it has only been necessary to study non-reciprocal polynomials, because it is known that the Mahler measure of reciprocal polynomials is bounded below. What by? The plastic number!
`Superfrabjous’, by George Hart – from the art exhibition at the 2013 JMM.
Continuing with the artistic theme, I as usual enjoyed the art exhbition (although I didn’t find the time to contribute a piece of my own). Sculptural work, such as shown to the left, always has immediate appeal for me, but there were some strong printed works this year too. Particularly striking were Daniel Gries’ Fractal Cylinder renders: there are lots more of these here, and the code to generate new examples is also available. As beautiful as they are on-screen, they’re even more impressive as a decently-sized and properly mounted print. I was also amazed to find that Charles Redmond’s Starry Pines was a purely generative work, using something called the Context Free Art language, which I’ll have to look into. Finally, I found myself repeatedly returning to Etienne Saint-Amant’s WABE: Broken Perspective.
I attended a couple of talks of a game-theoretic flavour in the AMS Special Session on Mathematics and Social Interactions. Angela Vierling-Classen examined the issue of gendered division of parenting, demonstrating models in which, even if both parents value equality of effort and it forms a valid Nash equilibrium, most starting states converge to equilibria with unequal assignments. Thus it’s not enough to want equality – you have to commit to it from day one! Her presentation also touched on some of the difficulties in publishing highly mathematical work in sociology journals. The other looked at ‘sacred values’, and how inviolable ties between players in adversarial evolutionary games could lead to new outcomes compared to models in which nothing is sacred. In particular, criminal gangs were able to persist in a game which otherwise tends to a crime-free utopia, as players may be compelled to act against self-interest in support of the gang, or alternatively may benefit from allegiance to such a group by way of protection from other criminals!
Loosely on the subject of sacred values, this session also hosted a talk that has surely the strangest abstract I’ve ever seen at a conference; tragically I couldn’t make it to the event, so feel I shouldn’t dismiss it outright as nonsense, but, well, take a look for yourself. Is anyone brave enough to buy the book?
Tony DeRose discussed some of the challenges of animating Merida – or rather, her hair!
Instead, I opted for the MAA Invited Address, How mathematics has changed Hollywood by Tony DeRose from Pixar. Obviously this was a visual treat, with behind-the-scenes (as it were) footage from Monsters Inc, Finding Nemo and Brave. Originally, handling physical constraints like the effects of gravity or momentum, or preservation of volume, were simply down to the animators; trying to implement real physics into the rendering systems introduces all kinds of difficulties when reality clashes with artistic vision! This causes both entertaining mathematical out-takes, and the need for creative solutions. For instance, Merida’s hair – which Tony describes as practically a character in itself – could not be implemented as individual strands, or it would whip around impossibly violently. To get the right mix of softness under low acceleration, whilst holding shape under high acceleration, a system was devised where curls are loosely coupled to a stiff core. Whilst no-one has hair like this, it paradoxically looks more realistic! Similarly, the robot Wall-E performs manoeuvres that would tear apart a real machine of that size; and no human is built like Mr Incredible! For Pixar, then, realistic physics is just the beginning – not an end. More technical detail was given in the context of a problem known as surface subdivision: a seemingly simple process of splitting and averaging raises interesting questions about its behaviour in the limit, with limit curves ranging from smooth, differentiable shapes to nowhere-smooth fractals: which can nonetheless be easily animated! Impressively, Pixar have made all this work freely available as the open source library opensubdiv, and indeed have a research arm that produces academic publications and technical memos.
DeRose is also clearly passionate about enthusing young people about STEM topics, and spoke a bit about his involvement with Young Makers, which supports Maker Faire-style projects. There has been a long-running Art of Pixar travelling exhibition; plans are apparently well underway for a corresponding Science of Pixar in collaboration with the Museum of Science in Boston. I’ll be looking out for that.
The invited addresses were linked to extended sessions on the same theme, with additional speakers- for De Rose’s talk, this was the MAA Invited Paper Session on Mathematics, Computer Graphics, and Film Production. I only had time for one of the talks, Tim Chartier’s Animating Class with Computer Graphics. But if I ever find myself lecturing linear algebra, I’d be highly tempted to use some of his ideas on illustrating matrix operations through their effects on graphics. Working in Matlab, linear transitions between two source images can be used to create animated tricks like invisibility or teleportation. Splitting images into separate matrices for each colour channel then manipulating them can give Warholesque artworks, or apply effects akin to Instagram or Photobooth.
In fact, Chartier is a mine of ideas for making undergraduate education more engaging (a theme that is picked up in many other sessions), and gave an MAA invited address himself, Thinking Linearly about Data. This focused largely on the questions of ranking and clustering of data – but whereas such talks normally look at Google’s pagerank, or recommendation tasks like the Netflix prize, this talk was new territory for me, tackling sports rankings. I have to admit that I was held back slightly by my complete lack of insight into the worlds of basketball and american football, but for US students these are relatable topics, and the mathematics is rather more accessible. Indeed, one of the ranking systems for american football was devised by an undergraduate! Best of all, students can take what they’ve learnt, make their own tweaks, and apply it successfully to a real-world problem. March madness is a highly popular basketball tournament, and literally millions of predictions as to who will be eliminated when are made by ‘bracketologists’. Using graph theory and linear algebra, undergraduate mathematicians have managed to out-perform sports `experts’ and win bracketology contests. There’s a writeup (and video version) of a previous MAA talk by Chartier on all this here.
The linked session, Thinking Linearly about data was just one of many I attended that looked at social network analysis, big data, and often both: other sessions included the AMS-MAA-SIAM Special Session on Research in Mathematics by Undergraduates and Students in Post-Baccalaureate Programs, the MAA Invited Paper Session on Mathematics in Industry, and the MAA Session on Mathematics Experiences in Business, Industry and Government. This seems to be quite the hot topic at the moment, and it was great to hear from a range of practitioners from outside of academia, and to see that even undergraduates are making progress in this area. There were talks on data forensics by mobile phone providers trying to detect the new identity of former customers; more on sports analysis; the challenges of performing even simple tasks like triangle-counting for clustering when data sets are several terabytes in size; the perils of `weapons of math destruction’, whereby metrics are used inappropriately and detrimentally in contexts as diverse as credit scoring, teacher evaluation, and medical insurance; assessing the efficiency of transport networks; and using community detection for understanding the brain. All excellent food for thought!
Finally, the Joint Meetings provided a great opportunity to raise awareness of The Mathematics of Planet Earth 2013, a year-long program of both research and outreach on some of the most fundamental problems related to challenges facing the planet. Climate change will naturally play a big part in this, and we were treated to two talks by mathematicians working in an environment where those changes could be most dramatic: Antarctica. I have long had a fascination with the polar regions, jealously following blogs such as The Dry Valleys, or pricing up impossibly ambitious sightseeing trips to remote parts of Norway. Turns out, if I’d stuck to applied maths, I could have visited such places and done useful things, rather than just hope to be a tourist! Fortunately I was able to live vicariously through these excellent presentations. Emily Shuckburgh from the British Antarctic Survey, gave the AMS-MAA Invited AddressUsing mathematics to better understand the Earth’s climate; whilst the MAA-AMS-SIAM Gerald and Judith Porter Public Lecture was Mathematics and the melting polar ice caps.by Kenneth Golden. This last finished with a fantastic video that I was hoping to share here, but it seems we got a sneak preview as it isn’t available online yet. However, you can get some idea (with less shots of curious penguins) from this earlier footage:
There were many other talks, from a variety of sessions, that I attended: but since I claimed this would be a selection of highlights rather than a full log, and is weighing in at 2000 words, I think I’ll stop here!
In the next academic year I’ll be one of the lecturers for Topics in Discrete Mathematics at the University of Bristol. This comes in two flavours- the level H/6 unit MATH30002 for third-year students, and the level M/7 unit MATHM0009 for those in the fourth year (which adds a project component).
This will be the first year such a course has been offered at Bristol, and it has been deliberately designed to allow some flexibility in the content. I’ll be covering the fundamentals of graph theory, and the main topics I intend to cover are Euler tours, Hamiltonian circuits, adjacency matrices / spectral graph theory, planarity, and the Platonic solids. This will be largely self-contained, although some confidence with linear algebra will be helpful in places. If you’re a student currently weighing up choices for next year, and have any questions about this part of the course, feel free to get in touch!
I’m offering a couple of possible projects for third-year students at Bristol (i.e., for MATH32001 or MATH32200 depending on amount of time) in the upcoming academic year (2012/13). Other topics in areas such as spectral graph theory or computational number theory could also be possibilities; students are welcome to get in touch (via my magdt@bristol account) to arrange a more in-depth discussion.
1) The Mathematics of Social Networks
This project would start with an introduction to the key concepts of graph theory, before turning to applications to ‘social’ graphs. For instance, how might we identify the most influential scientists from the graph of their collaborations? If two countries come into conflict, who are their neighbours more likely to ally with? And how can it be that, on average, your friends have more friends than you do- yet the same is true for them?
2) Discrete and Computational Geometry
Although the study of geometry is almost as old as mathematics itself, discrete and computational geometry – at the intersection of computer science and mathematics – has only attracted attention in the last few decades. Nonetheless, it has found many applications, such as terrain reconstruction, robot motion planning, and remarkable advances in the discipline of ‘mathematical origami’.
A project in this area might suit a student with a strong interest/ability in programming (particularly related to computer graphics), but the material can also be approached in a purely theoretical way.
These remarks started life as a series of short posts on Google+. But no-one uses Google+, so I’ve archived them here.
I: you can make Voronoi diagrams using fine sand and blocks with holes drilled in.
What’s a Voronoi diagram? In such an image, the plane is divided up into cells around sites, such that the closest site to any point is the one in the same cell. Thus the boundaries are equidistant between sites; for the sand, those are the raised ridges, with the sites being the holes.
There’s obvious applications to mapping, say, your nearest coffee shop; an early application was tracing the source of a cholera outbreak to a particular water pump. But it also explains natural processes that involve growing or spreading, such as the patterning of giraffes!
II: The one-cut theorem.
If you draw a shape out of straight lines then -even if it has holes, such as the letter A – there’s a way to fold a piece of paper such that a single straight cut will give you something which, when unfolded, is the shape you wanted. (Some example folding patterns which we used are at http://howtofoldit.org/ ). For more details, see The Fold-and-Cut Problem.
‘FastRunner‘ – prototype Ostrich-like legs that might be able to hit 30-50mph (I suspect they’re trying to make the roadrunner).< ?li>
Robotic birds, from gliders that can land on a perch, to flight via flapping wings.
IV: Polyhedral unfoldings
V: The complexity of games and puzzles.
For instance, a common question in the study of games is whether there’s a way to determine if you have a winning move this turn- the ‘mate in one’ problem for chess. It turns out that if you generalise Settlers of Catan to arbitrary-sized boards, then you can’t even feasibly handle the ‘mate in zero’ problem – that is, determine if you’ve already won! We also learnt of the hardest game in the world, Rengo Kriegspiel, which is blindfolded team Go, and turns out to be undecidable.
A while ago I became interested in `captured lightning‘ Lichtenberg figures, but without access to megavolt-scale physics gear, I wondered if I could simulate them in software instead. I was reminded of this when I had my JMM art exhibition entry printed on glass, as this would give me something a bit closer to the acrylic blocks. Some initially vague google searches eventually lead me to Diffusion-limited aggregation, a process that generates trees somewhere between ferns and lightning bolts. I set about implementing this in processing, and you can play around with a small version of it here:
Controls: To set things in motion (or pause them), press SPACE. To restart, press R. You can cycle through various colour options with G, and toggle rendering of the random walks with W. The screen is redrawn after a fixed number of points have been tested, which can be decreased with Z or increased with X: if your computer is powerful enough, it can cope with updating the screen more often; even if it can’t, you can decrease this to 1 to watch a step-by-step construction.
How does it work? There is an initial core disc of points which are included in the structure, and its horizon – the distance of the furthest point from the centre – is tracked. New points are launched from a ‘birth’ circle with radius a fixed multiple (until the edge of the screen gets in the way) of the horizon; further out, there is a ‘killing’ circle. Once launched, points take steps in random directions of size large enough to move them within the horizon- although of course they may go the wrong way! If they ever cross the killing circle they are abandoned, and a new point launched; if they move within the horizon, they switch to taking steps of unit distance instead. If at any stage they bump into a point already in the structure, they stick to it: they stop moving, become part of the structure (possibly increasing its horizon, and thus pushing out the birth/killing circles) and a new point is launched. There’s a fixed maximum radius for the horizon, and once this is reached, no more points are launched.