A family of graphs $\mathcal{ F}$ is $H$-intersecting if the edge intersection of any two graphs in $\mathcal{ F}$ contains a copy of a fixed graph $H$. A fundamental problem is to determine the maximum size of such a family. The trivial lower bound of $2^{ \binom{ n}{ 2} - e(H)}$ is known to be not sharp for some graphs, such as the $P_4$ graph, as shown by Christofides. This paper presents two main contributions. First, we introduce a general construction for $H$-intersecting families based on decompositions of complete multipartite graphs, yielding new lower bounds for $H = K_{ s_1, \dots, s_{ k-1}, t}$. We compare this construction to a result by Balogh and Linz, showing that our bound is valid for a substantially wider range of parameters (beginning at $t \ge 2^{ \sum_i s_i}$) and provides a stronger numerical bound for a large interval where both constructions are applicable. Second, we conjecture the $\frac{ 17}{ 128}$ Christofides bound for $P_4$ is optimal, which would resolve the Alon-Spencer conjecture. We computationally verify this density is optimal for families generated by connected 6-vertex host graphs with 7 or 8 edges.
Categories: math.CO