Speaker: Radu Curticapean
Abstract: TBA
ArXiv Links: TBA
Speaker: Marc Roth
Abstract
The starting point for this talk is the framework of Graph Motif Parameters introduced in the previous talk: The evaluation of a linear combination of homomorphism counts is precisely as hard as evaluating its hardest term. It has turned out over the past five years that proving the existence of a translation of a counting problem into such a linear combination is usually quite easy. The hard part is to figure out which terms survive in the "homomorphism basis" with a non-zero coefficient. Moreover, recent work has shown that the homomorphism coefficients often encode topological or algebraic invariants and are sometimes hard to compute themselves. This talk gives an overview over our current understanding of the structure of the homomorphism coefficients for a variety of well-studied counting problems and presents group-theoretic tools that make their analysis feasible.
ArXiv Links
Introduction of Graph Motif Parameters and their application to Subgraph Counting: https://arxiv.org/abs/1705.01595
Graph Motif Parameters and Induced Subgraph Counting: https://arxiv.org/abs/2004.06595
Speaker: Andreas Göbel
Abstract
We study the problem of counting the number of homomorphisms from an input graph G to a fixed (quantum) graph H modulo a prime. The subproblem with graph H was introduced by Faben and Jerrum and its complexity is subject to a series of research articles, finally resolved by Bulatov and Kazeminia. In this talk we will briefly overview this line of research and highlight its challenges. We will then focus our attention on quantum graphs and show that the complexity for a quantum graph H collapses to the complexity criteria found at dimension 1: graphs. Finally we discuss how one obtains a dichotomy for counting partially surjective homomorphisms (mod a prime) using the modular counting techniques developed for the quantum graph framework.
ArXiv Links
Speaker: Stefan Mengel
Abstract
Conjunctive queries are a basic but very important class of database queries that has been studied extensively in database theory for decades now. In this talk, I will survey their counting complexity which tightly connected to the complexity of homomorphism counting but differs in some key aspects. In particular, the existence of so-called projections in the queries has a dramatic complexity impact which has been studied systematically in the last roughly ten years and is, as we will see, by now quite well understood.
ArXiv Links
Complexity of counting answers to conjunctive queries: http://arxiv.org/abs/1408.0890
Complexity of counting answers to existential positive queries: http://arxiv.org/abs/1601.03240
Speaker: Lior Gishboliner
Abstract: TBA
ArXiv Links: TBA
Speaker: Marco Bressan
Abstract:
This talk investigates the fixed-parameter tractability of three fundamental problems -- counting induced subgraphs, counting subgraphs, and counting homomorphisms -- when the parameter includes both the size of the pattern and the degeneracy of the host graph. For the subgraph and induced subgraph problems we will prove clear complexity classifications based on structural parameters of the pattern, such as their induced matching number, generalising several previous results. For the homomorphism problem instead the complexity will remain open; in fact, we will obtain an intriguing conjecture that is an induced version of the celebrated excluded grid theorem. Talk based on joint work with Marc Roth.
ArXiv Links:
Speaker: Martin Grohe
Abstract: TBA
ArXiv Links: TBA
Speaker: David Roberson
Abstract: TBA
ArXiv Links: TBA
Speaker: Tim Seppelt
Abstract:
In 1967, Lovász proved that two graphs G and H are isomorphic iff they are homomorphism indistinguishable over the the family of all graphs, i.e. for all graphs F the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. In recent years, many natural relaxations of graph isomorphism like quantum isomorphism, cospectrality, or logical equivalences have been characterised as homomorphism indistinguishability relations over restricted graph classes.
Motivated by the wealth of such results, we set out in this talk to develop a more general theory of homomorphism indistinguishability. In particular, we aim at understanding the interplay of properties of a graph class (syntax) and its homomorphism indistinguishability relation (semantics). Concretely, we discuss how closure properties of a graph class are reflected by preservation properties of its homomorphism indistinguishability relation. As a corollary, we show that equivalences w.r.t. any self-complementarity logic admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. Self-complementarity is a mild property satisfied by most well-studied logics.
This talk is based on the paper Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors accepted for MFCS 2023.
ArXiv Links:
Speaker: Benjamin Scheidt
Abstract:
We introduce the 2-sorted counting logic GC^k that expresses properties of hypergraphs. This logic has available k variables to address hyperedges, an unbounded number of variables to address vertices, and atomic formulas E(e,v) to express that a vertex v is contained in a hyperedge e. We show that two hypergraphs H, H' satisfy the same sentences of the logic GC^k if, and only if, they are homomorphism indistinguishable over the class of hypergraphs of generalised hypertree width at most k. Here, H, H' are called homomorphism indistinguishable over a class C if for every hypergraph G in C the number of homomorphisms from G to H equals the number of homomorphisms from G to H'.
This is joint work with Nicole Schweikardt.
ArXiv Links:
Speaker: Daniel Král
Abstract:
Extremal combinatorics concerns determining minimum or maximum quantities related to combinatorial structures, e.g., the maximum number of edges of a graph avoiding a particular graph as a subgraph. The vast majority of problems in extremal combinatorics can be formulated as optimization problems based on homomorphism counts. In this talk, we will explore how homomorphism counts link extremal graph theory and the theory of graph limits, which provides analytic tools to analyze large graphs. In particular, we will present the flag algebra method for computing asymptotically true inequalities between homomorphism counts and discuss the asymptotic structure of graphs that are unique solutions of optimization problems involving linear combinations of homomorphism counts.
ArXiv Links: TBA