Supervisor: Dr Viresh Patel
Project description:
Combinatorial counting problems have rich connections to many areas of science including to algebra, probability, and dynamical systems in mathematics as well as to theoretical computer science and statistical physics outside of mathematics. Two fundamental counting problems in combinatorics are that of counting (weighted) independent sets and (weighted) colourings in graphs. These weighted counts are given by the independence polynomial and Tutte polynomial respectively, and these polynomials give a lot of information about the distribution of independent sets and colourings in the graphs. It turns out that these polynomials also appear as objects of study in statistical physics where they are known respectively as the partition function of the hard-core model (for modelling gases) and the partition function of the Ising/ Potts models (for modelling ferromagnetism).
One of the aims of the project is to understand the locations of the roots of these and other graph polynomials because, as it turns out, this is intimately connected with understanding when there is a fast algorithm to approximately solve the corresponding counting problem. A second aim is to understand the extremal problem of which graphs maximise / minimise these polynomials at different choices of their parameters.
Beyond the general direction discussed above, there is also the possibility to pursue projects in the general area of extremal combinatorics / graph theory.
Anyone with a strong background in any of the following areas is encouraged to apply: combinatorics / graph theory, discrete mathematics, algorithms and complexity. Please contact Viresh Patel (viresh.patel@qmul.ac.uk) for informal enquiries.
Further information: How to apply Entry requirements Fees and funding