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.
Lior Gishboliner, ETH Zurich
Martin Grohe, University of Aachen
Daniel Král, Masaryk University Brno
Stefan Mengel, CNRS, CRIL, Lens
David E. Roberson, Technical Univ. of Denmark
Radu Curticapean, IT University of Copenhagen
racu(at)itu.dk
Marc Roth , University of Oxford
marc.roth(at)cs.ox.ac.uk
July 10, 2023 in Paderborn, Germany
Seminar Room 4 (HNF) on-site
Detailed Schedule:
(all titles are preliminary and may be subject to changes)
09:00 - 09:40 The Complexity of Counting Homomorphisms from the Left (Radu Curticapean)
09:40 - 10:10 Techniques for Analysing Coefficients in the Homomorphism Basis (Marc Roth)
10:10 - 10:30 Counting Quantum-Graph Homomorphisms modulo a Prime (Andreas Goebel)
10:30 - 11:00 Coffee Break
11:00 - 11:30 Homomorphism Counting and Conjunctive Queries (Stefan Mengel)
11:30 - 12:10 TBA (Lior Gishboliner)
12:10 - 12:30 The Complexity of Subgraph Counting, Parameterized by Degeneracy (Marco Bressan)
12:30 - 14:00 Lunch Break
14:00 - 14:30 Introduction to Homomorphism Indistinguishability (Martin Grohe)
14:30 - 15:00 Quantum Isomorphism vs. Homomorphism Counts from Planar Graphs (David Roberson)
15:00 - 15:20 Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors (Tim Seppelt)
15:20 - 15:40 Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width (Benjamin Scheidt)
15:40 - 16:00 Coffee Break
16:00 - 16:40 Homomorphism Counts and Extremal Combinatorics (Daniel Král)
16:40 - 17:30 Open Problem Session
17:30 - 22:30 ICALP 2023 Get Together
You can still register via the ICALP 2023 Webpage
If you are interested in counting homomorphisms, you might also be interested in the Copenhagen Summer of Counting & Algebraic Complexity.