Extremal and stability results for graphs and hypergraphs

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

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

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