权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Graph decompositions via probability and designs

通过概率和设计进行图分解

基本信息

批准号：
EP/V025953/1
负责人：
Katherine Staden
金额：
$ 38.27万
依托单位：
The Open University
依托单位国家：
英国
项目类别：
Fellowship
财政年份：
2022
资助国家：
英国
起止时间：
2022 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FV025953%2F1
关键词：
Graph decompositions via probability designs

项目摘要

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.

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