×

Constructions of maximum few-distance sets in Euclidean spaces. (English) Zbl 1454.51007

This paper focuses on the problem of determining, given the natural numbers \(d\) and \(s\), the largest finite subsets of vectors in \(\mathbb{R}^d\) for which the set of mutual distances between distinct vectors has cardinality \(s\). More precisely, the authors focus primarly on the case \(d=4\) and \(s=3\), but also on the cases \(d=3\) and \(s=4\), \(d=3\) and \(s=3\), and \(d=2\) and \(s=6\), respectively. The given proofs are based on classical graph generation techniques and on elements of computational commutative algebra. Other related examples are also discussed.

MSC:

51K05 General theory of distance geometry
52C10 Erdős problems and related topics of discrete geometry
14N10 Enumerative problems (combinatorial problems) in algebraic geometry

Software:

CoCoALib; Cliquer
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] J. Abbott, A.M. Bigatti: CoCoALib: a C++ library for doing Computations in Commutative Algebra. Available athttp://cocoa.dima.unige.it/cocoalib, ver. 0.99560 (2018). · Zbl 1267.13048
[2] E. Bannai, E. Bannai, D. Stanton: An upper bound for the cardinality of an s-distance subset in real Euclidean space, II,Combinatorica,3147-152 (1983). · Zbl 0522.05022
[3] A. Barg, W.-H. Yu: New bounds for equiangular lines, in: “Discrete Geometry and Algebraic Combinatorics”, A. Barg and O.R. Musin (eds.), Providence, RI, AMS (2014).
[4] T. Becker, V. Weispfenning: Gr¨obner Bases, Springer-Verlag, New York (1993).
[5] A. Blokhuis: Few-Distance Sets, CWI Tract 7, CWI, Amsterdam (1984). · Zbl 0548.51014
[6] L.M. Blumenthal: Theory and Applications of Distance Geometry, 2nd ed., Chelsea, New York (1970). · Zbl 0208.24801
[7] V. Boltyanski, H. Martini, P.S. Soltan: Excursions into Combinatorial Geometry, Springer-Verlag, Berlin (1997). · Zbl 0877.52001
[8] W. Bruns, A. Conca: Gr¨obner Bases and Determinantal Ideals. In: Herzog J., Vuletescu V. (eds.)Commutative Algebra, Singularities and Computer Algebra. NATO Science Series (Series II: Mathematics, Physics and Chemistry),115, Springer, Dordrecht (2003).
[9] J. Cahill, P.G. Casazza, J.I. Haas, J. Tremain: Constructions of biangular tight frames and their relationships with equiangular tight frames,Contemp. Math., 7061-20 (2018). · Zbl 1398.42021
[10] H.T. Croft: 9-point and 7-point configuration in 3-space,Proc. Lond. Math. Soc., 3:12400-424 (1962).
[11] C.J. Colbourn, J.H. Dinitz: Handbook of Combinatorial Designs (Second Edition), CRC Press, Boca Raton (2007). · Zbl 1101.05001
[12] J.H.Conway, N.J.A. Sloane: Sphere Packings, Lattices and Groups (Third Edition), Springer, New York (1999). · Zbl 0915.52003
[13] S.J. Einhorn, I.J. Schoenberg: On Euclidean sets having only two distances between points I-II,Indag. Math.,69489-504 (1966). · Zbl 0145.17103
[14] P. Erd˝os, P. Fishburn: Maximum planar sets that determinekdistances,Discrete Math.,160115-125 (1996).
[15] M. Fickus, J. Jasper, D.G. Mixon: Packings in real projective spaces,SIAM J. Appl. Algebra Geom.,2:3377-409 (2018). · Zbl 1397.52010
[16] E.H.-A. Gerbracht: Eleven unit distance embeddings of the Heawood graph, arXiv:0912.5395[math.CO] (2009).
[17] M. Grassl: On SIC-POVMs and MUBs in dimension 6, in Proc. ERATO Conference on Quantum Information Science 2004, Tokyo 60-61 (2004).
[18] G. Greaves, J.H. Koolen, A. Munemasa, F. Sz¨oll˝osi: Equiangular lines in Euclidean spaces,J. Combin. Theory Ser. A,138208-235 (2016).
[19] H. Haanp¨a¨a, P. Kaski: The near resolvable 2-(13,4,3) designs and thirteen-player whist tournaments,Des. Codes Cryptogr.,35271-285 (2005). · Zbl 1066.05028
[20] A. Hanaki, I. Miyamoto: Classification of association schemes of small order, Discrete Math.,26475-80 (2003). · Zbl 1014.05073
[21] F. Harary, E.M. Palmer: Graphical Enumeration, Academic Press, New York (1973). · Zbl 0266.05108
[22] N.J. Higham: Cholesky Factorization,WIREs Comp. Stat.,1251-254 (2009).
[23] P. Kaski, P.R.J. ¨Osterg˚ard: Classification Algorithm for Codes and Designs, Springer, Berlin (2006).
[24] L.M. Kelly: Elementary problems and solutions. Isoscelesn-points,Amer. Math. Monthly,54227-229 (1947).
[25] D.G. Larman, C.A. Rogers, J.J. Seidel: On two-distance sets in Euclidean space,Bull. London Math. Soc.,9:3261-267 (1977). · Zbl 0399.51011
[26] P.W.H. Lemmens, J.J. Seidel: Equiangular lines,J. Algebra,27494-512 (1973). · Zbl 0255.50005
[27] L. Liberti, C. Lavor, N. Maculan, A. Mucherino: Euclidean distance geometry and applications,SIAM Rev.,56:13-69 (2014). · Zbl 1292.51010
[28] P. Lisonˇek: New maximal two-distance sets,J. Combin. Theory Ser. A,77318-338 (1997).
[29] B. McKay: Practical graph isomorphism,Congr. Numer.,3045-87 (1981).
[30] O.R. Musin: Spherical two-distance sets,J. Combin. Theory Ser. A,116988-995 (2009). · Zbl 1166.51300
[31] O.R. Musin, H. Nozaki: Bounds on three- and higher-distance sets,European J. Combin.,321182-1190 (2011). · Zbl 1235.51020
[32] A. Neumaier: Distance matrices, dimension, and conference graphs,Indag. Math., 84:4385-391 (1981). · Zbl 0523.05019
[33] S. Niskanen, P.R.J. ¨Osterg˚ard: Cliquer user’s guide, version 1.0,Technical Report T48, Communications Laboratory, Helsinki University of Technology, Espoo (2003).
[34] H. Nozaki: A generalization of Larman-Rogers-Seidel’s theorem,Discrete Math., 311792-799 (2011). · Zbl 1220.51002
[35] P.R.J. ¨Osterg˚ard: A fast algorithm for the maximum clique problem,Discrete Appl. Math.,120197-207 (2002).
[36] R.C. Read: Every one a winner, or how to avoid isomorphism search when cataloguing combinatorial configurations,Ann. Discrete Math.,2107-120 (1978). · Zbl 0392.05001
[37] I.J. Schoenberg: Remarks to Maurice Frechet’s article,Ann. Math.,36724-732 (1935). · JFM 61.0435.04
[38] M. Shinohara: On three-distance sets in the three-dimensional Euclidean space and maximum planar five-distance sets, PhD thesis, Kyushu University (2005).
[39] M. Shinohara:Uniqueness of maximum three-distance sets in the threedimensional Euclidean space,preprint,arXiv:1309.2047[math.MG] (2013).
[40] F.Sz¨oll˝osi:Allcomplexequiangulartightframesindimension3, arXiv:1402.6429[math.FA] (2014).
[41] F. Sz¨oll˝osi, P.R.J. ¨Osterg˚ard: Enumeration of Seidel matrices,European J. Combin.,69169-184 (2018).
[42] S.F.D. Waldron: An Introduction to Finite Tight Frames, Birkh¨auser (2018). · Zbl 1388.42078
[43] X.
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.