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

  • 3
    $\begingroup$ Doesn‘t the condition imply the graph is transitive? $\endgroup$
    – Farmer S
    Commented Aug 7, 2021 at 20:21
  • 2
    $\begingroup$ Sorry, if $\kappa$ is infinite, that is. $\endgroup$
    – Farmer S
    Commented Aug 7, 2021 at 20:29
  • $\begingroup$ 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 $\endgroup$ Commented Aug 8, 2021 at 14:17
  • 1
    $\begingroup$ 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$.) $\endgroup$
    – Farmer S
    Commented Aug 9, 2021 at 12:03

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.