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 2 + (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 G with 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 θ 2 (T) ≤ O(d√n) for any tree T with maximum‐degree d and θ 2 (T) ≤ O(n 3/4 ) for any tree on n vertices. We conjecture that our results can be further improved and that θ 2 (T) ≤ O(d√n) as long as Δ (T) ≤ √ n . If this conjecture is true, our method gives θ 2 (T) ≤ O(n 3/4 ) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.