The lex game and some applications
Let F be a field, V a finite subset of P. 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 subset of Z let V-D denote the vectors y is an element of {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, l, r) = (a is an element of Z : there exists a' is an element of Z with d <= a' <= d + l - 1 and a' equivalent to a (mod r)), for d, l, r is an element of N fixed with 0 <= d < r and 0 < l < r. This extends the results of [Anstee, R.P., Ronyai, L., Sali, A., 2002. Shattering news. Graphs and Combinatorics 18, 59-73, Friedl, K., Hegedus, G., Ronyai, L., Grobner bases for complete l-wide families (in press) and Hegedus, G., Ronyai, L., 2003. Grobner bases for complete uniform families. Journal of Algebraic Combinatorics 17, 171-1801. (c) 2005 Elsevier Ltd. All rights reserved.
standard monomials grobner basis combinatorial algorithm