# American Institute of Mathematical Sciences

doi: 10.3934/amc.2021036
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Domination mappings into the hamming ball: Existence, constructions, and algorithms

 1 Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 2 Department of Computer Science, Technion — Israel Institute of Technology, Haifa, Israel 3 School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 4 Department of Electrical & Computer Engineering, University of California San Diego, LA Jolla, CA, USA

Received  January 2021 Revised  May 2021 Early access August 2021

Fund Project: The research of Y. M. Chee is supported by the Singapore Ministry of Education under grant MOE2017-T3-1-007. T. Etzion and A. Vardy were supported in part by the United States — Israel Binational Science Foundation (BSF), Jerusalem, Israel, under Grant 2012016

The Hamming ball of radius $w$ in $\{0,1\}^n$ is the set $\mathcal{B}(n,w)$ of all binary words of length $n$ and Hamming weight at most $w$. We consider injective mappings $\varphi : \{0,1\}^m \to \mathcal{B}(n,w)$ with the following domination property: every position $j \in [n]$ is dominated by some position $i \in [m]$, in the sense that if position $i$ in ${\mathit{\boldsymbol{x}}} \in \{0,1\}^m$ is "switched off" (equal zero), then necessarily position $j$ in its image $\varphi({\mathit{\boldsymbol{x}}})$ is switched off. This property may be described more precisely in terms of a bipartite domination graph $G = \bigl([m] \cup [n], E\bigr)$ with no isolated vertices; for all $(i,j) \in E$ and all ${\mathit{\boldsymbol{x}}}\in \{0,1\}^m$, we require that $x_i = 0$ implies $y_j = 0$, where ${\mathit{\boldsymbol{y}}} = \varphi({\mathit{\boldsymbol{x}}})$. Although such domination mappings recently found applications in the context of coding for high-performance interconnects, to the best of our knowledge, they were not previously studied. The concept of domination mapping is thus interesting from both practical and combinatorial points of view.

In this paper, we begin with simple necessary conditions for the existence of an $(m,n,w)$-domination mapping $\varphi : \{0,1\}^m \to \mathcal{B}(n,w)$. We then provide several explicit constructions of such mappings, which show that the necessary conditions are also sufficient when $w = 1$, when $w = 2$ and $m$ is odd, or when $m \leqslant 3w$. One of our main results herein is a proof that the trivial necessary condition $| \mathcal{B}(n,w)| \geqslant 2^m$ is, in fact, sufficient for the existence of an $(m,n,w)$-domination mapping whenever $m$ is sufficiently large. We also present a polynomial-time algorithm that, given any $m$, $n$, and $w$, determines whether an $(m,n,w)$-domination mapping exists for a domination graph with an equitable degree distribution.

Citation: Yeow Meng Chee, Tuvi Etzion, Han Mao Kiah, Alexander Vardy. Domination mappings into the hamming ball: Existence, constructions, and algorithms. Advances in Mathematics of Communications, doi: 10.3934/amc.2021036
##### References:

show all references

##### References:
Bounds, constructions, and existence of $(m,n,w)$-domination mappings for $w = 3$
 [1] B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037 [2] Xiang Wang, Wenjuan Yin. New nonexistence results on perfect permutation codes under the hamming metric. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021058 [3] Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223 [4] Luciano Panek, Jerry Anderson Pinheiro, Marcelo Muniz Alves, Marcelo Firer. On perfect poset codes. Advances in Mathematics of Communications, 2020, 14 (3) : 477-489. doi: 10.3934/amc.2020061 [5] Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399 [6] Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021 [7] Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87 [8] Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008 [9] Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465 [10] Lassi Roininen, Markku S. Lehtinen. Perfect pulse-compression coding via ARMA algorithms and unimodular transfer functions. Inverse Problems & Imaging, 2013, 7 (2) : 649-661. doi: 10.3934/ipi.2013.7.649 [11] Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409 [12] Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385 [13] Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006 [14] Limengnan Zhou, Daiyuan Peng, Hongyu Han, Hongbin Liang, Zheng Ma. Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation. Advances in Mathematics of Communications, 2018, 12 (1) : 67-79. doi: 10.3934/amc.2018004 [15] Kang-Yu Ni, Shankar Rao, Yuri Owechko. Foveated compressive imaging for low power vehicle fingerprinting and tracking in aerial imagery. Inverse Problems & Imaging, 2017, 11 (1) : 177-202. doi: 10.3934/ipi.2017009 [16] Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295 [17] Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149 [18] Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425 [19] Nupur Patanker, Sanjay Kumar Singh. Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021013 [20] Vy Khoi Le. Existence and enclosure of solutions to noncoercive systems of inequalities with multivalued mappings and non-power growths. Discrete & Continuous Dynamical Systems, 2013, 33 (1) : 255-276. doi: 10.3934/dcds.2013.33.255