UC Santa Cruz

The Lovász Theorem asserts that two arbitrary graphs G and H are isomorphic if and only if hom(F, G) = hom(F, H) for all graphs F, here hom(A, B) denotes the number of homomorphisms from A to B. This characterization of graph isomorphism in terms of graph homomorphism counts motivated a wealth of research that seeks to characterize different relaxations of isomorphism -- equivalence relations that are coarser than isomorphism -- in terms of the numbers of homomorphisms "from" certain graphs F. Symmetrically, the Chaudhuri-Vardi Theorem says that two arbitrary graphs G and H are isomorphic if and only if hom(G, F) = hom(H, F) for all graphs F. While this dual characterization prompts to characterize relaxations of isomorphism in terms of the numbers of homomorphisms "to" certain graphs F, it received little attention, and is investigated in depth in this dissertation. The notions of isomorphism and homomorphism as well as these theorems also apply to relational structures. A different view of these theorems is that they give rise to query algorithms for testing membership in a class (in the case here the isomorphism type of a fixed graph or relational structure) that answer "yes" or "no" by making a bounded number of homomorphism-count queries. A variant of such an algorithm makes homomorphism-existence queries (whose values are 0 or 1) instead. An analysis is conducted in this dissertation for various classes regarding certain variants of query algorithms.