Termine Vorträge

Treffer 1 - 8 von 8 Ergebnissen

  • Termin
     
    Titel
  • 23.05.2019
    13:00 - 14:00
     
    The Weisfeiler-Leman Dimension of Graphs of Bounded Treedepth
    Luca Oeljeklaus
    In this talk we discuss the dimension of the Weisfeiler-Leman (WL) algorithm, which is a combinatorial algorithm used as a subroutine for graph isomorphism testing, in terms of treedepth, a graph invariant also referred to as minimum elimination tree height or vertex ranking number. More precisely, we prove upper and lower bounds on the WL-dimension of graphs of bounded treedepth by using two results from Cai, Fürer, and Immerman. In our proof to show that every graph of treedepth at most k is identified by the (k-1)-dimensional WL-algorithm, we use the fact that the (k-1)-dimensional WL-algorithm identifying a graph is equivalent to Spoiler having a winning strategy for the C_k-pebble game between a graph of treedepth at most k and any other non-isomorphic graph. From there we develop an inductive winning strategy for Spoiler over the treedepth of the graph. In our proof to show that there exists a family of pairs of graphs of treedepth k for arbitrarily large k such that the (k/25)-dimensional WL-algorithm does not distinguish them, we apply the CFI-graph construction to a family of graphs with large separators and then prove an upper bound on the treedepth of the resulting pairs of graphs.
  • 24.05.2019
    10:00 - 11:00
     
    First talk ATI seminar
    Jan Böker
  • 31.05.2019
    10:00 - 11:00
     
    Second talk ATI seminar
    Daniel Neuen
  • 31.05.2019
    10:00 - 11:00
     
    Second talk ATI seminar
    Daniel Neuen
  • 14.06.2019
    10:00 - 11:00
     
    Fourth talk ATI seminar
    Daniel Wiebking
  • 21.06.2019
    10:00 - 11:00
     
    Fifth talk ATI seminar
    Patrick Landwehr
  • 28.06.2019
    10:00 - 11:00
     
    Sixth talk ATI seminar
    Anton Pirogov
  • 12.07.2019
    10:00 - 11:00
     
    Seventh talk ATI seminar
    Eva Fluck