Article ID Journal Published Year Pages File Type
8903790 Journal of Combinatorial Theory, Series A 2018 23 Pages PDF
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
, ,