Zeros of Graph Polynomials and Computational Phase Transitions

This PhD project at the School of Mathematical Sciences, Queen Mary University of London, focuses on the study of zeros of graph polynomials and their connections to computational phase transitions. The research lies at the intersection of combinatorics, graph theory, algorithms, and statistical physics. Two central combinatorial counting problems—counting (weighted) independent sets and colourings in graphs—are encoded by the independence polynomial and Tutte polynomial, respectively. These polynomials not only provide insight into the distribution of independent sets and colourings but also appear as partition functions in statistical physics models such as the hard-core model (for gases) and the Ising/Potts models (for ferromagnetism). The project aims to understand the locations of the roots of these and related graph polynomials, which is closely linked to the existence of efficient algorithms for approximate counting. Another goal is to investigate extremal problems, identifying which graphs maximize or minimize these polynomials under various parameter choices. There is also scope to pursue related topics in extremal combinatorics and graph theory. The project is supervised by Dr Viresh Patel, and applicants with strong backgrounds in combinatorics, graph theory, discrete mathematics, algorithms, or complexity are encouraged to apply. Funding is available through EPSRC studentships, covering a 3.5-year stipend and Home tuition fees, with international students required to pay the difference between Overseas and Home fees. Self-funded applicants are also welcome, with flexible start dates in January, April, or September. The School of Mathematical Sciences is committed to equality and diversity, holding a Bronze Athena SWAN award and offering family-friendly benefits and support for part-time study. The application deadline is 28 January 2026, with the expected start date in September 2026. For more information or informal enquiries, prospective students are encouraged to contact Dr Viresh Patel at [email protected].