Isoperimetric inequalities, Erdos-Ko-Rado type problems, and other topics in Extremal Combinatorics

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).

Extremal Combinatorics is a relatively young area of mathematics; as many students will know, it was founded in earnest by a group of mainly Hungarian mathematicians in the early 1900s, and was given huge impetus by Paul Erdos and his collaborators. There has been much exciting progress in extremal combinatorics in recent years, utilising techniques both from combinatorics itself, and also from other areas of mathematics such as algebra, analysis and probability theory. This PhD project would involve gaining familiarity with research-level techniques in combinatorics, and simultaneously tackling some unsolved problems in extremal combinatorics.

The PhD candidate would have a large amount of flexibility over which topics and problems to focus on, within combinatorics. One possible area of investigation is that of isoperimetric inequalities. Isoperimetric problems are classical objects of study in mathematics. In general, they ask for the smallest possible `boundary’ of an object of a certain `size’. Perhaps the oldest is the isoperimetric problem in the plane: among all subsets of the plane of area 1, which has the smallest boundary? The answer was `known’ to the ancient Greeks, but it was not until the 19th century that a rigorous proof was given.

In the last fifty years, there has been a great deal of interest in `discrete isoperimetric inequalities’. These deal with discrete notions of boundary in graphs. They have important applications in computer science and information theory. One very natural unsolved problem in this area is the isoperimetric problem for r-element sets, popularised by Bollobas and Leader; there are many others, which may be slightly easier!

Another possible area of investigation is that of Erdos-Ko-Radotype problems. These ask for the largest possible size of a family of objects in which any two of the objects `agree’ in some way. Recently, several Erdos-Ko-Rado type problems have been tackled successfully using techniques from algebra and analysis. Many, however, remain unsolved. For example, a question of Simonovits and Sos: how many subsets of {1,2,3,…1,n) can you take, such that any two of the subsets share an arithmetic progression of length 3?

The application procedure is described on the School website. For further enquiries please contact Dr David Ellis ([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.