11/10/2023
10:30 - 11:30

 

What is Homomorphism Indistinguishability?
Tim Seppelt

Two graphs G and H are homomorphism indistinguishable over a class of graphs �� if for all graphs F ∊ �� the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. Homomorphism indistinguishability relations over certain graph classes can characterise various natural equivalence relations that compare graphs, such as (quantum) isomorphism, spectral, and logical equivalences.

Abstracting from the wealth of such instances, we show in this talk that there is a close correspondence between closure properties of the graph class �� and preservation properties of the homomorphism indistinguishability relation over ��. In particular, most well-studied logical equivalences admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. This result suggests that homomorphism indistinguishability relations are of a distinct nature.

The talk takes place at an UnRAVeL Biweekly Meeting.

13/10/2023
10:30 - 11:30

ATI

Going Deep and Going Wide
Eva Fluck
The class T^k_q of graphs admitting a k-pebble forest cover of depth q has recently gained relevance in the field of homomorpism indistinguishability. Dawar, Jakl and Reggio (2021) proved that two graphs satisfy the same C^k_q-sentence, that is a k-variable and quantifier-rank-q sentence of first-order logic with counting quantifiers, if and only if they are homomorphism indistinguishable over the class T^k_q.

We provide a graph theoretic analysis of the graph class T^k_q. A k-pebble forest cover of depth q can be interpreted as incorpotating a width paramenter into a tree-depth decomposition. We introduce a corresponding depth measure for tree-decompositions, that is the decomposition corresponding to tree-width. We also consider a third decomposition that is inspired by techniques of Dvořák (2010), that enable us to lift his proof technique from graphs of bounded tree-width to the class T^k_q and enables us to reprove the statement of Dawar, Jakl and Reggio. Furthermore we introduce a cops-and-robber game that characterizes the class T^k_q. This allows us to separate T^k_q from the intersection of the graph class TW_{k−1}, that is graphs of treewidth less or equal k − 1, and TD_q, that is graphs of treedepth at most q, if q is sufficiently larger than k. We are able to lift this separation to the semantic separation of the respective homomorphism indistinguishability relations. A part of this separation is to prove that the class TD_q is homomorphism distinguishing closed, which was already conjectured by Roberson (2022).

This is joined work with Tim Seppelt and Gian Luca Spitzer.

19/10/2023
14:30 - 15:00

BSc

Suchspiele für gerichtete Graphen
Lukas Stein
TBA

20/10/2023
10:30 - 11:30

ATI

ATI talk
Moritz Lichter
abstract

27/10/2023
10:30 - 11:30

ATI

ATI talk
Hinrikus Wolf
abstract

03/11/2023
10:30 - 11:30

ATI

ATI talk
Jan Böker
abstract

03/11/2023
10:30 - 11:30

ATI

ATI talk
Jan Böker
abstract

08/11/2023
10:30 - 11:30

 

TBA
Christoph Standke
The talk takes place at an UnRAVeL Biweekly Meeting.

22/11/2023
10:30 - 11:30

 

TBA
Eran Rosenbluth
The talk takes place at an UnRAVeL Biweekly Meeting.