Eva Fluck

Isolde Adler, Eva Fluck, Tim Seppelt et al.

We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment $\mathsf{C}^k_q$, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio (2021) proved that two graphs satisfy the same $\mathsf{C}^k_q$-sentences iff they are homomorphism indistinguishable over the class $\mathcal{T}^k_q$ of graphs admitting a $k$-pebble forest cover of depth $q$. After reproving this result using elementary means, we provide a graph-theoretic analysis of $\mathcal{T}^k_q$. This allows us to separate $\mathcal{T}^k_q$ from the intersection $\mathcal{TW}_{k-1} \cap \mathcal{TD}_q$, provided that $q$ is sufficiently larger than $k$. Here $\mathcal{TW}_{k-1}$ is the class of all graphs of treewidth at most $k-1$ and $\mathcal{TD}_q$ is the class of all graphs of treedepth at most $q$. We are able to lift this separation to a separation of the respective homomorphism indistinguishability relations $\equiv_{\mathcal{T}^k_q}$ and $\equiv_{\mathcal{TW}_{k-1} \cap \mathcal{TD}_q}$. We do this by showing that the classes $\mathcal{TD}_q$ and $\mathcal{T}^k_q$ are homomorphism distinguishing closed, as conjectured by Roberson (2022). In order to prove Roberson's conjecture for $\mathcal{T}^k_q$, we characterise $\mathcal{T}^k_q$ in terms of a monotone Cops-and-Robber game. The crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is monotone. To that end, we transform Cops' winning strategy into a pree-tree-decomposition, which is inspired by decompositions of matroids, and then apply an intricate breadth-first cleaning up procedure along the pree-tree-decomposition (which may temporarily lose the property of representing a strategy). Thereby, we achieve monotonicity while controlling the number of rounds across all branches of the decomposition via a vertex exchange argument.

Eva Fluck

We establish a connection between tangles, a concept from structural graph theory that plays a central role in Robertson and Seymour's graph minor project, and hierarchical clustering. Tangles cannot only be defined for graphs, but in fact for arbitrary connectivity functions, which are functions defined on the subsets of some finite universe. In typical clustering applications these universes consist of points in some metric space. Connectivity functions are usually required to be submodular. It is our first contribution to show that the central duality theorem connecting tangles with hierarchical decompositions (so-called branch decompositions) also holds if submodularity is replaced by a different property that we call maximum-submodular. We then define a connectivity function on finite data sets in an arbitrary metric space and prove that its tangles are in one-to-one correspondence with the clusters obtained by applying the well-known single linkage clustering algorithms to the same data set. Lastly we generalize this correspondence for any hierarchical clustering. We show that the data structure that represents hierarchical clustering results, called dendograms, are equivalent to maximum-submodular connectivity functions and their tangles. The idea of viewing tangles as clusters has first been proposed by Diestel and Whittle in 2016 as an approach to image segmentation. To the best of our knowledge, our result is the first that establishes a precise technical connection between tangles and clusters.

Eva Fluck, Sandra Kiefer, Christoph Standke

Tangles were originally introduced as a concept to formalize regions of high connectivity in graphs. In recent years, they have also been discovered as a link between structural graph theory and data science: when interpreting similarity in data sets as connectivity between points, finding clusters in the data essentially amounts to finding tangles in the underlying graphs. This paper further explores the potential of tangles in data sets as a means for a formal study of clusters. Real-world data often follow a normal distribution. Accounting for this, we develop a quantitative theory of tangles in data sets drawn from Gaussian mixtures. To this end, we equip the data with a graph structure that models similarity between the points and allows us to apply tangle theory to the data. We provide explicit conditions under which tangles associated with the marginal Gaussian distributions exist asymptotically almost surely. This can be considered as a sufficient formal criterion for the separabability of clusters in the data.