Designs and cycle decompositions

设计和循环分解

• 批准号: RGPIN-2019-04328
• 负责人: Burgess, Andrea
• 金额: $ 1.09万
• 依托单位: University of New Brunswick
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=714772
• 关键词: 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 凝胶扩散技术的方法进行涉及 v 种病毒的测试。 她可以将 k 病毒样本排列在培养皿中抗体周围的圆形区域。当病毒和抗体反应时会形成沉淀，相邻样品之间沉淀的形状表明抗体是否对两者的共同成分做出反应。出于这个原因，她想设计她的实验，让每对病毒彼此相邻出现一次；将 v 个顶点上的完整图分解为长度为 k 的循环使她能够做到这一点。如果病毒发生在家族中，并且不需要比较家族的不同成员，那么完整的多部分图的分解将是适当的。 该提案将考虑与某些图族的循环分解相关的存在问题，例如完整的多部分图和完整的有向图。此外，还将探索具有与顶点或循环着色相关的结构属性的分解，以及与此类分解相关的图的邻接属性。 拟议的研究将代表该领域知识的进步，提案中描述的主题与调度、代码和通信等领域的应用有联系。该研究将为本科生、研究生和博士后水平的培训提供机会。