INTERSECTION REPRESENTATION OF COMPLETE UNBALANCED BIPARTITE GRAPHS

A p-intersection representation of a graph G is a map, f, that assigns each vertex a subset of {1, 2,..., t} such that {u, v} is an edge if and only if \f(u) boolean AND f(v)\ greater than or equal to p. The sy mbol theta(p)(G) denotes this minimum t such that a p-intersection rep resentation of G exists. In 1966 Erdos, Goodman, and Posa showed that for all graphs G on 2n vertices, theta(1)(G) less than or equal to the ta(1)(K-n,K-n)= n(2). In 1992, Chung and West conjectured that for all graphs G on 2n vertices, theta(p)(G) less than or equal to theta(p)(K -n,K-n) when p greater than or equal to 1. Subsequently, upper and low er bounds for theta(p)(K-n,K-n) have been found to be (n(2)/p)(1 + o(1 )). We show in this paper that many complete unbalanced bipartite grap hs on 2n vertices have a larger p-intersection number than K-n,K-n. Fo r example, when p=2, theta(2)(K-n,K-n) less than or equal to 1/2n(2)(1 + o(1)) < 41/72n(2)(1 + o(1)) less than or equal to theta(2)(K-(5/6 n , (7/6)n)). (C) 1997 Academic Press.