Abstract
Bill Tutte was born on May 14, 1917 in Newmarket, England. In 1935, he began studying at Trinity College, Cambridge reading natural sciences specializing in chemistry. After completing a master’s degree in chemistry in 1940, he was recruited to work at Bletchley Park as one of an elite group of codebreakers that included Alan Turing. While there, Tutte performed “one of the greatest intellectual feats of the Second World War.” Returning to Cambridge in 1945, he completed a Ph.D. in mathematics in 1948. Thereafter, he worked in Canada, first in Toronto and then as a founding member of the Department of Combinatorics and Optimization at the University of Waterloo. His contributions to graph theory alone mark him as arguably the twentieth century’s leading researcher in that subject. He also made groundbreaking contributions to matroid theory including proving the first excluded-minor theorems for matroids, one of which generalized Kuratowski’s Theorem. He extended Menger’s Theorem to matroids and laid the foundations for structural matroid theory. In addition, he introduced the Tutte polynomial for graphs and extended it and some relatives to matroids. This paper will highlight some of his many contributions focusing particularly on those to matroid theory.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ball, W.W.R.: Mathematical Recreations and Essays, 1st edn. Macmillan, London (1892). Revised and updated by H.S.M. Coxeter, 13th edn. Dover, New York (1987)
BBC 2011: Code-breakers: Bletchley Park’s lost heroes. Documentary (October 2011). Producer/Director Julian Carey
Brooks, R.L., Smith, C.A.B., Stone, A.H., Tutte, W.T.: The dissection of rectangles into squares. Duke Math. J. 7, 312–340 (1940)
Crapo, H.H.: The Tutte polynomial. Aequationes Math. 3, 211–229 (1969)
Descartes, B.: The three houses problem. Recited by W.T. Tutte. Tutte Eightieth Birthday Conference Dinner, University of Waterloo, 1997
Edwards, K., Sanders, D.P., Seymour, P., Thomas, R.: Three-edge colouring doublecross cubic graphs. J. Combin. Theory Ser. B 119, 66–95 (2016)
Farr, G.: Remembering Bill Tutte: another brilliant codebreaker from World War II, 12 May 2017. http://theconversation.com/remembering-bill-tutte-another-brilliant-codebreaker-from-world-war-ii-77556
Farr, G.E.: Tutte-Whitney polynomials: some history and generalizations. In: Grimmett, G., McDiarmid, C. (eds.) Combinatorics, Complexity, and Chance, pp. 28–52. Oxford University Press, Oxford (2007)
Farr, G.E., The history of Tutte-Whitney polynomials, with commentary on the classics. In: Ellis-Monaghan, J., Moffatt, I. (eds.) Handbook of the Tutte Polynomial. CRC Press, Boca Raton (to appear)
Geelen, J.F., Gerards, A.M.H., Whittle, G.: Branch-width and well-quasi-ordering in matroids and graphs. J. Combin. Theory Ser. B 84, 270–290 (2002)
Geelen, J., Gerards, B., Whittle, G.: Excluding a planar graph from GF(q)-representable matroids. J. Combin. Theory Ser. B 97, 971–998 (2007)
Harper, N.: Keeping secrets. University of Waterloo Magazine, Spring, 2015. https://uwaterloo.ca/magazine/spring-2015/features/keeping-secrets
Hobbs, A.M., Oxley, J.G.: William T. Tutte, 1917–2001. Not. Am. Math. Soc. 51, 320–330 (2004)
Jaeger, F.: On nowhere-zero flows in multigraphs. In: Nash-Williams, C.St.J.A., Sheehan, J. (eds.) Proceedings of the Fifth British Combinatorial Conference, pp. 373–378. Congressus Numerantium, No. XV. Utilitas Mathematica, Winnipeg (1976)
Kuratowski, K.: Sur le problème des courbes gauches en topologie. Fund. Math. 15, 271–283 (1930)
Oxley, J.: Matroid Theory. 2nd edn. Oxford University Press, New York (2011)
Poincaré, H.: Second complément à l’analysis situs. Proc. London Math. Soc. 32, 277–308 (1900)
Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28, 305–359 (1980)
Seymour, P.D.: Nowhere-zero 6-flows. J. Combin. Theory Ser. B 30, 130–135 (1981)
Seymour, P.D.: On Tutte’s extension of the four-colour problem. J. Combin. Theory Ser. B 31, 82–94 (1981)
Sprague, R.: Beispiel einer Zerlegung des Quadrats in lauter verschiedene Quadrate. Math. Z. 45, 607–608 (1939)
Sutherland, G.B.B.M., Tutte, W.T.: Absorption of polymolecular films in the infra-red. Nature 144, 707 (1939)
Tait, P.G.: Listing’s topologie. Philos. Mag., 5th Series 17, 30–46 (1884)
Tutte, W.T.: On Hamiltonian circuits. J. Lond. Math. Soc. 21, 98–101 (1946)
Tutte, W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 22, 107–111 (1947)
Tutte, W.T.: A ring in graph theory. Proc. Camb. Philol. Soc. 43, 26–40 (1947)
Tutte, W.T.: A family of cubical graphs. Proc. Camb. Philol. Soc. 43, 459–474 (1947)
Tutte, W.T.: An algebraic theory of graphs. Ph.D. thesis, Cambridge University (1948). https://billtuttememorial.org.uk/links/
Tutte, W.T.: A contribution to the theory of chromatic polynomials. Canad. J. Math. 6, 80–91 (1954)
Tutte, W.T.: A class of Abelian groups. Canad. J. Math. 8, 13–28 (1956)
Tutte, W.T.: A homotopy theorem for matroids. I, II. Trans. Am. Math. Soc. 88, 144–174 (1958)
Tutte, W.T.: Squaring the square. In: Scientific American, Mathematical Games Column (November 1958). Reprinted in Gardner, M.: More Mathematical Puzzles and Diversions. G. Bell and Sons, London (1963) http://www.squaring.net/history_theory/brooks_smith_stone_tutte_II.html
Tutte, W.T.: Matroids and graphs. Trans. Am. Math. Soc. 90, 527–552 (1959)
Tutte, W.T.: A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64, 441–455 (1961)
Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. (3) 13, 743–767 (1963)
Tutte, W.T.: Lectures on matroids. J. Res. Nat. Bur. Stand. Sect. B 69B, 1–47 (1965)
Tutte, W.T.: Menger’s theorem for matroids. J. Res. Nat. Bur. Stand. Sect. B 69B, 49–53 (1965)
Tutte, W.T.: On the algebraic theory of graph colorings. J. Combin. Theory 1, 15–50 (1966)
Tutte, W.T.: Connectivity in graphs. University of Toronto Press, Toronto (1966)
Tutte, W.T.: Connectivity in matroids. Canad. J. Math. 18, 1301–1324 (1966)
Tutte, W.T.: A correction to: “On the algebraic theory of graph colorings”. J. Combin. Theory 3, 102 (1967)
Tutte, W.T.: On even matroids. J. Res. Nat. Bur. Stand. Sect. B 71B, 213–214 (1967)
Tutte, W.T.: Projective geometry and the 4-color problem. In: Tutte, W.T. (ed.) Recent Progress in Combinatorics, pp. 199–207. Academic Press, New York (1969)
Tutte, W.T.: A geometrical version of the four color problem. In: Bose, R.C., Dowling, T.A. (eds.) Combinatorial Mathematics and Its Applications, pp. 553–560. University of North Carolina Press, Chapel Hill (1969)
Tutte, W.T.: Selected Papers of W. T. Tutte/Edited by D. McCarthy, R. G. Stanton, vol. I. Charles Babbage Research Centre, Winnipeg (1979)
Tutte, W.T.: Selected Papers of W. T. Tutte/Edited by D. McCarthy, R. G. Stanton, vol. II. Charles Babbage Research Centre, Winnipeg (1979)
Tutte, W.T.: The coming of the matroids. In: Lamb, J.D., Preece, D.A. (eds.) Surveys in Combinatorics, pp. 3–14. Cambridge University Press, Cambridge (1999)
Tutte, W.T.: FISH and I. In: Joyner, D. (ed.) Coding Theory and Cryptography, pp. 9–17. Springer, Berlin (2000)
Tutte, W.T.: Graph-polynomials. Adv. Appl. Math. 32, 5–9 (2004)
Welsh, D.J.A.: Complexity: Knots, Colourings and Counting. Cambridge University Press, Cambridge (1993)
Whitney, H.: The coloring of graphs. Ann. Math. (2) 33, 688–718 (1932)
Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57, 509–533 (1935)
Younger, D.H.: William Thomas Tutte, 14 May 1917–2 May 2002. Biogr. Mem. Fellows Roy. Soc. 58, 283–297 (2012)
Acknowledgements
Part of this paper was presented by the second author at the Tutte Centenary Retreat (https://www.matrix-inst.org.au/events/tutte-centenary-retreat/) held at the MAThematical Research Institute (MATRIx), Creswick, Victoria, Australia, 26 Nov. to 2 Dec. 2017. The authors gratefully acknowledge the support of MATRIx for this retreat.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Farr, G., Oxley, J. (2019). The Contributions of W.T. Tutte to Matroid Theory. In: de Gier, J., Praeger, C., Tao, T. (eds) 2017 MATRIX Annals. MATRIX Book Series, vol 2. Springer, Cham. https://doi.org/10.1007/978-3-030-04161-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-030-04161-8_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-04160-1
Online ISBN: 978-3-030-04161-8
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)