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.$$
Best Answer
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.