Coloring some finite sets in \(\mathbb R^n\) (Q2866446)

The paper investigates the chromatic number of the following graph \(G_n\): the vertices are all triplets on some \(n\) points, and two triplets are connected with an edge if they intersect in exactly one point. Zsigmond Nagy determined the independence number of this graph. \textit{D. G. Larman} and \textit{C. A. Rogers} [Mathematika 19, 1--24 (1972; Zbl 0246.05020)] showed that \(\chi(G_n)\geq (1+o(1)) \frac{n^2}{6}\) from the inequality \(\chi(G_n)\geq |V(G_n)|/\alpha(G_n)\), and embedded the graph \(G_n\) into \(\mathbb R^{n-1}\) to obtain the first non-linear lower bound for the chromatic number of \(\chi(\mathbb R^n)\). This paper shows that \(\chi(G_n)= (1+o(1)) \frac{n^2}{6}\), and furthermore computes \(\chi(G_n)\) exactly for \(n=2^k\) and \(n=2^k-1\).