## Posts Tagged 'Graph Theory'

### Order in the midst of Chaos

We open with a simple mathematical puzzle that is easily solved using only elementary reasoning. Imagine a party where some guests are friends while others are unacquainted. Then the following is always true:

No matter how many guests there are at the party, there are
always two guests with the same number of friends present.

If you wish, try proving this before reading on. The proof is outlined at the end of this post.

Complete graphs with 6 to 10 vertices.

### Topology in the Oval Office

Imagine a room – the Oval Office for example – that has three electrical appliances:

•  An air-conditioner ( a ) with an American plug socket ( A ),

•  A boiler ( b ) with a British plug socket ( B ),

•  A coffee-maker ( c ) with a Continental plug socket ( C ).

The problem is to connect each appliance to the correct socket, avoiding any crossings of the connecting wires.

Fig. 1: Positions of appliances and sockets for Problem 1.

### Venn Again’s Awake

We wrote about the basic properties of Venn diagrams in an earlier post. Now we take a deeper look. John Venn, a logician and philosopher, born in Hull, Yorkshire in 1834, introduced the diagrams in a paper in 1880 and in his book Symbolic Logic, published one year later. The diagrams were used long before Venn’s paper, but he formalized and popularized them. He used them as logical diagrams: the interior of each set means the truth of a particular proposition. Unions and intersections of sets correspond to the logical operators OR and AND.

### Big Data: the Information Explosion

The world is awash with data. Large data sets have been available for many decades but in recent years their volumes have grown explosively. With mobile devices and internet connections data capture is simple and with powerful computers the analysis of “big data” is feasible [see TM092, or search for “thatsmaths” at irishtimes.com].

Google image search for “Big Data”

But there are challenges: many data sets are too large and too complex to be analysed or understood using traditional data processing methods. Our current armoury of analysis techniques is inadequate and new mathematical methods are needed.

### Numbering the Family Tree

The availability of large historical data sets online has spurred interest in genealogy and family history. Anyone who has assembled information knows how important it is to organize it systematically. A simple family tree showing the direct ancestors of Wanda One is shown here:

### It’s a Small – Networked – World

Networks are everywhere in the modern world. They may be physical constructs, like the transport system or power grid, or more abstract entities like family trees or the World Wide Web. A network is a collection of nodes linked together, like cities connected by roads or people genetically related to each other. Such a system of nodes and links is what mathematicians call a graph [TM078; or search for “thatsmaths” at irishtimes.com ].

Detail of a Twitter communications network.