Counting Graph Homomorphisms in Bipartite Settings

This paper studies the problem of counting homomorphisms from a bipartite source graph to a bipartite target graph.

An exact formula is first derived for the number of homomorphisms from a complete bipartite graph to a general bipartite graph.

Although exact, its evaluation is typically computationally intensive, and a computationally tractable combinatorial lower bound is derived.

When the target graph contains no 4-cycles, the lower bound simplifies and becomes exact.

Two additional lower bounds on the number of homomorphisms from a complete bipartite graph to an arbitrary bipartite graph are derived using properties of Shannon entropy.

The first depends only on the sizes of the partite sets in the source and target graphs, together with the edge density of the target graph.

The second further incorporates the degree profiles of the partite sets of the target graph, thereby strengthening the first bound.

Both entropy-based bounds improve upon the inequality implied by the validity of Sidorenko's conjecture for complete bipartite source graphs.

The lower bounds for complete bipartite source graphs are combined with new auxiliary results to derive general lower bounds on homomorphism counts between arbitrary bipartite graphs.

Furthermore, a known reverse Sidorenko inequality is employed to derive a corresponding upper bound.

This upper bound is attained when the source graph is a disjoint union of complete bipartite graphs, and admits a simple closed-form expression when the target graph contains no 4-cycles.

Numerical results compare the new computationally tractable bounds with exact homomorphism counts in cases where exact computation is feasible.