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.
Extremal combinatorics
Extremal combinatorics asks questions about the densest combinatorial structure satisfying a certain property. For example, what is the n-vertex graph with the most edges which does not contain a triangle? This particular question is 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 members David Ellis and Robert Johnson. In addition to delicate combinatorial arguments, solutions to problems in extremal combinatorics may use tools from areas of mathematics such as representation theory and discrete Fourier analysis.
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.
Theory of rigid 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 which do constrain the ends of the bars to move together. Bill Jackson considers the question: 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.
Group seminars
The Combinatorics Study Group meets on Fridays at 16:00 in Room W316 in the Queens' Building at Queen Mary University of London.
Find out more about the history of the Combinatorics Study Group here.
We also run joint colloquia with LSE - find out more here.
Find out more about our group
- Research grant projects and collaborations
- Combinatorics Study Group
- LSE / QM Colloquia
- Combinatorics News and Blog
Konrad Anand
Postgraduate Research Student
Mathematical Sciences Building, Room: MB-402
k.anand@qmul.ac.uk
Asier Calbet Rípodas
Postgraduate Research Student
Mathematical Sciences Building, Room: MB-402
a.calbetripodas@qmul.ac.uk

Felix Fischer
Lecturer in Optimisation/Operations Research
Mathematical Sciences Building, Room: MB-G23
+44 (0)20 7882 2607
felix.fischer@qmul.ac.uk
Ronald Gray
Postgraduate Research Student
Mathematical Sciences Building, Room: MB-402
r.f.gray@qmul.ac.uk
David Hannon
Postgraduate Research Student
Mathematical Sciences Building, Room: MB-402
d.hannon@qmul.ac.uk

Bill Jackson
Professor of Mathematical Sciences
Mathematical Sciences Building, Room: MB-515
+44 (0)20 7882 5476
b.jackson@qmul.ac.uk

Mark Jerrum
Professor of Mathematics / Director of Research
Mathematical Sciences Building, Room: MB-511
+44 (0)20 7882 5472
m.jerrum@qmul.ac.uk

Robert Johnson
Senior Lecturer in Pure Mathematics
Mathematical Sciences Building, Room: MB-422
+44 (0)20 7882 5480
r.johnson@qmul.ac.uk

Dudley Stark
Reader in Mathematics and Probability
Mathematical Sciences Building, Room: MB-315
+44 (0)20 7882 5487
d.s.stark@qmul.ac.uk
Mark Walters
Reader in Pure Mathematics / Director of Education
Mathematical Sciences Building, Room: MB-427
+44 (0)20 7882 5446
m.walters@qmul.ac.uk

Justin Ward
Senior Lecturer in Optimisation
Mathematical Sciences Building, Room: MB-126
5065
justin.ward@qmul.ac.uk