Реферат: 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.

Библиографическая ссылка: 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 . DOI: 10.1016/j.disc.2024.114138 WOS Scopus РИНЦ OpenAlex

Даты:

Поступила в редакцию:	9 нояб. 2023 г.
Принята к публикации:	5 июн. 2024 г.
Опубликована в печати:	19 июн. 2024 г.
Опубликована online:	19 июн. 2024 г.

Идентификаторы БД:

Web of science:	WOS:001346768700001
Scopus:	2-s2.0-85196271965
РИНЦ:	68731998
OpenAlex:	W4399835825

Цитирование в БД: Пока нет цитирований

Альметрики: