Novel methods in combinatorics

点击翻译按钮获取中文摘要

My research lies in the field of combinatorics, although several of my research directions are intrinsically linked to questions in number theory, probability and geometry. The overarching theme of my proposed research program concerns new methods. It involves both pioneering new methods that have the potential to revolutionise our understanding in certain areas, developing novel techniques that I (along with co-authors) have discovered and utilising existing powerful methods in areas where their strength has not yet been fully exploited. In the past I have substantially impacted the field in many distinct areas, and I intend to continue in this vein. To this end, my program contains several themes. Random Matrices: The study of random matrices lies at the intersection of combinatorial geometry, probability and number theory. Understanding the properties and parameters of random matrices has many applications to other areas of mathematics such as graph theory, stochastic growth models and tiling problems, but also to engineering (in particular in the design and analysis of wireless networks). I intend to develop techniques towards solving two of the major open problems in this area, then to apply these techniques to related problems. Graph colouring: It is very desirable to have an intelligible certificate that a graph is not k-colourable. With some colleagues, I recently developed a framework in which we could find simple algebraic certificates for non k-colourability, and for which existence can be proved by elementary arguments. This research direction involves developing our theory and applying it to prove a wide range of results in the area of graph colouring. We have successfully achieved our first goals and reproved several known results using our methods. Processes on graphs: The family of processes that I am interested in can be thought of as models of the spread of disease through a network. A typical such process begins with an initial set of `infected' nodes (the others are `healthy'), and at each time step, a healthy node can become infected according to a set of update rules. The questions I intend to study broadly fall into two categories: extremal and probabilistic. Extremal questions are often of the form, `What is the minimum number of vertices that need to be initially infected for the process to spread to infect everything?' The probabilistic questions concern the study of parameters of a process where the initially infected set is chosen randomly. Extremal graph theory: With Scott, I determined the maximum possible number of induced cycles in a graph with n vertices. I believe that our methods can be generalised and applied to related problems. One such problem is an extremal question on transversals in hypergraphs. This is interesting because results about minimal transversals of hypergraphs can be translated to give results about particular minimal models in CNF theories, which have applications in logic programming.