Star polynomials

Edward J Farrell is a celebrated mathematician of the African Diaspora. In 1978, he introduced a general class of graph polynomials, called Farrell-polynomials. Let $F$ be a family of connected graphs (meaning there exists a path between each pair of nodes – a path can be made up of edges and other nodes). With each element $\alpha$ belonging to $F$, we can associate an indeterminate or weight $w_{\alpha}$. An $F$-cover of a graph $G$ is a spanning subgraph, all of whose components belong to $F$. A spanning subgraph is a subgraph which contains all nodes of the original graph. With each $F$-cover $C$ of $G$, we associate the weight $w(C)=\prod w_{\alpha}$, where the product is taken over all the components $\alpha$ in $C$. The $F$-polynomial of $G$ is $F(G;\underline{w})=\sum w(C)$, where $\underline{w}$ is a vector of indeterminates defined by $w_{\alpha}$ and the summation is taken over all the $F$-covers in $G$.

A tree is a graph in which any pair of nodes is connected by exactly one path. An $m$-star $S_m$ is a tree with $m+1$ nodes, containing a node of valency (degree) $m$ called the centre of the star, meaning it is joined to $m$ other nodes. These $m$ nodes of valency 1 are called tips. A proper star is a star that contains at least one edge. A 0-star is a component node and a 1-star is a component edge as shown below.  Continue reading


The doodle theorem, and beyond…

One of the things I like about recreational maths is how we can start with a simple game, play around a bit, poke in the corners, and suddenly fall down a deep hole into some serious mathematics. In this article we start with some well-trodden ground, which some readers will find familiar. However, we quickly find that all is not as it seems, and we soon stumble over a veritable pot of gold. To see how, read on…

Continue reading


Cracking the Guess Who? board game

Does this person have ginger hair?
  Is this person a boy?
  Is she wearing a hat?
  Is your person Anita?

Maybe everyone has played Guess Who?: the board game where you try to guess which character your opponent has before they find out yours. For those who have never played Guess Who?, the game goes as follows: each player picks a card at random, on which will be drawn the face of a character. In turns, the two players ask each other yes/no questions to try and guess who their opponent has picked. A board with all the images of the characters initially standing up helps the player keep track of which ones have been eliminated along the way. Continue reading


A counterintuitive result in the theory of traffic flow

Traffic presents a nightmare for city planners. As well as being a pain for commuters, the environmental, financial and social cost of traffic is huge. Cities are still plagued with traffic jams, with rush ‘hour’ being a far too kind a name for the three hour period during which many of the roads are gridlocked. A possible solution to seemingly never ending traffic jams is to add additional infrastructure, but is this always the best solution? Consider the following (made up) scenario.

Banner1The school run

Every weekday, 8am sharp, 40 people drive their children from Aelston (A) to Deephurst (D). As things stand, there are two possible routes, going north via Byfair (B) or south via Churchgate (C). The roads connecting AB and CD have lots of lights and a slow speed limit, fixing the flux of traffic, with both roads taking 27 minutes to traverse. The roads connecting BD and AC have no traffic lights but are more prone to jams, taking 5 minutes to travel, plus half a minute for every other car using the road.

The local council, keen to win votes for the upcoming election, have tarmacked the local green space and built a new multilane motorway connecting BC. This 4-lane monstrosity is very fast and only takes 2 minutes to traverse. To the council’s dismay, the travel time for the school run has increased for everyone! Disgruntled and embarrassed, the council have brought in a mathematician to explain what has happened.

Networks and Braess’ paradox

When considering how to present the information above, one might quite naturally draw a network (often called a graph). We represent the areas A to D as ‘nodes’ and the roads as ‘edges’. We assign ‘weights’ to each road, the value being the number of minutes it takes to go from one end of the road to the other. Allowing the edges to have directions, we obtain the following graphs for the pre and post-motorway systems:

Traffic assignment before building the road

Traffic assignment before building the road

Traffic assignment after building the road

Traffic assignment after building the road

where T represents the number of cars on the road.

Now for both systems, we shall seek the user-optimised configuration. This models the selfish nature of individuals using the network. Every driver will, if possible, change their route to the quickest path,
without concern whether the change will slow down everyone else’s journey. This is in contrast with the system-optimised configuration: the routes are assigned by someone who determines the optimal way to minimise the amount of time cars are collectively on the road.

Before the motorway was constructed, it is clear that the user-optimised configuration is to have 20 cars take ABD and 20 take ACD. In this case:

\lvert ABD \rvert = \lvert ACD \rvert = 5 + \frac{20}{2} + 27 = 42 ,
where $\lvert – \rvert$ represents the time taken to complete the route $-$.

After the motorway was constructed, people taking the southern route noticed that avoiding CD would at worst take the same amount of time as going via CBD. This is because T satisfies $T\leq 40$, and hence

\lvert CBD \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert CD \rvert .\\
The drivers initially taking the northern route also noticed that the slow road AB could be avoided in a similar manner:

\lvert ACB \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert AB \rvert .\\
Hence, no matter what the other 39 cars are doing, it is always beneficial for the selfish driver to take the route ACBD. But, since all the drivers think the same thing, these roads are more congested than before, and the new travel time is
\lvert ACBD \rvert = 5+\frac{40}{2} +2+5+\frac{40}{2} = 52,
10 minutes slower than before! However, no driver is willing to change, since any other route in this network with such a configuration is slower! Only if all the drivers cooperate, and agree to resist the temptation of avoiding the slow roads, can the previous system-optimised configuration be achieved. Hence, we see that in user-optimised networks, improved connectivity between two points does not imply a more efficient system. This phenomenon in networks was first demonstrated by Dietrich Braess in 1968, and is aptly named “Braess’ paradox”.

Concluding remarks

In our model, before the new motorway, there were two balanced options. The addition of the motorway then created a new preferable route, with the negative result that all traffic chose to take it, causing congestion. Although this model may seem far from realistically modelling roads, it demonstrates that networks can have this characteristic. Braess’ paradox is seriously discussed in traffic flow literature, and real life examples of this phenomenon are documented. In New York, there were reports of improved traffic when 42nd Street was shut for Earth Day in 1990. In Seoul, South Korea, the government went as far as demolishing a highway near the centre of the city to avoid the road being overused.


Picture of Seoul before and after the destruction of the freeway.

This result is a nice example of how our intuition can be tricked.


Optimal Pac-Man

In the classic arcade game Pac-Man, the player moves the title character through a maze. The aim of the game is to eat all of the pac-dots that are spread throughout the maze while avoiding the ghosts that prowl it.

While playing Pac-Man recently, my concentration drifted from the pac-dots and I began to think about the best route I could take to complete the level.

Continue reading