Matchings and tilings in graphs

图论涉及网络（如计算机网络，社交网络和生物网络）的数学研究。图由一组顶点和一组连接这些顶点的边组成。在现实世界的网络中，配对资源通常很重要。例如，人们可能希望将工人分配到不同的任务，或者将供体分配给合适的患者。在图设置中，这些是匹配问题的示例（匹配是图中不相交的边的集合）。图中的完美匹配是覆盖图中所有顶点的不相交边的集合。图中的完美匹配是很好理解的，因为人们可以有效地确定（通过埃德蒙兹的算法）图是否包含完美匹配。考虑匹配概念的推广也是很自然的。例如，可以试图将劳动力分成给定规模的团队集合。这是图中完美平铺问题的一个例子。或者，可能希望将员工分配到基于各种不同位置的特定工作。这是3部3图中完美匹配问题的一个例子（即现在的边由三个顶点组成，而不是两个顶点）。与图中的完美匹配形成鲜明对比的是，人们认为没有有效的算法来找到图中的完美拼接，也没有找到3-图中的完美匹配（更一般地，对于任何整数至少为3的k-图）。事实上，这些都是NP完全问题的例子;因此找到这样有效的算法将解决千年奖问题之一。因此，一个新兴的研究方向是找到强制k-图包含完美匹配的一般条件，或者强制图包含完美平铺。这种方法的基础是通常集中在稠密图和k图的类随机行为上的方法。首先，该项目的重点是找到一般类的k-图，其中可以有效地确定k-图是否包含完美匹配。其次，我们将研究强制完美平铺的充分条件，以及确定给定密度的图距离包含完美平铺有多远。特别是，我们将研究顶点有序图中的完美平铺（即顶点现在具有某种给定的排序）。不幸的是，稠密图的一些关键的类随机性质并不扩展到顶点有序图。因此，该项目的一个目的是开发新的方法，这反过来又会让我们更好地了解这些属性的有序设置。

Graph theory concerns the mathematical study of networks (such as computer networks, social networks and biological networks). Graphs consist of a set of vertices and a set of edges connecting some pairs of these vertices. In a real-world network it is often important to pair off resources. For example, one might wish to assign workers to different tasks, or donors to suitable patients. In the graph setting, these are examples of matching problems (a matching is a collection of disjoint edges in a graph). A perfect matching in a graph is a collection of disjoint edges that cover all the vertices in the graph. Perfect matchings in graphs are well-understood in the sense that one can efficiently determine (via an algorithm of Edmonds) whether a graph contains a perfect matching.It is also natural to consider generalisations of the notion of a matching. For example, one may seek to split a workforce into collections of teams of a given size. This is an example of a perfect tiling problem in a graph. Alternatively, one may wish to assign employees to specific jobs based in various different locations. This is an example of a perfect matching problem in a 3-partite 3-graph (i.e. now edges consist of three, not two vertices). In stark contrast to perfect matchings in graphs, it is believed that there is no efficient algorithm for finding such perfect tilings in graphs, nor for finding perfect matchings in 3-graphs (and more generally in k-graphs for any whole number at least 3). Indeed, these are examples of NP-complete problems; so finding such efficient algorithms would resolve one of the Millennium Prize Problems.As such, an emergent research direction is to find general conditions that force a k-graph to contain a perfect matching, or force a graph to contain a perfect tiling. Underlying this approach are methods that often centre on the random-like behaviour of dense graphs and k-graphs.There are two key goals underpinning the research proposal. First, the project focuses on finding general classes of k-graphs where one can efficiently determine whether the k-graph contains a perfect matching. Second, we will investigate sufficient conditions that force a perfect tiling, as well as establishing how far away graphs of a given density can be from containing a perfect tiling. In particular, we will study perfect tilings in vertex ordered graphs (i.e. the vertices now have some given ordering). Unfortunately, some of the key random-like properties of dense graphs do not extend to vertex ordered graphs. Thus, an aim of the project is to develop novel approaches that will in turn give us a better understanding of such properties in the ordered setting.