Graph decompositions via probability and designs

分解的概念，即将一个较大的物体分割成较小的碎片，在数学中无处不在。有时这样做是为了更好地理解更大的对象，例如用傅立叶级数表示函数，或分解整数。另一方面，我们可能希望了解哪些部分可能分割给定的较大对象。我们可以用什么形状来平铺飞机？有没有可能把计算成本很高的除法运算“分解”成加法、减法和乘法(就像计算机用来除实数的算法一样)？这项建议试图在图或网络中研究这些问题。图是节点的集合，其中的一些对由边连接，以表示它们之间的某种关系或连接。更复杂的关系是用超图编码的，其中两个以上的节点可以一起位于一条边上。在生物、通信和计算机科学中，图被用来建模和描述许多不同的系统，它们的理论研究属于组合学的数学领域。在图的设置中，分解问题的目标是从具有多条边的大的宿主图和每条边都很少的客体图的集合开始，并试图将客体图完美地匹配到宿主图中，每条边恰好使用一次。这类问题是组合数学中最古老的问题之一，可以追溯到1792年的欧拉问题。到目前为止，每个访客图包含的节点很少的情况已经相当清楚，并构成了设计理论的领域。这个项目研究了另一种情况，在这种情况下，客户图可能包含许多与宿主图相当的节点。一个可以用图形语言表达的问题的例子，最近解决的Oberwolfach问题，要求一系列的座位计划，允许一个组中的每个人在几顿饭的过程中紧挨着人坐一次。最近在这个领域的成功，包括我参与的工作，解决了一些长期存在的猜想，并克服了以前工作中遇到的障碍，通过来自组合学以外学科的新工具的应用。我试图在这些成功的基础上，借鉴概率和设计理论中的工具来获得图形分解。例如，一种有效的策略是使用一种随机算法，进行连续的掷硬币，以选择将每个客户边缘放在哪里；需要概率论的工具来分析其演变。这样的算法不太可能正确地放置最终的碎片；设计理论中的工具将帮助完成分解。

The notion of decomposition, or splitting a larger object into smaller pieces, is ubiquitous in mathematics. Sometimes one does this to better understand the larger object, for example representing a function by a Fourier series, or factorising an integer. On the other hand, we may wish to understand which pieces can possibly partition a given larger object. With which shapes can we tile the plane? Is it possible to 'decompose' the computationally expensive operation of division into only addition, subtraction and multiplication (as in an algorithm used by a computer to divide real numbers)? This proposal seeks to investigate these problems in graphs, or networks. A graph is a collection of nodes in which some pairs are joined by edges, to represent some relationship or connection between them. More complicated relationships are encoded by hypergraphs, where more than two nodes can lie in an edge together. Graphs are used to model and describe many different systems in biology, communications and computer science and their theoretical study comes under the mathematical field of combinatorics.In the graph setting, the goal of a decomposition problem is to start with a large 'host' graph with many edges, and a collection of 'guest' graphs each with few edges, and to try to fit the guest graphs perfectly into the host graph, using each edge exactly once. This type of problem is one of the oldest in combinatorics, going back to a 1792 question of Euler. The case where each guest graph contains few nodes is by now fairly well-understood and constitutes the area of design theory. This project investigates the other end of the spectrum where guest graphs may contain a number of nodes comparable with the host graph. An example of such a question that can be expressed in the language of graphs, the recently solved Oberwolfach problem, asks for a sequence of seating plans which allow each person in a group to sit next to each other person exactly once over the course of several meals.Very recent successes in this area, including work in which I was involved, solved a number of longstanding conjectures and overcame the barriers met in previous works by novel application of tools from disciplines outside of combinatorics. I seek to build on these successes and draw from tools in probability and design theory to obtain graph decompositions. For example, an effective strategy has been to use a randomised algorithm that makes successive coin flips to choose where to put each guest edge; tools from probability are needed to analyse its evolution. Such an algorithm is very unlikely to be able to place the final pieces correctly; tools from design theory will help complete the decomposition.