The clique distribution in powers of hypercubes

DOI10.1016/J.DAM.2021.08.030MaRDI QIDQ2235258zbMATH OpenOpenAlexFDO

Authors Yongfang Kou, Weihua Yang, Xiaomin Hu

Publication date 21 October 2021

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

Full work available at URL https://doi.org/10.1016/j.dam.2021.08.030

zbMATH Keywords

cliquecoding theoryHamming distancehypercube

Mathematics Subject Classification ID

Distance in graphs (05C12) Linear codes (general theory) (94B05) Combinatorial codes (94B25)

Review text

A pertinent task in coding theory is to determine the values of \(A(n,d)\), where \(A(n,d)\) is the size of the maximum binary code set of length \(n\) and minimum Hamming distance \(d$. It can also be thought of as the size of the maximum independent set of \((d-1)\)th power of the \(n\)-dimensional hypercube \(Q_n\). In this paper the authors studied the distribution of the maximum clique and the structure of the point of \(Q_n^d\) for \(d\leq 5\). The proof techniques are quite mind blowing and novel. It will stimulate keen interest for further exploration.

Recommendations

• Construction of several classes of maximum codes
• On a hypercube coloring problem
• scientific article; zbMATH DE number 3843662
• Maximal Binary Cliques
• On the large maximal \(\{ 0,1,2,\dots,t\}\)-cliques in Hamming graph \(H(n,q)\)

Cites work

• A coloring problem on the \(n\)-cube
• A table of upper bounds for binary codes
• Asymptotic Improvement of the Gilbert–Varshamov Bound on the Size of Binary Codes
• Binary codes with a minimum distance of four (Corresp.)
• Error detecting and error correcting codes
• scientific article; zbMATH DE number 3133919 (Why is no real title available?)
• scientific article; zbMATH DE number 3167429 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• Improved upper bounds on sizes of codes
• On a combinatorial conjecture of Erdös
• Sharpening the Gilbert-Varshamov bound in the finite case
• Some results on the existence of binary linear codes (Corresp.)
• Strengthening the Gilbert-Varshamov bound
• The chromatic number of the square of the 8-cube
• The distinguishing number of the hypercube
• The generalized Gilbert-Varshamov bound is implied by Turan's theorem [code construction]

Cited in

(3)

• Some distribution numbers of the hypercubic association scheme
• Codes and Xor graph products
• Focusing of the scan statistic and geometric clique number

This page was built for publication: The clique distribution in powers of hypercubes

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