On p-intersection representations

For a graph G = (V,E) and integer p, a p-intersection representation is a family F = {S_x: × E V} of subsets of a set S with the property that |S_u ∩ S_ν| ≥ p ∩ {u, ν} E E. It is conjectured in 1] that θ_p(G) ≤ θ (K_n/2,n/2) (1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by 4]. In 1], θ (K_n/2,n/2) ≥ (n² + (2p− 1n)n)/4p is proved for any n and p. Here, we show that this is asymptotically best possible. Further, we provide a bound on θp(G) for all graphs with bounded degree. In particular, we prove θp(G) ≤ O(n^1/p) for any graph Gwith the maximum degree bounded by a constant. Finally, we also investigate the value of θ_p for trees. Improving on an earlier result of M. Jacobson, A. Kézdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), we show that θ₂(T) ≤ O(d√n) for any tree T with maximum-degree d and θ₂(T) ≤ O(n^3/4) for any tree on n vertices. We conjecture that our results can be further improved and that θ₂(T) ≤ O(d√n) as long as Δ(T) ≤ √n. If this conjecture is true, our method gives θ₂(T) ≤ O(n^3/4) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.