Intersection Representation of Complete Unbalanced Bipartite Graphs

Ap-intersectionrepresentation of a graphGis 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)∩f(v)|⩾p. The symbolθp(G) denotes this minimumtsuch that ap-intersection representation ofGexists. In 1966 Erdős, Goodman, and Pósa showed that for all graphsGon 2nvertices,θ1(G)⩽θ1(Kn, n)=n2. In 1992, Chung and West conjectured that for all graphsGon 2nvertices,θp(G)⩽θp(Kn, n) whenp⩾1. Subsequently, upper and lower bounds forθp(Kn, n) have been found to be (n2/p)(1+o(1)). We show in this paper that many complete unbalanced bipartite graphs on 2nvertices have a largerp-intersection number thanKn, n. For example, whenp=2,θ2(Kn, n)⩽12n2(1+o(1))<4172n2(1+o(1))⩽θ2(K(5/6) n, (7/6) n).