Michael D. Atkinson

  1. Home
  2. Wiki
Michael D. Atkinson
Alma materUniversity of Oxford
Known forPermutation patterns,
Algorithm design
Scientific career
FieldsMathematics,
Theoretical computer science
InstitutionsUniversity of Otago,
University of St Andrews,
Carleton University,
University College, Cardiff
Thesis Varieties of Exponent 6 and Related Topics  (1970)
Doctoral advisorPeter M. Neumann
Doctoral studentsStephanie van Willigenburg

Michael D. Atkinson is a mathematician and computer scientist known for his work in the theory of permutation patterns and for contributions to algorithm design, data structures, and algebra. He is an emeritus professor at the University of Otago.

Education and career

[edit]

Atkinson earned his B.A. (1967) and D.Phil. (1970) in mathematics from the University of Oxford, where he was a member of The Queen's College and a student of Peter M. Neumann.[1] His doctoral work focused on varieties of groups, within the area of group theory.

He taught at University College, Cardiff from 1970 to 1982, then joined the Carleton University School of Computer Science in Canada, where he became a full professor in 1983. In 1992, Atkinson moved to the University of St Andrews 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.[2]

Research

[edit]

Atkinson's early research spanned algebra, permutation groups, bilinear complexity, and algorithmic linear algebra. His 1975 paper on block-finding algorithms for permutation groups[3] gave the first polynomial-time algorithm for the problem[4]. He later made contributions to data structures and computational geometry, notably on min-max heaps,[5] geometric congruence testing,[6] the cyclic Towers of Hanoi,[7] and frequency assignment problems in communication networks.[8]

In the late 1990s, Atkinson shifted his research to permutation patterns[9]. His 1999 paper Restricted permutations[10] has been described as "foundational" in the field.[11] In 2003, he co-founded the Permutation Patterns conference with Michael H. Albert, which has played a central role in the development of the field.[12] Their 2005 joint paper Simple permutations and pattern restricted permutations[13] introduced structural decomposition techniques, now known as the substitution decomposition. This work, described as "formative",[14] refined the analysis begun in his earlier work with Tim Stitt on the wreath product.[15] Together with Albert and Martin Klazar, Atkinson also enumerated the simple permutations that arise in this decomposition.[16] In later work, he and co-authors introduced the notion of geometric grid classes,[17] another tool in the study of the structure of permutation classes.

References

[edit]
  1. ^ Michael D. Atkinson at the Mathematics Genealogy Project
  2. ^ Atkinson, Mike. "Brief career history". www.cs.otago.ac.nz. Retrieved 2025-05-28.
  3. ^ Atkinson, M. D. (1975). "An algorithm for finding the blocks of a permutation group". Mathematics of Computation. 29 (131): 911–913. doi:10.2307/2005304.
  4. ^ Luks, Eugene M. (1987-03-01). "Computing the composition factors of a permutation group in polynomial time". Combinatorica. 7 (1): 89. doi:10.1007/BF02579204. ISSN 1439-6912.
  5. ^ Atkinson, M. D.; Sack, J.-R.; Santoro, N.; Strothotte, T. (1986). "Min-max heaps and generalized priority queues". Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.
  6. ^ Atkinson, M. D. (1987). "An optimal algorithm for geometrical congruence". Journal of Algorithms. 8 (2): 159–172. doi:10.1016/0196-6774(87)90036-8.
  7. ^ Atkinson, M. D. (1981). "The cyclic towers of Hanoi". Information Processing Letters. 13 (3): 118–119. doi:10.1016/0020-0190(81)90123-X.
  8. ^ Atkinson, M. D.; Santoro, N.; Urrutia, J. (1986). "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters". IEEE Transactions on Communications. 34 (6): 614–617. doi:10.1109/TCOM.1986.1096587.
  9. ^ Atkinson, Mike. "A life in mathematics". www.cs.otago.ac.nz. Retrieved 2025-05-28.
  10. ^ Atkinson, M. D. (1999). "Restricted permutations". Discrete Mathematics. 195 (1–3): 27–38. doi:10.1016/S0012-365X(98)00306-0.
  11. ^ Brignall, Robert (2024-04-19). "Labelled well-quasi-order in juxtapositions of permutation classes". The Electronic Journal of Combinatorics. 31 (2): 2. doi:10.37236/12655. ISSN 1077-8926.
  12. ^ Bassino, Frédérique; Bouvel, Mathilde; Rossin, Dominique (2015-03-20). "A foreword by the guest editors". Journal of Combinatorics. 6 (1): 1–2. ISSN 2150-959X.
  13. ^ Albert, M. H.; Atkinson, M. D. (2005). "Simple permutations and pattern restricted permutations". Discrete Mathematics. 300 (1–3): 1–15. doi:10.1016/j.disc.2004.12.013.
  14. ^ Vatter, Vincent (2015). "Permutation classes". In Bóna, Miklós (ed.). Handbook of Enumerative Combinatorics. Boca Raton, Florida: CRC Press. p. 793. doi:10.1201/b18255. ISBN 978-1-4822-2085-8.
  15. ^ Atkinson, M. D.; Stitt, T. (2002). "Restricted permutations and the wreath product". Discrete Mathematics. 259 (1–3): 19–36. doi:10.1016/S0012-365X(02)00443-0.
  16. ^ Albert, M. H.; Atkinson, M. D.; Klazar, Martin (2003). "The enumeration of simple permutations". Journal of Integer Sequences. 6 (4): Article 03.4.4.
  17. ^ Albert, M. H.; Atkinson, M. D.; Bouvel, M.; Ruškuc, N.; Vatter, V. (2013). "Geometric grid classes of permutations". Transactions of the American Mathematical Society. 365 (11): 5859–5881. doi:10.1090/S0002-9947-2013-05804-7.