Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903790 | Journal of Combinatorial Theory, Series A | 2018 | 23 Pages |
Abstract
The main object of this paper is to determine the maximum number of {0,±1}-vectors subject to the following condition. All vectors have length n, exactly k of the coordinates are +1 and one is â1, nâ¥2k. Moreover, there are no two vectors whose scalar product equals the possible minimum, â2. Thus, this problem may be seen as an extension of the classical ErdÅs-Ko-Rado theorem. Rather surprisingly there is a phase transition in the behaviour of the maximum at n=k2. Nevertheless, our solution is complete. The main tools are from extremal set theory and some of them might be of independent interest.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Peter Frankl, Andrey Kupavskii,