Symmetry in graphs and hypergraphs

图和超图的对称性

• 批准号: 251352-2011
• 负责人: Sajna, Mateja
• 金额: $ 0.95万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570960
• 关键词: Symmetry; graphs; hypergraphs

The four main research directions of this proposal pertain to the study of symmetry in graphs and related structures (digraphs and hypergraphs). Graphs are mathematical objects consisting of points (called vertices) and links (called edges) that join pairs of vertices. Graphs are used in computer science and many other disciplines to model such objects as data structures, communication networks, computational flows, traffic networks, chemical molecules, social networks, ecosystems etc. I am particularly interested in graphs with a lot of symmetry. Symmetry of a graph can be measured in many different ways: via transformations (called automorphisms) that preserve the graph; by the existence of certain substructures, for example, cycles that traverse every vertex (called Hamilton cycles); by the substructures into which the graph can be decomposed, and so on. Graphs with high symmetry (and their generalizations) play an important role in designing reliable networks, as well as in scheduling problems. Apart from applications, such graphs are interesting and beautiful from a purely theoretical point of view. Some of the problems I am interested in (for example, the problems on digraph decompositions and Hamilton cycles) are basic unsolved problems about graphs: beautiful in the simplicity of their statement and yet very difficult to solve; some have been open for decades. Solutions to these problems would improve our understanding of some important algebraic and combinatorial aspects of graph theory. The fifth research direction included in this proposal is a student project in applications of discrete mathematics. Its main objective is development of algorithms and software that would efficiently solve the problem of outcome prediction for three specific real-life applications, and thus may assist in: (a) the design of proteomic experiments and development of targeted gene therapies for a number of diseases (e.g. coronary heart disease, diabetes, and cancer); (b) predicting new drug-target associations for previously approved drugs; (c) predictive environmental and health risk assessment of chemical mixtures.

该提案的四个主要研究方向涉及图和相关结构（有向图和超图）的对称性研究。图是由点（称为顶点）和连接顶点对的链接（称为边）组成的数学对象。图在计算机科学和许多其他学科中用于对数据结构、通信网络、计算流、交通网络、化学分子、社交网络、生态系统等对象进行建模。我对具有大量对称性的图特别感兴趣。图的对称性可以通过多种不同的方式来测量：通过保留图的变换（称为自同构）；通过某些子结构的存在，例如，遍历每个顶点的循环（称为汉密尔顿循环）；通过图可以分解成的子结构，等等。具有高度对称性的图（及其泛化）在设计可靠网络以及调度问题中发挥着重要作用。除了应用之外，从纯理论的角度来看，这些图也很有趣且美观。我感兴趣的一些问题（例如，有向图分解和哈密尔顿循环的问题）是有关图的基本未解决问题：它们的陈述很简单，但很难解决；有些已经开放了几十年。这些问题的解决方案将提高我们对图论的一些重要代数和组合方面的理解。 该提案中包含的第五个研究方向是离散数学应用的学生项目。其主要目标是开发算法和软件，有效解决三种特定现实生活应用的结果预测问题，从而可能有助于：（a）针对多种疾病（例如冠心病、糖尿病和癌症）设计蛋白质组学实验和开发靶向基因疗法； (b) 预测先前批准药物的新药物靶点关联； (c) 化学混合物的预测性环境和健康风险评估。