Weitere Informationen zum ausgewählten Vortrag

Classes of graphs characterizable by finitely many homomorhism counts

Jörg Flum

Dienstag, 24. Mai 2022 14:30Uhr

In 1967 Lovász showed that up to isomorphism every finite relational structure A is determined by the homomorphism counts hom(B,A), i.e, by the number of homomorphisms from B to A, where B ranges over all structures (of the same vocabulary as A). Moreover, it suffices that B ranges over the structures with at most as many elements as A.

In the talk, we deal with classes C of graphs characterizable by finitely many homomorphism counts, i.e., classes for which there are finitely many graphs F_1,...,F_k such that for every graph G already hom(F_1,G),...,hom(F_k,G) determines whether G is in C. Among others, we show which prefix classes of first-order logic have the property that each class of graphs definable by a sentence of this prefix class is characterizable by finitely many homomorphism counts.