ON P-INTERSECTION REPRESENTATIONS

For a graph G = (V, E) and integer p, a p-intersection representation is a family F = {S-x: x is an element of V} of subsets of a set S with the property that \S-u boolean AND S-v\ greater than or equal to p do uble left right arrow {u, v} is an element of E. It is conjectured in [1] that theta(p)(G) less than or equal to theta(K-n/2,K- 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], theta(K-n/2,K- n/2) greater than or equal to (n(2 ) + (2p - 1)n)/4p is proved for any n and p. Here, we show that this i s asymptotically best possible. Further, we provide a bound on theta(p )(G) for all graphs with bounded degree, in particular, we prove theta (p)(G) less than or equal to O(n(1/p)) for any graph G with the maximu m degree bounded by a constant. Finally, we also investigate the value of theta(p) for trees. Improving on an earlier result of M. Jacobson, A. Kezdy, and D. West, (The 2-intersection number of paths and bounde d-degree trees, preprint), we show that theta(2)(T) less than or equal to O(d root n) for any tree T with maximum degree d and theta(2)(T) l ess than or equal to O(n(3/4)) for any tree on n vertices. We conjectu re that our result can be further improved and that theta(2)(T) less t han or equal to O(root n) as long as Delta(T) less than or equal to ro ot n. If this conjecture is true, our method gives theta(2)(T) less th an or equal to O(n(2/3)) for any tree T which would be the best possib le. (C) 1996 John Wiley & Sons, Inc.