Some Meeting Points of Gröbner Bases and Combinatorics

Bálint Felszeghy () and Lajos Rónyai ()
Additional contact information
Bálint Felszeghy: Hungarian Academy of Science, Computer and Automation Institute
Lajos Rónyai: Hungarian Academy of Science, Computer and Automation Institute

A chapter in Algorithmic Algebraic Combinatorics and Gröbner Bases, 2009, pp 207-227 from Springer

Abstract: Summary Let $$ \mathbb{F} $$ be a field, $$ V \subseteq {\mathbb{F}^n} $$ be a set of points, and denote by I(V) the vanishing ideal of V in the polynomial ring $$ \mathbb{F}\left[ {{x_1}, \ldots ,{x_n}} \right] $$ . Several interesting algebraic and combinatorial problems can be formulated in terms of some finite V, and then Gröbner bases and standard monomials of I(V) yield a powerful tool for solving them. We present the Lex Game method, which allows one to efficiently compute the lexicographic standard monomials of I(V) for any finite set $$ V \subseteq {\mathbb{F}^n} $$ . We apply this method to determine the Gröbner basis of I(V) for some V of combinatorial and algebraic interest, and present four applications of this type. We give a new easy proof of a theorem of Garsia on a generalization of the fundamental theorem of symmetric polynomials. We also reprove Wilson’s theorem concerning the modulo p rank of some inclusion matrices. By examining the Gröbner basis of the vanishing ideal of characteristic vectors of some specific set systems, we obtain results in extremal combinatorics. Finally, we point out a connection among the standard monomials of I(V) and I(V c ), where V⊆{0,1} n and V c ={0,1} n ∖V. This has immediate consequences in combinatorial complexity theory. The main results have appeared elsewhere in several papers. We collected them into a unified account to demonstrate the usefulness of Gröbner basis methods in combinatorial settings.

Keywords: Gröbner basis; Standard monomial; Lexicographic order; Vanishing ideal; Hilbert function; Inclusion matrix; Rank formula (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-01960-9_6

Ordering information: This item can be ordered from
http://www.springer.com/9783642019609

DOI: 10.1007/978-3-642-01960-9_6

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().