A counterexample to the very sparse greedy conjecture for random hitting sets

Let $A$ be a random $m\times n$ zero-one matrix with independent Bernoulli$(p)$ entries, whose rows are to be hit by a set of columns. Arpino, Dmitriev and Grometto proved that with high probability the linear programming (LP) relaxation, the fractional hitting set, is within a constant factor of the optimum when $mp\lesssim\log n$, and the greedy algorithm is within a constant factor of the optimum when $p\ge n^{-\delta}$ with $\delta<1/2$. They conjectured that in the very sparse regime $mp\to0$ the ratio of the greedy value to the LP value tends to one. We show that this fails. For $m=k$, $n=k^{10}$ and $p=1/(10k^4)$, with the explicit constant $c=1/(196608\cdot10^9)$, the greedy algorithm that breaks ties by the leftmost column, as in their analysis, uses at least $(1+c/8)$ times the LP value with probability at least $c/4$ for every $k\ge10^{20}$; these parameters satisfy their Assumption 2. The same holds with probability at least $c/8$ when ties are broken uniformly at random. So the ratio does not converge to one in probability. The obstruction is a path of three triples whose middle triple greedy takes first; exchanging it for its two ends saves half a column per path. The proofs are elementary counting arguments, checked in Lean from the definitions. This work has not yet been reviewed by experts. The proofs, the Lean formalization and the text were produced by AI models (from OpenAI and Anthropic), working under the author's direction. Computer-assisted; not yet reviewed by experts. Produced by AI models under the author's direction.