Erdős’s balanced-line problem for two-colored projective planes
Let be a projective plane of odd order , with point set and line set . For a two-coloring , call a line balanced if it contains red points and blue points. Determine the maximum possible number of balanced lines over all such colorings, in an arbitrary projective plane of order .
Equivalent formulations
Equivalently, determine the minimum possible number of unbalanced lines, where an unbalanced line is a line containing unequal numbers of red and blue points.
source: Blokhuis, Markó, Szőnyi, and Weiner, Two-coloring the points of a projective plane
References
- Two-coloring the points of a projective plane — arXiv — Aart Blokhuis, Ádám Markó, Tamás Szőnyi, Zsuzsa Weiner
Source: arXiv
Progress summary
A new paper gives strong bounds for a restricted family of colorings, but does not settle the general question.
Erdős asked in the 1980s how many lines can contain equal numbers of red and blue points in a two-colored projective plane of odd order . The central general problem remains the extremal question for arbitrary projective planes.
Known results
- In a Galois plane , the maximum number of balanced lines is , equivalently there are at least unbalanced lines; equality is attained by a pencil coloring.
- In the balanced case, , every nontrivial coloring has at least unbalanced lines.
October 2026 structural bounds
Aart Blokhuis, Ádám Markó, Tamás Szőnyi, and Zsuzsa Weiner report near-extremal classifications for prime-order planes: for , they classify colorings with at most unbalanced lines, and prove a stability theorem under a related bound. These results advance the Galois-plane case but do not resolve arbitrary projective planes; the claims are unverified.
Current status (as of November 2026): The Galois-plane extremal bounds and new prime-order near-extremal classifications are reported, while the general Erdős problem remains open.
Sources
Solutions 0
No solutions have been posted yet.