Generating binary partial Hadamard matrices. (English) Zbl 1414.05059
Summary: This paper deals with partial binary Hadamard matrices. Although there is a fast simple way to generate about a half (which is the best asymptotic bound known so far, see [W. de Launey, Discrete Appl. Math. 102, No. 1–2, 37–45 (2000; Zbl 0961.05010)] and [W. de Launey and D. M. Gordon, J. Comb. Theory, Ser. A 95, No. 1, 180–184 (2001; Zbl 0973.05011)]) of a full Hadamard matrix, it cannot provide larger partial Hadamard matrices beyond this bound. In order to overcome such a limitation, we introduce a particular subgraph \(G_t\) of N. Ito’s Hadamard graph \(\Delta(4 t)\) [Graphs Comb. 1, 57–64 (1985; Zbl 0587.05046)], and study some of its properties, which facilitates that a procedure may be designed for constructing large partial Hadamard matrices. The key idea is translating the problem of extending a given clique in \(G_t\) into a constraint satisfaction problem, to be solved by Minion. Actually, iteration of this process ends with large partial Hadamard matrices, usually beyond the bound of half a full Hadamard matrix, at least as our computation capabilities have led us thus far.
MSC:
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
References:
| [1] | V. Álvarez, J.A. Armario, R.M. Falcón, M.D. Frau, F. Gudiel, M.B. Güemes, A. Osuna, Generating partial Hadamard matrices as solutions to a constraint satisfaction problem characterizing cliques. in: Proceedings of X Encuentro Andaluz de Matemática Discreta, pp. 17-20 ISBN: 978-84-697-4743-8, (La Línea, Cádiz, July 10-11 2017).; V. Álvarez, J.A. Armario, R.M. Falcón, M.D. Frau, F. Gudiel, M.B. Güemes, A. Osuna, Generating partial Hadamard matrices as solutions to a constraint satisfaction problem characterizing cliques. in: Proceedings of X Encuentro Andaluz de Matemática Discreta, pp. 17-20 ISBN: 978-84-697-4743-8, (La Línea, Cádiz, July 10-11 2017). |
| [2] | Álvarez, V.; Armario, J. A.; Frau, M. D.; Gudiel, F.; Güemes, M. B.; Martín, E.; Osuna, A., Searching for partial Hadamard matrices (2012), arXiv:1201.4021 [math.CO] |
| [3] | Bomze, I. M.; Budinich, M.; Paradalos, P. M.; Pelillo, M., (Du, D. Z.; Paradalos, P. M., The maximum clique problem. The maximum clique problem, Handbook of Combinatorial Optimization, vol. 4 (1999), Kluwer: Kluwer Norwell, MA) · Zbl 1253.90188 |
| [4] | de Launey, W., On the assymptotic existence of partial complex hadamard matrices and related combinatorial objects, Discrete Appl. Math., 102, 37-45 (2000) · Zbl 0961.05010 |
| [5] | de Launey, W.; Gordon, D. M., A comment on the hadamard conjecture, J. Combin. Theory Ser. A, 95, 1, 180-184 (2001) · Zbl 0973.05011 |
| [6] | Dechter, R., Constraint Processing (2003), Morgan Kaufmann |
| [7] | Đokovic, D.v.; Golubitsky, O.; Kotsireas, I. S., Some new orders of hadamard and skew-hadamard matrices, J. Combin. Des., 22, 6, 270-277 (2014) · Zbl 1295.05071 |
| [8] | Gent, I. P.; Jefferson, C.; Miguel, I., MINION: a fast scalable constraint solver, (Brewka, G.; Coradeschi, S.; Perini, A.; Traverso, P., ECAI (2006), IOS, Amsterdam), 98-102 |
| [9] | J. Hastad, Clique is hard to approximate within \(n^{1 - \epsilon}\); J. Hastad, Clique is hard to approximate within \(n^{1 - \epsilon}\) · Zbl 0989.68060 |
| [10] | Horadam, K. J., Hadamard Matrices and their Applications (2007), Princeton University Press · Zbl 1145.05014 |
| [11] | Ito, N., Hadamard graphs i, Graphs Combin., 1, 1, 57-64 (1985) · Zbl 0587.05046 |
| [12] | S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring, in: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2001, pp. 600-609.; S. Khot, Improved inapproximability results for maxclique, chromatic number and approximate graph coloring, in: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2001, pp. 600-609. |
| [13] | MINION official site (2017) |
| [14] | Sloane, N. J.A., The on-line encyclopedia of integer sequences (2017), http://www2.research.att.com/ njas/hadamard · Zbl 1274.11001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
