Set intersection representations for almost all graphs

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if θ k ( G ) is defined to be the minimum number of labels with which G may be represented using the rule that two vertices are adjacent if and only if they share at least k labels, there exist positive constants c k and c′ k such that almost every graph G on n vertices satisfies $${{c_k n^2}\over{\log^2 n}} \leq \theta_k(G) \leq {{{c\prime }_k n^2}\over{\log^2 n}}$$ Changing the representation only slightly by defining θ; odd ( G ) to be the minimum number of labels with which G can be represented using the rule that two vertices are adjacent if and only if they share an odd number of labels results in quite different behavior. Namely, almost every graph G satisfies $$n-\sqrt{2n}-\lceil\log n\rceil < \theta_{\rm odd}(G) \leq n -1 $$ Furthermore, the upper bound on θ odd ( G ) holds for every graph. © 1996 John Wiley & Sons, Inc.