Novel methods in combinatorics

组合数学中的新方法

• 批准号: RGPIN-2021-02511
• 负责人: Morrison, Natasha
• 金额: $ 1.89万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759067
• 关键词: Novel; methods; 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.

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