1
$\begingroup$

This is a follow-up to this question.

For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$. If $G=(V,E)$ is a simple undirected graph, and $v\in V$, we set $N(v) = \{w\in V:\{v,w\}\in E\}$.

Let $\kappa$ be an infinite cardinal and suppose $c: [\kappa]^2 \to \kappa$ is an arbitrary function.

Is there $E \subseteq [\kappa]^2$ such that the graph $(\kappa, E)$ has the following property?

For all $\{a,b\}\in [\kappa]^2$ we have $c(\{a,b\}) = |N(a)\cap N(b)|$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Assume we have 2 distinct elements $W,X$ such that $c(\{W,X\})=2$, $c(\{U,V\})\le 1$ for all other pairs. Let $P,Q$ be the elements in $N(W)\cap N(X)$. So $WPZQ$ forms a square (with 4 distinct vertices, but possibly extra edges, i.e. possibly not a full subgraph). In particular, $W,X$ are distinct elements in $N(P)\cap N(Q)$, hence $c(\{P,Q))\ge 2$. This forces $\{P,Q\}=\{W,X\}$, contradiction. So such a function $c$ cannot be realized. $\endgroup$
    – YCor
    Commented Apr 11, 2016 at 14:01
  • $\begingroup$ Thanks for your comment - could you post it as an answer so we can close this thread? $\endgroup$
    – Dominic van der Zypen
    Commented Apr 12, 2016 at 6:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .