On perfect 2-colorings of the q-ary n-cube

DOI10.1016/J.DISC.2011.12.004zbMATH Open1245.05051arXiv1104.1293OpenAlexW2169084983MaRDI QIDQ409480FDOQ409480

Vladimir N. Potapov

Publication date: 13 April 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: A coloring of the $q$-ary $n$-dimensional cube (hypercube) is called perfect if, for every $n$-tuple $x$, the collection of the colors of the neighbors of $x$ depends only on the color of $x$. A Boolean-valued function is called correlation-immune of degree $n-m$ if it takes the value 1 the same number of times for each $m$-dimensional face of the hypercube. Let $f=ch{i}^S$ be a characteristic function of some subset $S$ of hypercube. In the present paper it is proven the inequality $ho(S)q(mcor(f)+1)leqalpha(S)$, where $mcor(f)$ is the maximum degree of the correlation immunity of $f$, $alpha(S)$ is the average number of neighbors in the set $S$ for $n$-tuples in the complement of a set $S$, and $ho(S)=|S|/q^n$ is the density of the set $S$. Moreover, the function $f$ is a perfect coloring if and only if we obtain an equality in the above formula.Also we find new lower bound for the cardinality of components of perfect coloring and 1-perfect code in the case $q>2$. Keywords: hypercube, perfect coloring, perfect code, MDS code, bitrade, equitable partition, orthogonal array.

Full work available at URL: https://arxiv.org/abs/1104.1293

Recommendations

• scientific article; zbMATH DE number 7310103
• On perfect colorings of Boolean \(n\)-cube and correlation immune functions with small density
• Cardinality spectra of components of correlation immune functions, bent functions, perfect colorings, and codes
• A bound on correlation immunity
• Perfect colorings of the 12-cube that attain the bound on correlation immunity
• Local and interweight spectra of completely regular codes and of perfect colorings
• scientific article; zbMATH DE number 1353832
• scientific article; zbMATH DE number 2077652
• Testing Sets for 1-Perfect Code
• On construction of vertex-transitive partitions of the \(n\)-cube into perfect codes

zbMATH Keywords

equitable partitionorthogonal array\(q\)-ary hypercubeperfect codeMDS codeperfect 2-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• The Perfect Binary One-Error-Correcting Codes of Length 15: Part II—Properties
• Title not available (Why is that?)
• A bound on correlation immunity
• Perfect colorings of the 12-cube that attain the bound on correlation immunity
• Title not available (Why is that?)
• On perfect colorings of Boolean \(n\)-cube and correlation immune functions with small density
• Bounds on orthogonal arrays and resilient functions
• Construction of perfect \(q\)-ary codes by switchings of simple components
• 10.17686/sced_rusnauka_2008-1040
• Title not available (Why is that?)
• Ranks of \(q\)-ary 1-perfect codes

Cited In (20)

• A bound on correlation immunity
• Perfect colorings of the 12-cube that attain the bound on correlation immunity
• Title not available (Why is that?)
• Minimum supports of functions on the Hamming graphs with spectral constraints
• On the non-existence of extended 1-perfect codes and MDS codes
• Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph
• Title not available (Why is that?)
• Combinatorial designs, difference sets, and bent functions as perfect colorings of graphs and multigraphs
• Perfect colorings of the infinite square grid: coverings and twin colors
• Eigenfunctions supports of minimum cardinality in cubical distance-regular graphs
• On the \(\mathrm{OA}(1536,13,2,7)\) and related orthogonal arrays
• Perfect 2‐colorings of Hamming graphs
• On \(q\)-ary bent and plateaued functions
• Minimum supports of eigenfunctions with the second largest eigenvalue of the star graph
• On unbalanced Boolean functions with best correlation immunity
• Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph
• Two results on the bit extraction problem
• Minimum supports of eigenfunctions in bilinear forms graphs
• Minimum supports of eigenfunctions of Hamming graphs
• Minimum supports of eigenfunctions of graphs: a survey

This page was built for publication: On perfect 2-colorings of the \(q\)-ary \(n\)-cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q409480)