# Combinatorics Group

Combinatorics is 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, but they are also pursued for their own interest. The School of Mathematical Sciences at Queen Mary has a long tradition in combinatorics, and contains one of the strongest groups in the UK. The group includes a vibrant community of PhD students and has strong connections with other research groups.

## Research interests of the group

### Extremal combinatorics

Extremal combinatorics asks questions about the densest combinatorial structure satisfying a certain property. Here are two examples. What is the n-vertex graph with the most edges which does not contain a triangle? What is the largest collection of subsets of {1,2,...,n} with the property that the intersection of any two of them is non-empty? These particular questions are not difficult to answer, but similar questions, only slightly more complicated to state than this one, can be fiendishly difficult. This area is a particular focus of group member Robert Johnson.

Extremal combinatorics often involves a mixture of ingenious combinatorial arguments, and a wide toolbox of techniques from other areas of mathematics such as linear algebra, probability and discrete Fourier analysis. As well as graphs and set systems, extremal questions can be posed about any combinatorial structure. One interesting direction is to find and prove analogues of extremal results about sets in the realm of permutations.

### Random structures

Instead of looking at extremal combinatorial structures one can study typical ones: this is the concern of Dudley Stark and Mark Walters, who study random structures. For example, suppose radio transceivers with limited range are randomly scattered over an area; what is the probability that they will be able to cooperate to send messages over long distances? Or, again, what is the distribution of certain small substructures in a large random structure, for example a large random graph? To solve problems in this area one needs to combine methods from probability theory with combinatorial insights.

### Operational Research and Theoretical Computer Science

The fields of Operational Research and Theoretical Computer Science have had a long relationship with Combinatorics. Felix Fischer’s research is concerned with problems that arise from the interaction of self-interested computationally bounded entities, or agents. His approach is mathematical and uses concepts and techniques from game theory, social choice, and mechanism design, from theoretical computer science, and from related areas of mathematics like optimization, probability theory, and graph theory. Mark Jerrum studies the complexity of counting problems, which even now contains some large relatively unexplored areas. A prominent emerging Leitmotiv here is the idea that phase transitions in a model in statistical physics may provably be associated with a sudden change in the complexity of computing the partition function (generating function of configurations) of the system. Justin Ward’s research involves the study and development of algorithms for combinatorial optimisation problems, with a focus on practical heuristics such as local search and greedy algorithms. His most recent work involves new frameworks for largescale and distributed submodular maximisation, as well as new algorithms for k-means clustering.

### Graphs and Matroids

A graph is an abstract representation of connections between objects. Mathematically it consists of some points (called vertices) and some lines (called edges) with each edge joining some pair of vertices. Graphs can be used to model many real situations and are also studied from a pure mathematical perspective. Research in graph theory tackles questions on many aspects of graphs including probabilistic, geometric and algorithmic. Graph theory makes up a large and important part of combinatorics and appears in some form in the research of all members of the group.

One major research theme of group member Bill Jackson which combines geometry and graph theory is rigidity of frameworks. Consider a framework of bars of fixed length connected by universal joints that do not in any way constrain the angles between the bars, but do constrain the ends of the bars to move together. When is such a framework rigid? Although geometry often plays a part in the theory of rigid frameworks, there is a general setting in which the answer to the above question is purely combinatorial, i.e., is dependent only on the incidences of the bars and joints. In these cases, the rigidity of a framework is determined by a related combinatorial structure called a matroid.

Matroids generalise both cycles in graphs and linear independent sets in vector spaces. They feature in the research in optimization of group member Justin Ward.

## Group seminars

The Combinatorics Study Group meets on Fridays at 14:00 currently meetings are online.

Find out more about the history of the Combinatorics Study Group here

We also run joint colloquia with LSE - find out more here

## Group members

#### Head of Group: Dr Robert Johnson

Natalie Behague was a PhD student in the Combinatorics group between 2016 and 2020 supervised by Robert Johnson and Mark Walters. We caught up with her to find out about her time at QMUL and what she has been doing since.

2021 QMUL-LSE Colloquia in Combinatorics
22 April 2021

We are pleased to announce the return of the QMUL-LSE Colloquia in Combinatorics which will be held on 12-13 May 2021.