Abstract
Let \(\mathbb F\) be a field, \(V \subseteq\mathbb F^n\) be a (combinatorially interesting) finite set of points. Several important properties of V are reflected by the polynomial functions on V. To study these, one often considers I(V), the vanishing ideal of V in the polynomial ring \(\mathbb F[x_1... x_n]\). Gröbner bases and standard monomials of I(V) appear to be useful in this context, leading to structural results on V.
Here we survey some work of this type. At the end of the paper a new application of this kind is presented: an algebraic characterization of shattering-extremal families and a fast algorithm to recognize them.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Abbott, J., Bigatti, A., Kreuzer, M., Robbiano, L.: Computing Ideals of Points. J. Symbolic Comput. 30, 341–356 (2000)
Adams, W.W., Loustaunau, P.: An Introduction to Gröbner bases. Graduate Studies in Mathematics, vol. 3. American Mathematical Society, Providence (1994)
Aharoni, R., Holzman, R.: Personal communication, cited in [24]
Alon, N.: Combinatorial Nullstellensatz. Combinatorics, Probability and Computing 8, 7–29 (1999)
Alon, N., Tarsi, M.: Colorings and Orientation of Graphs. Combinatorica 12, 125–134 (1992)
Anstee, R.P., Rónyai, L., Sali, A.: Shattering News. Graphs and Combinatorics 18, 59–73 (2002)
Babai, L., Frankl, P.: Linear Algebra Methods in Combinatorics. Prel. vers (1992)
Bayer, D.: The Division Algorithm and the Hilbert Scheme. PhD. Thesis. Harvard University (1982)
Bernasconi, A., Egidi, L.: Hilbert Function and Complexity Lower Bounds for Symmetric Boolean Functions. Information and Computation 153, 1–25 (1999)
Bollobás, B., Radcliffe, A.J.: Defect Sauer Results. Journal of Combinatorial Theory, Series A 72, 189–208 (1995)
Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Doctoral thesis, University of Innsbruck (1965), English Translation: An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal. Journal of Symbolic Computation, Special Issue on Logic, Mathematics, and Computer Science: Interactions 41, 475–511 (2006)
Buchberger, B.: Ein algorithmisches Kriterium fur die Lösbarkeit eines algebraischen Gleichungssystems. Aequationes Mathematicae 4, 374–383 (1970); English translation: An Algorithmic Criterion for the Solvability of Algebraic Systems of Equations. In: Buchberger, B., Winkler, F. (eds.) Gro ̈bner Bases and Applications. London Mathematical Society Lecture Note Series, vol. 251, pp. 535–545. Cambridge University Press, Cambridge (1998)
Buchberger, B.: Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory. In: Bose, N.K. (ed.) Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems Theory, pp. 184–232. Reidel Publishing Company, Dordrecht (1985)
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms. Springer, Heidelberg (1992)
Farr, J.B., Gao, S.: Computing Gröbner Bases for Vanishing Ideals of Finite Sets of Points. In: Fossorier, P.C.M., Imai, H., Lin, S., Poli, A. (eds.) AAECC 2006. LNCS, vol. 3857, pp. 118–127. Springer, Heidelberg (2006)
Felszeghy, B., Hegedűs, G., Rónyai, L.: Algebraic Properties of Modulo q complete ℓ-wide Families. Combinatorics, Probability and Computing 18, 309–333 (2009)
Felszeghy, B., Ráth, B., Rónyai, L.: The lex game and some applications. J. Symbolic Computation 41, 663–681 (2006)
Felszeghy, B., Rónyai, L.: On the lexicographic standard monomials of zero dimensional ideals. In: Proc. 10th Rhine Workshop on Computer Algebra (RWCA), pp. 95–105 (2006)
Frankl, P.: Intersection Theorems and mod p Rank of Inclusion Matrices. Journal of Combinatorial Theory, Series A 54, 85–94 (1990)
Frankl, P.: Extremal set systems. In: Graham, R.L., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, vol. 2, pp. 1293–1329. MIT Press, Cambridge (1996)
Friedl, K., Hegedűs, G., Rónyai, L.: Gröbner Bases for Complete ℓ-wide Families. Publ. Math. Debrecen. 70, 271–290 (2007)
Friedl, K., Rónyai, L.: Order Shattering and Wilson’s Theorem. Discrete Mathematics 270, 127–136 (2003)
Garsia, A.M., Procesi, C.: On Certain Graded S n -modules and the q-Kostka Polynomials. Advances in Mathematics 94, 82–138 (1992)
Greco, G.: Embeddings and Trace of Finite Sets. Information Processing Letters 67, 199–203 (1998)
Hegedűs, G., Nagy, A., Rónyai, L.: Gröbner Bases for Permutations and Oriented Trees. Annales Univ. Sci. Budapest, Sectio Computatorica 23, 137–148 (2004)
Hegedűs, G., Rónyai, L.: Gröbner Bases for Complete Uniform Families. Journal of Algebraic Combinatorics 17, 171–180 (2003)
Hegedűs, G., Rónyai, L.: Standard Monomials for q-uniform Families and a Conjecture of Babai and Frankl. Central European Journal of Mathematics 1, 198–207 (2003)
Hegedűs, G., Rónyai, L.: Standard Monomials for Partitions. Acta Mathematica Hungarica 111, 193–212 (2006)
Hegedűs, G., Rónyai, L.: Multivalued Generalizations of the Frankl–Pach Theorem. To appear, Journal of Algebra and its Applications, http://arxiv.org/pdf/1008.4660
Herzog, J., Hibi, T.: Monomial Ideals. GTM, vol. 260. Springer, Heidelberg (2010)
Hillar, C.J., Windfeldt, T.: Algebraic Characterization of Uniquely Vertex Colorable Graphs. Journal of Combinatorial Theory, Series B 98, 400–414 (2007)
Kós, G., Rónyai, L.: Alon’s Nullstellensatz for multisets, http://arxiv.org/pdf/1008.2901
Kós, G., Mészáros, T., Rónyai, L.: Some Extensions of Alon’s Nullstellensatz, http://arxiv.org/abs/1103.4768
de Loera, J.A.: Gröbner Bases and Graph Colorings. Beiträge zur Algebra und Geometrie 36, 89–96 (1995)
Lovász, L.: Stable sets and Polynomials. Discrete Mathematics 124, 137–153 (1994)
Marinari, M.G., Möller, H.M., Mora, T.: Gröbner Bases of Ideals Defined by Functionals with an Application to Ideals of Projective Points. Appl. Algebra Engrg. Comm. Comput. 4, 103–145 (1993)
Mészáros, T.: S-extremal Set Systems and Gröbner Bases. MSc Thesis, BME, Budapest (2010), http://www.math.bme.hu/~slovi/thesiswork.pdf
Michałek, M.: A Short Proof of Combinatorial Nullstellensatz. American Mathematical Monthly 117, 821–823 (2010)
Mnuk, M.: On an Algebraic Description of Colorability of Planar Graphs. In: Nakagawa, K. (ed.) Logic, Mathematics and Computer Science: Interactions. Proc. of the Symposium in Honor of Bruno Buchberger’s 60th Birthday, pp. 177–186 (2002)
Möller, H.M., Buchberger, B.: The Construction of Multivariate Polynomials with Preassigned Zeros. In: Calmet, J. (ed.) ISSAC 1982 and EUROCAM 1982. LNCS, vol. 144, pp. 24–31. Springer, Heidelberg (1982)
Pajor, A.: Sous-espaces l 1 n des espaces de Banach, Travaux en Cours. Hermann, Paris (1985)
Pintér, D., Rónyai, L.: Standard Monomials of some Symmetric Sets. Acta Universitatis Apulensis. Math. Inform. (10), 331–344 (2005)
Sauer, N.: On the Density of Families of Sets. Journal of Combinatorial Theory, Series A 13, 145–147 (1972)
Shelah, S.: A Combinatorial Problem: Stability and Order for Models and Theories in Infinitary Language. Pacific Journal of Mathematics 41, 247–261 (1972)
Vapnik, V.N., Chervonenkis, A.Y.: On the Uniform Convergence of Relative Frequencies of Events to their Probabilities. Theory of Probability and its Applications 16, 264–280 (1971)
Wilson, R.M.: A Diagonal Form for the Incidence Matrices of t-subsets vs. k-subsets. European Journal of Combinatorics 11, 609–615 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rónyai, L., Mészáros, T. (2011). Some Combinatorial Applications of Gröbner Bases. In: Winkler, F. (eds) Algebraic Informatics. CAI 2011. Lecture Notes in Computer Science, vol 6742. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21493-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-21493-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21492-9
Online ISBN: 978-3-642-21493-6
eBook Packages: Computer ScienceComputer Science (R0)