# Representing graphs by sets of small symmetric difference

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

• Doesn‘t the condition imply the graph is transitive? Commented Aug 7, 2021 at 20:21
• Sorry, if $\kappa$ is infinite, that is. Commented Aug 7, 2021 at 20:29
• Good point @FarmerS - thanks for noticing! - I would be delighted in a counterexample for any graph where no $\kappa$, finite or infinite, with the property stated in the question exists Commented Aug 8, 2021 at 14:17
• For infinite graphs, the statement is equivalent to transitivity. (If $G$ is infinite and transitive, and $x\in V$, let $C_x$ be the transitively connected component $\{y\in V\bigm|xEy\}$, and for such a component $C$, let $A_C$ be a subset of $V$ of size $\mathrm{card}(V)$, with the $A_C$'s pairwise disjoint. Then define $\psi(x)=A_{C_x}\backslash\{x\}$, and note this works, using $\kappa=\mathrm{card}(V)$, or using $\kappa=3$, since for $x\neq y$, we have $xEy$ iff $C_x=C_y$ iff $A_{C_x}=A_{C_y}$ iff $\psi(x)\Delta\psi(y)=\{x,y\}$ iff $\psi(x)\Delta\psi(y)$ has card $<\kappa$.) Commented Aug 9, 2021 at 12:03

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.