Algorithms and Complexity Seminar
The Homomorphism Domination Exponent
Swastik Kopparty (MIT)
For fixed graphs F and G, we study the relationship between the
number of homomorphisms from F to T and from G to T for an
arbitrary graph T. We define the homomorphism domination
exponent of F and G, denoted by hde(F,G), to be the largest
constant c such that |Hom(F,T)| \geq |Hom(G,T)|^c for all T.
The decidability of "hde(F,G) \geq 1" is an important open question
in database theory (known as the containment problem for
conjunctive queries with multiset semantics). We investigate the combinatorial and computational properties of the homomorphism domination exponent, proving upper and lower bounds and isolating classes of F and G where hde(F,G) can be computed exactly. In particular, we show that hde(F,G) is computable when F is chordal and G is series-parallel.
Our techniques are based on information theory and linear programming, and generalize the entropy variants of Shearer's lemma due to Radhakrishnan, Friedgut, Kahn and others.
Joint work with Ben Rossman (MIT).