2025/10/20 by Paul Hamrick, Hamrick, Paul, Gary Hu +1
Computer Science · Engineering · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2510.18064
openalex publication_date 2025/10/20 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
A family of graphs F is H-intersecting if the edge intersection of any two graphs in 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^\binomn2 - e(H) is known to be not sharp for some graphs, such as the P4 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_s1, …, sk-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 ≥ 2∑i si) and provides a stronger numerical bound for a large interval where both constructions are applicable. Second, we conjecture the (17)/(128) Christofides bound for P4 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.