Generalized face-uniformity bound for two-valued functions on Hamming graphs

Let f:{0,,q1}n{0,1}f: \{0,\ldots,q-1\}^n \rightarrow \{0,1\} be a function with BB zeros and CC ones, where q3q\geq 3. Suppose that for some kk, every kk-face has the same number

CqkB+C\frac{Cq^k}{B+C}

of ones of ff. Generalized face-uniformity bound. If

B+Cgcd(B,C)>q,\frac{B+C}{\gcd(B,C)}>q,

then

knq+1+1.k\geq\frac{n}{q+1}+1.

This is proposed as a more general form of the perfect-coloring bound, applying to any two-valued function; the case q=2q=2 is identified with the known correlation-immunity bound, while the cases q>2q>2 remain open.

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.