Combinational, Structural and algorithmic aspects of temporal graphs

点击翻译按钮获取中文摘要

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