Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleBalancing sets of vectors.
Author(s) Gleb Gusev
TypeArticle in Journal
AbstractLet n be an arbitrary integer, let p be a prime factor of n . Denote by ω 1 the p th primitive unity root,

.Define ω i ≔ ω 1 i for 0 ≦ i ≦ p − 1 and B ≔ {1, ω 1 , , ω p −1 } n ⊆ ℂ n .Denote by K ( n; p ) the minimum k for which there exist vectors ν 1 , , ν k ∈ B such that for any vector w ∈ B , there is an i , 1 ≦ i ≦ k , such that ν i · w = 0, where ν · w is the usual scalar product of ν and w .Gröbner basis methods and linear algebra proof gives the lower bound K ( n; p ) ≧ n ( p − 1).Galvin posed the following problem: Let m = m ( n ) denote the minimal integer such that there exists subsets A 1 , , A m of {1, , 4 n } with | A i | = 2 n for each 1 ≦ i ≦ n , such that for any subset B ⊆ [4 n ] with 2 n elements there is at least one i , 1 ≦ i ≦ m , with A i ∩ B having n elements. We obtain here the result m ( p ) ≧ p in the case of p > 3 primes.
KeywordsGröbner bases, polynomial ideals, standard monomials, extremal combinatorics
ISSN0081-6906; 1588-2896/e
URL http://www.akademiai.com/doi/abs/10.1556/SScMath.2009.1134
LanguageEnglish
JournalStud. Sci. Math. Hung.
Volume47
Number3
Pages333--349
PublisherAkad
Year2010
Edition0
Translation No
Refereed No
Webmaster