Definition of Borsuk graph Can someone please clarify what exactly the infinite Borsuk graph is?
I am finding 2 different definitions on the internet, some sources say we join to elements of $\mathbb{S}^n$ iff the distance between them is at least $\alpha$ , whereas some other sources suggest the distance should be strictly greater than $\alpha$.
 A: Lovász's 1977 paper Kneser's conjecture, chromatic number, and homotopy attributes the definition of Borsuk's graph to Erdős and Hajnal in the 1967 paper Kromatikus gráfokról ("On chromatic graphs") where they write

Gráfunk szögpontjai a $k$-dimenziós egységgömb pontjai lesznek. Legyen $\varepsilon = \varepsilon(c)$ elegendő kis pozitív szám. Két pontot akkor kötünk össze éllel, ha távolságuk na­gyobb, mint $2-\epsilon$.

In Hungarian, "nagyobb, mint $2-\epsilon$" means "greater than $2-\epsilon$" and so the original definition did not join two points at distance exactly $2-\epsilon$.
Lovász himself, on the other hand, writes

Let the vertices of graph $B_k$ be the points of the $k$-sphere $S^k$, two of them being adjacent iff their distance is at least $2-\epsilon$ for some $\epsilon>0$ (i.e., iff they are almost antipodal).

So you can see that the confusion goes back over four decades and that very prestigious graph theorists disagreed on this point.
The reason that they disagreed is that their results about Borsuk's graph don't really depend on whether you say "at least $2-\epsilon$" or "greater than $2-\epsilon$". The graph defined with parameter $\epsilon$ by one definition is sandwiched between the graphs defined with parameters $2\epsilon$ and $\frac12\epsilon$ by the other definition. This means that theorems about one definition carry over to the other definition provided $\epsilon$ is small enough. Specifically, when $\epsilon$ is sufficiently small,

*

*$B_k$ has chromatic number $k+2$ no matter which definition we use;

*$B_k$ contains no short odd cycles no matter which definition we use ($\epsilon$ being chosen for the definition of "short" you want);

*$m$-vertex subgraphs of $B_k$ have independence number $\ge cm$ for $c<\frac12$ no matter which definition we use ($\epsilon$ being chosen for the $c$ you want);

*I don't know all the other interesting properties of Borsuk's graph, but I bet they also keep working no matter which definition we use.

So it never really mattered and that is why the definition is not standardized. I suppose that if you want an authoritative source, there is none more authoritative than Erdős and Hajnal.
