Adjoint Homomorphism Counting Workshop (ad hoc)
10 July 2023, adjoint with ICALP 2023

Description

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.

Location and Schedule

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