Talks

Showing 1 - 9 of 9 Results

  • Date
     
    Title
  • 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.