On set intersection representations of graphs
Stasys P. Jukna · Journal of Graph Theory · 2009
Abstract The intersection dimension of a bipartite graph with respect to a typeLis the smallest numbertfor which it is possible to assign setsAx⊆{1, …,t} of labels to verticesxso that any two verticesxandyfrom different parts are adjacent if and only if |Ax∩Ay|∈L. The weight of such a representation is the sum Σx|Ax| over all verticesx. We exhibit explicit bipartiten×ngraphs whose intersection dimension is (i) at leastn1/|L| with respect to any typeL, (ii) at least$\sqrt{n}$ with respect to any type of the formL={k, k+ 1, …}, and (iii) at leastn1/|R| with respect to any type of the formL={k|k modp∈R}, wherepis a prime number. We also show that any intersection representation of a Hadamard graph must have weight aboutn lnn/ln lnn, independent on the used typeL. Finally, we formulate several problems about intersection dimensions of graphs related to some basic open problems in the complexity of boolean functions. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 55‐75, 2009