# 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:
 [1] A. H. Ajami, K. Banerjee, M. Pedram and L. P. P. P. van Ginneken, Analysis of non-uniform temperature-dependent interconnect performance in high performance ICs, DAC 2001: Proceedings of the 38-th Annual Design Automation Conference, ACM Press, (2001), 567–572. [2] R. Bodi and K. Herr, Symmetries in linear and integer programs, arXiv: 0908.3329, preprint, (2009). [3] Y. M. Chee, T. Etzion, H. M. Kiah and A. Vardy, Cooling codes: Thermal-management coding for high-performance interconnects, IEEE Trans. Inform. Theory, 64 (2018), 3062-3085.  doi: 10.1109/TIT.2017.2771245. [4] Y. M. Chee, T. Etzion, H. M. Kiah, A. Vardy and H. Wei, Low-power cooling codes with efficient encoding and decoding, IEEE Trans. Inform. Theory, 66 (2020), 4804-4818.  doi: 10.1109/TIT.2020.2977871. [5] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1998. [6] T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350.  doi: 10.1007/s10623-015-0156-5. [7] A. Fazeli, A. Vardy and E. Yaakobi, Generalized sphere packing bound, IEEE Trans. Inform. Theory, 61 (2015), 2313-2334.  doi: 10.1109/TIT.2015.2413418. [8] P. Hall, On representatives of subsets, J. London Math. Society, 10 (1935), 26-30. [9] O. Heden, A survey of perfect codes, Adv. Math. Commun., 2 (2008), 223-247.  doi: 10.3934/amc.2008.2.223. [10] D. König, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 38 (1931), 116-119. [11] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. [12] F. Margot, Exploiting orbits in symmetric ILP, Math. Program., 98 (2003), 3-21.  doi: 10.1007/s10107-003-0394-6. [13] SageMath, Sage Mathematics Software System (Version 7.6), Sage Developers, 2017, http://www.sagemath.org. [14] P. Sithambaram, A. Macii and E. Macii, New adaptive encoding schemes for switching activity balancing in on-chip buses, PATMOS 2007: Proceedings of the 17-th International Workshop on Power and Timing Modeling, Optimization and Simulation, Gothenburg, Sweden, (2007), 232–241. [15] F. I. Solov'eva, On perfect binary codes, Discrete Appl. Math., 156 (2008), 1488-1498.  doi: 10.1016/j.dam.2005.10.023. [16] E. Nǎstase and P. A. Sissokho, The maximum size of a partial spread in a finite projective space, J. Combin. Theory Ser. A, 152 (2017), 353-362.  doi: 10.1016/j.jcta.2017.06.012. [17] F. Wang, M. D. Bole, X. Wu, Y. Xie, N. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, IET Computers & Digital Techniques, 1 (2007), 590-599. [18] F. Wang, Y. Xie, N. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, DATE 2006: Proceedings of the Conference on Design, Automation, and Test in Europe, Munich, Germany, 2006, 850–855.

show all references

##### References:
 [1] A. H. Ajami, K. Banerjee, M. Pedram and L. P. P. P. van Ginneken, Analysis of non-uniform temperature-dependent interconnect performance in high performance ICs, DAC 2001: Proceedings of the 38-th Annual Design Automation Conference, ACM Press, (2001), 567–572. [2] R. Bodi and K. Herr, Symmetries in linear and integer programs, arXiv: 0908.3329, preprint, (2009). [3] Y. M. Chee, T. Etzion, H. M. Kiah and A. Vardy, Cooling codes: Thermal-management coding for high-performance interconnects, IEEE Trans. Inform. Theory, 64 (2018), 3062-3085.  doi: 10.1109/TIT.2017.2771245. [4] Y. M. Chee, T. Etzion, H. M. Kiah, A. Vardy and H. Wei, Low-power cooling codes with efficient encoding and decoding, IEEE Trans. Inform. Theory, 66 (2020), 4804-4818.  doi: 10.1109/TIT.2020.2977871. [5] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1998. [6] T. Etzion and L. Storme, Galois geometries and coding theory, Des. Codes Cryptogr., 78 (2016), 311-350.  doi: 10.1007/s10623-015-0156-5. [7] A. Fazeli, A. Vardy and E. Yaakobi, Generalized sphere packing bound, IEEE Trans. Inform. Theory, 61 (2015), 2313-2334.  doi: 10.1109/TIT.2015.2413418. [8] P. Hall, On representatives of subsets, J. London Math. Society, 10 (1935), 26-30. [9] O. Heden, A survey of perfect codes, Adv. Math. Commun., 2 (2008), 223-247.  doi: 10.3934/amc.2008.2.223. [10] D. König, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 38 (1931), 116-119. [11] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16. North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. [12] F. Margot, Exploiting orbits in symmetric ILP, Math. Program., 98 (2003), 3-21.  doi: 10.1007/s10107-003-0394-6. [13] SageMath, Sage Mathematics Software System (Version 7.6), Sage Developers, 2017, http://www.sagemath.org. [14] P. Sithambaram, A. Macii and E. Macii, New adaptive encoding schemes for switching activity balancing in on-chip buses, PATMOS 2007: Proceedings of the 17-th International Workshop on Power and Timing Modeling, Optimization and Simulation, Gothenburg, Sweden, (2007), 232–241. [15] F. I. Solov'eva, On perfect binary codes, Discrete Appl. Math., 156 (2008), 1488-1498.  doi: 10.1016/j.dam.2005.10.023. [16] E. Nǎstase and P. A. Sissokho, The maximum size of a partial spread in a finite projective space, J. Combin. Theory Ser. A, 152 (2017), 353-362.  doi: 10.1016/j.jcta.2017.06.012. [17] F. Wang, M. D. Bole, X. Wu, Y. Xie, N. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, IET Computers & Digital Techniques, 1 (2007), 590-599. [18] F. Wang, Y. Xie, N. Vijaykrishnan and M. J. Irwin, On-chip bus thermal analysis and optimization, DATE 2006: Proceedings of the Conference on Design, Automation, and Test in Europe, Munich, Germany, 2006, 850–855.
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] Haode Yan, Zhen Li, Zhitian Song, Rongquan Feng. Two classes of power mappings with boomerang uniformity 2. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022046 [9] 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 [10] Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems and Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465 [11] Lassi Roininen, Markku S. Lehtinen. Perfect pulse-compression coding via ARMA algorithms and unimodular transfer functions. Inverse Problems and Imaging, 2013, 7 (2) : 649-661. doi: 10.3934/ipi.2013.7.649 [12] 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 [13] 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 [14] 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 [15] 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 [16] Kang-Yu Ni, Shankar Rao, Yuri Owechko. Foveated compressive imaging for low power vehicle fingerprinting and tracking in aerial imagery. Inverse Problems and Imaging, 2017, 11 (1) : 177-202. doi: 10.3934/ipi.2017009 [17] 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 [18] 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 [19] 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 [20] 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

2020 Impact Factor: 0.935

## Tools

Article outline

Figures and Tables