Alon's transmitting problem for the Hamming graph H(n, 3): Tokushige's Problem 12 at k=1,2, and the burning number of H(6, 3)

Problem 12 of arXiv:2406.19945 has an affirmative answer at k = 1 (n = 4, q = 3): for every u₁,u₂,u₃,u₄ in 0,1,2⁴ there is a vertex w of H(4,3) with g(uᵢ,w) < i for i = 1,2,3,4 – stated both in the source's rational form (probₒneᵣational) and in the denominator-cleared integer form (probₒne)

Problem 12 of arXiv:2406.19945 has an affirmative answer at k = 2 (n = 7, q = 3), proved by counting rather than by search: the four live constraint sets at the zero vertex have sizes |A₁| = 630 and |A₂ᶜ| = 507, |A₃ᶜ| = 45, |A₄ᶜ| = 3, and 630 > 507+45+3 = 555, so at least 75 vertices w work for every u₁,...,u₇

b(H(4,3)) = 4 and b(H(7,3)) = 6, kernel-bound, as corollaries of HB1/HB2 and the source's derivation; with the matching refutations that H(4,3) has no burning sequence of length 3 and H(7,3) none of length 5

b(H(3k+1,3)) <= 2k+2 for EVERY k, formalized: the three constant words 0-bar, 1-bar, 2-bar are the first three terms of a burning sequence of length 2k+2, by a pigeonhole on the letter counts (k-1)+k+(k+1) < 3k+1

The source's derivation, formalized for EVERY k: an affirmative answer to Problem 12 at k rules out every burning sequence of length 2k+1 and hence gives b(H(3k+1,3)) = 2k+2 exactly; the step it rests on, sum over the three diagonal shifts t of d(u, w + t*1) = 2n, is proved for every n

Negative controls: (i) no vertex w has 3g(a,w) < 2 at n = 4 or n = 7, so the i = 1 threshold cannot be tightened; (ii) 45 of 81 vertices at n = 4 and 1557 of 2187 at n = 7 fail the i = 1 constraint, so the existential is not vacuous; (iii) the bands must widen with i – for u₁ = 0000, u₂ = 0011, u₃ = 0022 no w satisfies the i = 1 band three times

MEASUREMENT: the counting proof of HB2 has an exact reach. The plain union bound |D₁| > sumᵢ |Dᵢᶜ| holds only for k <= 2 (36 > 3; 630 > 555; fails at k = 3 by 12600 < 28047). Sharpening it by taking, for each i, the worst shift rather than the whole complement – legitimate because the count depends only on the sorted colour-profile of the shift – settles k = 1,2,3,4,5 with slacks 33, 429, 5793, 68697, 374163 and FAILS at k = 6 (139675536 < 156258609) and at every k = 6..11 computed. So k = 6 (n = 19) is where this argument stops, and the obstruction is mathematical, not computational.

b(H(n,3)) <= floor(2n/3) + 2 for EVERY n (not only n = 3k+1), kernel-clean: the three constant words are the first three terms of a burning sequence of that length, by a pigeonhole on the letter counts

b(H(6,3)) = 6, kernel-bound by a two-ball bound: however Gamma₄(v₁) and Gamma₃(v₂) are placed they leave at least 118 of the 729 vertices uncovered (minimum at v₂-v₁ = 111111), while the remaining three balls of a length-5 burning sequence hold only 73+13+1 = 87; with HB8 this pins the value

PROSE: the same two-ball bound settles b(H(14,3)) = 11 and b(H(22,3)) = 16, the two further cells the ball-volume bound misses within n <= 22; n = 22 is 3k+1 at k = 7, i.e. the first case for which Tokushige's Problem 12 was actually needed. Slacks 95609 and 530378004; the bound still fails at n = 9,12,15,17,18,20,21

PROSE: b(H(9,3)) = 8 by a three-ball bound. With v₁ = 0 by vertex-transitivity, the 2816 of 19683 vertices v₂ whose two-ball residue is at most 1018 + |Gamma₄| = 3869 were swept against all v₃: min |V minus (Gamma₆(0) u Gamma₅(v₂) u Gamma₄(v₃))| = 1260 > 1018 = |Gamma₃|+|Gamma₂|+|Gamma₁|+|Gamma₀|, so no length-7 burning sequence exists

The ball-volume bound as one reusable kernel-clean lemma (notᵢsBurningₒf_ballSum: for every n and b, if sum_(j<b) |Gamma_(b-1-j)| < 3ⁿ there is no burning sequence of length b), and the values it pins kernel-bound: b(H(5,3)) = 5, b(H(8,3)) = 7, b(H(10,3)) = 8, b(H(11,3)) = 9; plus the control that the same sum fails at n = 6 (793 >= 729)

PROSE: the three-ball bound in closed form. Fixing u = 0, the stabiliser of 0 in Aut(H(n,3)) reduces a pair (v,w) to how many coordinates fall in each of five agreement classes, and a DP over the C(n+4,4) type vectors gives the exact minimum residue. It reproves b(H(9,3)) = 8 and settles, beyond the two-ball bound, b(H(17,3)) = 13 (residue 14702688 > tail 14597433). Every n <= 22 now has a value except n = 12, 15, 18, 20, 21, and the source's conjectured floor(2n/3)+2 is confirmed at every settled n. The extremal configuration is always the three constant words.

The colour-band reformulation of Problem 12, kernel-clean for every n and every i: G(u,w) < 3i (i.e. the source's g(u,w) < i) holds exactly when every letter count of w - u lies in the band [k+1-i, k+i], where n = 3k+1. Consequences proved with it: the condition is vacuous for i >= 2k+1, so a list of 3k+1 vertices constrains only its first 2k members; and the i = 1 band is the set of words whose letter counts are k+1,k,k in some order. The identity behind it, d(u, w+t*1) + #j: (w-u)ⱼ = -t = n, is proved for every n.