Michael D. Atkinson is a mathematician and computer scientist known for his work in the theory of

permutation patterns In combinatorics, combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in Permutation#One-line_notation, one-line notation as a seq ...

and for contributions to algorithm design, data structures, and algebra. He is an emeritus professor at the

University of Otago The University of Otago () is a public university, public research university, research collegiate university based in Dunedin, Otago, New Zealand. Founded in 1869, Otago is New Zealand's oldest university and one of the oldest universities in ...

Education and career

Atkinson earned his B.A. (1967) and D.Phil. (1970) in mathematics from the

University of Oxford The University of Oxford is a collegiate university, collegiate research university in Oxford, England. There is evidence of teaching as early as 1096, making it the oldest university in the English-speaking world and the List of oldest un ...

, where he was a member of

The Queen's College The Queen's College is a constituent college of the University of Oxford, England. The college was founded in 1341 by Robert de Eglesfield in honour of Philippa of Hainault, queen of England. It is distinguished by its predominantly neoclassi ...

and a student of

Peter M. Neumann Peter Michael Neumann OBE (28 December 1940 – 18 December 2020) was a British mathematician. His fields of interest included the history of mathematics and Galois theory. Biography Born in December 1940, Neumann was a son of the German-bo ...

. His doctoral work focused on varieties of groups, within the area of

group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ( ...

. He taught at

University College, Cardiff Cardiff University () is a public research university in Cardiff, Wales. It was established in 1883 as the University College of South Wales and Monmouthshire and became a founding college of the University of Wales in 1893. It was renamed Unive ...

from 1970 to 1982, then joined the

Carleton University Carleton University is an English-language public university, public research university in Ottawa, Ontario, Canada. Founded in 1942 as Carleton College, the institution originally operated as a private, non-denominational evening college to se ...

School of Computer Science in Canada, where he became a full professor in 1983. In 1992, Atkinson moved to the

University of St Andrews The University of St Andrews (, ; abbreviated as St And in post-nominals) is a public university in St Andrews, Scotland. It is the List of oldest universities in continuous operation, oldest of the four ancient universities of Scotland and, f ...

as Professor of Algorithms and head of the School of Mathematical and Computational Sciences (1994–1997). He joined the University of Otago in 2000 and retired in 2012.

Research

Atkinson's early research spanned algebra, permutation groups, bilinear complexity, and algorithmic linear algebra. His 1975 paper on block-finding algorithms for permutation groups gave the first polynomial-time algorithm for the problem. He later made contributions to data structures and computational geometry, notably on min-max heaps, geometric congruence testing, the cyclic Towers of Hanoi, and frequency assignment problems in communication networks. In the late 1990s, Atkinson shifted his research to permutation patterns. His 1999 paper ''Restricted permutations'' has been described as "foundational" in the field. In 2003, he co-founded the

Permutation Patterns In combinatorics, combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in Permutation#One-line_notation, one-line notation as a seq ...

conference with Michael H. Albert, which has played a central role in the development of the field. Their 2005 joint paper ''Simple permutations and pattern restricted permutations'' introduced structural decomposition techniques, now known as the substitution decomposition. This work, described as "formative", refined the analysis begun in his earlier work with Tim Stitt on the wreath product. Together with Albert and Martin Klazar, Atkinson also enumerated the simple permutations that arise in this decomposition. In later work, he and co-authors introduced the notion of geometric grid classes, another tool in the study of the structure of permutation classes.

References

{{DEFAULTSORT:Atkinson, Michael D. Living people 20th-century mathematicians 21st-century mathematicians Academic staff of the University of Otago Combinatorialists Theoretical computer scientists