6 papers
Topological and Geometric Perspectives on Homomorphism Indistinguishability
Josse van Dobben de Bruyn, Jérémie Marquès, David E. Roberson +3
Two graphs and are homomorphism indistinguishable over a graph class if, for every graph , the number of homomorphisms from to is e…
Unification of Quantum Graph Properties
Gian Luca Spitzer
Many properties of classical graphs are defined in terms of subsets of the vertex set. Examples include connected components, which are subsets such that $X \tim…
Quantum Graph Theory by Example
Gian Luca Spitzer, Ion Nechita
Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of s…
Homomorphism Indistinguishability Relations induced by Quantum Groups
Tim Seppelt, Gian Luca Spitzer
Homomorphism indistinguishability is a way of characterising many natural equivalence relations on graphs. Two graphs and are called homomorphism indistinguishable over a g…
Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
Isolde Adler, Eva Fluck, Tim Seppelt +1
We study the expressive power of first-order logic with counting quantifiers, especially the -variable and quantifier-rank- fragment, using homomorphism indistinguishability.…
Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth
Eva Fluck, Tim Seppelt, Gian Luca Spitzer
We study the expressive power of first-order logic with counting quantifiers, especially the -variable and quantifier-rank- fragment , using homomorphism indi…