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


TitleThe lex game and some applications
Author(s) Bálint Felszeghy, Balázs Ráth, Lajos Rónyai
TypeArticle in Journal
AbstractLet F be a field, V a finite subset of F_n . We introduce the lex game, which yields a combinatorial description of the lexicographic standard monomials of the ideal I(V) of polynomials vanishing on V . As a consequence, we obtain a fast algorithm which computes the lexicographic standard monomials of  I(V). We apply the lex game to calculate explicitly the standard monomials for special types of subsets of 0 , 1^n . For D &#8838; Z let VD denote the vectors y &#8712; 0 ,1 n in which the number of ones (the Hamming weight of y ) is in D . We calculate the lexicographic standard monomials of VD, where D = D(d ,&#8467; ,r) = a &#8712; Z : &#8707; a &#8242; &#8712; Z with d &#8804; a &#8242; &#8804; d + &#8467; &#8722; 1 and a &#8242; &#8801; a ( mod r ) , for d , &#8467; , r &#8712; N fixed with 0 &#8804; d < r and 0 < &#8467; < r. This extends the results of [Anstee, R.P., Rónyai, L., Sali, A., 2002. Shattering news. Graphs and Combinatorics 18, 5973, Friedl, K., Heged&#369;s, G., Rónyai, L., Gröbner bases for complete l -wide families (in press) and Heged&#369;s, G., Rónyai, L., 2003. Gröbner bases for complete uniform families. Journal of Algebraic Combinatorics 17, 171180].
KeywordsStandard monomials, Gröbner basis, Combinatorial algorithm
URL http://www.sciencedirect.com/science/article/pii/S0747717105001689
JournalJournal of Symbolic Computation
Pages663 - 681
Translation No
Refereed No