+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************

Zeit: Freitag, 16.08.2024, 10:00 Uhr Ort: Informatikzentrum der RWTH Aachen University, Gebäude E3, 2. Etage, Raum 9222

Referent: Eva Fluck, M.Sc. Lehrstuhl für Logik und Theorie diskreter Systeme

Thema: Graph decompositions. A study on decompositions of graphs and their application to logic and data science

Abstract:

We study decompositions of graphs and their application to the expressiveness of first-order logic with counting quantifiers and clustering data. Besides the decompositions themselves we also consider graph parameters that arise from these decompositions as well as obstructions to the existence of good decompositions.

The graph class T_q^k are all graphs which have a bounded tree-depth decomposition that also bounds the width. Its homomorphism indistinguishability relation enjoys a rich connection to the expressiveness of counting logic, as shown by Dawar, Jakl and Reggio (2021). Building upon ideas by Dvořák (2010), we reprove this connection. Our proof strategy also enables to construct a graph class which characterizes equivalence under guarded counting logic. A graph theoretic analysis of T_q^k allows us separate it from the intersection of TW_k−1 , the class of graphs of tree-width at most k−1, and TD_q the graphs of tree-depth at most q, if q is sufficiently larger than k. This also yields a new characterization of tree-depth via treedecompositions and a characterization of T_q^k via a Cops-and- Robber game. To lift this separation to the respective equivalence relations, we show that this game is monotone, that is Robber can never reach a vertex that was cleared in some earlier round. This also give a novel proof of the monotonicity of the Cops-and-Robber game for tree- width without the use of any dual object, like brambles. Another part of the separation of the equivalence classes is to prove that T_q^k and TD_q are homomorphism distinguishing closed, which was conjectured by Roberson (2022).

Tangles are a concept to formalize regions of high connectivity in graphs in an unambiguous way. It can be translated to more abstract connectivity systems, where they describe highly connected regions in the underling universe. Recently they emerged as a new approach to clustering data. We find that the non-trivial clusters resulting from the well known single linkage hierarchical clustering algorithm are exactly the tangles of an appropriately chosen connectivity function on the data points. We generalize this connection to a one-to-one correspondence between connectivity functions that are maximum- submodular and dendograms which are a way to represent the result of an arbitrary hierarchical clustering algorithm.

Es laden ein: die Dozentinnen und Dozenten der Informatik