Recently I attacked this combinatorial question. The value of $m(n)$ introduced in it equals to a clique cover number of a generalized Kneser graph $KG_{n,4,1}=K(n,4,2)$ (or the chromatic number of its complement). I tried to find references with bounds for this number, but failed. On the other hand, the chromatic number of generalized Kneser graphs was investigated, see the references. For instance, if $n = (k-1)s+r$, $0\le r<k–1$ then Proposition 2.6 from [AJ] implies that $\chi(K(n,k,2))\le (k-1){s\choose 2}+rs$ and Frankl [F] showed that if $n >10k^3e^k$ then this bound is exact.

RobPratt calculated the values of $m(n)$ for $m\le 9$. Max Alekseyev showed that $m(n)\ge \frac{(n-2)(n-3)}2$. If $n$ is a power of an odd prime using a finite field of order $n$ we can show that $m(n)\le n^2$. This observation implies an upper bound $m(n)\le (n+n^{0.525})^2$ for sufficiently large $n$, becase for sufficiently large $x$ there is a prime belonging to $[x-x^{0.525}, x]$, see [BHP].

Thanks.

References

[AJ] Sharareh Alipour, Amir Jafari, On the chromatic number of generalized Kneser graphs, Contributions to discrete mathematics 12:2 69–76.

[BCK] József Balogh, Danila Cherkashin, Sergei Kiselev, Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs.

[BHP] R. Baker, G. Harman, J. Pintz, The difference between consecutive primes. II. Proc. Lond. Math. Soc., (3) Ser. 83 (2001) 532–562.

[F] Peter Frankl, On the chromatic number of the general Kneser-graph, Journal of Graph Theory, 9:2 (1985) 217–220.

[FF] Peter Frankl, Zoltán Füredi, Extremal problems concerning Kneser graphs, Journal of Combinatorial Theory, Series B, 40:3 (1986) 270–284.