The chromatic number of the square of the $8$-cube
HTML articles powered by AMS MathViewer
- by Janne I. Kokkala and Patric R. J. Östergård PDF
- Math. Comp. 87 (2018), 2551-2561 Request permission
Abstract:
A cube-like graph is a Cayley graph for the elementary abelian group of order $2^n$. In studies of the chromatic number of cube-like graphs, the $k$th power of the $n$-dimensional hypercube, $Q_n^k$, is frequently considered. This coloring problem can be considered in the framework of coding theory, as the graph $Q_n^k$ can be constructed with one vertex for each binary word of length $n$ and edges between vertices exactly when the Hamming distance between the corresponding words is at most $k$. Consequently, a proper coloring of $Q_n^k$ corresponds to a partition of the $n$-dimensional binary Hamming space into codes with minimum distance at least $k+1$. The smallest open case, the chromatic number of $Q_8^2$, is here settled by finding a 13-coloring. Such 13-colorings with specific symmetries are further classified.References
- M. R. Best, Binary codes with a minimum distance of four, IEEE Trans. Inform. Theory 26 (1980), no. 6, 738–742. MR 596287, DOI 10.1109/TIT.1980.1056269
- M. R. Best and A. E. Brouwer, The triply shortened binary Hamming code is optimal, Discrete Math. 17 (1977), no. 3, 235–245. MR 441537, DOI 10.1016/0012-365X(77)90158-3
- M. R. Best, A. E. Brouwer, F. Jessie MacWilliams, Andrew M. Odlyzko, and Neil J. A. Sloane, Bounds for binary codes of length less than $25$, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 81–93. MR 479645, DOI 10.1109/tit.1978.1055827
- Tomáš Dvořák, Ivan Havel, Jean-Marie Laborde, and Petr Liebl, Generalized hypercubes and graph embedding with dilation, Proceedings of the 7th Fischland Colloquium, II (Wustrow, 1988), 1990, pp. 13–20. MR 1090602
- Frank Harary, Four difficult unsolved problems in graph theory, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 249–256. MR 0382042
- Tommy R. Jensen and Bjarne Toft, Graph coloring problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. MR 1304254
- Petteri Kaski and Patric R. J. Östergård, Classification algorithms for codes and designs, Algorithms and Computation in Mathematics, vol. 15, Springer-Verlag, Berlin, 2006. With 1 DVD-ROM (Windows, Macintosh and UNIX). MR 2192256
- P. Kaski and O. Pottonen, libexact user’s guide, version 1.0, Tech. Report TR 2008-1, Helsinki Institute for Information Technology HIIT, Helsinki, 2008.
- Dongsoo S. Kim, Ding-Zhu Du, and Panos M. Pardalos, A coloring problem on the $n$-cube, Discrete Appl. Math. 103 (2000), no. 1-3, 307–311. MR 1762219, DOI 10.1016/S0166-218X(99)00249-8
- Antti Laaksonen and Patric R. J. Östergård, Constructing error-correcting binary codes using transitive permutation groups, Discrete Appl. Math. 233 (2017), 65–70. MR 3711970, DOI 10.1016/j.dam.2017.08.022
- J. Lauri, The square of the 9-hypercube is 14-colorable, preprint, available at http://arxiv.org/abs/1605.07613.
- Nathan Linial, Roy Meshulam, and Michael Tarsi, Matroidal bijections between graphs, J. Combin. Theory Ser. B 45 (1988), no. 1, 31–44. MR 953893, DOI 10.1016/0095-8956(88)90053-6
- Brendan D. McKay and Adolfo Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112. MR 3131381, DOI 10.1016/j.jsc.2013.09.003
- Hung Quang Ngo, Ding-Zhu Du, and Ronald L. Graham, New bounds on a hypercube coloring problem, Inform. Process. Lett. 84 (2002), no. 5, 265–269. MR 1931730
- S. Niskanen and P. R. J. Östergård, Cliquer User’s Guide, Version 1.0, Tech. Report T48, Communications Laboratory, Helsinki University of Technology, Espoo, 2003.
- Patric R. J. Östergård, On a hypercube coloring problem, J. Combin. Theory Ser. A 108 (2004), no. 2, 199–204. MR 2098840, DOI 10.1016/j.jcta.2004.06.010
- Patric R. J. Östergård, On the size of optimal three-error-correcting binary codes of length 16, IEEE Trans. Inform. Theory 57 (2011), no. 10, 6824–6826. MR 2882264, DOI 10.1109/TIT.2011.2144955
- Patric R. J. Östergård, Tsonka Baicheva, and Emil Kolev, Optimal binary one-error-correcting codes of length $10$ have $72$ codewords, IEEE Trans. Inform. Theory 45 (1999), no. 4, 1229–1231. MR 1686256, DOI 10.1109/18.761273
- Charles Payan, On the chromatic number of cube-like graphs, Discrete Math. 103 (1992), no. 3, 271–277. MR 1171780, DOI 10.1016/0012-365X(92)90319-B
- J. G. Rix, Hypercube coloring and the structure of binary codes, Master’s thesis, The University of British Columbia, 2008.
- Joseph J. Rotman, An introduction to the theory of groups, 4th ed., Graduate Texts in Mathematics, vol. 148, Springer-Verlag, New York, 1995. MR 1307623, DOI 10.1007/978-1-4612-4176-8
- Peng-Jun Wan, Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network, J. Comb. Optim. 1 (1997), no. 2, 179–186. MR 1606905, DOI 10.1023/A:1009759916586
- Günter M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the $0/1$-Borsuk problem in low dimensions, Computational discrete mathematics, Lecture Notes in Comput. Sci., vol. 2122, Springer, Berlin, 2001, pp. 159–171. MR 1911588, DOI 10.1007/3-540-45506-X_{1}2
Additional Information
- Janne I. Kokkala
- Affiliation: Aalto University, School of Electrical Engineering, Department of Communications and Networking, P.O. Box 13000, 00076 Aalto, Finland
- Email: janne.kokkala@aalto.fi
- Patric R. J. Östergård
- Affiliation: Aalto University, School of Electrical Engineering, Department of Communications and Networking, P.O. Box 13000, 00076 Aalto, Finland
- Email: patric.ostergard@aalto.fi
- Received by editor(s): December 2, 2016
- Received by editor(s) in revised form: April 15, 2017
- Published electronically: December 22, 2017
- Additional Notes: The work of the first author was supported by Aalto ELEC Doctoral School, Nokia Foundation, Emil Aaltonen Foundation, and by Academy of Finland Project 289002
The work of the second author was supported in part by Academy of Finland Project 289002. - © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 87 (2018), 2551-2561
- MSC (2010): Primary 05C15; Secondary 94B25
- DOI: https://doi.org/10.1090/mcom/3291
- MathSciNet review: 3802446