


























This work derives an upper bound on the maximum cardinality of a family of graphs on a fixed number of vertices, in which the intersection of every two graphs in that family contains a subgraph that is isomorphic to a specified graph H. Such families are referred to as H-intersecting graph families. The bound is derived using the combinatorial version of Shearer's lemma, and it forms a nontrivial extension of the bound derived by Chung, Graham, Frankl, and Shearer (1986), where H is specialized to a triangle. The derived bound is expressed in terms of the chromatic number of H, while a relaxed version, formulated using the Lovász $\vartheta$-function of the complement of H, offers reduced computational complexity. Additionally, a probabilistic version of Shearer's lemma, combined with properties of the Shannon entropy, are employed to establish bounds related to the enumeration of graph homomorphisms, providing further insights into the interplay between combinatorial structures and information-theoretic principles.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。