Tim Seppelt

The central open question of algebraic complexity is whether VP is unequal to VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020) who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. As a concrete example, we examine the symmetric complexity of immanant families (a generalisation of the determinant and permanent) and show that a known conditional dichotomy due to Curticapean (2021) holds unconditionally in the symmetric setting.

Two graphs G and H are homomorphism indistinguishable over a class of graphs 𝓕 if, for all graphs F ∊ 𝓕, the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. In 1967, Lovász showed that two graphs are isomorphic if, and only if, they are homomorphism indistinguishable over the class of all graphs. Subsequently, many graph isomorphism relaxations such as quantum isomorphism, spectral, and logical equivalences have been characterised as homomorphism indistinguishability relations over certain graph classes. Thereby, homomorphism indistinguishability connects seemingly disparate fields such as quantum information, finite model theory, and machine learning.

This thesis explores three themes: We first review the plenitude of characterisations of graph isomorphism relaxations as a homomorphism indistinguishability relation. Focusing on integer programming relaxations for graph isomorphism, we prove that the feasibility of each level of the Sherali–Adams and Lasserre hierarchies is characterised as homomorphism indistinguishability relations. These results, which are derived using (bi)labelled graphs and homomorphism tensors, shed light on the distinguishing power of these hierarchies. In particular, we determine the precise number of Sherali–Adams levels necessary such that their feasibility guarantees the feasibility of a given Lasserre level.

Abstracting from the wealth of homomorphism indistinguishability characterisations, we embark on a more principled study of homomorphism indistinguishability investigating the distinguishing power and the complexity of homomorphism indistinguishability relations over minor-closed graph class.

The homomorphism distinguishing closure cl(𝓕) of a graph class 𝓕 is the central notion for studying the distinguishing power of homomorphism indistinguishability relations. It is defined as the maximal graph class whose homomorphism indistinguishability relation coincides with the one of 𝓕. Roberson conjectured that every minor-closed union-closed graph class 𝓕 is homomorphism distinguishing closed, i.e. cl(𝓕) = 𝓕. We confirm Roberson’s conjecture, which is generally wide open, for further graphs classes and prove unconditionally that if 𝓕 is minor-closed then so is cl(𝓕).

Lastly, we investigate the complexity of deciding whether two graphs are homomorphism indistinguishable over a fixed graph class. For infinite graph classes, this problem is a priori not even decidable. In stark contrast to this, we show that, over every minor-closed graph class of bounded treewidth, homomorphism indistinguishability can be decided in randomised polynomial time.

We show that feasibility of the t^th level of the Lasserre semidefinite programming hierarchy for graph isomorphism can be expressed as a homomorphism indistinguishability relation. In other words, we define a class ℒ_t of graphs such that graphs G and H are not distinguished by the t^th level of the Lasserre hierarchy if and only if they admit the same number of homomorphisms from any graph in ℒ_t. By analysing the treewidth of graphs in ℒ_t we prove that the 3t^th level of Sherali-Adams linear programming hierarchy is as strong as the t^th level of Lasserre. Moreover, we show that this is best possible in the sense that 3t cannot be lowered to 3t-1 for any t. The same result holds for the Lasserre hierarchy with non-negativity constraints, which we similarly characterise in terms of homomorphism indistinguishability over a family ℒ_t^+ of graphs. Additionally, we give characterisations of level-t Lasserre with non-negativity constraints in terms of logical equivalence and via a graph colouring algorithm akin to the Weisfeiler-Leman algorithm. This provides a polynomial time algorithm for determining if two given graphs are distinguished by the t^th level of the Lasserre hierarchy with non-negativity constraints.

Two simple undirected graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality yields an equivalence relation on the family of graphs which is provably weaker than isomorphism. In this paper, we study cospectrality in relation to another well-studied relaxation of isomorphism, namely k-dimensional Weisfeiler-Leman (k-WL) indistinguishability. Cospectrality with respect to standard graph matrices such as the adjacency or the Laplacian matrix yields a strictly finer equivalence relation than 2-WL indistinguishability. We show that individualising one vertex plus running 1-WL already subsumes cospectrality with respect to all such graph matrices. Building on this result, we resolve an open problem of Fürer (2010) about spectral invariants.
Looking beyond 2-WL, we devise a hierarchy of graph matrices generalising the adjacency matrix such that k-WL indistinguishability after a fixed number of iterations can be captured as a spectral condition on these matrices. Precisely, we provide a spectral characterisation of k-WL indistinguishability after d iterations, for k,d ∈ ℕ. Our results can be viewed as characterisations of homomorphism indistinguishability over certain graph classes in terms of matrix equations. The study of homomorphism indistinguishability is an emerging field, to which we contribute by extending the algebraic framework of Mančinska and Roberson (2020) and Grohe et al. (2022).