Braun, Michael; Östergård, Patric R. J.; Wassermann, Alfred New lower bounds for binary constant-dimension subspace codes. (English) Zbl 1391.51005 Exp. Math. 27, No. 2, 179-183 (2018). Summary: Let \(\mathcal A_q(n,d,k)\) denote the maximum cardinality of a set \(\mathcal C\) of \(k\)-dimensional subspaces of an \(n\)-dimensional vector space over the finite field of order \(q\), \(\mathbb F_q\), such that any two different subspaces \(U\), \(W\in\mathcal C\) have a distance \(d(U,W):=\operatorname{dim}(U+W)-\operatorname{dim}(U\cap W)\) of at least \(d\). Lower bounds on \(\mathcal A_q(n,d,k)\) can be obtained by explicitly constructing corresponding sets \(\mathcal C\). When searching for such sets with a prescribed group of automorphisms, the search problem leads to instances of the maximum weight clique problem. The main focus is here on subgroups with small index in the normalizer of a Singer subgroup of \(\mathrm{GL}(n,q)\). With a stochastic maximum weight clique algorithm and a systematic consideration of groups of the above mentioned type, new lower bounds on \(\mathcal A_2(8,4,4)\) and \(\mathcal A_2(n,4,3)\) for \(8\leq n\leq 11\) are obtained. Cited in 5 Documents MSC: 51E20 Combinatorial structures in finite projective spaces 51E23 Spreads and packing problems in finite geometry 94B65 Bounds on codes 05B40 Combinatorial aspects of packing and covering 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 90C10 Integer programming Keywords:constant-dimension codes; integer linear programming; packing; random network coding; maximum weight clique problem Software:Cliquer PDFBibTeX XMLCite \textit{M. Braun} et al., Exp. Math. 27, No. 2, 179--183 (2018; Zbl 1391.51005) Full Text: DOI References: [1] Abe, [Abe And Yoshiara 93] T.; Yoshiara, S., On Suzuki’s Construction of 2-Designs Over GF(q)., Sci. Rep. Hirosaki Univ., 40, 119-122 (1993) · Zbl 0792.05013 [2] Alltop, [Alltop 69] W. O., An Infinite Class of 4-Designs., J. Combin. Theory, 6, 320-322 (1969) · Zbl 0169.01903 [3] Artin, [Artin 57] E., Geometric Algebra (1957), New York: Interscience Publishers, New York · Zbl 0077.02101 [4] Bomze, [Bomze Et Al. 99] I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M.; Du, D. Z.; Pardalos, P. M., Handbook of Combinatorial Optimization, A, The Maximum Clique Problem., 1-74 (1999), Dordrecht: Kluwer, Dordrecht · Zbl 1253.90188 [5] Braun, [Braun 05] M., Some New Designs Over Finite Fields., Bayreuth. Math. Schr., 74, 58-68 (2005) · Zbl 1103.05013 [6] Braun, [Braun Et Al. 16] M.; Etzion, T.; Östergård, P. R. J.; Vardy, A.; Wassermann, A., Existence of q-Analogs of Steiner Systems.” Forum of Mathematics. Pi 4 (2016), e7, 14pp [7] Braun, [Braun Et Al. 05] M.; Kerber, A.; Laue, R., Systematic Construction of q-Analogs of Designs., Des. Codes Cryptogr., 34, 55-70 (2005) · Zbl 1055.05009 [8] Braun, [Braun Et Al. 14] M.; Kohnert, A.; Östergård, P. R. J.; Wassermann, A., Large Sets of t-Designs Over Finite Fields., J. Combin. Theory Ser. A, 124, 195-202 (2014) · Zbl 1283.05035 [9] Braun, [Braun And Reichelt 14] M.; Reichelt, J., q-Analogs of Packing Designs., J. Combin. Des., 22, 306-321 (2014) · Zbl 1301.05060 [10] El-Zanati, [El-Zanati Et Al. 10] S.; Jordon, H.; Seelinger, G.; Sissokho, P.; Spence, L., The Maximum Size of a Partial 3-Spread in a Finite Vector Space Over GF(2)., Des. Codes Cryptogr., 54, 101-107 (2010) · Zbl 1200.51008 [11] Etzion, [Etzion Preprint] T., Problems on q-Analogs in Coding Theory. [12] Etzion, [Etzion And Silberstein 13] T.; Silberstein, N., Codes and Designs Related to Lifted MRD Codes., IEEE Trans. Inf. Theory, 59, 1004-1017 (2013) · Zbl 1364.94597 [13] Etzion, [Etzion And Vardy 11] T.; Vardy, A., Error-correcting Codes in Projective Space., IEEE Trans. Inf. Theory, 57, 1165-1173 (2011) · Zbl 1366.94589 [14] Honold, [Honold Et Al. 15] T.; Kiermaier, M.; Kurz, S.; Kyureghyan, G.; Mullen, G. L.; Pott, A., Topics in Finite Fields, Contemporary Mathematics, 632, Optimal Binary Subspace Codes of Length 6, Constant Dimension 3 and Minimum Subspace Distance 4., 157-176 (2015) [15] Huppert, [Huppert 67] B., Endliche Gruppen I (1967), Berlin: Springer-Verlag, Berlin · Zbl 0217.07201 [16] Kantor, [Kantor 80] W. M., Linear Groups Containing a Singer Cycle., J. Algebra, 62, 232-234 (1980) · Zbl 0429.20004 [17] Khaleghi, [Khaleghi Et Al. 09] A.; Silva, D.; Kschischang, F. R.; Parker, M. G., Cryptography and Coding, 5921, Subspace Codes., 1-21 (2009), Berlin: Springer, Berlin [18] Kohnert, [Kohnert And Kurz 08] A.; Kurz, S.; Calmet, J.; Geiselmann, W.; Müller-Quade, J., Mathematical Methods in Computer Science, 5393, Construction of Large Constant Dimension Codes with a Prescribed Minimum Distance., 31-42 (2008), Berlin: Springer, Berlin [19] Kötter, [Kötter And Kschischang 08] R.; Kschischang, F. R., Coding for Errors and Erasures in Random Network Coding., IEEE Trans. Inf. Theory, 54, 3579-3591 (2008) · Zbl 1318.94111 [20] Kramer, [Kramer And Mesner 76] E. S.; Mesner, D. M., t-Designs on Hypergraphs., Discrete Math., 15, 263-296 (1976) · Zbl 0362.05049 [21] Kschischang, [Kschischang 12] F. R.; Médard, M.; Sprintson, A., Network Coding: Fundamentals and Applications, An Introduction to Network Coding., 1-37 (2012), Amsterdam: Elsevier, Amsterdam [22] Kurz, [Kurz Preprint] S., Improved Upper Bounds for Partial Spreads. · Zbl 1378.51010 [23] Mathew, [Mathew And Östergård To Appear] K. A.; Östergård, P. R. J., New Lower Bounds for the Shannon Capacity of Odd Cycles., Des. Codes Cryptogr. · Zbl 1367.05160 [24] Miyakawa, [Miyakawa Et Al. 95] M.; Munemasa, A.; Yoshiara, S., On A Class of Small 2-Designs Over GF(q)., J. Combin. Des., 3, 61-77 (1995) · Zbl 0823.05009 [25] Montemanni, [Montemanni And Smith 09] R.; Smith, D. H., Heuristic Algorithms for Constructing Binary Constant Weight Codes., IEEE Trans. Inf. Theory, 55, 4651-4656 (2009) · Zbl 1367.94375 [26] Năstase, [Năstase And Sissokho Preprint] E.; Sissokho, P., The Maximum Size of A Partial Spread in A Finite Projective Space. · Zbl 1367.51007 [27] Niskanen, [Niskanen And Östergård 03] S.; Östergård, P. R. J., “Cliquer User’s Guide, version 1.0, Technical Report T48, Communications Laboratory, Helsinki University of Technology, Espoo (2003) [28] Pullan, [Pullan 09] W., Optimisation of Unweighted/Weighted Maximum Independent Sets and Minimum Vertex Covers., Discrete Optim., 6, 214-219 (2009) · Zbl 1169.05383 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.