← All problems

Erdős’s balanced-line problem for two-colored projective planes

Let Π\Pi be a projective plane of odd order nn, with point set PP and line set L\mathcal{L}. For a two-coloring c:P→{red,blue}c:P\to\{\mathrm{red},\mathrm{blue}\}, call a line ℓ∈L\ell\in\mathcal{L} balanced if it contains (n+1)/2(n+1)/2 red points and (n+1)/2(n+1)/2 blue points. Determine the maximum possible number of balanced lines over all such colorings, in an arbitrary projective plane of order nn.

Equivalent formulations
  1. 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

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 qq. The central general problem remains the extremal question for arbitrary projective planes.

Known results

  • In a Galois plane PG(2,q)\mathrm{PG}(2,q), the maximum number of balanced lines is q2q^2, equivalently there are at least q+1q+1 unbalanced lines; equality is attained by a pencil coloring.
  • In the balanced case, q>3q>3, every nontrivial coloring has at least 2q+12q+1 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 p≥19p\geq 19, they classify colorings with at most max⁡{3p+1,4p−22}\max\{3p+1,4p-22\} 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.