William Tutte’s Hidden Past

If William Tutte is remembered at all by architects, it is for his contribution to solving the problem of Squaring the Square . (Tutte 1958) A solution using Graph Theory and Kirchhoff’s Laws for electrical flow in wires that was subsequently used in Philip Steadman’s The Automatic Generation of Minimum Standard House Plans. (Steadman 1970)

112x112squaredsquare

This last, ultimately failed enterprise is explained in some detail here.

Bill Tutte died in 2002 and his obituaries, like this from the Guardian, reveal that he also had a wider influence on world events.

The Squaring the Square problem had been worked on at Cambridge by Bill Tutte, Leonard Brooks, Arthur Stone and Cedric Smith. They had met in 1936 and formed  the self-styled Important Members of the Trinity Mathematical Society. Collectively they published papers under the pseudonym Blanche Descartes, name created from their first names; Bill, Leonard, Arthur, and Cedric to form BLAnChe and Descartes giving a play on carte blanche.

Code Breaking

At the outbreak of the Second World War, Tutte was invited to join the  Government Code and Cipher School at Bletchley Park where he initially worked on Italian Naval Codes, before moving onto the Lorenz cipher. Enigma coding machines were used by all branches of the Wehrmacht, but the Lorenz code was only used for the top-secret, high-level traffic of the German general staff.

The breaking of the Enigma code, worked on by Alan Turing, benefited from earlier work by Polish mathematicians passed onto the French and then the British. Lorenz on the other hand had to be broken from scratch. The Enigma machines had 3 or 4 rotors or code wheels but the never seen Lorenz machine had an unknown number of rotors, eventually established as 12.

Bill Tutte’s relation to Lorenz has been described as being equivalent to Alan Turing’s relation to Enigma.

At first, each Lorenz coded message had to laboriously broken by hand, but Max Newman suggested that Turing’s pre-war idea of a computing machine could be applied to the problem. But the first machine called Robinson, named after cartoonist Heath Robinson’s amazingly ramshackle machines, proved unreliable.

Discussions between Newman, Turing, Tutte and Tommy Flowers, a Post Office telephone engineer, led to an electronic version of Robinson. This was Colossus; the first semi-programmable computer.

The application of Colossus to Lorenz messages provided continuing access to high grade intelligence, particularly that the D-day landing deceptions had been successful; ensuring that the Normandy landings could be carried out with a high degree of confidence.

Four Colour Theorem

A coloured map can be represented as a planar graph if the coloured regions of the map are replaced by same coloured vertices in the graph, and vertices are joined by an edge in the graph if their corresponding regions in the map share an edge.

/Users/grahamshawcross/Documents/blog_drafts/bill_tutte/FourColo

In fact the planar graph is a dual of the map, and the map can be generated from the graph and vice versa. Both map and graph obey Euler’s formula for networks f + v -e = 1, or regions + vertices – edges = 1. In the examples above 7 regions + 11 vertices – 17 edges = 1 for the map and 10 regions + 8 vertices – 17 edges = 1 for the graph.

The planar graph is therefore an exact equivalent of the map and the Four Colour Conjecture can be expressed as seeing if the vertices of the graph can be coloured with 4 colours so that no 2 adjacent vertices have the same colour.

More importantly planar graphs lend themselves to computer manipulation.

In 1976 Appel and Haken announced a ‘Proof’ of the Four Colour Conjecture that required the unavoidable computer testing of the reducibility of 1,936 graph configurations. (Appel and Haken 1977)

These tests were done by different software and computers, but the idea of  a computer checked proof remained problematic, particularly as the method was complicated and checking by hand so tedious that no one had tried it.

In 1996 Robertson, Sanders, Seymour and Thomas announced a simpler proof, that still required computer checking but was more amenable to verification by manual means. Their paper bears the following dedication (Robertson et al 1996)

DEDICATED TO PROFESSOR W.T.TUTTE ON THE OCCASION

OF HIS EIGHTIETH BIRTHDAY

Bibliography

Appel, K., Haken, W. and Koch, J.  1977 Every Planar Map is Four Colorable. I: Discharging. Illinois J. Math. 21, 429-490

Appel, K. and Haken, W. 1977 Every Planar Map is Four-Colorable, II: Reducibility. Illinois J. Math. 21, 491-567.

Brooks, R.L., Smith, C.A.B., Stone, A.H. and Tutte, W.T., 1940 The Dissection of Rectangles into Squares Duke Mathematical Journal, vol. 7, pages 312-40

Robertson, N.; Sanders, D. P.; Seymour, P. D.; and Thomas, R. A. 1996 New Proof of the Four Colour Theorem. Electron. Res. Announc. Amer. Math. Soc. 2, 17-25.

Steadman, P., 1970. The Automatic Generation of Minimum Standard House Plans Working Paper 23 University of Cambridge Land Use and Built Form Studies

Tutte, W. T., 1958. Squaring the Square from ‘Mathematical Games’ column, Scientific American Nov 1958.

About Graham Shawcross

Architect PhD student at Edinburgh University Interested in order, rhythm and pattern in Architectural Design
This entry was posted in Architecture, Design Methods, Geometry, Logic, Tiling and tagged , , , , , , . Bookmark the permalink.

3 Responses to William Tutte’s Hidden Past

  1. Wish I could show my short proof of the 4CT to Bill Tutte
    https://www.academia.edu/541633/On_the_Algorithmic_Proofs_of_the_Four_Color_Theorem

    P.S. Similar feeling has been expressed during my presentation at the ICM 2006, Madrid by his colleague and friend Henry Crapo:
    Discussion "Four Color Theorem" over a bottle of wine

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s