Talks
Showing 1  9 of 9 Results
Turn Page
 Sie sind auf Seite:19

DateTitle

11/10/2023
10:30  11:30What is Homomorphism Indistinguishability?
Tim SeppeltTwo 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 wellstudied logical equivalences admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minorclosed 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:30ATIGoing Deep and Going Wide
Eva Fluck
The class T^k_q of graphs admitting a kpebble 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_qsentence, that is a kvariable and quantifierrankq sentence of firstorder 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 kpebble forest cover of depth q can be interpreted as incorpotating a width paramenter into a treedepth decomposition. We introduce a corresponding depth measure for treedecompositions, that is the decomposition corresponding to treewidth. 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 treewidth to the class T^k_q and enables us to reprove the statement of Dawar, Jakl and Reggio. Furthermore we introduce a copsandrobber 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:00BScSuchspiele für gerichtete Graphen
Lukas Stein
TBA 
20/10/2023
10:30  11:30ATI 
27/10/2023
10:30  11:30ATI 
03/11/2023
10:30  11:30ATI 
03/11/2023
10:30  11:30ATI 
08/11/2023
10:30  11:30 
22/11/2023
10:30  11:30
Turn Page
 Sie sind auf Seite:19