×

The contributions of W.T. Tutte to matroid theory. (English) Zbl 1415.05033

Wood, David R. (ed.) et al., 2017 MATRIX annals. Cham: Springer. MATRIX Book Ser. 2, 343-361 (2019).
Summary: 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.
For the entire collection see [Zbl 1411.37003].

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05-03 History of combinatorics
01A70 Biographies, obituaries, personalia, bibliographies
01A60 History of mathematics in the 20th century

Biographic References:

Tutte, William T.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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) · JFM 36.0312.03
[2] BBC 2011: Code-breakers: Bletchley Park’s lost heroes. Documentary (October 2011). Producer/Director Julian Carey
[3] 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) · JFM 66.0181.01 · doi:10.1215/S0012-7094-40-00718-9
[4] Crapo, H.H.: The Tutte polynomial. Aequationes Math. 3, 211-229 (1969) · Zbl 0197.50202 · doi:10.1007/BF01817442
[5] Descartes, B.: The three houses problem. Recited by W.T. Tutte. Tutte Eightieth Birthday Conference Dinner, University of Waterloo, 1997 · Zbl 1315.01062
[6] Edwards, K., Sanders, D.P., Seymour, P., Thomas, R.: Three-edge colouring doublecross cubic graphs. J. Combin. Theory Ser. B 119, 66-95 (2016) · Zbl 1334.05037 · doi:10.1016/j.jctb.2015.12.006
[7] 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
[8] 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) · Zbl 1124.05020 · doi:10.1093/acprof:oso/9780198571278.003.0003
[9] 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) · Zbl 1512.05217
[10] 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) · Zbl 1037.05013 · doi:10.1006/jctb.2001.2082
[11] Geelen, J., Gerards, B., Whittle, G.: Excluding a planar graph from GF(q)-representable matroids. J. Combin. Theory Ser. B 97, 971-998 (2007) · Zbl 1125.05025 · doi:10.1016/j.jctb.2007.02.005
[12] Harper, N.: Keeping secrets. University of Waterloo Magazine, Spring, 2015. https://uwaterloo.ca/magazine/spring-2015/features/keeping-secrets
[13] Hobbs, A.M., Oxley, J.G.: William T. Tutte, 1917-2001. Not. Am. Math. Soc. 51, 320-330 (2004) · Zbl 1168.01332
[14] 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) · Zbl 0324.90023
[15] Kuratowski, K.: Sur le problème des courbes gauches en topologie. Fund. Math. 15, 271-283 (1930) · JFM 56.1141.03 · doi:10.4064/fm-15-1-271-283
[16] Oxley, J.: Matroid Theory. 2nd edn. Oxford University Press, New York (2011) · Zbl 1254.05002 · doi:10.1093/acprof:oso/9780198566946.001.0001
[17] Poincaré, H.: Second complément à l’analysis situs. Proc. London Math. Soc. 32, 277-308 (1900) · JFM 31.0477.10 · doi:10.1112/plms/s1-32.1.277
[18] Seymour, P.D.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28, 305-359 (1980) · Zbl 0443.05027 · doi:10.1016/0095-8956(80)90075-1
[19] Seymour, P.D.: Nowhere-zero 6-flows. J. Combin. Theory Ser. B 30, 130-135 (1981) · Zbl 0474.05028 · doi:10.1016/0095-8956(81)90058-7
[20] Seymour, P.D.: On Tutte’s extension of the four-colour problem. J. Combin. Theory Ser. B 31, 82-94 (1981) · Zbl 0471.05031 · doi:10.1016/S0095-8956(81)80013-5
[21] Sprague, R.: Beispiel einer Zerlegung des Quadrats in lauter verschiedene Quadrate. Math. Z. 45, 607-608 (1939) · Zbl 0021.29501 · doi:10.1007/BF01580305
[22] Sutherland, G.B.B.M., Tutte, W.T.: Absorption of polymolecular films in the infra-red. Nature 144, 707 (1939) · doi:10.1038/144707b0
[23] Tait, P.G.: Listing’s topologie. Philos. Mag., 5th Series 17, 30-46 (1884) · JFM 16.0468.03
[24] Tutte, W.T.: On Hamiltonian circuits. J. Lond. Math. Soc. 21, 98-101 (1946) · Zbl 0061.41306 · doi:10.1112/jlms/s1-21.2.98
[25] Tutte, W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 22, 107-111 (1947) · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107
[26] Tutte, W.T.: A ring in graph theory. Proc. Camb. Philol. Soc. 43, 26-40 (1947) · Zbl 0031.41803 · doi:10.1017/S0305004100023173
[27] Tutte, W.T.: A family of cubical graphs. Proc. Camb. Philol. Soc. 43, 459-474 (1947) · Zbl 0029.42401 · doi:10.1017/S0305004100023720
[28] Tutte, W.T.: An algebraic theory of graphs. Ph.D. thesis, Cambridge University (1948). https://billtuttememorial.org.uk/links/
[29] Tutte, W.T.: A contribution to the theory of chromatic polynomials. Canad. J. Math. 6, 80-91 (1954) · Zbl 0055.17101 · doi:10.4153/CJM-1954-010-9
[30] Tutte, W.T.: A class of Abelian groups. Canad. J. Math. 8, 13-28 (1956) · Zbl 0070.02302 · doi:10.4153/CJM-1956-004-9
[31] Tutte, W.T.: A homotopy theorem for matroids. I, II. Trans. Am. Math. Soc. 88, 144-174 (1958) · Zbl 0081.17301
[32] 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 · Zbl 0040.39102
[33] Tutte, W.T.: Matroids and graphs. Trans. Am. Math. Soc. 90, 527-552 (1959) · Zbl 0084.39504 · doi:10.1090/S0002-9947-1959-0101527-3
[34] Tutte, W.T.: A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64, 441-455 (1961) · Zbl 0101.40903 · doi:10.1016/S1385-7258(61)50045-5
[35] Tutte, W.T.: How to draw a graph. Proc. Lond. Math. Soc. (3) 13, 743-767 (1963) · Zbl 0115.40805
[36] Tutte, W.T.: Lectures on matroids. J. Res. Nat. Bur. Stand. Sect. B 69B, 1-47 (1965) · Zbl 0151.33801 · doi:10.6028/jres.069B.001
[37] Tutte, W.T.: Menger’s theorem for matroids. J. Res. Nat. Bur. Stand. Sect. B 69B, 49-53 (1965) · Zbl 0151.33802 · doi:10.6028/jres.069B.002
[38] Tutte, W.T.: On the algebraic theory of graph colorings. J. Combin. Theory 1, 15-50 (1966) · Zbl 0139.41402 · doi:10.1016/S0021-9800(66)80004-2
[39] Tutte, W.T.: Connectivity in graphs. University of Toronto Press, Toronto (1966) · Zbl 0146.45603
[40] Tutte, W.T.: Connectivity in matroids. Canad. J. Math. 18, 1301-1324 (1966) · Zbl 0149.21501 · doi:10.4153/CJM-1966-129-2
[41] Tutte, W.T.: A correction to: “On the algebraic theory of graph colorings”. J. Combin. Theory 3, 102 (1967) · Zbl 0152.41202 · doi:10.1016/S0021-9800(67)80023-1
[42] Tutte, W.T.: On even matroids. J. Res. Nat. Bur. Stand. Sect. B 71B, 213-214 (1967) · Zbl 0165.26801 · doi:10.6028/jres.071B.028
[43] 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) · Zbl 0195.25606
[44] 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) · Zbl 0204.57001
[45] Tutte, W.T.: Selected Papers of W. T. Tutte/Edited by D. McCarthy, R. G. Stanton, vol. I. Charles Babbage Research Centre, Winnipeg (1979) · Zbl 0403.05028
[46] Tutte, W.T.: Selected Papers of W. T. Tutte/Edited by D. McCarthy, R. G. Stanton, vol. II. Charles Babbage Research Centre, Winnipeg (1979) · Zbl 0403.05028
[47] 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) · Zbl 0936.05029
[48] Tutte, W.T.: FISH and I. In: Joyner, D. (ed.) Coding Theory and Cryptography, pp. 9-17. Springer, Berlin (2000) · Zbl 0985.94500 · doi:10.1007/978-3-642-59663-6_2
[49] Tutte, W.T.: Graph-polynomials. Adv. Appl. Math. 32, 5-9 (2004) · Zbl 1041.05001 · doi:10.1016/S0196-8858(03)00041-1
[50] Welsh, D.J.A.: Complexity: Knots, Colourings and Counting. Cambridge University Press, Cambridge (1993) · Zbl 0799.68008 · doi:10.1017/CBO9780511752506
[51] Whitney, H.: The coloring of graphs. Ann. Math. (2) 33, 688-718 (1932) · Zbl 0005.31301
[52] Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57, 509-533 (1935) · JFM 61.0073.03 · doi:10.2307/2371182
[53] Younger, D.H.: William Thomas Tutte, 14 May 1917-2 May 2002. Biogr. Mem. Fellows Roy. Soc. 58, 283-297 (2012) · doi:10.1098/rsbm.2012.0036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.