zbMATH — the first resource for mathematics

On perfect colorings of Boolean \(n\)-cube and correlation immune functions with small density. (Russian. English summary) Zbl 1329.05117
Summary: A coloring of Boolean \(n\)-cube is called perfect if, for every vertex, the collection of colors of its neighbors depends only on its own color. Parameters of a perfect coloring are given by an array. A Boolean function is called correlation immune of degree \(n-m\) if it takes the value 1 equal number of times on any \(m\)-face of Boolean \(n\)-cube. It is proved that Boolean function \(\chi^s\) (\(S\subset E^n\)) is a perfect coloring if it satisfies the equality \(\rho(S)=1-\frac{n}{2(1+\operatorname{cor}(S))}\), where \(\operatorname{cor}(S)\) is the maximum degree of the correlation immune of \(\chi^S\) and \(\rho(S)=|S|/2^n\).
It is offered a straightforward concatenative construction for a perfect coloring of Boolean \(n\)-cube with array \(\begin{matrix} 0 & {k(2^s-1)} \\ k & {k(2^s-2)}\end{matrix}\). This construction provides a new lower bound on the number of such perfect colorings. Also we give an upper bound for this number. We find the cardinality of the minimal component of perfect coloring with these parameters and prove that any minimal component of such perfect coloring is linear.

05C15 Coloring of graphs and hypergraphs
05C30 Enumeration in graph theory
Full Text: Link