





















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 into a general bipartite graph. While exact, this formula is typically computationally intensive to evaluate. To address this, computable combinatorial lower bounds are established. 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, along with the edge density of the target graph. The second further incorporates the degree profiles within the target's partite sets, yielding a strengthening of the first. Both entropy-based bounds improve upon the inequality implied by the validity of Sidorenko's conjecture for complete bipartite graphs. Lower bounds for complete bipartite sources are combined with new auxiliary results to derive general lower bounds on homomorphism counts between arbitrary bipartite graphs, while a known reverse Sidorenko inequality is employed to establish corresponding upper bounds. The upper bound is attained when the source is a disjoint union of complete bipartite graphs, and it admits a simple closed-form expression when the target contains no 4-cycles. Numerical results compare the proposed easy-to-compute bounds with exact counts in computationally tractable cases.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。