Extremal and stability results for graphs and hypergraphs

图和超图的极值和稳定性结果

• 批准号: RGPIN-2017-04215
• 负责人: Haxell, Penny
• 金额: $ 1.75万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=709980
• 关键词: Extremal; stability; results; graphs; hypergraphs

A graph is an abstract configuration consisting of a set of vertices and a set of edges, where each edge is a subset of the vertex set of size two. A hypergraph is similar except that edges can have any size. Many real-world phenomena can be modelled as graphs or hypergraphs, and contributions to the theory of graphs and hypergraphs can have important practical applications, for example in efficiency and reliability of communication or power systems networks. My research is in extremal problems for graphs and hypergraphs. The general extremal problem is to maximize or minimize one parameter in terms of another (or others). For example, a natural graph parameter is the maximum degree, the largest number of edges containing any given vertex. Here is a typical extremal question: what is the smallest M such that every vertex partition of a graph G with maximum degree d into classes of size at least M contains an independent transversal (a choice of one vertex in each class such that no edge of G joins any two chosen vertices)? This very general problem comes up in many different settings in mathematics and computer science. I answered it in my work some years ago, showing that M=2d is the correct value. Moreover this is best possible, in that there exist graphs with partition class size 2d-1 that do not have independent transversals (such graphs are called extremal for the problem). This theorem now has many applications by various authors, to results in graph theory (including many different aspects of graph colouring), hypergraph matching, group theory, ring theory and resource allocation problems in computer science. An important problem associated with any extremal question is the so-called stability version: if the chosen parameter of a given graph G is close to the maximum (or minimum) possible value, is the structure of G close to that of an extremal configuration? The significance of the stability version of an extremal theorem is seen in its applications: if in an application one knows structural information about the graphs involved that shows they are not close to extremal examples, then improved bounds will result. One of the main aims of my proposed research is to obtain stability versions of certain extremal problems in graphs and hypergraphs, e.g. the one described above. Because of the large number of existing applications of the results I intend to address, stability versions would have significant impact in many areas. Other aspects of my current research are more directly tied to applications. For example, I have worked with a team of power systems engineers on using graph theory for efficient modelling of power supply networks in the setting of the new Smart Grid in Ontario, and I expect to continue on similar projects with this same team. With colleagues in computer science I have developed algorithms for morphing planar graphs, a problem that arises in computer animation, medical imaging and motion planning.

图是由一组顶点和一组边组成的抽象配置，其中每条边是大小为2的顶点集的子集。超图是类似的，除了边可以有任何大小。许多现实世界的现象可以被建模为图或超图，并且对图和超图理论的贡献可以具有重要的实际应用，例如在通信或电力系统网络的效率和可靠性方面。 我的研究方向是图和超图的极值问题。一般极值问题是根据另一个（或其他）参数最大化或最小化一个参数。例如，自然图参数是最大度，即包含任何给定顶点的最大边数。这是一个典型的极值问题：什么是最小的M，使每个顶点划分的图G的最大程度d到类的大小至少M包含一个独立的横截（一个选择的一个顶点，在每个类，使没有边G加入任何两个选定的顶点）？这个非常普遍的问题出现在数学和计算机科学的许多不同环境中。几年前我在工作中回答了这个问题，证明M=2d是正确的值。此外，这是最好的可能性，因为存在分区类大小为2d-1的图，它们没有独立的横截（这样的图被称为极值）。这个定理现在有许多应用程序的各种作者，结果在图论（包括许多不同方面的图着色），超图匹配，群论，环理论和资源分配问题的计算机科学。 与任何极值问题相关的一个重要问题是所谓的稳定性版本：如果给定图G的所选参数接近最大（或最小）可能值，则G的结构是否接近极值配置？极值定理的稳定性版本的意义在于它的应用：如果在一个应用程序中，人们知道所涉及的图的结构信息，表明它们不接近极值的例子，那么就会产生改进的边界。 我提出的研究的主要目的之一是获得稳定版本的某些极值问题的图和超图，例如，上面描述的。由于我打算解决的结果的大量现有应用，稳定性版本将在许多领域产生重大影响。 我目前研究的其他方面更直接地与应用有关。例如，我曾与一个电力系统工程师团队合作，在安大略的新智能电网中使用图论对供电网络进行有效建模，我希望继续与同一团队进行类似的项目。与计算机科学的同事们一起，我开发了平面图形变形的算法，这是计算机动画，医学成像和运动规划中出现的问题。