Combinatorics

CeCANT contains one of the strongest groups in combinatorics in the UK. Queen Mary has a long tradition of research in combinatorics, the study of finite or countable discrete structures. Combinatorial problems may arise in several areas of mathematics, including algebra and probability, or in real-world applications, from ensuring impartiality of peer assessment to modelling the distribution of mutations among cells and many more. They are also pursued for their own interest.

The emphases of our research are:

  • Extremal combinatorics (Dr Johnson, Dr Patel), which asks about the densest combinatorial structure, e.g. a graph or a set system, with a certain property. One interesting direction is to extend extremal results about sets to the realm of permutations (Dr Johnson).
  • Random structures (Dr Patel, Dr Stark, Dr Walters). For example, suppose radio transceivers with limited range are randomly scattered over an area; what is the probability that messages can be sent over long distances? How are small substructures distributed in large random structures?
  • Operational research and theoretical computer science, in which we recently held two New Investigator Awards. These include problems arising from the interaction of self-interested agents (Dr Fischer); algorithms for combinatorial optimisation with a focus on practical heuristics (Dr Ward); and the complexity of counting problems, in which an emerging theme is proving associations between phase transitions in statistical physics and the computational complexity of the partition function (Prof. Jerrum, Dr Patel).
  • Graph theory and/or matroid theory appear in some form in the research of all members of this theme.
  • Algebraic combinatorics features in the work of Dr Fayers, Prof Fink and Dr Rincón.

Combinatorics at Queen Mary is highly visible. We will host the British Combinatorical Conference for the second time in 2024, and hosted the Conference on Formal Power Series and Algebraic Combinatorics in 2017. Our seminar, the Combinatorics Study Group, has been running since 1986, and we have held annual joint colloquia with LSE since 2007.

Correlation of monotone families in the strong and weak permutation order
Correlation of monotone families in the strong and weak permutation order
Construction of an automaton which synchonises k-sets slowly
Construction of an automaton which synchonises k-sets slowly