School of Mathematical Sciences

Research menu

Combinatorics Group

 
FACULTY MEMBERS POSTDOC FELLOWS PhD STUDENTS
David Ellis Heng Guo Jack Bartley
Bill Jackson (Head of Group)   Natalie Behague
Mark Jerrum   Katie Clinch
Robert Johnson   Nick Day
Dudley Stark   Hakan Guler
Mark Walters   Teerasak Khoploykang
    Anitha Rajkumar
    William Raynaud
     

For more information on the members of the group, seminars and the joint LSE/QM combinatorics colloquia please follow the  links on the left.

The interests of the group in brief

Combinatorics is the study of finite or countable discrete structures. Although the objects of study are discrete, the methods used to study them come from both continuous and discrete mathematics. 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 has a long tradition in combinatorics, and contains one of the strongest groups in the UK. The group includes a vibrant community of nine PhD students and has strong connections with the other research groups: Algebra; Goemetry and Analysis; Probability and Applications. The interests of the group are wide ranging, as can be judged from the following brief survey. Note that it is only possible to present a selection of topics, and members of the group have interests beyond those sketched here.

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, and are grist to the mill for 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.

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.

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.

The theory of computation, and particularly the field of computational complexity, has a long relationship with combinatorics. 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.

External contacts

The combinatorics group has a number of contacts beyond academia. Some of the work on rigidity of frameworks has been conducted jointly with J. C. Owen of Siemens. In collaboration with IBM, ideas from the theory of random structures have been applied to the analysis (and has influenced the development) of the IBM Gaian database [4]. The interests of the group even extend to applications in the area of oil production [3]. Not all the external projects can be mentioned, owing to confidentially considerations.

Funding

The work on computational complexity is supported by Mark jerrum's  EPSRC grant `Algorithms that count: exploring the limits of tractability' valued at £362K.

External recognition

Bill Jackson is an organiser for two international workshops on rigidity: DIMACS Workshop on Distance Geometry: Theory and Applications, Rutgers University, USA in July 2016; Geometric Rigidity Theory and Applications, ICMS, Edinburgh May 30 to June 3, 2016. Mark Jerrum was awarded, jointly with Leslie Goldberg of Oxford University, the prize for the best paper in Track A of the International Colloquium on Automata Languages and Programming, the leading European conference on theoretical computer science [1].  He spoke at the IMA meeting on 'The power of randomness in computation' at Georgia Tech. and was an organiser for the meeting 'Phase transitions in discrete structures and computational problems' at Warwick in 2014.  Mark Walters was invited to speak at the conferences `Additive Combinatorics' at Bristol and `Extremal and Probabilistic Combinatorics at Birmingham in 2015. David Ellis gave invited talks at the Clay Mathematics Workshop on Extremal and Probabilistic Combinatorics in 2014 and at the workshop `Non-combinatorial Combinatorics' at Warwick in 2015.

References

[1] Leslie Ann Goldberg and Mark Jerrum, The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation), Proc. 39th International Colloquium on Automata Languages and Programming (ICALP 2012).


[2] Dudley Stark, Oil production models with normal rate curves, Probability in the Engineering and Informational Sciences, 25 (2011) 205–217.

[3] Mark Walters, Paul Stone, Patrick Dantressangle and Abbe Mowshowitz, The Evolution of Gaian Preferential Attachment Graphs, Annual Conference of the International Technology Alliance, Southampton, September 2012.