Skip to main content
broken link fixed
Source Link
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

Apparently, Schrijver defined a function $\vartheta'$ in the paper A Comparison of the Delsart and Lovasz BoundsA Comparison of the Delsart and Lovasz Bounds which (I am pretty sure) is equivalent to vector chromatic number of the complement. Furthermore, he gives an example of a vertex transitive graph $X$ which has $\vartheta'(X) < \vartheta(X)$. The graph $X$ has the $01$-strings of length 6 as its vertices, and two such strings are adjacent if they are at Hamming distance at most 3. Taking complements obviously provides an example answering my question in the affirmative.

Considering the graph $Y = \overline{X}$, two strings are adjacent if they are at Hamming distance 4 or more. We can then replace 01-strings with $\pm 1$ vectors in the obvious way, and then normalize these vectors. Now, adjacency will correspond to two vectors having inner product less than or equal to $-1/3$. This then implies that $\chi_{vec}(Y) \le 4$, which happens to be the clique number of $Y$, and thus $\chi_{vec}(Y) = 4$ (this value is given in Schrijver's paper, but it is not discussed how he comes to this value). According to Schrijver, $\bar{\vartheta}(Y) = 16/3 > 4$. Obviously, the way $Y$ was defined gave rise to a "natural" vector coloring, and I would guess that other similarly defined graphs might be examples of graphs with vector chromatic number less than strict vector chromatic number.

Interestingly, Schrijver's paper was written in 1979, about 15 years before Karger, Motwani, and Sudan defined vector chromatic number.

Apparently, Schrijver defined a function $\vartheta'$ in the paper A Comparison of the Delsart and Lovasz Bounds which (I am pretty sure) is equivalent to vector chromatic number of the complement. Furthermore, he gives an example of a vertex transitive graph $X$ which has $\vartheta'(X) < \vartheta(X)$. The graph $X$ has the $01$-strings of length 6 as its vertices, and two such strings are adjacent if they are at Hamming distance at most 3. Taking complements obviously provides an example answering my question in the affirmative.

Considering the graph $Y = \overline{X}$, two strings are adjacent if they are at Hamming distance 4 or more. We can then replace 01-strings with $\pm 1$ vectors in the obvious way, and then normalize these vectors. Now, adjacency will correspond to two vectors having inner product less than or equal to $-1/3$. This then implies that $\chi_{vec}(Y) \le 4$, which happens to be the clique number of $Y$, and thus $\chi_{vec}(Y) = 4$ (this value is given in Schrijver's paper, but it is not discussed how he comes to this value). According to Schrijver, $\bar{\vartheta}(Y) = 16/3 > 4$. Obviously, the way $Y$ was defined gave rise to a "natural" vector coloring, and I would guess that other similarly defined graphs might be examples of graphs with vector chromatic number less than strict vector chromatic number.

Interestingly, Schrijver's paper was written in 1979, about 15 years before Karger, Motwani, and Sudan defined vector chromatic number.

Apparently, Schrijver defined a function $\vartheta'$ in the paper A Comparison of the Delsart and Lovasz Bounds which (I am pretty sure) is equivalent to vector chromatic number of the complement. Furthermore, he gives an example of a vertex transitive graph $X$ which has $\vartheta'(X) < \vartheta(X)$. The graph $X$ has the $01$-strings of length 6 as its vertices, and two such strings are adjacent if they are at Hamming distance at most 3. Taking complements obviously provides an example answering my question in the affirmative.

Considering the graph $Y = \overline{X}$, two strings are adjacent if they are at Hamming distance 4 or more. We can then replace 01-strings with $\pm 1$ vectors in the obvious way, and then normalize these vectors. Now, adjacency will correspond to two vectors having inner product less than or equal to $-1/3$. This then implies that $\chi_{vec}(Y) \le 4$, which happens to be the clique number of $Y$, and thus $\chi_{vec}(Y) = 4$ (this value is given in Schrijver's paper, but it is not discussed how he comes to this value). According to Schrijver, $\bar{\vartheta}(Y) = 16/3 > 4$. Obviously, the way $Y$ was defined gave rise to a "natural" vector coloring, and I would guess that other similarly defined graphs might be examples of graphs with vector chromatic number less than strict vector chromatic number.

Interestingly, Schrijver's paper was written in 1979, about 15 years before Karger, Motwani, and Sudan defined vector chromatic number.

Source Link
David Roberson
  • 2.3k
  • 15
  • 25

Apparently, Schrijver defined a function $\vartheta'$ in the paper A Comparison of the Delsart and Lovasz Bounds which (I am pretty sure) is equivalent to vector chromatic number of the complement. Furthermore, he gives an example of a vertex transitive graph $X$ which has $\vartheta'(X) < \vartheta(X)$. The graph $X$ has the $01$-strings of length 6 as its vertices, and two such strings are adjacent if they are at Hamming distance at most 3. Taking complements obviously provides an example answering my question in the affirmative.

Considering the graph $Y = \overline{X}$, two strings are adjacent if they are at Hamming distance 4 or more. We can then replace 01-strings with $\pm 1$ vectors in the obvious way, and then normalize these vectors. Now, adjacency will correspond to two vectors having inner product less than or equal to $-1/3$. This then implies that $\chi_{vec}(Y) \le 4$, which happens to be the clique number of $Y$, and thus $\chi_{vec}(Y) = 4$ (this value is given in Schrijver's paper, but it is not discussed how he comes to this value). According to Schrijver, $\bar{\vartheta}(Y) = 16/3 > 4$. Obviously, the way $Y$ was defined gave rise to a "natural" vector coloring, and I would guess that other similarly defined graphs might be examples of graphs with vector chromatic number less than strict vector chromatic number.

Interestingly, Schrijver's paper was written in 1979, about 15 years before Karger, Motwani, and Sudan defined vector chromatic number.