Matchings and tilings in graphs

图论关注网络（如计算机网络、社会网络和生物网络）的数学研究。图由一组顶点和一组连接这些顶点对的边组成。在现实世界的网络中，配对资源通常很重要。例如，可能希望将工人分配给不同的任务，或将捐赠者分配给合适的患者。在图设置中，这些是匹配问题的示例（匹配是图中不相交边的集合）。图中的完美匹配是覆盖图中所有顶点的不相交边的集合。图中的完美匹配在某种意义上是很容易理解的，因为人们可以有效地确定（通过Edmonds的算法）图是否包含完美匹配。考虑匹配概念的一般化也是很自然的。例如，一个人可能会寻求将劳动力分成给定规模的团队集合。这是图中完美平铺问题的一个例子。或者，您可能希望将员工分配到不同位置的特定工作。这是一个3-partite 3-graph中完美匹配问题的例子（即现在边由三个顶点组成，而不是两个顶点）。与图中的完美匹配形成鲜明对比的是，人们认为没有有效的算法可以在图中找到这样的完美拼接，也没有有效的算法可以在3图中找到完美匹配（更普遍的是在k图中找到至少3个整数的完美匹配）。事实上，这些都是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.