Novel methods in combinatorics

我的研究领域是组合学，尽管我的几个研究方向本质上与数论、概率和几何中的问题有关。我提出的研究计划的首要主题是新方法。它包括开创性的新方法，这些方法有可能彻底改变我们在某些领域的理解，开发我(与合著者)发现的新技术，以及在尚未充分利用其优势的领域利用现有的强大方法。在过去，我在许多不同领域对该领域产生了重大影响，我打算继续这样做。为此，我的节目包含几个主题。随机矩阵：研究随机矩阵是组合几何学、概率论和数论的交叉学科。了解随机矩阵的性质和参数在其他数学领域有许多应用，如图论、随机增长模型和平铺问题，但也适用于工程(特别是在无线网络的设计和分析中)。我打算开发技术来解决这一领域中的两个主要开放问题，然后将这些技术应用于相关问题。图的着色：一个图不是k-色的，这是非常可取的。最近，我和一些同事开发了一个框架，在这个框架中，我们可以找到非k-色性的简单代数证书，并且可以用初等论点来证明它的存在性。这一研究方向包括发展我们的理论并将其应用于证明图着色领域的一系列结果。我们已经成功地实现了我们的第一个目标，并用我们的方法驳斥了几个已知的结果。图上的过程：我感兴趣的过程家族可以被认为是疾病通过网络传播的模型。典型的这种过程开始于一组初始的“受感染”节点(其他节点是“健康的”)，并且在每个时间步，根据一组更新规则，一个健康的节点可能会被感染。我打算广泛研究的问题分为两类：极端问题和概率问题。极端的问题通常是这样的，‘最初需要感染多少个顶点，这个过程才能传播到所有东西？’概率问题涉及随机选择初始感染集合的过程参数的研究。极值图论：与Scott一起，我确定了一个有n个顶点的图中诱导圈的最大可能数目。我相信我们的方法可以推广并应用于相关问题。一个这样的问题是关于超图中横截的极端问题。这很有趣，因为关于超图最小断面的结果可以转化为关于CNF理论中特定极小模型的结果，这些理论在逻辑编程中有应用。

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.