Combinational, Structural and algorithmic aspects of temporal graphs

布尔矩阵(即0/1-矩阵)出现在计算机科学、机器学习、数学和其他领域的不同环境中。例如，在图论中，它们提供了一种通过所谓的邻接和关联矩阵来表示图的标准方法。在通信复杂性方面，主要研究对象是通信问题，用布尔矩阵[9，11]来描述。在学习理论中，布尔矩阵用于表示假设类[10]。在所有这些领域，研究人员使用布尔矩阵的布尔组合作为一种自然的方式，通过“更简单”的对象来表达新的对象。通常，我们的目标是得出这样的结论：如果某些属性适用于“较简单”的对象，则它可以或不能扩展为适用于这些对象的布尔组合。在图论中，这种方法最近被用于图标记方案的上下文中[4，7]。在通信复杂性方面，它被用来研究访问Oracle[6，7，8]的通信协议。在学习理论中，它被用来组合假设类以获得更强大的假设类[2]。因此，布尔矩阵的布尔组合在许多领域自然成为一种有用的工具。然而，(1)它们的使用是临时的；(2)它们在不同领域的研究大多是独立的。本项目的中心目标是：1.在图论的背景下系统地研究布尔组合作为一种通过其他图类来表示图类的方法。这个项目的主要目的是了解布尔组合保留了哪些图形属性，以及在什么条件下。该项目的次要目标是：2.使用公共语言制定关于不同领域中已知的布尔矩阵的布尔组合的结果，并在适当的情况下将这些结果从一个领域转移到另一个领域；这将有助于在计算机科学和数学的不同领域之间建立联系。开始系统地研究布尔矩阵的布尔组合，独立于它们的应用。我们将调查某些遗传类上的哪些布尔函数保持特定的图性质。以前已经研究过这些情况，例如，图的盒性是将G表示为其交集所需的最小区间图的数目[12]，将图表示为其异或所需的完全图的数目[3]，将图表示为其并[1]所需的完全或等价图的数目[1]，以及将n-顶点图表示为它们的特定函数所需的阈值图的数目[5]。我们将更一般地看图函数。参考文献[1]诺加。用最小等价关系数覆盖图。《联合体》，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]莫里斯·昌杜。合理的标签方案。《离散数学》，第346(10)：113565,2023年。[5]保罗·埃德·S、爱德华·T·奥德曼和叶切兹克尔·扎尔茨坦。门限维度和不相交门限覆盖的界。《暹罗代数离散方法学报》，8(2)：151-154,1987。[6]方雨婷、利亚娜·汉巴德祖米安、纳撒尼尔·哈姆斯和普亚·哈塔米。固定成本的随机通信没有完全的问题。《计算理论研讨会论文集》(STEC 2024)，2024年。[7]纳撒尼尔·哈姆斯、塞巴斯蒂安·怀尔德和维克托·扎马拉耶夫。随机化交流和隐式图形表示。《第54届ACM Sigact计算理论研讨会论文集》(STOC 2022)，第1220-1233页，2022年。[8]纳撒尼尔·哈姆斯和维克托·扎马拉耶夫。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