Let $G=(V,E)$ be a simple, undirected graph, finite or infinite, with $V \neq \emptyset$. Is the following statement true?



> 
> There is a cardinal $\kappa \leq |V|$ and an injective map $\psi : V \to {\cal P}(V)$ such that for $v\neq w\in V$ we have: $$\{v,w\} \in E \; \text{ if and only if }\; \big|\big(\psi(v) \setminus \psi(w)\big)\cup\big(\psi(w)\setminus \psi(v)\big)\big| < \kappa.$$
> 
> 
> 



Representing graphs by sets of small symmetric difference
Statement fails for $G = K\_{2, 3}$. Proof is either with computer search, or by case analysis (an attempt follows).


Let the parts of $G$ be $v\_0, v\_1$ and $u\_0, u\_1, u\_2$ respectively. Consider $\Delta = |\psi(u\_0) \triangle \psi(u\_1)| + |\psi(u\_0) \triangle \psi(u\_2)| + |\psi(u\_1) \triangle \psi(u\_2)|$. On one hand, $\Delta \geq 3|\kappa|$, and on the other hand, considering contribution of each bit (element of the underlying set of the image of $\psi$), $\Delta \leq 2 \cdot 5$. This implies $|\kappa| \leq 3$.


$|\kappa| = 1$ is trivially impossible. $|\kappa| = 2$, together with injectiveness of $\psi$, implies (WLOG) $\psi(v\_0) = \varnothing$, $\psi(u\_i) = \{i\}$. The only $\psi(v\_1)$ at distance at most $1$ from all $\psi(u\_i)$ is $\varnothing$, which clearly fails.


If $|\kappa| = 3$, then pairwise distances between $u\_i$ are (in some order) $3, 3, 4$. WLOG $\psi(u\_0) = \varnothing$, $\psi(u\_1) = \{0, 1, 2\}$, $\psi(u\_2) = \{0, 3, 4\}$. $\psi(v\_i)$ must be at distance at most $2$ from each of them. The only suitable set is $\{0\}$, thus choosing $\psi(v\_i)$ is impossible.


