Designs and cycle decompositions

设计和循环分解

• 批准号: RGPIN-2019-04328
• 负责人: Burgess, Andrea
• 金额: $ 1.09万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675519
• 关键词: Designs; cycle; decompositions

A graph can be thought of as a mathematical representation of a network; it consists of a collection of vertices (often represented as points) together with edges (lines joining pairs of vertices) representing relationships between vertices. Suppose that in a graph, we start at a vertex v and traverse a sequence of edges, each adjacent to the previous. If we arrive back at v without repeating any vertex along the way, we have traversed a cycle, whose length equals the number of edges traversed.******A cycle decomposition of a graph is a partition of its edge set into cycles. Cycle decompositions of highly structured graphs, such as complete graphs (which have an edge joining each pair of vertices) and complete multipartite graphs (whose vertices occur in parts, with edges between any pair in different parts), can be considered as a class of combinatorial design, and have applications in the design of certain types of statistical experiment. Consider, for instance, the following example described in a paper of D.H. Rees (Some designs of use in serology, Biometrics 23 (1967), 779-791). A biologist is conducting a test involving v types of virus using a method called the Ouchterlony gel diffusion technique. She can arrange k virus samples in a circular shape around an antibody in a Petri dish. Precipitates form when a virus and antibody react, and the shape of a precipitate between neighbouring samples indicates whether the antibody is responding to a common component of the two. For this reason, she wants to design her experiment so that each pair of viruses appear next to each other once; a decomposition of the complete graph on v vertices into cycles of length k allows her to do this. If the viruses occur in families, where different members of a family are not to be compared, a decomposition of a complete multipartite graph would be appropriate.******This proposal will consider existence questions related to cycle decompositions of certain families of graphs such as complete multipartite graphs and complete directed graphs. Additionally, decompositions with structural properties related to colouring of vertices or cycles will be explored, as will adjacency properties of graphs related to such decompositions. ******The proposed research will represent an advancement of knowledge in the area and the topics described in the proposal have connections to applications in areas such as scheduling, codes and communications. The research will provide opportunity for training at the undergraduate, graduate and postdoctoral levels. **

图可以被认为是网络的数学表示；它由一组顶点（通常表示为点）和表示顶点之间关系的边（连接顶点对的线）组成。假设在一个图中，我们从顶点v开始，遍历一系列边，每条边都与前一条边相邻。如果我们回到v点时没有重复任何顶点，我们就遍历了一个循环，它的长度等于所遍历的边的数量。******图的循环分解是将其边集划分为循环。高度结构化图的循环分解，如完全图（有一条边连接每对顶点）和完全多部图（其顶点出现在部分中，在不同部分的任何对之间都有边），可以被认为是一类组合设计，并在某些类型的统计实验设计中有应用。例如，考虑D.H. Rees在一篇论文中描述的以下例子（血清学中使用的一些设计，Biometrics 23(1967), 779-791）。一位生物学家正在进行一项涉及五种病毒的测试，使用的方法是一种叫做Ouchterlony凝胶扩散技术。她可以将k个病毒样本在培养皿中的抗体周围排列成圆形。当病毒和抗体发生反应时，会形成沉淀物，相邻样品之间沉淀物的形状表明抗体是否对两者的共同成分产生反应。出于这个原因，她想设计她的实验，使每对病毒彼此相邻出现一次；将v个顶点的完全图分解成长度为k的循环，使她能够做到这一点。如果病毒发生在家庭中，而家庭的不同成员不进行比较，则对完全多部图进行分解将是适当的。******本提案将考虑与某些图族（如完全多部图和完全有向图）的循环分解相关的存在性问题。此外，将探讨与顶点或循环着色相关的结构属性的分解，以及与此类分解相关的图的邻接属性。******拟议的研究将代表该领域知识的进步，提案中描述的主题与调度、代码和通信等领域的应用有关。这项研究将为本科生、研究生和博士后提供培训机会。**