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

DOI10.1016/J.DISC.2011.12.004MaRDI QIDQ409480zbMATHOpenAlexFDO

Authors Vladimir N. Potapov

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

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

Cited in

(27)

• On the non-existence of extended 1-perfect codes and MDS codes
• Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph
• On perfect colorings of Boolean \(n\)-cube and correlation immune functions with small density
• Minimum supports of functions on the Hamming graphs with spectral constraints
• On unbalanced Boolean functions with best correlation immunity
• Perfect colorings of the infinite square grid: coverings and twin colors
• On the \(\mathrm{OA}(1536,13,2,7)\) and related orthogonal arrays
• Local distributions of \(q\)-ary eigenfunctions and of \(q\)-ary perfect colorings
• A bound on correlation immunity
• Perfect colorings of the 12-cube that attain the bound on correlation immunity
• On perfect 2-colorings of the hypercube
• Perfect 2‐colorings of Hamming graphs
• Minimum supports of eigenfunctions with the second largest eigenvalue of the star graph
• Local distributions for eigenfunctions and perfect colorings of \(q\)-ary Hamming graph
• On \(q\)-ary bent and plateaued functions
• Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph
• On perfect colorings of the halved 24-cube
• Minimum supports of eigenfunctions of graphs: a survey
• [[Publication:6643242|Equitable \([[2, 10], [6, 6]]\)-partitions of the 12-cube]]
• Two results on the bit extraction problem
• scientific article; zbMATH DE number 5379405 (Why is no real title available?)
• On degree-3 and \((n - 4)\)-correlation-immune perfect colorings of \(n\)-cubes
• scientific article; zbMATH DE number 7310103 (Why is no real title available?)
• Minimum supports of eigenfunctions in bilinear forms graphs
• Minimum supports of eigenfunctions of Hamming graphs
• Combinatorial designs, difference sets, and bent functions as perfect colorings of graphs and multigraphs
• Eigenfunctions supports of minimum cardinality in cubical distance-regular graphs

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)