Two-coloring the points of a projective plane
Abstract
Let us color the points of a projective plane of odd order $n$ with two colors, say red and blue. Erd\H{o}s asked the question of determining the maximum number of balanced lines (that have the same number of red and blue points). The answer is $n^2$, and in the corresponding trivial coloring the unbalanced lines go through a point. In this paper, we consider the Galois plane $\mathrm{PG}(2,q)$ and determine the number of unbalanced lines for a non-trivial coloring. The problem can also be generalized to $(r,b)$-colored lines (see Definition 1.1) and in many cases we extend the results to the generalized problem. Our strongest result for Galois planes of prime order $p$ describes all 2-colorings with at most $\max\{3p+1,4p-22\}$ not $(r,b)$-colored lines (see Theorem 5.13). Finally, in case of the generalized problem, we allow even more not $(r,b)$-colored lines if $r$ is small and the order is prime (for more details, see Theorem 5.18).