Generalized correlation-immunity bound for perfect 2-colorings of Hamming graphs

Let H(n,q)H(n,q) be the Hamming graph, and let a (b,c)(b,c)-coloring have color parameters b,cb,c. Define

b=bgcd(b,c),c=cgcd(b,c).b'=\frac{b}{\gcd(b,c)},\qquad c'=\frac{c}{\gcd(b,c)}.

Generalized correlation-immunity bound. If there exists a (b,c)(b,c)-coloring in H(n,q)H(n,q) with b+c>qb'+c'>q, then

nq+1q2(b+c).n\geq\frac{q+1}{q^2}(b+c).

For q=2q=2, the corresponding bound is known from correlation immunity; extending it to q>2q>2 is presented as an open research problem, and the conjecture begins with q=3q=3.

Sources & referencesView supporting material

Primary source

Evgeny A. Bespalov, Denis S. Krotov, Aleksandr A. Matiushev, Anna A. Taranenko and Konstantin V. Vorob'ev, “Perfect 2-colorings of Hamming graphs”, arXiv:1911.13151 (2021).

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.