Erdős Problem #1159
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Attempts
submit one →Read our full write-up →
Erdős asked whether every finite projective plane has a blocking set meeting every line in at most C points, for one constant C. The floor is 4 for every order ≥ 5 and is met at q = 5, 7, 8, 9, 11 and all 3^r. The q = 11 optimum — returned by two solvers here and by Illés–Pisinger's 1997 annealing, whose posted set is the same configuration — is Klein's (21₄) configuration: the 21 involution centres of a PSL(2,7) inside PGL(3,11), all coordinate permutations of (1,0,0), (1,±1,0), (1,±1,±6). At q = 13 no blocking set with at most four points per line is invariant under any of the symmetric reductions we tried, plain SAT finds none, and the 1997 annealing stopped at 5; a cube campaign for an UNSAT certificate is running and reported on this page when it lands. Illés–Pisinger's posted 24-point set (and our own 34-point one) gives c(PG(2,13)) ≤ 5.
PARTIAL