Applying algebra to computing the clique number of a graph

The School of Mathematical Sciences of Queen Mary University of London invite applications for a PhD project commencing either in September 2016 (funded students) or at any point in the academic year (self-funded students).

This project is for students interested in applying algebra and computation to an important problem in graph theory. A clique in a graph is a set of vertices with the property that every pair of distinct vertices in the set is joined by an edge, and the clique number of a graph is the size of a largest clique in that graph. Being able to determine the clique number of a graph has many applications, but is a computationally difficult problem. Algebra can be a big help in determining or bounding the clique number, including linear algebra and eigenvalue techniques, the clique adjacency polynomial for classes of graphs with certain regularity properties, and if the graph has nontrivial symmetries, group theory. The GRAPE package for the GAP system contains functions for the classification of cliques with given properties, and these are especially powerful for graphs with large groups of symmetries.

As part of any project in this area, a student could start by computing an extensive catalogue of interesting graphs in GRAPE format for use in forming and testing conjectures and for testing new algorithmic ideas and programs. Such a library would be a tremendous resource both for the student and the international algebraic graph theory community.

There is large scope for further research, which may take several directions. One direction is to better understand the clique adjacency polynomial and its efficient application. Another is to enhance the GRAPE functions to classify cliques to be able to more efficiently determine the clique number, including the development of new techniques, and possibly implementing the heart of the program in C-code, which should provide a big speed-up and extend the range of applicability to new research problems.

This project will be supervised by Professor Leonard Soicher.

Further details can be found in the project abstract: http://www.maths.qmul.ac.uk/sites/default/files/phd%20projects%202015/Algebra/phdproject_soicher-1.pdf

The application procedure is described on the School website. For further enquiries please contact Prof. Leonard Soicher ([Email Address Removed]).

This project is eligible for several sources of full funding for the 2016/17 academic year, including support for 3.5 years’ study, additional funds for conference and research visits and funding for relevant IT needs. Applicants interested in the full funding will have to participate in a highly competitive selection process. The best candidates will be eligible to receive a prestigious Ian Macdonald Postgraduate Award of £1000, for which you will be considered alongside your application. The application deadline for full funding is January 31st 2016.

There is also 50% funding scheme available for students who are able to find the matching 50 % of the cost of their studies. Competition for these half-funded slots will be less intensive, and eligible students should mention their willingness to be considered for them in their application. The application deadline for 50 % funding is January 31st 2016.

This project can be also undertaken as a self-funded project, either through your own funds or through a body external to Queen Mary University of London. Self-funded applications are accepted year-round.