On set intersection representations of graphs

Stasys Jukna

Abstract.

An L-intersection representation of a graph G=(V,E) is an assignment f:V-->2^T of subsets f(x) of labels to its vertices such that two vertices x and y are adjacent iff the number |f(x)\cap f(y)| of common labels belongs to L. The minimum number |T| of labels used in such a representation is the intersection dimension of G with respect to the type L. Any explicit bipartite graph G of intersection dimension at least n^c for some constant c>0 with respect to all types L would give us a boolean function outside the class ACC.

We exhibit explicit bipartite n\times n graphs whose intersection dimension is:

at least n^{1/|L|} with respect to any type L

at least n^{1/2} with respect to any type of the form L={k,k+1,...}

at least n^{1/|R|} with respect to any type of the form L={k:k(mod p)\in R}, where p is a prime number.

We also prove that for any intersection representation f:V-->2^T of a Hadamard graph H, the sum \sum_{x\in V}|f(x)| must be at least n\log n/\log\log n. This is almost optimal, because some Hadamard graphs (namely, Sylvester graphs) can be represented with this sum being at most n\log n.

Finally, we formulate several problems about intersection dimensions of graphs related to some open problems in the complexity of boolean functions.