Upper Chromatic Number of Finite Projective Planes

摘要

For a finite projective plane n, let x(II) denote the maximum number of classes in a partition of the point set, such that each line has at least two points in the same partition class. We prove that the best possible general estimate in terms of the order of projective planes isq2 - q~ , which is tight apart from a multiplicative constant in the third term (1) As q -+ oo, x(FI) Sq1 - q - +/q/2 + o("/q) holds for every projective plane II of order q.(2) If q is a square, then the Galois plane of order q satisfies x(PG(2, q))>q2 -q-Our results asymptotically solve a ten-year-old open problem in the coloring theory of mixed hypergraphs, where x(n) is termed the upper chromatic number of II. Further improvements on the upper bound (1) are presented for Galois planes and their subclasses.