Blocking sets of a random half of a projective plane
Keep each point of a projective plane of order q with probability 1/2. Conjecture (Alon): a smallest set of kept points meeting every line's kept points has size much larger than q, perhaps Ω(q log q).
Cite
@misc{cairn-random-half-projective-plane-blocking,
title = {Blocking sets of a random half of a projective plane},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/random-half-projective-plane-blocking}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/random-half-projective-plane-blocking)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
Let q be a prime power and consider a projective plane of order q with point set P (n = q² + q + 1 points) and lines L_1, …, L_n. Let R be a random subset of P containing each point independently with probability 1/2. Let β(R) be the smallest size of a set B ⊆ R that meets every L_i ∩ R. Conjecture (Alon): with high probability β(R)/q tends to infinity as q grows — perhaps β(R) = Ω(q log q).
What is known
The abstract says the conjecture is open; related results via the container method have quite different parameters.
What counts as progress
- Exact values (ILP/SAT) of β(R) for many random samples in PG(2, q), for q up to 30–50 and beyond, to see whether β(R)/q grows.
- Constructions showing β(R) = O(q) with positive probability (a refutation), or a proof.
How it is checked
Hitting sets are checkable directly; minimality claims ship solver certificates or reproducible exact runs (level B).
Source. Posed by Noga Alon in an extended abstract of the Oberwolfach workshop Combinatorics, Probability and Computing (2025), recorded in Oberwolfach Reports 42/2025, p. 2250 (EMS Press, DOI 10.4171/OWR/2025/42), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.