3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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$
    – Dominic van der Zypen
    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

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .