On Set Intersection Representations of Graph

by Stasys Jukna

Abstract

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 $A_x\subseteq\{1,\ldots,t\}$ of labels to vertices $x$ so that any two vertices $x$ and $y$ from different parts are adjacent if and only if $|A_x\cap A_y|\in L$. The weight of such a representation is the sum $\sum_x|A_x|$ over all vertices~$x$. We exhibit explicit bipartite $n\times n$ graphs whose intersection dimension is: (i) at least $n^{1/|L|}$ with respect to any type $L$, (ii) at least $\sqrt{n}$ with respect to any type of the form $L=\{k,k+1,\ldots\}$, and (iii) at least $n^{1/|R|}$ with respect to any type of the form $L=\{k\colon k\bmod{p}\in R\}$, where $p$ is a prime number. We also show that any intersection representation of a Hadamard graph must have weight about $n\ln n/\ln\ln n$, independent on the used type~$L$. Finally, we formulate several problems about intersection dimensions of graphs related to some basic open problems in the complexity of boolean functions.