Crispin St. J. A. Nash-Williams
Encyclopedia
Crispin St. John Alvah Nash-Williams (December 19, 1932 – January 20, 2001) was a British
and Canadian
mathematician. His research interest was in the field of discrete mathematics
, especially graph theory
.
Nash-Williams was born December 19, 1932, in Cardiff, Wales; his father, Victor Erle Nash-Williams
, was an archaeologist at University College Cardiff, and his mother had studied classics at Oxford University. After studying mathematics at Cambridge University, earning the title of Senior Wrangler in 1953, he remained for his graduate studies at Cambridge, studying under the supervision of Shaun Wylie
and David Rees
. He continued his studies for a year at Princeton University
, with Norman Steenrod
; all three of Wylie, Rees, and Steenrod are listed as the supervisors of his Ph.D. thesis. He finished his thesis in 1958, but before doing so he returned to the UK as an assistant lecturer at the University of Aberdeen
. He kept his position at Aberdeen through ten years and two promotions until 1967, when he moved to the University of Waterloo
and became one of the three faculty members in the newly formed Department of Combinatorics there. In 1972 he returned to Aberdeen, as Professor of Pure Mathematics; in 1975 he moved to the University of Reading
, where he took the chair previously held by Richard Rado
, who had been one of his thesis examiners. In 1996 he retired; he died on January 20, 2001, in Ascot, Berkshire
, where his brother was rector.
He was elected to the Royal Society of Edinburgh
in 1969. In 1994, the University of Waterloo gave him an honorary doctorate for his contributions to combinatorics
. A conference in his honor was held on his retirement in 1996, the proceedings of which were published as a festschrift
. The 18th British Combinatorial Conference, held in Sussex in July 2001, was dedicated to his memory.
Hilton writes that "Themes running through his papers are Hamiltonian cycles, Eulerian graphs, spanning tree
s, the marriage problem, detachments, reconstruction
, and infinite graphs."
In his first papers Nash-William considered the knight's tour
and random walk
problems on infinite graphs; the latter paper included an important recurrence criterion for general Markov chain
s, and was also the first to apply electrical network techniques of Rayleigh
to random walks. His graduate thesis, which he finished in 1958, concerned generalizations of Euler tours to infinite graphs. Welsh writes that his subsequent work defining and characterizing the arboricity
of graphs (discovered in parallel and independently by W. T. Tutte
) has "had a huge impact," in part because of its implications in matroid
theory. Nash-Williams also studied k-edge-connected graph
s, Hamiltonian cycles in dense graph
s, versions of the reconstruction conjecture
for infinite graphs, and the theory of quasi-orders. He also gave a short elegant proof on
Kruskal's tree theorem
.
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...
and Canadian
Canada
Canada is a North American country consisting of ten provinces and three territories. Located in the northern part of the continent, it extends from the Atlantic Ocean in the east to the Pacific Ocean in the west, and northward into the Arctic Ocean...
mathematician. His research interest was in the field of discrete mathematics
Discrete mathematics
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not...
, especially graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
.
Nash-Williams was born December 19, 1932, in Cardiff, Wales; his father, Victor Erle Nash-Williams
Victor Erle Nash-Williams
Victor Erle Nash-Williams was a noted Welsh archaeologist.Educated at the Lewis School, Pengam, and at the University College in Cardiff, he was appointed Keeper at the National Museum of Wales...
, was an archaeologist at University College Cardiff, and his mother had studied classics at Oxford University. After studying mathematics at Cambridge University, earning the title of Senior Wrangler in 1953, he remained for his graduate studies at Cambridge, studying under the supervision of Shaun Wylie
Shaun Wylie
Shaun Wylie was a British mathematician and World War II codebreaker.-Early life:Wylie was born in Oxford, England, the fourth son of Sir Francis Wylie, later the first Warden of Rhodes House in Oxford. He was educated at Dragon School and then Winchester College...
and David Rees
David Rees (mathematician)
David Rees ScD Cantab, FIMA, FRS is an emeritus professor of pure mathematics at the University of Exeter, having been head of the Mathematics / Mathematical Sciences Department at Exeter for many years....
. He continued his studies for a year at Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, with Norman Steenrod
Norman Steenrod
Norman Earl Steenrod was a preeminent mathematician most widely known for his contributions to the field of algebraic topology.-Life:...
; all three of Wylie, Rees, and Steenrod are listed as the supervisors of his Ph.D. thesis. He finished his thesis in 1958, but before doing so he returned to the UK as an assistant lecturer at the University of Aberdeen
University of Aberdeen
The University of Aberdeen, an ancient university founded in 1495, in Aberdeen, Scotland, is a British university. It is the third oldest university in Scotland, and the fifth oldest in the United Kingdom and wider English-speaking world...
. He kept his position at Aberdeen through ten years and two promotions until 1967, when he moved to the University of Waterloo
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
and became one of the three faculty members in the newly formed Department of Combinatorics there. In 1972 he returned to Aberdeen, as Professor of Pure Mathematics; in 1975 he moved to the University of Reading
University of Reading
The University of Reading is a university in the English town of Reading, Berkshire. The University was established in 1892 as University College, Reading and received its Royal Charter in 1926. It is based on several campuses in, and around, the town of Reading.The University has a long tradition...
, where he took the chair previously held by Richard Rado
Richard Rado
Richard Rado FRS was a Jewish German mathematician. He earned two Ph.D.s: in 1933 from the University of Berlin, and in 1935 from the University of Cambridge. He was interviewed in Berlin by Lord Cherwell for a scholarship given by the chemist Sir Robert Mond which provided financial support to...
, who had been one of his thesis examiners. In 1996 he retired; he died on January 20, 2001, in Ascot, Berkshire
Ascot, Berkshire
Ascot is a village within the civil parish of Sunninghill and Ascot, in the Royal Borough of Windsor and Maidenhead, Berkshire, England. It is most notable as the location of Ascot Racecourse, home of the prestigious Royal Ascot meeting...
, where his brother was rector.
He was elected to the Royal Society of Edinburgh
Royal Society of Edinburgh
The Royal Society of Edinburgh is Scotland's national academy of science and letters. It is a registered charity, operating on a wholly independent and non-party-political basis and providing public benefit throughout Scotland...
in 1969. In 1994, the University of Waterloo gave him an honorary doctorate for his contributions to combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
. A conference in his honor was held on his retirement in 1996, the proceedings of which were published as a festschrift
Festschrift
In academia, a Festschrift , is a book honoring a respected person, especially an academic, and presented during his or her lifetime. The term, borrowed from German, could be translated as celebration publication or celebratory writing...
. The 18th British Combinatorial Conference, held in Sussex in July 2001, was dedicated to his memory.
Hilton writes that "Themes running through his papers are Hamiltonian cycles, Eulerian graphs, spanning tree
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
s, the marriage problem, detachments, reconstruction
Reconstruction conjecture
Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.-Formal statements:...
, and infinite graphs."
In his first papers Nash-William considered the knight's tour
Knight's tour
The knight's tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from...
and random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
problems on infinite graphs; the latter paper included an important recurrence criterion for general Markov chain
Markov chain
A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized as memoryless: the next state depends only on the current state and not on the...
s, and was also the first to apply electrical network techniques of Rayleigh
John Strutt, 3rd Baron Rayleigh
John William Strutt, 3rd Baron Rayleigh, OM was an English physicist who, with William Ramsay, discovered the element argon, an achievement for which he earned the Nobel Prize for Physics in 1904...
to random walks. His graduate thesis, which he finished in 1958, concerned generalizations of Euler tours to infinite graphs. Welsh writes that his subsequent work defining and characterizing the arboricity
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...
of graphs (discovered in parallel and independently by W. T. Tutte
W. T. Tutte
William Thomas Tutte, OC, FRS, known as Bill Tutte, was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher, a major German code system, which had a significant impact on the Allied...
) has "had a huge impact," in part because of its implications in matroid
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
theory. Nash-Williams also studied k-edge-connected graph
K-edge-connected graph
In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.-Formal definition:Let G = be an arbitrary graph....
s, Hamiltonian cycles in dense graph
Dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...
s, versions of the reconstruction conjecture
Reconstruction conjecture
Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.-Formal statements:...
for infinite graphs, and the theory of quasi-orders. He also gave a short elegant proof on
Kruskal's tree theorem
Kruskal's tree theorem
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered...
.