On the chromatic number of certain highly symmetric graphs (Q1062067)

For \(1\leq k\leq n\) let G(n,k) be the graph whose vertices are the \(n(n- 1)...(n-k+1)\) sequences of k distinct elements from \(\{\) 1,2,...,n\(\}\), two such sequences being joined by an edge if they differ in exactly one place. Let N(n,k) denote the maximum number of classes in a partition of the vertices of G(n,k) such that for every class C, every vertex v and every i, \(1\leq i\leq k\), there is a w in C that differs from v in at most place i. This number N(n,k) and the chromatic number \(\chi\) (n,k) of G(n,k) are investigated. It is proved that \(N(n,k)\leq n-k+11\leq \chi (n,k)\) with equality for certain values of n and k. The problems discussed are related to questions in mathematical logic by \textit{L. Henkin}, \textit{J. D. Monk}, and \textit{A. Tarski}, and \textit{H. Andréka} and \textit{I. Németi} [Cylindric set algebras, Lect. Notes Math. 883 (1981; Zbl 0497.03025)].