Skip to main content
3 of 6
added 79 characters in body
Mike
  • 1k
  • 6
  • 14

Couldn't you write (almost) every $d$-regular simple graph this way? That is, for any regular graph where the length of the smallest cycle is at least 5 [which for any fixed $d$ and $n$ sufficiently large relative to $d$, is almost every $d$-regular graph on $n$ vertices]. Indeed, let $G$ be your favorite $d$-regular graph on $n$ vertices where the length of the smallest cycle in $G$ is at least 5.

Set $f_u$ to be the vector on $\mathbb{R}^{V(G)}$ s.t. $f_u(u) = 1$ and $f_u(v) = 0$ for each $v \in V(G) \setminus \{u\}$.

Set $g_u$ to be the vector on $\mathbb{R}^{V(G)}$ s.t. $g_u(u') = \frac{1}{\sqrt{d}}$ if either $u'=u$ or $u' \in N_G(u)$, and $g_u(v) = 0$ for each remaining $v$.

Then for every two vertices $u$ and $v$, note that $||f_u-f_v||_2^2$ is precisely 2. However, $||g_u-g_v||_2^2$ is no more than $\left(\frac{1}{d} \right) \times 2d = 2$ iff $u$ and $v$ are adjacent in $G$, and is at least $\frac{2d+1}{d}$ otherwise. [Precisely $\frac{2d+1}{d}$ iff nonadjacent $u$ and $v$ share a neighbour; $\frac{2d+2}{d}$ iff nonadjacent $u$ and $v$ do not share a neighbour.]

My point is that the family of graphs that you just specified is likely quite a big family.

Mike
  • 1k
  • 6
  • 14