Combinational, Structural and algorithmic aspects of temporal graphs

布尔矩阵（即0/1矩阵）出现在计算机科学、机器学习、数学和其他领域的不同背景中。例如，在图论中，它们通过所谓的邻接矩阵和关联矩阵提供了一种表示图的标准方法。在通信复杂性中，主要的研究对象——通信问题是用布尔矩阵来描述的[9,11]。在学习理论中，布尔矩阵被用来表示假设类[10]。在所有这些领域，研究人员使用布尔矩阵的布尔组合作为一种通过“更简单”的对象来表达新对象的自然方式。通常，目标是得出结论，如果某些属性适用于“更简单”的对象，那么它可以或不可以扩展为适用于这些对象的布尔组合。在图论中，这种方法最近被用于图标记方案[4,7]。在通信复杂度方面，它用于研究具有访问oracle权限的通信协议[6,7,8]。在学习理论中，它被用来组合假设类以获得更强大的假设类。因此，布尔矩阵的布尔组合自然成为许多领域的有用工具。然而，(1)它们的使用是临时的；(2)他们在不同领域的研究大多是独立的。本项目的中心目标是：1。系统地研究图论背景下的布尔组合作为通过其他图类表示图类的一种方法。这样做的主要目的是了解哪些图属性是由布尔组合保存的，以及在什么条件下保存的。该项目的第二个目标是：用一种共同的语言表述不同地区已知的布尔矩阵的布尔组合的结果，并在适当的情况下将这些结果从一个地区转移到另一个地区；这将有助于在计算机科学和数学的不同领域之间建立联系。开始系统地研究布尔矩阵的布尔组合，而不考虑它们的应用。我们将研究哪些布尔函数在某些遗传类上保留特定的图属性。这些情况以前已经研究过了，例如图的有利性G是表示G为区间图的交点[12]所需的最小数量，表示图的异或[3]所需的完全图的数量，表示图为其并点[1]所需的完全图或等价图的数量，以及表示n顶点图为它们的某些函数[5]所需的阈值图的数量。我们会更广泛地研究图函数。参考资料[1]Noga Alon。用最少数量的等价关系覆盖图。组合数学，6(3):201-206,1986。Noga Alon, Amos Beimel， Shay Moran和Uri Stemmer。用于私有分类和在线预测的闭包属性。《学习理论会议》，第119-152页。PMLR, 2020年。[3]卡勒姆·布坎南，克里斯托弗·珀塞尔和帕克·罗姆巴赫。子图补和最小秩。电子组合学报，29(1),2022。b[4]莫里斯·钱杜。逻辑标签方案。离散数学学报，36(10):113565,2023。[5] Paul Erdös, Edward T . Ordman和yeechezkel Zalcstein。阈值维度和不相交阈值覆盖的边界。代数离散方法学报，8(2):151-154,1987。[6]方玉婷，Lianna Hambardzumyan， Nathaniel Harms和Pooya Hatami。对于恒定成本随机通信来说，没有完全的问题。计算理论学术研讨会论文集（STOC 2024）， 2024。[7]纳撒尼尔·哈姆斯，塞巴斯蒂安·怀尔德和维克多·扎马拉耶夫。随机通信和隐式图表示。第54届ACM SIGACT计算理论研讨会论文集（STOC 2022）， 1220-1233页，2022。bb0纳撒尼尔·哈姆斯和维克多·扎马拉耶夫。sm矩阵与图的随机通信与隐式表示

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