In recent years, the study of homomorphism counting resurged in various subfields within theoretical computer science. For example, from a complexity theoretic point of view, it was shown that counting problems from different domains can be understood by expressing them as linear combinations of homomorphism counts. Such linear combinations enjoy the exceptional and very useful "monotonicity property" of being exactly as hard to compute as their hardest terms. Since the complexity of computing the individual terms, i.e., of counting homomorphisms, is reasonably well understood, this strategy allowed the community to make significant progress in the study of the complexity of various counting problems arising in database theory and network sciences.
From a more abstract perspective, the numbers of homomorphisms between graphs encode valuable information. For example, a classical result by Lovász shows that homomorphism counts from all graphs into a given graph G identify G up to isomorphism. Restricting the class of graphs from which homomorphisms are counted yields natural relaxations of graph isomorphism that are connected to the expressiveness of logics. Furthermore, in pure mathematics, homomorphism counts enable a definition of convergent graph sequences that leads to so-called graph limits, which are an active area of study.
The purpose of this workshop is two-fold, namely,
to provide a forum for researchers whose work already relates to homomorphism counts, with the goal of translating results between different domains and finding common grounds for collaborations, and
to invite others with a background/interest in algorithms and complexity, logic, graph theory, and/or combinatorics to the theory and applications of homomorphism counts.
Confirmed Invited Speakers
Lior Gishboliner, ETH Zurich
Martin Grohe, University of Aachen
Daniel Král, Masaryk University Brno
Laura Mančinska, University of Copenhagen
Stefan Mengel, CNRS, CRIL, Lens
David E. Roberson, Technical Univ. of Denmark
Radu Curticapean, IT University of Copenhagen
Marc Roth , University of Oxford
Location and Schedule
July 10, 2023 in Paderborn, Germany
on-site, but virtual participation possible in exceptional cases
9:00 - 18:00
final schedule TBA