Combinatorics Group

For more information on the members of the group please follow the links in the above table. For information on seminars and the joint LSE/QM combinatorics colloquia please follow the links on the left of this page.

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.

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.

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.

External contacts

The combinatorics group has a number of contacts beyond academia. Justin Ward has been invited to talk at both Yahoo! Labs and Google Research in New York. Some of Bill Jackson’s work on rigidity of frameworks has been conducted jointly with J. C. Owen of Siemens. Mark Walter’s collaboration with IBM applied ideas from the theory of random structures to the analysis 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 was an organiser for two international workshops on rigidity: DIMACS Workshop on Distance Geometry: Theory and Applications(link is external), Rutgers University, USA in July 2016; Geometric Rigidity Theory and Applications(link is external), 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. Felix Fischer and his co-authors P. Dütting, P. Jirapinyo, J. Lai and B. Lubin won the best paper award at the 13th ACM Conference on Electronic Commerce [1]. Justin Ward was on the program committee for ICALP ’16 and has given talks at other prestigious conferences on theoretical computer science such as FOX and SODA.

References

[1] P. Dütting, F. Fischer, P. Jirapinyo, J. Lai, B. Lubin, and D. C. Parkes, Payment rules through discriminant-based classifiers, Proceedings of the 13th ACM Conference on Electronic Commerce, 477–494. ACM Press, 2012

[2] 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).


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

[4] 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.