The sharp lower-bound conjecture for multicolor Hamming graphs

From papers

Let H(n,q)H(n,q) denote the qq-ary Hamming graph, and let b(H(n,q))b(H(n,q)) denote its bipartite independence-related parameter as defined in the paper. Fix an integer q3q\geq 3. Sharp-bound conjecture. For sufficiently large nn,

b(H(n,q))=(11q)n+q+12.b(H(n,q))=\left\lfloor\left(1-\tfrac1q\right)n+\tfrac{q+1}2\right\rfloor.

The surrounding discussion says that the author could not extend Alon's argument to H(n,q)H(n,q) for q3q\geq 3, suggesting that the lower bound in the main theorem may be improvable. Thus the proposed equality is not established in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Norihide Tokushige, “Alon's transmitting problem and multicolor Beck–Spencer Lemma”, arXiv:2406.19945 (2025).

Solutions 0

No solutions have been posted yet.