On the upper chromatic number and multiplte blocking sets of PG($n,q$)

Zoltán L. Blázsik, Tamás Héger, Tamás Szőnyi

Published 2019-09-06Version 1

We investigate the upper chromatic number of the hypergraph formed by the points and the $k$-dimensional subspaces of $\mathrm{PG}(n,q)$; that is, the most number of colors that can be used to color the points so that every $k$-subspace contains at least two points of the same color. Clearly, if one colors the points of a double blocking set with the same color, the rest of the points may get mutually distinct colors. This gives a trivial lower bound, and we prove that it is sharp in many cases. Due to this relation with double blocking sets, we also prove that for $t\leq \frac38p+1$, a small $t$-fold (weighted) $(n-k)$-blocking set of $\mathrm{PG}(n,p)$, $p$ prime, must contain the weighted sum of $t$ not necessarily distinct $(n-k)$-spaces.