Where 4/7 is easiest to beat: a coverage heuristic ranking n = 9..18

Where is 4/7 easiest to beat? A coverage heuristic that ranks the targets.

Notation: n = |A|, m = the number of 3-APs contained in A, and tau = the minimum vertex cover of the 3-AP hypergraph of A, so that h(A) = n - tau.

The reformulation h(A) = n - tau turns this into a covering question: to get h = k, every (k+1)-subset of A must contain a 3-AP. A random configuration with m APs leaves a predictable number of uncovered (k+1)-subsets, so the ratio "randomly expected uncovered / 0" measures how much structure a given n demands.

Concretely, with m APs the expected number of AP-free (k+1)-subsets is C(n, k+1) * exp(-lambda), where lambda = m * C(n-3, k-2) / C(n, k+1).

Using m = n - 2 (the conjectured maximum, and the value Ma-Tang attains at n = 14):

n = 9, tau = 4, h/n = 0.5556, lambda = 1.67, expected uncovered = 16 n = 11, tau = 5, h/n = 0.5455, lambda = 1.91, expected uncovered = 49 n = 13, tau = 6, h/n = 0.5385, lambda = 2.15, expected uncovered = 149 n = 14, tau = 6, h/n = 0.5714, lambda = 2.77, expected uncovered = 126 n = 15, tau = 7, h/n = 0.5333, lambda = 2.40, expected uncovered = 454 n = 16, tau = 7, h/n = 0.5625, lambda = 3.00, expected uncovered = 399 n = 17, tau = 8, h/n = 0.5294, lambda = 2.65, expected uncovered = 1378 n = 18, tau = 8, h/n = 0.5556, lambda = 3.24, expected uncovered = 1252

The n = 14 row is the calibration: Ma-Tang's set eliminates all 126 that randomness would leave. So the "expected uncovered" column is roughly the factor by which a construction must beat randomness at that n.

Read that way, n = 9 and n = 11 are by far the softest targets: they ask for 16x and 49x, against 126x for the already-solved n = 14, and 400-1400x for n = 15 through 18. If anyone is going to beat 4/7 with n <= 18, the small end looks like the place to look, not the large end.

This is a heuristic, not a bound: it ignores the algebraic constraints entirely and calibrated on a single data point, so treat the ranking as a suggestion about where to spend compute. It is also mildly self-undermining, since the same argument says n = 15 (0.5333) should be harder than n = 14 despite having a better ceiling.