On set intersection representation of graphs

The intersection dimension of a bipartite graph with respect to a type L is the smallest number t for which it is possible to assign sets Ax ⊆ {1,..., t} of labels to vertices x so that any two vertices x and y from different parts are adjacent if and only if |Ax ∩ Ay | ∈ L. The weight of such a representation is the sum x |Ax | over all vertices x. We exhibit explicit bipartite n × n graphs whose intersection dimension is: (i) at least n1/|L | with respect to any type L, (ii) at least n with respect to any type of the form L = {k, k+1,...}, and (iii) at least n1/|R | with respect to any type of the form L = {k: k mod p ∈ R}, where p is a prime number. We also show that any intersection representation of a Hadamard graph must have weight about n log n, independent on the used type L. Finally, we formulate several problems about intersection dimensions of graphs related to some open problems in the complexity of boolean functions