Abstract: Aperfect k-coloring of the Boolean hypercube Qn is a function from the set of binary words of length n onto a k-set of colors such that for any colors i and j every word of color i has exactly S(i, j) neighbors (at Hamming distance 1) of color j, where the coefficient S(i, j) depends only on i and j but not on the particular choice of the word. The k-by-k table of all coefficients S(i, j) is called the quotient matrix. We characterize perfect colorings of Qn of degree at most 3, that is, with quotient matrix whose all eigenvalues are not less than n −6, or, equivalently, such that every color corresponds to a Boolean function represented by a polynomial of degree at most 3 over R. Additionally, we characterize (n −4)-correlation-immune perfect colorings of Qn, whose all colors correspond to (n −4)correlation-immune Boolean functions, or, equivalently, all non-main (different from n) eigenvalues of the quotient matrix are not greater than 6 −n.

Cite: Krotov D.S. , Valyuzhenich A.A.
On degree-3 and (n − 4)-correlation-immune perfect colorings of n-cubes
Discrete Mathematics. 2024. V.347. N10. 114138 :1-14. DOI: 10.1016/j.disc.2024.114138 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Nov 9, 2023
Accepted:	Jun 5, 2024
Published print:	Jun 19, 2024
Published online:	Jun 19, 2024

Identifiers:

Web of science:	WOS:001346768700001
Scopus:	2-s2.0-85196271965
Elibrary:	68731998
OpenAlex:	W4399835825

Citing:

DB	Citing
Scopus	1
Web of science	1

Altmetrics: