Bounds on the maximum number of vectors with given scalar products
HTML articles powered by AMS MathViewer
- by M. Deza and P. Frankl PDF
- Proc. Amer. Math. Soc. 95 (1985), 323-329 Request permission
Abstract:
Suppose $M$, $L$ are sets of real numbers, $V = \{ {\upsilon _1}, \ldots ,{\upsilon _m}\}$ is a collection of vectors in ${R^n}$, having $k$ nonzero coordinates all from $M$ and satisfying $({\upsilon _i},{\upsilon _j}) \in L$ for $i \ne j$. Theorem 1.1 establishes a polynomial upper bound for $\left | V \right |$, generalizing previous results for subsets of a set and $(0, \pm 1)$-vectors. Theorem 1.4 asserts that if $\left | L \right | = s$ then $\left | V \right | \leqslant \left ( {\begin {array}{*{20}{c}} {n + s} \\ s \\ \end {array} } \right )$. For $M = \{ - 1,1\}$, $L = [ - (k - 1),k - 1]$, Theorem 1.5 gives $\left | V \right | \leqslant {2^{k - 1}}\left ( {\begin {array}{*{20}{c}} n \\ {k - 1} \\ \end {array} } \right )/k$, where equality holds if and only if $V$ is a "signed" $(n,k,k - 1)$ Steiner-system.References
- Eiichi Bannai, Etsuko Bannai, and Dennis Stanton, An upper bound for the cardinality of an $s$-distance subset in real Euclidean space. II, Combinatorica 3 (1983), no. 2, 147–152. MR 726452, DOI 10.1007/BF02579288
- A. Blokhuis, Few-distance sets, CWI Tract, vol. 7, Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1984. MR 751955
- P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388. MR 485471, DOI 10.1007/bf03187604
- M. Deza, Une propriété extrémale des plans projectifs finis dans une classe de codes équidistants, Discrete Math. 6 (1973), 343–352 (French). MR 332310, DOI 10.1016/0012-365X(73)90065-4
- M. Deza and P. Frankl, On $t$-distance sets of $(0,\,\pm 1)$-vectors, Geom. Dedicata 14 (1983), no. 3, 293–301. MR 710578, DOI 10.1007/BF00146909
- M. Deza and P. Frankl, Every large set of equidistant $(0,\,+1,\,-1)$-vectors forms a sunflower, Combinatorica 1 (1981), no. 3, 225–231. MR 637827, DOI 10.1007/BF02579328
- P. Frankl, On large vector systems with equal scalar products, European J. Combin. 2 (1981), no. 2, 123–125. MR 622076, DOI 10.1016/S0195-6698(81)80002-9
- P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457
- Z. Füredi, On finite set-systems whose every intersection is a kernel of a star, Discrete Math. 47 (1983), no. 1, 129–132. MR 720617, DOI 10.1016/0012-365X(83)90081-X
- Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1980. MR 591457
- Tom H. Koornwinder, A note on the absolute bound for systems of lines, Nederl. Akad. Wetensch. Proc. Ser. A 79=Indag. Math. 38 (1976), no. 2, 152–153. MR 0404174
- L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977) Academic Press, London, 1977, pp. 45–86. MR 0480111
- Dijen K. Ray-Chaudhuri and Richard M. Wilson, On $t$-designs, Osaka Math. J. 12 (1975), no. 3, 737–744. MR 392624
- Vojtěch Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78. MR 793489, DOI 10.1016/S0195-6698(85)80023-8
Additional Information
- © Copyright 1985 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 95 (1985), 323-329
- MSC: Primary 52A37; Secondary 05C35, 51K99
- DOI: https://doi.org/10.1090/S0002-9939-1985-0801348-0
- MathSciNet review: 801348