On degree-$3$ and $(n-4)$-correlation-immune perfect colorings of $n$-cubes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913428242694144 |
|---|---|
| author | Krotov, Denis S. Valyuzhenich, Alexandr A. |
| author_facet | Krotov, Denis S. Valyuzhenich, Alexandr A. |
| contents | A perfect $k$-coloring of the Boolean hypercube $Q_n$ 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 $Q_n$ 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 $Q_n$, 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$.
Keywords: perfect coloring, equitable partition, resilient function, correlation-immune function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_05566 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On degree-$3$ and $(n-4)$-correlation-immune perfect colorings of $n$-cubes Krotov, Denis S. Valyuzhenich, Alexandr A. Combinatorics Discrete Mathematics 05B99, 05B15, 94D10 A perfect $k$-coloring of the Boolean hypercube $Q_n$ 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 $Q_n$ 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 $Q_n$, 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$. Keywords: perfect coloring, equitable partition, resilient function, correlation-immune function. |
| title | On degree-$3$ and $(n-4)$-correlation-immune perfect colorings of $n$-cubes |
| topic | Combinatorics Discrete Mathematics 05B99, 05B15, 94D10 |
| url | https://arxiv.org/abs/2311.05566 |