We call a set system $\mathcal{A}$ of subsets of the $n$ element universe $U$ a separating system if for any pair of elements $x,y \in U$ there is at least one set $A \in \mathcal{A}$ such that either ($x\in A$ and $y \notin A$) or ($x \notin A$ and $y \in A$). We call a set system completely separating if for any $x,y\in U$ both conditions hold.
For the sake of generalization first let us reformulate this definition. Instead of the sets consider their characteristic vectors instead. Their length is $|U|$ and they consists of zeros and ones. Now the separating system property is translated as follows: For any pair of coordinates there is at least one vector such that one coordinate is zero and the other is one. The complete separating system requires for any pair of coordinates at least one vector such that the first coordinate is zero and the second one, and at least one other vector the other way.
A classical question is the minimal size of a separating system on an $n$ element universe. I am interested in the literature of the following generalization of the classical question:
Consider vectors with coordinates $\{1,\ldots,k\}$ and a graph $G$ with vertex set $\{1,\ldots,k\}$. We would like the vectors to be a separating system with respect to coordinates $(i,j)$ if this is an edge of $G$. By being a separating system with respect to $(i,j)$ I mean that for any pair of coordinates there is at least one vector such that the first coordinate is $i$ and the second $j$ or vice versa. How many vectors do we need to satisfy all these requirements?
I am particularly interested in a small special case where $k=3$, and where one of the edges mean a completely separating system. But i doesn't seem to be fortunate enough to find any results of this type.
My question is: Are there any results of this type?
