UoSLogoShieldStrathclyde Combinatorics Group

Department of Mathematics and Statistics, University of Strathclyde

 

 

Research

The main research interests of the group lie in aspects of enumerative, bijective, algebraic and topological combinatorics, with applications to computer science, physics and biology. Much of our work has focussed on patterns in permutations and other combinatorial objects. Central to this area is concept of a permutation class, which is a downset under the permutation containment order. The study of these structures began in the 1960s with Donald Knuth’s investigation of computational sorting devices, which is still an active area of research. Subsequently, they have been used to analyse models of genome rearrangement, the layout of integrated circuits, and gas models in statistical physics, among other things.

 

Who are we?

Sergey Kitaev (Head of Group)

Sergey’s research interests encompass aspects of enumerative and algebraic combinatorics, combinatorics on words, and graph theory. Successes include the enumeration of (2+2)-free posets via an encoding of them as ascent sequences. Sergey is the author of two monographs, one on patterns in permutations and words, and the other on words and graphs. Recently, he has pioneered the theory of word-representable graphs (a topic on the boundary of graph theory and combinatorics on words, with roots in algebra), including giving an effective characterization in terms of graph orientations.

 

 

David0

David Bevan

David’s research interests mainly concern enumerative and asymptotic questions, particularly in relation to permutations. Achievements include an explicit formula for the growth rate of grid classes of permutations, and a structural characterisation of the class of permutations avoiding 1324 together with new bounds on its growth rate. Current research topics include the evolution of the random permutation (as the number of its inversions increases), permutation limits at different scales, and enumerative and structural questions concerning permutation grid classes.

 

 

Elizabeth Dombi

Elizabeth’s research background lies in combinatorial semigroup theory, the algebraic theory of formal languages, and combinatorial optimization concerning edge covering of grid graphs. More recently, she has started working on subdivision-resilience of non-word-representable graphs.

 

 

Einar0

Einar Steingrímsson

Einar’s research interests primarily concern algebraic combinatorics, particularly in relation to permutation patterns, and with an emphasis on permutation statistics. He pioneered the concept of a vincular pattern, which has since been generalised further by the notion of a mesh pattern. A particular focus has been on the topology and Möbius function of intervals in the poset of permutations ordered by pattern containment. Other recent work has concerned the Abelian sandpile model, and the introduction and analysis of new combinatorial structures whose motivation comes from particle physics.

 

Research visitor

Herman Z. Q. Chen, Chongqing Normal University (2024 – 2025)

 

Current PhD students

Dan Threlfall (from 2020)

Noura Alshammari (from 2021)

Humaira Hameed (from 2023)

Mohammed Alshammari (from 2024)

 

Past events

Scottish Combinatorics Meeting 2023, 22–23 May 2023

 Virtual Workshop, 15–16 June 2021

26th British Combinatorial Conference, 3–7 July 2017

Permutation Patterns 2012, 11–15 July 2012

FPSAC 2011, 13–17 June 2011

 

Research funding

Shortening universal words and DNA sequence assembly (Sergey Kitaev, Leverhulme Research Fellowship, 2023–2024)

Connecting physics models via permutations (Einar Steingrímsson, Leverhulme Research Fellowship, 2018–2020)

New combinatorial perspectives on the Abelian sandpile model (Mark Dukes and Einar Steingrímsson, EPSRC, 2015–2018)

The Möbius function of the poset of permutations (Einar Steingrímsson, EPSRC, 2015–2018)

Finding structure in sets of permutations (Anders Claesson, Icelandic Research Fund, 2014–2016)

Combinatorics of permutations and words (Einar Steingrímsson, Anders Claesson, Sergey Kitaev and Mark Dukes, Icelandic Research Fund, 2009–2012)

 

History

The Strathclyde Combinatorics Group had its origins in Gothenburg, Sweden, then moved to Reykjavík, Iceland, before coming to Glasgow, Scotland. Einar has written a history of the group, published in Enumerative Combinatorics and Applications.

 

Former faculty members of the group

Anders Claesson (2011–2016; now Professor at the University of Iceland, Reykjavík)

Mark Dukes (2011–2016; now Associate Professor at University College, Dublin)

 

Former research associates

Thomas Selig (2015–2018; now Assistant Professor at Xi'an Jiaotong-Liverpool University, Suzhou, China)

Jason Smith (2015–2018; now Senior Lecturer at Nottingham Trent University)

 

Former PhD students

Kittitat Iamthong (2018–2021; now Lecturer at Suranaree University of Technology) Encoding graphs by words and morphisms

Marc Glen (2016–2019) On word-representability of polyomino triangulations and crown graphs

Jason Smith (2012–2015; now Senior Lecturer at Nottingham Trent University) On the Möbius function and topology of the permutation poset

Stuart Hannah (2011–2015) Interval order enumeration