The sharp lower-bound conjecture for multicolor Hamming graphs

About 2 years old · traced to

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 q≥3q\geq 3. Sharp-bound conjecture. For sufficiently large nn,

b(H(n,q))=⌊(1−1q)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 q≥3q\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.