Combinational, Structural and algorithmic aspects of temporal graphs

时间图的组合、结构和算法方面

• 批准号: 2903280
• 金额: --
• 依托单位: University of Liverpool
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2903280
• 关键词: Combinational; Structural; algorithmic; aspects; temporal

Boolean matrices (i.e., 0/1-matrices) appear in different contexts in computer science, machine learning, mathematics, and other areas. For example, in graph theory they provide a standard way to represent graphs, via so called adjacency and incidence matrices. In communication complexity, the main objects of study, communication problems, are described by Boolean matrices [9, 11]. In learning theory, Boolean matrices are used to represent hypothesis classes [10]. In all these areas, researchers used Boolean combinations of Boolean matrices as a natural way to express new objects via "simpler" objects. Usually, the goal is to conclude that if some property holds for the "simpler" objects, then it can or cannot be extended to hold for Boolean combinations of these objects. In graph theory, this approach was recently used in the context of graph labelling schemes [4, 7]. In communication complexity, it is used to study communication protocols with access to oracles [6, 7, 8]. In learning theory, it is used to combine hypothesis classes to obtain more powerful ones [2]. Thus, Boolean combinations of Boolean matrices naturally appear as a useful tool in a number of areas. However, (1) their usage is ad-hoc; and (2) their studies in different areas are mostly independent. The central aim of the present project is to: 1. Systematically study Boolean combinations in the context of graph theory as a means of expressing graph classes via some other graph classes. The main intention of this is to understand which graph properties are preserved by Boolean combinations, and under what conditions.The secondary aims of the project are to: 2. Formulate results about Boolean combinations of Boolean matrices known in different areas using a common language and where appropriate transfer such results from one area to another; this will contribute to building links between different areas of computer science and mathematics.3. Initiate a systematic study of Boolean combinations of Boolean matrices independently of their application.We will investigate which Boolean functions on certain hereditary classes preserve particular graph properties. Cases of these have been studied before, for example the boxicity of a graph, G, is the minimum number of interval graphs needed to represent G as their intersection [12], the number of complete graphs needed to represent graphs as their XOR [3], the number of complete or equivalence graphs needed to represent graphs as their union [1] and the number of threshold graphs needed to represent n-vertex graphs as certain functions of them [5]. We will be looking at graph functions more generally.References[1] Noga Alon. Covering graphs by the minimum number of equivalence relations. Combinatorica, 6(3):201-206, 1986. [2] Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In Conference on Learning Theory, pages 119-152. PMLR, 2020. [3] Calum Buchanan, Christopher Purcell, and Puck Rombach. Subgraph complementation and minimum rank. The Electronic Journal of Combinatorics, 29(1), 2022. [4] Maurice Chandoo. Logical labeling schemes. Discrete Mathematics, 346(10):113565, 2023. [5] Paul Erdös, Edward T Ordman, and Yechezkel Zalcstein. Bounds on threshold dimension and disjoint threshold coverings. SIAM Journal on Algebraic Discrete Methods, 8(2):151-154, 1987. [6] Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, and Pooya Hatami. No complete problem for constant-cost randomized communication. In Proceedings of the Symposium on Theory of Computing (STOC 2024), 2024. [7] Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev. Randomized communication and implicit graph representations. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), pages 1220-1233, 2022. [8] Nathaniel Harms and Viktor Zamaraev. Randomized communication and implicit representations for matrices and graphs of sm

布尔矩阵（即 0/1 矩阵）出现在计算机科学、机器学习、数学和其他领域的不同上下文中，例如，在图论中，它们通过所谓的邻接矩阵和关联矩阵提供了图形表示的标准方法。在通信复杂性中，主要研究对象——通信问题，是通过布尔矩阵来描述的[9, 11]。在学习理论中，布尔矩阵用于表示假设类。 [10] 在所有这些领域，研究人员使用布尔矩阵的布尔组合作为通过“更简单”对象表达新对象的自然方式，通常，目标是得出结论：如果某些属性适用于“更简单”对象，则它可以或不能扩展到支持这些对象的布尔组合。在图论中，这种方法最近被用于图标记方案的背景中[4, 7]。在通信复杂性中，它用于研究具有访问权限的通信协议。到在学习理论中，它用于组合假设类以获得更强大的假设类[2]，因此，布尔矩阵的布尔组合自然地在许多领域中成为有用的工具。 (1) 它们的使用是临时的；(2) 它们在不同领域的研究大多是独立的。本项目的中心目标是： 1. 在图论的背景下系统地研究布尔组合作为表达手段。其主要目的是了解布尔组合保留哪些图属性以及在什么条件下保留。该项目的次要目标是： 2. 制定有关已知布尔矩阵的布尔组合的结果。在不同领域使用通用语言，并在适当的情况下将这些结果从一个领域转移到另一个领域；这将有助于建立计算机科学和数学不同领域之间的联系。3．我们将研究某些遗传类上的哪些布尔函数保留了特定的图属性，例如图的盒子性 G 是将 G 表示为它们的区间图的最小数量。交集 [12]、将图表示为其 XOR [3] 所需的完整图的数量、将图表示为其并集 [1] 所需的完整或等价图的数量以及表示 n 顶点所需的阈值图的数量图作为它们的某些函数 [5]。我们将更广泛地研究图函数。参考文献 [1] Noga Alon，《通过最小数量的等价关系覆盖图》，6(3):201-206, 1986。 [2] Noga Alon、Amos Beimel、Shay Moran 和 Uri Stemmer。《学习理论会议》页面。 119-152。PMLR，2020。[3]Calum Buchanan、Christopher Purcell 和 Puck Rombach。组合学电子杂志，29(1)，2022。[4] Maurice Chandoo。离散数学，346(10):113565, 2023。 [5] 保罗Erdös、Edward T Ordman 和 Yechezkel Zalcstein。《SIAM 代数离散方法杂志》，8(2):151-154, 1987。 [6] Yuting Fang、Lianna Hambardzumyan、Nathaniel Harms 和Pooya Hatami。《理论研讨会论文集》中的恒定成本随机通信没有完整的问题。计算 (STOC 2024)，2024。 [7] Nathaniel Harms、Sebastian Wild 和 Viktor Zamaraev。第 54 届年度 ACM SIGACT 计算理论研讨会论文集 (STOC 2022)，第 1220 页1233, 2022。 [8] 纳撒尼尔·哈姆斯和维克托·扎马拉耶夫。 sm 矩阵和图的随机通信和隐式表示